Best-First Minimax Search: OTHELLO Results
Richard E. Korf, David Maxwell Chickering · 1994
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-