Formal analyses of board games
The study of board games in computer science and artiﬁcial intelligence has generated a considerable literature, which can only be brieﬂy 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 speciﬁed depth or by selective search. Since Shannon’s seminal paper, computer scientists have developed many techniques for improving the eﬃciency 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.