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

Re:Slashdot effect. . .

[garcia]

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 little difficult to play when you can't even load the game...

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 [wikipedia.org]
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:can non-intelligence make humans obsolete?

[DavidShor]

The easiest way to keep "dumb" code from killing us is not to program them to do so. They could mutate their code and decide to kill us anyway, but at that point, they become "smart".

Re:numerosity and solutions within bounds

[TaoPhoenix]

This type of proof is not the same as "your checkers set comes with a handheld database reader to show you the solution of the position you are in" - because it's NOT about 'average players making mistakes'.

They went for the proof of the math behind the game. This article will also be a good flash answer against the wailers who say "but there are 500 billion billion *possible* positions in the game..."

The answer: only a small portion of them *matter*.

Here's the basic chain logic.

"All endgames of 8 pieces or less with a 2 checker advantage are wins except the following known cases... (see appendix.)"

Therefore, any time you can reach that conclusive endgame table, *all further deviations fail to matter*. It matters not that you are an 'average player who played something else'. The remainder of your game became theoretically irrelevant.

What Schafer and team banked on (and Drew) was that the quantity of Theoretically Critical Positions is far smaller than the Possible Positions. At the Master level of both checkers and chess, the results of games after mistakes are actually less important. Someone else also mentioned that it is even harder to turn a checkers game around than a chess game.

Re:skynet is coming...

[Anonymous Coward]

Hardly. The checkers program has no degree of intelligence whatsoever, it's just a gigantic brute force "tree" of board positions.

It is no smarter than a choose-your-own-adventure paperback with the "good" endings already mapped out.

Re:Checkers, Not Draughts

[pugugly]

I've never particularly seen that as an indication of 'subtlety' - Great, it's so subtle that you're allowed one mistake, then your done. By that definition, Tic Tac Toe is a deeply subtle game. Golly Gee.

Or to put it differently, it's a game so subtle that one bad move will kill you, and tournament chess requires three moves at the beginning just to randomize it a bit.

I guess I have a Chess bias - [Grin] Pug

Re:Chess?

[ichigo 2.0]

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.

number = 1000^(x+1)

x is the beginning part of the word, e.g. septillion = 1000^(7+1)

Re:Wow.

[PCM2]

Two points:

a) The post you responded to was inquiring about tic-tac-toe, not checkers.

No it wasn't. Every game of tic-tac-toe I've ever played used Xs and Os, not black and white pieces.

b) Checkers is deceivingly complicated...the article mentions somewhere that it is very likely that checkers is likely more complicated than chess.

Uhhhh... no it most certainly doesn't. It states quite plainly that "chess is even harder to solve than checkers, with a state-space complexity of 10^46," and furthermore that "chess and Go cannot be solved with the type of technology that we have today," but that they might be solved "between 2060 and 2070" (A.D., to you).

Damn, man. That's got to be the most pathetic example of not reading TFA, or the post you're responding to, or the post before that ... or anything ... that I've seen on Slashdot so far. You might want to look into vocational school.

Re:CmdrTaco = pwn3d

[Anonymous Coward]

Something tells me that the script they used to give game analysis is flawed, because it will most likely never tell you Chinook is at a disadvantage (because it can't recognize it, it will only think it has winning moves left).

Need a proof? Play 2 boards, use the moves from Chinook Board 1 to play the moves of the other Chinook on Board 2.

If either board says "Chinook has a small advantage." then the other board should obviously state "disadvantage".