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

Wow.

[Anonymous Coward]

Wow. Reminds me of how awesome I thought I was when I was 7 years old and I solved Tic Tac Toe.

Re:Wow.

[Zantetsuken]

Well, since it's already playing a board game, would it perhaps decide to play "global thermonuclear war" when it looses checkers/chess? Talk about a sore looser!

Slashdot effect. . .

[ookabooka]

They've set up a site where you can see the proof, traverse the logic, and play their unbeatable automaton.

Holy crap. . .you have any idea how badly their server is going to be slashdotted now? It's bad enough when its a php driven webpage but now you've just encouraged slashdotters to try a game or two against it. . .if the server crashes in the middle of a game is it considered a win for the human player?

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.

Re:It's a draw

[$RANDOMLUSER]

They claim the best you can do is draw against chinook in deterministic checkers.

Ooooohhhh! Nondeterministic checkers!!

<clack....clack....clack>
"That's a inside giraffe, king me."

Flawed proof

[eln]

Now, far be it from me to criticize the research of a group that can manage to convince someone to give them a grant to play checkers with a computer all day, but their "proof" on that site is a little suspect.

When I click on the proof, all I get is a Java error saying "Unable to connect to server". While the inability to connect to the Checkers server may make it "Unbeatable" in a Wargames-esque "the only way to win is not to play" kind of way, it's kind of a cop-out.

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:We'll always have Go

[Derek Pomery]

'course, Go would be kind of dull too on an 4x8 board (checkers only uses half the squares)
http://www.chessvariants.com/d.betza/chessvar/16x1 6.html

Checkers, Not Draughts

[eldavojohn]

From the Wikipedia entry:

The most popular forms are international draughts, played on a 10×10 board, followed by English draughts, also called American checkers that is played on an 8×8 board, but there are many other variants. Draughts developed from alquerque.[2] Draughts would be a much much larger gamespace than Checkers. I noticed that draughts appeared in the tags of this story but it shouldn't.

Also, I've heard before that "it takes longer to learn to play checkers at the master level than it does chess. What checkers lacks in breadth, it makes up in precision and finality." I realize that puts me at risk of being modded as flamebait but I wonder if any other Slashdot reader can confirm or contest that.

Re:Checkers, Not Draughts

[mebollocks]

I will, therefore, take occasion to assert that the higher powers of the reflective intellect are more decidedly and more usefully tasked by the unostentatious game of draughts than by all the elaborate frivolity of chess. In this latter, where the pieces have different and bizarre motions, with various and variable values, what is only complex is mistaken (a not unusual error) for what is profound. The attention is here called powerfully into play. If it flag for an instant, an oversight is committed, resulting in injury or defeat. The possible moves being not only manifold but involute, the chances of such oversights are multiplied; and in nine cases out of ten it is the more concentrative rather than the more acute player who conquers. In draughts, on the contrary, where the moves are unique and have but little variation, the probabilities of inadvertence are diminished, and the mere attention being left comparatively what advantages are obtained by either party are obtained by superior acumen. To be less abstract --Let us suppose a game of draughts where the pieces are reduced to four kings, and where, of course, no oversight is to be expected. It is obvious that here the victory can be decided (the players being at all equal) only by some recherche movement, the result of some strong exertion of the intellect. Deprived of ordinary resources, the analyst throws himself into the spirit of his opponent, identifies himself therewith, and not unfrequently sees thus, at a glance, the sole methods (sometimes indeed absurdly simple ones) by which he may seduce into error or hurry into miscalculation. Edgar Allan Poe - The murders in the Rue Morgue.
Great Story!

Re:Chess?

[rustalot42684]

RTFA: 10^46.

So, who wins?

[drfuchs]

Right. So, is it a win for the first or the second player? Would be nice to mention somewhere.

Re:So, who wins?

[Anonymous Coward]

According to the site, it's a draw.

Re:If it's unbeatable...

[$RANDOMLUSER]

...what happens if it plays another version of itself?

Don't cross the streams. That would be bad.

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:Chess?

[youthoftoday]

you didn't answer the question. How many gazillion?

Chinook wind

[hey]

For non-Albertans... a Chinook wind is some hot air the blows down the mountains and melts the winter snow for a week or so.
http://en.wikipedia.org/wiki/Chinook_wind
So it an analogy for a bright new idea -- like a lite up light bulb.
Therefore there are a zillion things called "Chinook" in Alberta.

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

[dprovine]

They randomise starting back-rank positions now in some tournaments, to stave off the eventual "book death" that has already conquered checkers.

I made up my own variation with randomness that I call Schrödinger's Chess.

Let me know if you try it out.

Kobayashi Maru

[3vi1]

The day an automaton is "unbeatable" is the day it's 500ft tall and shoots nuclear rockets from its fingertips. I think I know a relatively easy way to beat this checkers program.

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 :)

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:The writing's been on the wall...

[fractoid]

Schrodinger's chess is when you set up a chess board in a box with a cat. You then shake the box, and declare that you beat the cat at chess.

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

[TED Vinson]

Good idea. Perhaps Checkers can be revitalized by randomizing which piece goes on which starting space too...

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....