And Another Book

It’s hard to find books that cover chess AIs. I read ‘The Binary Revolution’ by Neil Barrett. It would have been very useful to read this before I did Computing at AS level, it covers a lot of the content in an easier way. There was a small bit on chess at the end, which I may as well copy here:

“The principle of playing chess was actually found to be reasonably straightforward for a computer. At any stage of the game, each player has only a limited set of available moves, creating a small set of alternative board positions. From each one of these, a further set of moves can be made and board positions created; and from those again, a small set of yet further moves is possible. At each stage, a ‘tree’ of possible board positions is produced. Chess programs work by producing a complete set of ‘If I do this, then you can do this, and then I can do this’ sequences of anticipated moves; the number of future moves calculated is called the ‘depth’. For each of the board positions then produced, the program calculates a score for itself and for its opponent; it chooses the move which minimizes the opponent’s advantage whilst maximizing its own. This is a strategy called ‘minimax’, created by Claude Shannon in 1949 and perfected by Alan Turing the following year. The first computer program written to execute minimax for chess was produced in 1956 at Los Alamos, followed two years later by a more powerful system at IBM.

Using minimax and a depth of only five moves, chess programs can trounce all but the most experienced of club players; given a slightly greater depth, the programs can beat all but the most experienced chess grandmasters. In 1997, when a dedicated computer system developed by IBM (called ‘Deep Blue’ and capable of examining 200 million chess positions per second) was allowed a depth of 14 moves, it beat the then world champion, Gary Kasparov. Although chess is indeed a striking example of human intelligence, and although computers are not programmed to play in anything like the same way as humans apparently do, it seems to be at least one human-like thing that can better performed by computers.”

That “five moves” bit is interesting, I hadn't heard that before.