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

Checkers, Not Draughts

[eldavojohn]

From the Wikipedia [wikipedia.org] 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. [smithsonianmagazine.com]" 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.

So, who wins?

[drfuchs]

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

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 [chessvariants.com]

Re:Checkers, Not Draughts

[tgeller]

Here's a relevant quote from Bob Newell (editor of The Checker Maven [bobnewell.net]) that didn't make it into the story:

"[Checkers is] a very finely balanced game, and a very subtle game. The subtleties of checkers are not very well appreciated by the average player. You play as a kid and someone always wins. In chess, differences are larger: In chess, you can make a mistake and still recover. In checkers, if you make a mistake, even a small one, you probably won't recover. People are fascinated by this game of minutiae, if you will. At a high level, at least two games out of three, no-one can gain that small advantage and so the game ends in a draw."

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 [rowan.edu].

Let me know if you try it out.

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

[SL Baur]

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

Randomize or start with the pieces off the board? When I was still a member of the USCF in the 1970s, someone introduced a chess variant similar to that. Each side starts with 8 pawns on the 2nd on the board and the back rank empty. White still moves first, but the first 8 moves for each side must be to put the major pieces on the 1st rank. This eliminates the memorized opening book openings too and emphasizes chess middle game play which is what the game is about anyway IMO. This adds 16! different starting positions and maybe makes the game complex enough that it can never be solved deterministically in a useful amount of time, I hope so.

I'm not surprised that checkers has been solved. As a programmer and an engineer, I cheer in the fact that a difficult problem has been solved, as a human being, I'm sad in a way. Computers are tools, humans are well, humans. There must remain some ways we can think better.

Shaeffer's book about Chinook

[ferguson731]

Jonathan Schaeffer 's book about the development of Chinook (from 1997):

http://www.amazon.com/One-Jump-Ahead-Challenging-S upremacy/dp/0387949305 [amazon.com]

Includes the details of the Tinsley matches and Tinsley's untimely death. Interesting for people interested in the effects of technology on human societies, as well as some of the technical aspects of the program (as it was in 1997).

Re:We'll always have Go

[Anonymous Coward]

> 'course, Go would be kind of dull too on an 4x8 board (checkers only uses half the squares)

Duh? Go is _designed_ to be played on a 19x19 grid; the sheer size of the board is an important aspect to strategy. Chess on a 4x2 board doesn't sound too exciting, either (but I'd try 3/2x3/4 tic-tac-toe any day). For the record, 9x9 go (as played on a chess board) is still quite interesting. As for full size go, here is a quote from http://senseis.xmp.net/ [xmp.net], the go wiki: "It is commonly said that no game has ever been played twice. This may be true: On a 19×19 board, there are about 3^361×0.012 = 2.1×10^170 possible positions, most of which are the end result of about (120!)^2 = 4.5×10^397 different (no-capture) games, for a total of about 9.3×10^567 games. Allowing captures gives as many as 10^(7.49×10^48) possible games, most of which last for over 1.6×10^49 moves! (By contrast, [...] physicists estimate that there are not more than 10^90 protons in the entire universe.)"

Re:Flawed proof

[The Flying Guy]

Quoting about graph theory (to be exact 4 colour theorem): "a good mathematical proof is like a poem--this is a telephone directory!"

Not sure who wrote it, but the 4 colour theorem was the first computer aided proof.

And I am afraid I have to agree.

Funny Story

[Cola Junkee]

I did my undergraduate at the U of A, and had the pleasure of being a number of Jonathan Schaeffer's classes. The man is a gifted professor, and rather quirky on top of that.

One day, we were learning about the "Dining Philosopher" problem. The problem is about 3 philosophers that have to acquire two (shared) utensils on either side of them before they can eat the food in front of them. Those of you familiar with the problem should understand ..

Anyway, he came in with a pot of spaghetti, forks, and plates. He actually had some students sit down and go through the algorithm. When the first one took a bite off the plate, he asked "Pretty Good, huh?" (of course the student agreed). He also threw some spaghetti against the wall to prove that it was well cooked.

So, after the first student went through the algorithm and used the fork, you can imagine the grimace from the second student that had to use the same shared fork as the first student..

hah! Still makes me laugh.

I won't ever forget about acquiring mutexes in the correct order, however.

Re:Two Words

[Anonymous Coward]

Try Shogi; it's great, but good luck finding someone else who can play....