3.3. THE GAME OF CHECKERS

The game of checkers is played on an 8X8 board such as shown in Figure 3.3.1a. There is a system of numbering the squares (Fig. 3.2.1b) that is used to describe game moves.

(a)	(b)
Figure 3.3.1: (a) Initial position of a checker's game; (b) Numbering system.

Checkers is the earlier game for which a computer program was written. Claude Shannon, the founder of Information Theory, wrote such a program and reported the results in 1950. The modern era of the computer checkers, based on exhaustive search strategies, dates from 1989 when Jonathan Schaeffer (University of Alberta in Canada) started the Chinook project. The result was a computer program that by 1996 could defeat any human player [1]. Once this goal was achieved, the next challenge was to find the perfect strategy for checkers.

There are about 5*10²⁰ possible moves for checkers [1], a huge number but much smaller than that of possible chess moves. The number of moves to be examined can be reduced by eliminating duplicate positions. (For example, the sequence of moves 9-14, 23-19, 11-15, and 22-17 leads to the same board configuration as the moves 11-15, 22-17, 9-14, and 23-19.) If we use a scoring system to estimate how good a position, then need not examine clealry losing positions and that reduces the possibilities even more. (For the mathematically brave: this is called the alpha-beta pruning strategy.) According to [1] the reduced number of positions to be examined is about 10¹⁴.

If a program spends one millisecond (10^-3) per move, examining all possible moves would require 10¹¹ seconds. There are 86,400 seconds in a day and 31,536,000 seconds in a year. We can write the last number as 3*10⁷ so that the time to examine all possible moves would be about 3*10³ or three thousand years. If we spread the work amongst 1000 computers that will take only three years.

This is roughly what happened in the Chinook project. They used up to 200 computers at one time and the project took about 15 years to complete [1]. An initial effort took seven years (1989-1996) and the project was halted. By 2001 computer speed had improved so much that the task that had taken seven years could then by done in a month. The project was resumed and it was completed by 2004. One of the results was that the opening move 9-13 (Figure 3.3.2a) guarantess a draw if subsequent moves are chosen optimally, no matter how well the opponent plays. The worst opening move, one that results in a loss if the opponent plays optimally, is 12-16 (Figure 3.3.2b).

(a)	(b)
Figure 3.3.2: (a) The best opening move; (b) The worst opening move.

Any of the seven possible moves in reply to 9-13 are equally good [1, Table 2]. Figure 3.3.3a shows one of them, 22-17. In this case the ensuing move of the first player must be 13-22 (Figure 3.3.3b) because of the rule that if a piece can be taken it must be taken.

(a)	(b)
Figure 3.3.3: (a) One of the equally good replies, 22-17, to the 9-13 move; (b) The forced second move of Black in response to 22-17.

Endgame ADD

There are several computer checkers programs, some of them are listed in the table below.

Notes

[1] J. Scaeffer et al "Checkers Is Solved" Science, vol. 317, pp. 1518-1522 (Sept. 14, 2007)

Back to Contents --- Previous Section --- Next Section