Name
Abstract | ||
|---|---|---|
This article presents the results of experiments designed to gain insight into the effect of the minimax algorithm on the error of a heuristic evaluation function. Two types of effect of minimax are considered: (a) evaluation accuracy (Are the minimax backed-up values more accurate than the heuristic values themselves?), and (b) decision accuracy (Are moves played by deeper minimax search better than those by shallower search?). The experiments were performed in the King-Rook-King (KRK) chess endgame and in randomly generated game trees. The results show that, counter-intuitively, evaluation accuracy may decline with search depth, whereas at the same time decision accuracy improves with depth. In the article, this is explained by the fact that minimax in combination with a noisy evaluation function introduces a bias into the backed-up evaluations, which masks the evaluation effectiveness of minimax, but this bias still permits decision accuracy to improve with depth. This observed behaviour of minimax in the KRK endgame is discussed in the light of previous studies of pathology in minimax. It is shown that explaining the behaviour of minimax in an actual chess endgame in terms of previously known results requires special care. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.tcs.2005.09.073 | Theor. Comput. Sci. |
Keywords | Field | DocType |
minimax backed-up value,decision accuracy,minimax principle,minimax pathology,evaluation-function quality,time decision accuracy,evaluation accuracy,minimax algorithm,backed-up evaluation,krk chess endgame,noisy evaluation function,heuristic evaluation function,bias,evaluation effectiveness,deeper minimax search,heuristic evaluation,evaluation function,experience design | Minimax,Negamax,Heuristic,Killer heuristic,Computer science,Evaluation function,Algorithm,Chess endgame,Minimax search,Game tree,Pathology | Journal |
Volume | Issue | ISSN |
349 | 2 | Theoretical Computer Science |
Citations | PageRank | References |
8 | 0.65 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksander Sadikov | 1 | 53 | 9.96 |
| Ivan Bratko | 2 | 1526 | 405.03 |
| Igor Kononenko | 3 | 2940 | 384.95 |