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

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.

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?

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.

Re:skynet is coming...

[moderatorrater]

So all we have to do to crash the eventual skynet is move in a direction that isn't diagonal? This is going to be easy.

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

Re:skynet is coming...

[reytron]

no, to crash it, you tell it to play against itself. then it realizes that in the game of thermonuclear warfare, there is no winner.

Re:If it's unbeatable...

[$RANDOMLUSER]

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

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

Strange

[hcdejong]

the only winning move is not to play...

CmdrTaco = pwn3d

[x.Draino.x]

http://games.cs.ualberta.ca/~chinook/cgi-bin/statu s.cgi [ualberta.ca]

GAME 17:
Opponent: Cmdr Taco ([e-mail])
Chinook color: White
Level: Novice
Move number: 3
Game analysis: Chinook has a small advantage.

Re:Chess?

[youthoftoday]

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

Hmmmmm

[TheOldSchooler]

So what happens if one automaton plays another? Does the universe implode in some kind of horrible checkers armageddon?

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.

Re:Not Impressed

[Anonymous Coward]

Screw Go. I'll be impressed when they solve Mario Party....

Re:Chess?

[justfred]

I think it depends; how many Brazilians are in a gazillion?

Re:Chess?

[Ecuador]

42

Re:Wow.

[Golgafrinchan]

WOPR blows up, the world is saved from nuclear disaster, and the system asks if you'd like to play a nice game of chess.

Re:We'll always have Go

[tooler]

Good Lord, the Go nuts have invaded Checkers posts too.

Re:Wow.

[aichpvee]

DOUBLE KO!

Re:We'll always have Go

[Wannabe Code Monkey]

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

I've always wondered what God is... Now I know, God is 'cussions'. Now if only I knew what a 'cussion' is. Is it like a cushion?

Re:Slashdot effect. . .

[kryten_nl]

With checkers, I find that pointing a gun to the person sitting across the table, usually guarantees a win.

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

[db32]

Well...if its any consolation, I am reasonably certain we will have the ability to think with our genitals quite a long time before computers ever master that one, if they even can. Logic be damned!

Re:CmdrTaco = pwn3d

[UbuntuDupe]

LOL look at this:

http://games.cs.ualberta.ca/~chinook/cgi-bin/statu s.cgi?05 [ualberta.ca]

Someone put:

Spectator comments about this game:

Hitler: This kind of reminds me of Poland, in '39.

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

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

[crontabminusell]

You then shake the box, and declare that you beat the cat at chess.

Correction: beat the cat with chess. ;)

Re:It's come a long way

[ajlitt]

Cue the STL police and their iterator nightsticks.

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

[clickety6]

In 1986, I tried a variant by putting all the black pieces on black squares and all the white pieces on white squares.

It's now 2007 and we still haven't completed the first game...

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

[Faylone]

Correction to the correction: MAY have beat the cat with chess.