Note: [1] This article is an improved version of earlier published ideas under the title Beyond Optimal Play in Two-Person Zero-Sum Games, published in the Proceedings of the 12th Annual European Symposium on Algorithms (ESA), 2004, Bergen, Norway, LNCS 3221, pp. 749-759, eds. S. Albers and T. Radzik, Springer-Verlag, Heidelberg, Germany.
Note: [2] Department of Mathematics and Computer Science, Paderborn University, Germany, email: [email protected]
Abstract: Game-tree search is the core element of most attempts to make computers play games. Yet another approach is (1) to store all possible positions in a database, (2) to precompute the true values for all the positions, and (3) to extract a move with the help of a depth-one search. The databases allow computers to play optimally, in the sense that they will win every game once they have reached a winning position. Moreover, they will never lose from a drawn or won position. We find the database approach in games such as Nine-Men’s-Morris and Connect-4, in endgames of chess, and in many other settings. Nevertheless, it has been observed that the database programs do not play strongly when they have to play a tournament with strong, but non-perfect human players attending. In this paper, we will present an algorithm which has the perfect knowledge of a game database as input, and whose task it is to bring an opponent without perfect knowledge into trouble. The proposed method exploits a specialised game-tree search on top of the database. More precisely, we perform an extended local look-ahead, although the true values of all positions are known. The idea is borrowed from a known theoretical error analysis in game trees. It emphasises that the combinatorial structure of the tree underlying a given position determines how difficult it is for a fallible opponent to find a correct answer. Our experiments show encouraging results.
DOI: 10.3233/ICG-2006-29202
Journal: ICGA Journal, vol. 29, no. 2, pp. 55-64, 2006
