Saturday 21 July 2007

Chinook solves Checkers

Looks like Checkers has been "solved", the result being a draw with best play for both sides. For this piece of information we can thank Dr Jonathan Schaeffer (University of Alberta) and his program Chinook.
Chinook has been around since 1989 and first came to prominence in the early 90's when it played Dr Marion Tinsley is a match for the World Championship. Tinsley won that match, but resigned his title to Chinook due to ill health, before a second match could be completed.
The "solving" of games has been going on for quite a while (think tic-tac-toe or nim), although the solving of connect-4 in 1989 was one of the first big computer solutions in this area. However, the method of solving a game can be a little different from the method for playing a game. In the case of checkers or reversi, the problem is tackled from opposite ends. Working backwards a table-base is generated from "final" positions (like stalemates, draws or checkmates in chess). At the same time computing power is utilised to generate a search tree from the starting position. Once these two efforts collide with each other (completely), then an assessment for every legal position can be made.
In the case of reversi (which I thought would have been solved before checkers), a program like Zebra can search 24 moves deep and play the final 26 moves perfectly leaving only a gap of 14 moves in the middle of the game.
Still I wouldn't worry about chess being "solved" just yet. One of the things that checkers, connect-4, tic-tac-toe all have in common is that they are "simple" games, in terms of the movement of pieces and board size. This means the search space is quite small compared to chess or go, although still quite huge compared to what humans can do.

(Many thanks to the readers who tipped me off about this story)

No comments: