[QUOTE=Indistinguishable]
This is already not true.
[/QUOTE]
Well, to be fair, perhaps you meant it differently than I took it. By “outcome of the game”, I interpreted just “who, if anyone, wins if both players engage in ‘perfect play’”, but perhaps you meant “an entire sequence of moves from start to finish of a game where both players engage in ‘perfect play’”, in which case, yeah, your statement is obviously tautologously true.
[QUOTE=Indistinguishable]
Not in this context, no. In the full relevant game-theoretic sense, the only possible “values” positions can have are “The game is a forcible win for white now”, “The game is a forcible win for black now”, and “Both players can force non-loss now, so perfect play will result in a stalemate now”.
[/QUOTE]
Forgive this irrelevant nitpick, but I would say “draw” instead of “stalemate” because there could arise, for example, the 50 move rule. Or even a mutually agreed draw.
[QUOTE=Liberal]
Forgive this irrelevant nitpick, but I would say “draw” instead of “stalemate” because there could arise, for example, the 50 move rule. Or even a mutually agreed draw.
[/QUOTE]
Interestingly enough, I had said “draw” originally, and then edited the post to say “stalemate”, fearful someone would pounce on me for not using proper chess terminology. But it seems I just screwed it up; I had mistakenly thought the 50 move rule, the three repetition rule, and even draws by agreement counted as stalemates, but apparently not. (Hey, at least I know chess has non-wins. :))
(Might as well note that, game theoretically, perfect players never have motivation to abandon the game for a mutually agreed draw. Either one player can force a win, and thus wouldn’t accept, or both players can force a non-loss, in which case all that Player A accepting a draw would do for Player A is shut him out of the possibility that Player B (who he may not know to be perfect) could make a blunder for him to capitalize on. Either way, there’s never any advantage to a perfect player to accept a draw by agreement.)
Just to add some URLs, I attended the University of Alberta, where Jonathan Schaeffer teaches, and once attended a very interesting presentation by him on Chinook and the development thereof.
That last link has some interesting links if you’re interested in playing Chinook, examining the endgame cases, etc.
[QUOTE=Indistinguishable]
Interestingly enough, I had said “draw” originally, and then edited the post to say “stalemate”, fearful someone would pounce on me for not using proper chess terminology. But it seems I just screwed it up; I had mistakenly thought the 50 move rule, the three repetition rule, and even draws by agreement counted as stalemates, but apparently not. (Hey, at least I know chess has non-wins. :))
[/quote]
No problem. A stalemate is a particular type of drawn position in which the player’s king is not in check, but the player has no legal move of any kind.
That’s interesting to know, thanks! I’ve been known to offer/accept draws for things like splitting guaranteed money or just being tired of playing. 
[QUOTE=Indistinguishable]
Interestingly enough, I had said “draw” originally, and then edited the post to say “stalemate”, fearful someone would pounce on me for not using proper chess terminology. But it seems I just screwed it up; I had mistakenly thought the 50 move rule, the three repetition rule, and even draws by agreement counted as stalemates, but apparently not. (Hey, at least I know chess has non-wins. :))
[/quote]
Liberal gave the correct definitions.
[QUOTE=Indistinguishable]
(Might as well note that, game theoretically, perfect players never have motivation to abandon the game for a mutually agreed draw. Either one player can force a win, and thus wouldn’t accept, or both players can force a non-loss, in which case all that Player A accepting a draw would do for Player A is shut him out of the possibility that Player B (who he may not know to be perfect) could make a blunder for him to capitalize on. Either way, there’s never any advantage to a perfect player to accept a draw by agreement.)
[/QUOTE]
When Kramnik played a computer recently, he insisted on an agreement that if a known ‘drawn with perfect play’ position was reached, the game would be stopped and declared drawn.
So you’re right - a computer that can play a position perfectly (and doesn’t get tired and emotional, like us carbon-based lifeforms) has no reason to stop before the end.
(Mind you, us humans can always disconnect its power supply :eek: )
[QUOTE=glee]
Liberal gave the correct definitions.
[/QUOTE]
Yeah; in retrospect, I guess I did know, somewhere in my mind, that draws by agreement, at the least, weren’t really stalemates, and of course I knew that a checkmate-less lack of legal moves was the canonical stalemate, but, for whatever reason, I thought of the 50 move rule and three repetition rule as stalemates as well. I mean, all those moves with no real action? The monotonous drudgery of the same configuration over and over? What’s staler than those? 
Something I completely lacked any knowledge of till motivated to go looking at things today was that the fifty move rule has within recent history had all kinds of exceptions and extensions, though not any more, I gather. And what was really interesting was the discovery that certain endgames are known which could be forced to a win without the fifty move rule, but which would instead get trapped at draws by its intercession. That’s amazing. It makes me wonder anew, as I sometimes have before, about the possibility that perfect chess without the fifty move rule would be a win for one player but with the fifty move rule is a draw. (If I got to refashion the rules of chess to suit my aesthetics, I’d get rid of the fifty move rule and change the threefold repetition rule to a onefold repetition rule. Why not? For perfect players, the only thing a repetition does is induce an infinite loop… of course, what perfect players do is far removed from what real people do)
This is interestingly sort of the opposite of the situation I outlined above; in this case, Kramnik did know his opponent was “perfect” and didn’t know himself to be “perfect”, so he would want to take the draw, so as to prevent the possibility that he himself would blunder and his opponent would capitalize on it.
Given that there are experts in game theory here, I’d like to learn more. 
(Although I have extensive practical experience in chess, I realise its still not conclusive proof of anything.)
Take 3 games (in which each player moves in turn - and must make a move):
If I’ve set the conditions correctly, this is a forced win for the second player to move.
If the first player takes 1, he takes 2. If the first player takes 2, he takes 1.
So each pair of moves removes 3 matches, leaving the first player to take the last one.
We know this is drawn with perfect play.
If two beginners play, the first player has a better chance of winning.
The empirical evidence is that White has a clear advantage (approx 5%), but we only know how to play prefectly when there are 6 or less pieces on the board.
OK, let me try to use correct terminology on the above.
The first two are solved, chess isn’t.
In the first game, the initial position is a forced win for the second player. So the first player is in zugswang.
Since no draws are possible in any case, any position in this game is either a forced win or zugswang.
In any position, changing the player to move automatically alters the result for that player from forced win to zugswang (or vice versa).
In Noughts + Crosses, the initial position is drawn with perfect play.
There are no zugswangs, because any move cannot weaken your position. (If you were lost before, you’re still lost. But your move doesn’t change the result.)
(Assume that even a beginner can spot the threat of completing one line of 3. I suspect that in that case the first player to move can afford one mistake and still draw. I think the second player cannot afford any mistakes. Am I right?)
In chess, the empirical evidence is that White has an advantage because of having the intial move.
In the vast majority of chess positions, having the move will be an advantage. There is a small subset of positions (zugswang) where the player to move is at a disadvantage, and an even smaller set where both players are in zugswang.
Is this analysis correct?
[QUOTE=Indistinguishable]
Yeah; in retrospect, I guess I did know, somewhere in my mind, that draws by agreement, at the least, weren’t really stalemates, and of course I knew that a checkmate-less lack of legal moves was the canonical stalemate, but, for whatever reason, I thought of the 50 move rule and three repetition rule as stalemates as well. I mean, all those moves with no real action? The monotonous drudgery of the same configuration over and over? What’s staler than those?
[/quote]
If you want to see real suffering, watch Grandmasters in an ending of King, Rook + Bishop v King and Rook.
A chap called Philidor (about 200 years ago - well before computers!) gave a couple of positions that were drawn (they are named after him). But the problem is reaching them.
It’s pretty comfortable to play the attacking side. You know you have to force the enemy King to the edge of the board, whilst shielding your King from checks with your bishop. You also know the Philidor positions and try to avoid them.
Meanwhile the defender knows everything you know. But he has the added strain that the best he can hope for is a draw, whilst a mistake will lose him the game.
Add in the fact that **these endings occur after several hours play and that everyone else at the tournament is watching to see how you do ** - that is a real strain!
Thanks to computer analysis, we also know that the ending of King + Queen v King and Rook is a forced win.
However it can be well defended (especially by a perfect computer program!).
Grandmasters can get frustrated trying to win this (you’re a professional player and you can’t win a won position… :rolleyes: )
I tested one of the first programs that knew that the rare ending of King and 2 Bishops v King and Knight was a forced win (unless one of the bishops is immediately captured).
It was scary to have a computer report on how well I was doing after each move.
Intial position: 33 moves to the win of the Knight.
I went 32, 31, 30, 29, 28, 27 (hah! making progress), 31 (blast!), 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15 (smugness), 34 ( :smack: ).
The moved required are often counter-intuitive to a player (the bishops retreat away from the opposing pieces) and there is no overall statement of strategy.
[QUOTE=Indistinguishable]
Something I completely lacked any knowledge of till motivated to go looking at things today was that the fifty move rule has within recent history had all kinds of exceptions and extensions, though not any more, I gather. And what was really interesting was the discovery that certain endgames are known which could be forced to a win without the fifty move rule, but which would instead get trapped at draws by its intercession. That’s amazing.
[/quote]
This is partly due to the actual ending where White has King, Rook and Pawn on a2 v King, Bishop (black squares) and Pawn on a3. (I think it was GM Timman who first played and analysed it).
It is (probably) a win, but it can take 50 moves without a pawn moving or a capture being made (which was the definition of the ‘50 move rule draw’). As a result of this position, the World Chess Federation (FIDE) changed the rules to allow more than 50 moves. They’ve now changed them back, so in theory you can have a forced win, but only be able to draw!
[QUOTE=Indistinguishable]
It makes me wonder anew, as I sometimes have before, about the possibility that perfect chess without the fifty move rule would be a win for one player but with the fifty move rule is a draw. (If I got to refashion the rules of chess to suit my aesthetics, I’d get rid of the fifty move rule and change the threefold repetition rule to a onefold repetition rule. Why not? For perfect players, the only thing a repetition does is induce an infinite loop… of course, what perfect players do is far removed from what real people do)
[/quote]
Only a few positions need more that 50 moves (without pawn moves or captures) to win, and they don’t occur much in practical chess.
Now the threefold repetition rule does have some point.
For example, one side can have a clear advantage in an ending, but not a forced win. The way to proceed is to attack on one side of the board and see if your opponent defends correctly. if he does, you go back to the original position (2nd repetition) and try the other side. If that is defended correctly, you agree the draw (partly because the third repetion will force it anyway).
I don’t know of any positions where there are 3 possible ways into your opponent’s position, so you need a 4 time repetition rule to allow you to test them all…
l also saw a last round British Championship game between GMs Ward and Hodgson where both needed a win to be in the prize money. They reached an exciting position where the only sound play was to repeat, but either could risk playing on by making a technically inferior move. They repeated 6 times :eek: before agreeing the draw.
[QUOTE=Indistinguishable]
This is interestingly sort of the opposite of the situation I outlined above; in this case, Kramnik did know his opponent was “perfect” and didn’t know himself to be “perfect”, so he would want to take the draw, so as to prevent the possibility that he himself would blunder and his opponent would capitalize on it.
[/QUOTE]
Indeed - and there was a lot of money (and prestige) at stake.
[QUOTE=glee]
OK, let me try to use correct terminology on the above.
The first two are solved, chess isn’t.
[/QUOTE]
Correct. The first two are solved in the strongest sense possible (we know everything about their full game trees), chess isn’t even solved in the weakest of senses (we can’t disprove anything about the final winner or lack thereof in perfect play; all the possibilities (first player win, second player win, draw) are still on the table).
Correct; the first player could pass, his position would improve from certain loss to certain win.
Correct in the sense that, in a game of this sort with no draws, any position in the game is either a forced win for the turnholder, or a zugzwang for the turnholder because it’s a forced win for the non-turnholder. In the specific case of Nim, we can say something even stronger: since the board remembers no distinctions between the players (i.e., any configuration that one player could legally move to were it his turn is one that the other player could legally move to as well, were it his turn), zugzwang for any player is “reciprocal zugzwang”, by which I mean zugzwang for both players (in that both would prefer the other to make the next move). So, with Nim, every configuration is either a forced win for whoever moves next or a forced loss for whoever moves next. Which implies…
Right, this is true for Nim because of the statement above. (Remember, that was a consequence of two things: there are no draws in Nim, and the board remembers no distinctions between the players).
Correct, of course.
Correct. This puts it in the same category as a game like Hex. Incidentally, the non-constructive proof that the first player in Hex can force a win really depends only on two things (beyond it being one of these turn-based games of complete information and so on): that it has no zugzwangs and has no draws. Any game of this sort with no zugzwangs and no draws is a first-player win: since it has no draws, it must be either a forced win for the first player or a forced win for the second player. Furthermore, since it has no zugzwangs, the first player cannot want to pass at the beginning of the game, which is to say, the first player cannot want to switch roles at the beginning of the game; thus, the initial configuration must be a first player win. It’s a very neat argument that gives no information at all about what the first-player’s winning strategy is, but ensures that one exists. (Even if there were possible draws, the lack of zugzwangs ensures that the first player has a strategy to avoid loss).
Well, almost. If by “mistake” you mean a move which lowers the game-theoretic value of the board for the player who made it, then neither player can afford any mistakes at all. Since the game is a forcible draw, perfect play keeps it constantly valued at a forcible draw. The first player to make a mistake and lower his value will therefore be moving to a forcible win for his opponent. Basically, on this account, every player is constantly on the tight-rope at forcible draw just above forcible loss, with no inbetween values, and thus there are no non-fatal mistakes: any move you can afford to make doesn’t count as a mistake, because of the very grounds that you can, in fact, afford to make it. Of course, there may be more than one possible non-mistake move, though; there’s nothing saying there can be only one right or acceptable move.
There are some more subtle notions of “mistake” we can think about than just drop in forcible value: if we look at values not just coarsely as “forcible X”, but more finely with notions like “forcible X, with opportunities for improvement if the opponent blunders” then our notion of “mistake” can broaden. But all the new mistakes this subtler notion adds are moves from “forcible X with …” to “forcible X with …”; thus, none of these new “mistakes” are ones you can’t afford, in the sense that they move you for the first time into a forcible loss.
I assume you are correct about all of those; I defer to your expertise.
Almost entirely so, yes, except for that bit about the first player being able to afford one mistake in Tic-Tac-Toe, unless perhaps you have some particularly subtle account of what you mean by this which I failed to take into account. But everything else was all spot-on.
I tried to edit it in and only got some of it down before getting hit by the shutting of the edit window. The full parenthetical I wanted to mention regarding Hex was “(Even if there were possible draws, the lack of zugzwangs ensures that the first player has a strategy to avoid loss, by the essentially same argument. Thus, we see right away that the first player has an unbeatable strategy in Tic-Tac-Toe, simply from the fact that it lacks zugzwangs).”
Also, I should clarify that when I say a position in a game is a forcible draw, I mean that perfect play from the current point onwards will result in a draw, but this takes into account the matter of the current turnholder. I don’t mean the stronger statement that “Perfect play from this position onwards will result in a draw, no matter who makes the next move”; though perfect play in Tic-Tac-Toe stays at positions of the former kind, it obviously doesn’t always stay at positions of the latter kind.
[QUOTE=Indistinguishable]
…
I assume you are correct about all of those; I defer to your expertise.
[/quote]
Most kind!
[QUOTE=Indistinguishable]
Almost entirely so, yes, except for that bit about the first player being able to afford one mistake in Tic-Tac-Toe, unless perhaps you have some particularly subtle account of what you mean by this which I failed to take into account. But everything else was all spot-on.
[/QUOTE]
I should have explained better.
I use the word ‘mistake’ in games to mean three things:
What I meant in Tic-Tac-Toe terms was a move that lessens your possibilities of winning and increases your opponents chances (compared to a better move).
I am also assuming there is not perfect play.
[QUOTE=Indistinguishable]
For any two-player turn-based game of perfect information with win, lose, draw outcomes, such a program exists, though not necessarily efficiently.
[/QUOTE]
Two letters: Go.
[QUOTE=yelimS]
Two letters: Go.
[/QUOTE]
I didn’t quite catch your point.
-FrL-
I think that the nim-like game described above is a good counterexample. If the game starts with 100,000 matches, then there are far more than 2^50,000 ways that the game could be played. So there are at least 10^10,000 possible games, which is a lot greater than 10^123.
Nevertheless, the game is easily solved because of its internal structure.
Of course, the structure of chess is a lot more complex, but the fact that there are some boss number of possible games doesn’t mean it will never be solved.
My guess is that, at a minimum, chess will be solved in the practical sense that the best computer programs will be able to play a million games without losing. In other words, computer programs will play close enough to perfect that they will never lose; and the same computer programs will draw when they play eachother.
[QUOTE=yelimS]
Two letters: Go.
[/QUOTE]
Two letters: So?
One day, a computer might play perfect chess - but it’s hard to imagine.
One day, a computer might play perfect Go - but it’s even harder to imagine.
But a computer will never be able to beat quality human opposition when it comes to Mornington Crescent.
[QUOTE=ianzin]
But a computer will never be able to beat quality human opposition when it comes to Mornington Crescent.
[/QUOTE]
Well, only because of the blasted equilateral transfer rule.
[QUOTE=brazil84]
I think that the nim-like game described above is a good counterexample. If the game starts with 100,000 matches, then there are far more than 2^50,000 ways that the game could be played. So there are at least 10^10,000 possible games, which is a lot greater than 10^123.
Nevertheless, the game is easily solved because of its internal structure.
[/quote]
Well yes, but that’s because I set up the rules that you win if there are 1 + (a power of 3) matches left. Once you have this condition, you can play each individual move perfectly (by taking 1 match if your opponent took 2 and 2 if he took 1).
So you only need to look one move ahead.
[QUOTE=brazil84]
Of course, the structure of chess is a lot more complex, but the fact that there are some boss number of possible games doesn’t mean it will never be solved.
[/quote]
Chess is really complex!
For example:
None of these are easy to program - and most chess positions have some such advantages to one side, plus some disadvantages. The trick is knowing which are more important in that particular position…
The number of possible games is certainly large.
But more importantly, there are typically 30 legal moves in a position. So for a computer using brute force to analyse ahead just one move for each side, you need to look at nearly 1000 positions. But you can only crudely assess these positions (perhaps by counting the pieces).
So you need to look further ahead, but each pair of moves demands 1000 times more analysis, and 1000 times more computer time.
Top players use pattern recognition and judgement (which computers can’t) to eliminate all but say 3 possible moves in a position. This allows them to analyse ahead (though of course they may miss something when ‘pruning’).
[QUOTE=glee]
Well yes, but that’s because I set up the rules that you win if there are 1 + (a power of 3) matches left. Once you have this condition, you can play each individual move perfectly (by taking 1 match if your opponent took 2 and 2 if he took 1).
So you only need to look one move ahead.
[/quote]
Of course. Like I said before, the game has a very simple internal structure. And you’re right that chess is much more complex.
My point is simply that you can’t rule out the possibility that chess will be solved based on the total number of possible games or positions.
It’s not just the number of moves, it’s also the complexity of the game’s structure. To illustrate, I could set up a nim-like game where each person can take between 1 and 50 pieces. Even so, it would be very simple to solve the game.