Fri, 20 Jul 2007

Checkers Solved, Unbeatable Database Created

Years ago I monkeyed around with AI and game design, mostly for fun but also looking for faster ways to solve certain switching and prediction problems. Ultimately I concluded that the most efficient way to solve these sorts of problems was a database lookup, because memory was a much more important factor in human intelligence than we generally believe.

At the time, however, silicon memory was quite expensive, and the average hard disk was 20MB, so there was no way for me to really run through a test of any scale, especially considering that it probably would've delved deeper into game theory, and the boss might've looked askance at that.

But this seems to back up my thinking - nice to know I was at least on the right track.

A story on the Nature site announced that a team of computer scientists at the University of Alberta has solved checkers. From the game's 500 billion billion positions (5 * 10^20), 'Chinook' has determined which 100,000 billion (10^14) are needed for their proof, and run through all relevant decision trees. They've set up a site where you can see the proof, traverse the logic, and play their unbeatable automaton. Jonathan Schaeffer notes that his research has implications beyond the checkers board. The same algorithms his team writes to solve games could be helpful in searching other databases, such as vast lists of biological information because, as he says, "At the core, they both reduce to the same fundamental problem: large, compressed data sets that have to be accessed quickly."

(link) [Slashdot]

/Technology | 0 writebacks | permanent link

comment...

 
Notes: If you put a <mailto:> link in the URL field your address will not be mangled: this could be a bad idea as your email address could be easily harvested by bots designed for SPAM. The comments field should now format correctly for line feeds and carriage returns: when you hit the 'Enter' or 'Return' keys in your comment it should break to a new line. The text should wrap cleanly. Please let me know if it doesn't. No HTML tags will pass through - entering links seems to be the main cause of comment SPAM. Also, please be sure that Javascript is enabled in your browser before attempting to post a writeback. Sorry for any inconvenience, but this really helps cut down on the amount of comment SPAM I have to deal with.
 
 Name:
 URL:(optional)
 Title: (optional)
 Comments:  
Save my Name and URL/Email for next time