Checkers Solved?
July 23rd, 2007 by WaltDoes anyone understand the claim being made here in this New York Times article? There is some sense in which the creators of the Chinook checkers-playing program have shown that Chinook cannot ever lose at checkers, but the article includes the caveat:
Even with the advances in computers over the past two decades, it is still impossible, in practical terms, to compute moves for all 500 billion billion board positions. Instead, the researchers took the usual starting position and then looked only at the positions that would occur during the normal course of play.
Do they mean that from the normal starting position that Chinook cannot lose? Or does checkers have stylized openings the way chess does, and they mean that Chinook cannot lose from any of those openings?
July 23rd, 2007 at 8:34 pm
First, the standard opening position has been done to death, to the point that most tournament plays would go the exact same way all the time. So in tournaments there is a list of various sequences of the first four moves (two moves for each side). One of these openings is chosen randomly and play goes from there. As I understand it, Chinook has just attacked the standard opening position.
Secondly, Chinook rather aggressvely prunes its tree. That is, if a given move is so clearly bone-headed that no sensible player would make it, Chinook lops off that whole branch and doesn’t investigate it further. So, what if there’s a hidden win in one of those “obviously stupid” moves? Well, Chinook doesn’t know about it.
July 23rd, 2007 at 9:20 pm
I assume that the Chinook engine doesn’t have anything to do with the effort to solve checkers. Assuming they do it the same way as they do in chess, they just look at every possible position and see if it reduces to any positions that win. If not, they see if it reduces to any position that draws. The process doesn’t involve any sophisticated knowledge of checkers.
July 23rd, 2007 at 11:03 pm
I took it to mean that they only used game trees (thus only obtaining moves that could potentially occur in play), instead of looking at every single physically possible board position and computing the best move from there.
July 23rd, 2007 at 11:55 pm
I read it as Domenic did: they looked only at the positions which may actually happen during a match.
July 24th, 2007 at 2:02 am
It’s clear that Chinook isn’t playing checkers but a completely different game that happens to have identical rules - which is exactly the state of affairs with “chess”-playing programs.
Is there any commonly played game for which brute force enumeration is inadequate and reasoning is necessary?
July 24th, 2007 at 6:56 am
I think go has proven rather resistant to AI players (given that computers can’t yet beat masters, to my knowledge)
July 24th, 2007 at 7:45 am
The impression I got was that they only consider positions that actually occur in games. It doesn’t seem immediately obvious to me that that cuts down on the number of possible positions by a lot, but I guess it does.
As for whether go can be done by brute force: I don’t see why not, given enough computing power. But I have no idea whether enough computing power exists. And there are clearly games which are complicated enough that the number of possible game positions is greater than the number of particles in the universe (just take go on a large enough board).
July 24th, 2007 at 7:47 am
Actually, looking at the applet at , which displays the game tree, certain positions are called “unresolved”. These appear to be only positions in which white has the move, though. So my guess is that this program can play perfectly if playing black, but not if playing white.
July 24th, 2007 at 7:48 am
(My previous comment is broken — I didn’t close my “a” tag — but just click on the now-too-long link to see what I’m talking about.
July 25th, 2007 at 3:24 am
“…have shown that Chinook cannot ever lose at checkers …”
So if Chinook plays against Chinook both can’t loose ?
July 25th, 2007 at 3:25 am
BTW your reCAPTCHA doesn’t work either
July 25th, 2007 at 12:35 pm
“So if Chinook plays against Chinook both can’t loose?”
Yes, they said a perfect game by both sides would lead to a draw. The claim’s an overreach though as the article shows.
July 26th, 2007 at 12:01 pm
What do you mean, Johan? Is there a problem with it that we need to fix?
July 26th, 2007 at 1:10 pm
It’s explained properly in the actual paper. They (claim to) have ‘weakly solved’ checkers, meaning that from the starting position, their program can never lose. They have not ’strongly solved’ checkers, meaning that they can’t guarantee that their program will play optimally if you give it a position to start from. In other words, if you play for a bit before letting Chinook take over, and make some moves that Chinook never would, you can get to a state they have not analysed. But as long as Chinook plays from the start, it doesn’t matter what moves the opponent makes - Chinook will obtain the optimal outcome (that, at least, is what is claimed when they say they’ve weakly solved checkers).
July 27th, 2007 at 12:33 am
Walt said:
“What do you mean, Johan? Is there a problem with it that we need to fix?”
well, I did (unvoluntarily) manage to submit a post without typing the two words required. Frankly, I hadn’t even noticed that reCAPTCHA gizmo. Not able to replicate this particular feat, so possibly some kind of fluke.