Abstract:
Computer game-playing is a challenging topic in artificial intelligence. The recent results by the computer programs Deep Blue (1996, 1997) and Deep Junior (2002) against Kasparov show the power of current game-tree search algorithms in Chess. This success is owed to the fruitful combination of the theoretical development of algorithms and their practical application. As an example of the theoretical development we discuss a game-tree algorithm called Opponent-Model search. In contrast to most current algorithms, this algorithm uses an opponent model to predict the opponent's moves and uses these predictions to lure the opponent into uncomfortable positions. We concentrate on the time complexity of two different implementations of the algorithm and show how these are derived. Moreover, we discuss some possible dangers when applying Opponent-Model search in practice.