The game of checkers seems to have been solved.
Its a draw.
See
here or
here if you don't mind seeing an ad for low cholestrol cooking before
getting to the article or
here if
you subscribe to the nytimes or
here if you trust
wikepedia.
The checkers program CHINOOK cannot lose (it can draw).
The program has been around for quite some time, being
improved over time. The researchers are Jon Schaeffer (the originator),
Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar.
They say they have a `computational proof not a math proof'.
Not sure what that means, but I do believe that Checkers is now done.
There is a very good book called One Jump Ahead
that is about the program Chinook that plays Checkers very
well (now perfectly apparently) but it was written a long
time ago, before the recent news.
My impression of Chess and Checkers playing programs is
that they are very clever engineering but not really
much for a theorist to get excited about.
However, very clever engineering should not be underrated.
I also think that these programs have taught us
that (some) humans are very good at these games in a way
that is different than machines. When Deep Blue beat
Kasporov, rather than thinking (as the popular press did)
Oh no, computers are smarter than humans!! I thought
Wow, it took that much computing power and that much
look-ahead to beat Kasporov. Kasporov must be very good
(duh) and the way he plays is different than what
a computer would do.
Similarly, the Chinook researchers ended up being
very impressed with Marion Tinsley (the best checkers
player of all time, since deceased). Analysing his games it
seems as though he almost never made a mistake.
Chinook and Tinsley had two matches- Tinsley won the first one with
4 wins to Chinook's 2. During the second one Tinsley took ill
and had to forfeit- he died a few months later.
Will checkers decline in popularity?
I don't think so--- its already so unpopular that
it can't decline much. This story may give it
a temporary revival.
Just as a point of clarification, is it possible with this solution that the computer would draw in a situation where a win is possible?
ReplyDeleteAs I understand it, against an optimal opponent the computer would always draw. But Checkers has not yet been "strongly solved" (i.e., optimal play from all positions has not yet been computed) and so, somewhat paradoxically, it is possible that against a player who makes mistakes the computer might sometimes lose.
ReplyDeleteAs a side note, I read the ScienceDirect article describing the result, and wasn't convinced. It wasn't so much the issue of a "math" proof vs. a "computer" proof, more the sense I got that the authors had not been completely rigorous. (The article seems to suggest that, for efficiency reasons, certain moves from certain positions were not checked because they were "obviously" inferior.)
so, somewhat paradoxically, it is possible that against a player who makes mistakes the computer might sometimes lose.
ReplyDeleteYou mean, if the computer has to continue to play after two imperfect players played half a match, it might lose. But if the computer starts the match against any player, it won't lose.
You mean, if the computer has to continue to play after two imperfect players played half a match, it might lose.
ReplyDeleteNo, I meant what I wrote. (At least this is my understanding of what is being claimed.) The optimal sequence of moves, from each initial state (in Checkers tournament play, the first 3 moves are randomized), has been computed. If, however, the opponent deviates from the optimal strategy, the computer may not know the optimal response.
Anon4, that doesn't make any sense. In particular, how are you thinking that an "optimal player" is defined? If it is possible to win against the computer, as you are claiming it is (by playing 'suboptimally'), surely the "optimal" strategy would be one that leads to a win.
ReplyDeleteSo if it always draws against an optimal player, it certainly cannot lose to a 'suboptimal player'.
From what I understand, there are board positions from which it might be possible to win, but which this program cannot. However, if it plays from the start, it can ensure that these board positions are not reached.
I'm not sure why it's so hard to understand. Say the computer opens. The optimal opening move A is known, as is the optimal response B. If B is played, the computer knows the optimal response C, etc. However, if move B' \neq B is played, it is known that B' is not better than B, but it may NOT be known what is the best response to B'. So the computer may in this case make a suboptimal move C' (and lose).
ReplyDeleteI am going to stop posting about this, because the above is my interpretation of the article, but may not be actually correct. (All I claim is that it is logically consistent with what the article says.) (In general, I advise people to read the actual scientific article -- it is only 5 pages long! -- before commenting further.)
It's unfair to say Kasparov lost: (1) all in all he won the game in two matches (2) he underperformed in the last match and (3) Deep Blue refused to give its analysis lines... But no doubt computers will win sooner or later. The engine Rybka seems unbeatable at the moment...
ReplyDeleteIs othello next? Are both (generalised) othello and checkers PSPACE-complete?
Don't know about Othello, but here's a paper that claims generalized checkers is *EXPTIME* complete. At stake is whether the game is such that possible legal moves can generate a game tree that is exponential in the size of the board (which is the "input length").
ReplyDeleteJ. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing, 13 (2): 252–267.
Othello is also PSPACE complete.
ReplyDeleteS. Iwata and T. Kasai (1994). "The Othello game on an n*n board is PSPACE-complete". Theor. Comp. Sci. (123): 329–340.
Breaking news!
ReplyDeleteThe first Man-Machine Poker Championship ended minutes ago. The event had a $50,000 purse and was held as part of an artificial intelligence conference. It pitted the world's best poker program, Polaris, against two top human pros.
For the record, the humans won... this time!
The Polaris project is led by the same Jon Schaefer of Chinook. He does get around. :-)
From the tournament blog entries it seems as though Polaris is more or less where computer chess was in 1990, when the famous Karpov-Deep Thought game was played. Karpov outplayed Deep Thought in a drawn rook ending. Deep Thought's team was later quoted in Chess Life as saying they would make sure the computer never lost such an endgame again.
In this poker tournament, the human players were much better at riding out their opponent's rushes -- maximizing the size of the pots when they were favored, and getting the hell out of the way when they were not.
Jump from 1990 to 1997, and Deep Blue famously beat Kasparov. Interestingly, this game involved an early piece sacrifice that Deep Blue assessed as an error, but even so was directed to play the move by its opening book programmers. (For those who care, Kasparov was black and played a ...Nd7 Caro-Kan. The move in question was Nxe6 followed by Bg6+, depriving black's king of the right to castle and establishing a bind on the white squares.)
These kind of sacrifices are called "positional sacrifices." There is no tactical trick, no forced mate, just an intuitive sense that "my game will be better than my opponent's." This is an area where humans still outperform computers.
In 2007, computers are far better than humans at exact calculation, but still nowhere near independent reproduction of human understanding of opening analysis. Rybka, mentioned above, just won the computer world championship, and its victory against the program Shredder was due in large part to the home analysis of its opening programmer. The game followed the preprogrammed opening analysis until move 40(!!!).
http://www.cs.ualberta.ca/~games/poker/man-machine/Live/
Greetings from the NJ Shore, where I have sometime-access from a nearby tavern with Wi-Fi.
ReplyDeleteCommenter #2 is correct, as I recall they preserved only enough of the game tree to prove evaluations of win or draw. However, Chinook long-ago had perfect "tablebases" for all positions with 10 or fewer checkers (kings too), and coupled with a typical 19-ply search depth, was often able to declare the final result in over-the-board-play after only 5 moves! So the chance of fooling Chinook now with an inferior move is nearly nil, I'd say...
Chess has about 10^46 compared with 10^20 positions to go through. Nevertheless, there is greater concern than ever before that some major opening lines will be "played out". Care of Hans Bodlaender's amazing "Chess Variants" website, I recommend a non-random version of "FischerRandom" aka. "Chess 960" described here.
However, this change won't faze computers. IMHO the *only* thing that matters is the "human depth" of a game, defined rigorously as follows: Say Player A is "one class ahead" of Player B if Player A wins 75% of the games between them. This notion is ingrained into the Elo rating system used in chessa dn some other games as a difference of 200 rating points---i.e., a player rated 1800 needs to win 75% against one rated 1600 in order not to lose rating points. Since the lowest regular ratings are about 600, and Kasparov got just above 2800, chess has a human span of about 11 class units. The top rating I've seen for a chess program is 3122 for Rybka. Checkers has a human span of 10. Go does not have a comparable rating system, but I've seen estimates of 25--40 class units for its human span. I believe the lower figure, but that's still exponentially deeper than chess---and IMHO that alone is a determinative statistic on why humans can still beat computers at Go, and how far they have to go...
Whether Go and Chess belong to PSPACE-complete or EXP-complete depends on which rules are adopted governing the possible lengths of games (e.g. the "50-move rule" for 8x8 chess, ko-resolution rules and repetition in Go) as you generalize to nxn boards.
The piece sacrifice played by Deep Blue in Game 6 of the 1997 match with Kasparov is indeed known to opening-book theory, as a strong move. Kasparov had erred on the previous move by playing the second part of an intended sequence first, and then he compounded the error with a weak reply to the sacrifice. By his own admission he was truly psyched out...but what happened to Kramnik last Nov 29 against Deep Fritz 10 when he overlooked mate-in-one was just paranormal!
Against the best 'version' of the late Dr Marion Tinsley, Chinook could still lose an extended 3-move match: fact! Therefore, claims that it has solved the game are incorrect. (Other than in an very specifically defined way.)
ReplyDelete