Game tree search is the core of most attempts to make computers play games. Yet another approach is to store all possible positions in a database and to precompute the true values for all the positions. The databases allow computers to play optimally, in the sense that they will win every game once they reach a winning position. Moreover, they will never lose from a draw or win position. This is the situation that we find in games like Connect-4, in endgames of chess and in many other settings. Nevertheless, it has been observed that the programs do not play strongly when they have to play a tournament with strong, but non-perfect human players attending. In this paper we propose a mixture of game tree search and the database approach which attacks this problem on the basis of a known theoretical error analysis in game trees. Experiments show encouraging results.
展开▼
