How Chess Computers Work

Three-Level Tree Diagram

Prev NEXT

The following diagram shows a three-level tree that looks three moves ahead and has evaluated the value of the final board positions:

The computer is playing as the white player. The black player has moved and left the board position at the top of the tree. In this tree, white can make three possible moves. From each of those three possible moves, black can make three possible moves. From each of those nine board positions, white can make two possible moves. (In real life, the total number of moves from any position is 20 or so, but that would be hard to draw.)

To decide what to do, the computer looks at this tree and works upward from the bottom. Its calculations are set up so that it finds the best board positions from each of the possible positions black will take (it takes the maximum):

One level up, it assumes that black will choose the worst possible position for white (it takes the minimum):

Finally, it takes the maximum of the top three numbers: 7. That is the move the computer will make. Once black makes its move, the computer goes through this whole process again, generating a new tree and evaluating all of the board positions to figure out its next move.

This approach is called the minimax algorithm because it alternates between the maximums and minimums as it moves up the tree. By applying a technique called alpha beta pruning, the algorithm can run about twice as fast and requires a lot less memory. As you can see, this process is completely mechanical and involves no thought. It is simply a brute force calculation that applies an evaluation function to all possible board positions in a tree of a certain depth.

What is interesting is that this sort of technique works pretty well. On a fast-enough computer, the algorithm can look far enough ahead to play a very good game. If you add in learning techniques that modify the evaluation function based on past games, the machine can even improve over time.

The key thing to keep in mind, however, is that this is nothing like human thought. When we learn how human thinking works and create a computer that uses those techniques to play chess, we will really be onto something...

For more information on chess computers and related topics, check out the links below.