ML Anthology

Best-First Minimax Search: Othello Results

Richard E. Korf, David Maxwell Chickering
AAAI 1994 pp. 1365-1370
/aaai/1994/korf1994aaai-best/

Abstract

We present a very simple selective search algorithm for two-player games. It always expands next the frontier node that determines the minimax value of the root. The algorithm requires no information other than a static evaluation function, and its time overhead per node is similar to that of alpha-beta minimax. We also present an implementation of the algorithm that reduces its space complexity from exponential to lin-ear in the search depth, at the cost of increased time complexity. In the game of Othello, using the evalu-ation function from BiIl (Lee & Mahajan 1990), best-first minimax outplays alpha-beta at moderate depths. A hybrid best-first extension algorithm, which com-bines alpha-beta and best-first minimax, performs sig-

PDF AAAI Semantic Scholar

Cite

Text

Korf and Chickering. "Best-First Minimax Search: Othello Results." AAAI Conference on Artificial Intelligence, 1994.

Markdown

[Korf and Chickering. "Best-First Minimax Search: Othello Results." AAAI Conference on Artificial Intelligence, 1994.](https://mlanthology.org/aaai/1994/korf1994aaai-best/)

BibTeX

@inproceedings{korf1994aaai-best,
  title     = {{Best-First Minimax Search: Othello Results}},
  author    = {Korf, Richard E. and Chickering, David Maxwell},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {1994},
  pages     = {1365-1370},
  url       = {https://mlanthology.org/aaai/1994/korf1994aaai-best/}
}