chapter  2
20 Pages

Formal analyses of board games

The study of board games in computer science and artificial intelligence has generated a considerable literature, which can only be briefly surveyed here. Ignoring chess automata-most of them have turned out to be fraudulentcomputer game playing started at the beginning of the twentieth century with Torres y Quevedo’s chess machine, which was able to play the endgame King and Rook against King. In his classic 1913 paper, Zermelo formalized the concept of game tree. Just after World War II, Shannon (1950) augmented ideas proposed by Turing in the forties (Turing, 1953), and described a computer program able to play an entire game of chess, either by full search to a specified depth or by selective search. Since Shannon’s seminal paper, computer scientists have developed many techniques for improving the efficiency and selectivity of search algorithms. Combined with powerful hardware, this ‘brute-force’ approach, as it is often called, has enabled computers to play a number of board games at world-class level.