Solving the Game of Checkers
Jonathan Schaeffer, Robert W. Lake · 1997
In 1962, a checkers-playing program written by Arthur Samuel defeated a self-proclaimed master player, creating a sensation at the time for the fledgling field of computer science called artificial intelligence. The historical record refers to this event as having solved the game of checkers. This paper discusses achieving three different levels of solving the game: publicly (as evidenced by Samuel's results), practically (by the checkers program Chinook, the best player in the world) and provably (by considering the 5 x 10 20 positions in the search space). The latter definition may be attainable in the near future. 1. Introduction Checkers is a popular game around the world, with over 150 documented variations. Only two versions, however, have a large international playing community. What is commonly known as checkers (or draughts) in North America is widely played in the United States and the British Commonwealth. It is played on an 8 x 8 board, with checkers moving one square forward and kings moving one square in any direction. Captures take place by jumping over an opposing piece, and a player is allowed to jump multiple men in one move. Checkers promote to kings when they advance to the last rank of the board. So-called international checkers is popular in the Netherlands and the former Soviet Union. This variant uses a 10 x 10 board, with checkers allowed to capture backwards, and kings allowed to move many squares in one direction, much like bishops in chess. This paper is restricted to the 8 x 8 variant, but many of the ideas presented here also apply to the 10 x 10 game.