pageok
pageok
pageok
Checkers Program Proved Invincible,

reports the New York Times; this also shows that checkers is guaranteed to be a draw if both players play optimally. Of course, it must also be the case that chess played optimally is a draw, that chess played optimally is a win for white, or that chess played optimally is a win for black (though the smart money isn't betting on that last one). It's just that we don't know the answer to that yet, or have a program that is guaranteed to win (or not to lose, if the optimal play yields a draw).

Note that, to be precise,

The new research proves that Chinook is invincible in the traditional game of checkers. But in most tournament play, a match starts with three moves chosen at random. In solving the traditional game, the researchers have also solved 21 of the 156 three-move openings, leaving a crack of hope for humans, at least for now.

Though of course that's not much of a crack, given that it seems likely that a computer program will very soon be able to optimally play all the games yielded by those openings, and lose only if the opening is inherently unwinnable and undrawable for it.

Thanks to my friend and computer science professor Haym Hirsh for the pointer.

anonVCfan:
I knew that computers hadn't solved chess yet, but I didn't realize that checkers was still a work in progress.
7.20.2007 1:53pm
rbj:
Then they can get cracking at Go
7.20.2007 2:06pm
Salixquercus (mail):
"After much wrangling in the checkers world, Dr. Tinsley and Chinook battled for the Man-Machine checkers title in 1992."

I'm still scarred by the ferocity of those debates. Dr. Tinsley is the true king.
7.20.2007 2:20pm
Ejote (mail):
A strange game. The only winning move is not to play. How about a nice game of chess?
7.20.2007 2:35pm
SP:
I still like my chances at Yahtzee.
7.20.2007 2:38pm
Duffy Pratt (mail):
First off, if you don't believe in the law of the excluded middle (and many mathematicians don't), then the outcome of chess would not have to be determinative (win, lose, or draw).

Even if you do believe in the law of the excluded middle, a chess game played optimally could at least theoretically go on forever -- no win, no loss, and no draw. Unless you can prove that a draw scenario was somehow inevitable by the number of possible board combinations. I don't know if that's been done or not.
7.20.2007 3:09pm
Arvin (mail) (www):
Even if you do believe in the law of the excluded middle, a chess game played optimally could at least theoretically go on forever -- no win, no loss, and no draw. Unless you can prove that a draw scenario was somehow inevitable by the number of possible board combinations. I don't know if that's been done or not.

Chess has a rule that if the board has been in the same position for three turns, the game is a draw. Well, actually, I think the rule is that one player can now CLAIM a draw, so I guess technically the game could still go on forever if neither player wanted to draw.
7.20.2007 3:14pm
Sasha Volokh (mail) (www):
Duffy Pratt: I think the proof of chess is from (I think it's called) Zorn's Lemma, which says that a finite game of perfect information is solvable by backward induction. This applies directly to chess as long as it's finite. So by "chess" we have to mean the variant of chess where (I've read this in some rule books) it's deemed to be a draw if you have something like 50 moves without any pieces being taken or pawns advancing.
7.20.2007 3:18pm
Henry T:
I never actually expected this blog to end up discussing my field of study (constructive mathematics), but it's actually happened.

So:
1) Very few mathematicians, even those who study the implications of avoiding the law of excluded middle, actually reject it philosophically (actually, the few who still do are mostly in computer science departments)
2) Whether chess is guaranteed to end in a draw or not depends on exactly what rules you have to handle situations where the players go forever. But if you have a rule ensuring that there's a finite limit on how long the game can go (like the one Sasha mentions) then the law of excluded middle isn't needed. (More precisely, it's only needed for computable statements, and that weakened form can be derived, even in constructive mathematics.)
3) Zorn's Lemma isn't needed for backwards induction, since there are only finitely many moves available at each step, and doesn't address Duffy Pratt's concern, since just about anyone who rejects the law of excluded middle also rejects Zorn's Lemma.
7.20.2007 3:55pm
steve (mail):
There used to be a chicken in Chinatown in New York City that played tic-tac-toe. Calvin Trillin used to take his friends to see it and to see if they could beat it. They always lost, and Trillin said their response was always the same: But he got to move first.
7.20.2007 4:01pm
Tagore Smith:
Yes, the 50 move rule is enough to make Chess finite, and I think it, by itself, leads to a much smaller game tree than draw by three-fold repetition (assuming the draw is always claimed).

There's an easy to understand proof, related to the minimax algorithm, that Chess must then result either in either a forced win for one of the colors, or a forced draw.

We already know that the game tree is finite, so each node must either be a leaf node, or have a leaf node as a descendant. Each leaf node can be unambiguously be determined to be a win for white, a win for black or a draw (if a leaf node is not a win for either player, it must be a draw to be a leaf node).

So let's assign each leaf node a value: 1 for a win or white, -1 for a win for black, or 0 for a draw- call this "marking" the node, and let any node that has been assigned a value be called a "marked" node. Now we find all nodes that have only marked nodes as children and mark them, noting that in each case the player to play will choose a child node with the best available value for that player (white will seek to maximize the value, while black will seek to minimize it). It should be easy to see that doing this repeatedly will eventually lead all nodes in the tree to be marked, including the root node (the starting position). At that point it is a simple matter to read off the value- a 1 means a forced win for white, etc.

This is actually not that different from hoiw computers play chess, though of course they are not evaluating all the way to the leaves of the game tree at most points, and so must rely on estimated values for the leaf nodes.
7.20.2007 4:07pm
Dan Weber:

Of course, it must also be the case that chess played optimally is a draw, that chess played optimally is a win for white, or that chess played optimally is a win for black (though the smart money isn't betting on that last one)


That is true only if chess is well-ordered. AFAIK this hasn't been proven, although most computer scientists have faith that it is such (like P != NP).

An example of a non-well-ordered game is rock-paper-scissors. There is no optimal strategy in that, since any play is beat by one other play.
7.20.2007 4:33pm
Henry T:
Dan: Chess is a finite game with no secret information or simultaneous plays, so EV's statement was correct (modulo the concerns about termination of the game which have been mentioned).
7.20.2007 5:46pm
Tagore Smith:
Dan Weber writes:
That is true only if chess is well-ordered. AFAIK this hasn't been proven, although most computer scientists have faith that it is such (like P != NP).

An example of a non-well-ordered game is rock-paper-scissors. There is no optimal strategy in that, since any play is beat by one other play.


My post directly above yours provides a(n admittedly somewhat informal) proof. It should be good enough for you to convince yourself though (hint: other than some awkwardness caused by the fact that I wanted it to be more iterative than recursive in form, the only dicey bit is showing that there will always be an unmarked node all of whose children are marked in any finite game tree in which all of the leaf nodes have been marked, if there is an unmarked node at all).

The important difference between Chess and Rock-Paper-Scissors in this case is that moves in Chess are not simultaneous. At any given (non-leaf) node in the game tree one player has absolute control over which child node will be the successor. 2 player R-P-S is a forced win for the second player if plays are made sequentially. In fact, at least one grandmaster (I think British, and I'm guessing Tony Miles because of the perverseness factor) claimed to believe Chess was a forced win for Black, on similar grounds. My money is definitely on forced draw.

Actually it's pretty simple to write a program that plays Chess perfectly (orders of magnitude easier than writing a _practical_ program that plays well). It is hard to run such a program, but that is simply because of time and space constraints ;).

Go is interesting for a couple of reasons beyond the fact that it is hard to write practical programs that play even decently (so hard that it has yet to be done).

To make Go finite you need to adopt what is called the "super ko" rule- basically it is against the rules for a player to play such that a position that has previously occurred in the same game appears on the board. It's actually more complicated than that, but...

The really interesting thing is komi- in Go the player of white (who plays second) is given a number of points at the outset to compensate for playing second. This has varied over time, and varies from country to country. In Japan it has just been changed from 5.5 to 6.5 in professional play, I think. One consequence of using a fractional komi is that no game can have a tied score as a result, and this makes draws very rare. They can occur, in some rulesets, when a situation arises in which it would be disadvantageous (to a game losing degree) for either player to make a play, and the game cannot yet be scored. This can't occur in more sensible rulesets though.

The mention of rulesets though- well, Go is a simple game, but it is prone to some pathological conditions and it is hard to rigorously define certain important concepts... also, there are a number of radically different rulesets in use (though they tend to lead to the same outcome in almost all cases). So it's actually a bit hard to discuss without agreeing on a ruleset in which context to discuss it, and it is important to choose this ruleset well ;).

I don't think Chess will be solved anytime soon, but I do think that the game can be made pointless at high levels without having been solved, and I think we are not far from the point where it will die the "death of the draw". Go looks to me as if it will have a lot more longevity.
7.20.2007 5:58pm
David Schwartz (mail):
For the purposes of evaluating Go, it is common to make the following assumptions:

1) To prevent things like triple ko, a move that repeats a previous total board position is prohibited.

2) There is no Komi. The question is not whether white can force a win but what the resulting score will be if both players play optimally.

These are the most neutral possible rules that preserve the theoretical purity of the question.
7.20.2007 7:26pm
Tagore Smith:

1) To prevent things like triple ko, a move that repeats a previous total board position is prohibited.

2) There is no Komi. The question is not whether white can force a win but what the resulting score will be if both players play optimally.


Hmm, that's interesting. To explore the game at all in this way you definitely do need more than basic ko. Is there a reason that this form of superko was chosen over others? Just convention? Superko does change a few things, compared to basic ko+additional ko rules- I wonder if it might be enough of a change to change the outcome?

I'm actually inclined to think (based on a very quick gut-check) that with only basic ko, for instance, it might be possible to force a draw even with no komi- the burden of avoiding degenerate situations might be too great, against perfect play, for Black to force a win. Haven't given it a great deal of thought though- not that I would likely have a good basis for thinking that, or otherwise, even after a great deal of thought.

About not using komi- I see the point of course, but I do think questions about what komi is "fairest" are interesting. Excuse me for being thick, but is it necessarily the case that if, say, Black forces a win by 7 points with best play in an even game, best play with a komi of 7 will lead to jigo? Or jigo or a score of 1`for the winner?

Anyway, there are some other rules questions that must also be agreed on, I think- things like area vs territory scoring (this should make a difference in at least a few cases, I'd think) and whether or not suicide is allowed (again, just a few cases, but I'd think they might matter). There are so many variations on the rules... and actually, the most popular rulesets don't seem to me to exhaustively cover all situations.
7.20.2007 9:08pm