[Computational Complexity] Checkers Solved- its a draw!
- The game of checkers seems to have been solved. Its a draw. See here or here if you don't mind seeing an ad for low cholestrol cooking before getting to the article or here if you subscribe to the nytimes or here if you trust wikepedia. The checkers program CHINOOK cannot lose (it can draw). The program has been around for quite some time, being improved over time. The researchers are Jon Schaeffer (the originator), Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar. They say they have a `computational proof not a math proof'. Not sure what that means, but I do believe that Checkers is now done.
There is a very good book called One Jump Ahead that is about the program Chinook that plays Checkers very well (now perfectly apparently) but it was written a long time ago, before the recent news.
My impression of Chess and Checkers playing programs is that they are very clever engineering but not really much for a theorist to get excited about. However, very clever engineering should not be underrated. I also think that these programs have taught us that (some) humans are very good at these games in a way that is different than machines. When Deep Blue beat Kasporov, rather than thinking (as the popular press did) Oh no, computers are smarter than humans!! I thought Wow, it took that much computing power and that much look-ahead to beat Kasporov. Kasporov must be very good (duh) and the way he plays is different than what a computer would do.
Similarly, the Chinook researchers ended up being very impressed with Marion Tinsley (the best checkers player of all time, since deceased). Analysing his games it seems as though he almost never made a mistake. Chinook and Tinsley had two matches- Tinsley won the first one with 4 wins to Chinook's 2. During the second one Tinsley took ill and had to forfeit- he died a few months later.
Will checkers decline in popularity? I don't think so--- its already so unpopular that it can't decline much. This story may give it a temporary revival.
Posted By GASARCH to Computational Complexity at 7/23/2007 12:00:00 PM