Checkers Solved, Unbeatable Database Created

tgeller writes "My 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."'"

Comments

The writing's been on the wall...

[Eco-Mono]

...ever since the swelling of Chess's "opening book" began. They randomise starting back-rank positions now in some tournaments, to stave off the eventual "book death" that has already conquered checkers.

Re:The writing's been on the wall...

[eclectro]

For those that are interested, I think the parent is referring to Chess960.

It's a draw

[elwinc]

The New York Times has the story too http://www.nytimes.com/2007/07/19/science/19cnd-ch eckers.html?ref=science:. They claim the best you can do is draw against chinook in deterministic checkers. The Times points out that:

The new research proves that Chinook is invincible in the traditional game of checkers. But in most tournament play, a match starts with three moves chosen at random. In solving the traditional game, the researchers have also solved 21 of the 156 three-move openings, leaving a crack of hope for humans, at least for now.

We'll always have Go

[roscivs]

Since Go always comes up in these discussions, I'll take this opportunity to point those curious about the game to some places to learn more about it:

http://playgo.to/interactive/, learn how to play the game in an interactive fashion.

http://361points.com/atarigo/, play "capture" Go against a simple computer opponent.

http://www.gokgs.com/, after you've learned the rules, play against others online worldwide.

http://www.godiscussions.com/, have more questions about the game? Ask them on this discussion board devoted to the game.

Re:Chess?

[rustalot42684]

RTFA: 10^46.

Re:So, who wins?

[Anonymous Coward]

According to the site, it's a draw.

Re:Theoretical vs. practical

[edremy]

No. Schaeffer has a book out ("One Jump Ahead") about writing Chinook. He thought the same when he started, but the project got rapidly far harder than he thought. It helped that the existing human champion (Marion Tinsley) was literally as close to perfection as any human has ever been at any game- they exhaustively studied every professional game he ever played and found something like a grand total of 10 actual mistakes in a 40 year career.

It's a very sad book in many ways- there was a lot of tension between certain members of the team and you realized that professional checkers was dying rapidly. Tinsley and Schaffer set up a world championship rematch between them (Tinsely won the first one) and Tinsely pulled out after six games saying he felt ill. He checked himself into the hospital, was diagnosed with some aggressive form of cancer and died a few months later. Schaeffer basically retired Chinook from human tournaments since nobody else was even remotely close to Tinsley.

It didn't make many headlines because everyone knows checkers is easy. Except that they are wrong- it's not.

Re:Wow.

[DavidShor]

According to TFA, a draw

Chinook vs Tinsley

[Anonymous Coward]

One can get much of the overall story online here.

For people wondering what is checkers

[marcosdumay]

Ok, for other english impared people wondering what is checkers, it is the US name for game of draughts. If you follow that link, you'll instantly recognize the board :)

Of course, as a brazilian, I had no idea people played that on a 10x10 board around the world. Too bad they can't reuse the chess board :)

Gratuitous nostalga post

[Joe Decker]

HAKMEM item 93 is solved. Back in 1972 when HAKMEM was written, the AI Lab folks estimated a year or so of computer time then, I'm guessing, given how long has passed, that this was a bit optimistic.

Re:It's come a long way

[mikeb]

for(int i=60;i>0;i++) ... that loop is going to run for some time, especially if i is declared unsigned

Re:Chess?

[NewsWatcher]

Oh yeah, not that complicated, until you consider that in the USA a billion is a thousand million, but in most of the world it is a million million. Or that a sextillion is derived from prefix "sex" which means six, (as in a sextet of ale) but is actually a one followed by 21 zeros.

A septillion (from the word for seven) contains 24 zeros.

So what you may ask is a one followed by 22 naughts? 10 sextillion. A one followed by 23 naughts? 100 sextillion. And yet instead of a one followed by 24 naughts being 1000 sextillion, it is all of a sudden a septillion, even though it has nothing whatsoever to do with the number seven.

I don't even know why I care about all of this. I got to this thread late and the chances of anyone reading my post in the developers section of Slashdot are next to zero. Of course next to zero would be one and minus one. Oh gawd, don't get me started on that....