To infinity and beyond
Jul. 17th, 2008 05:49 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackI've spent all day thinking about this now, and not got that far, because go is a game of unsurpassed depth and subtlety, and my head hurts :) In any game where each player acts in turn, and it's possible for a sequence of moves to repeat, the rules have to face the question of what to do if the players get stuck in a loop.
In Magic:TG there are complicated but well-defined set of rules which invite you to compare them to either conceptualised rules "what would happen if you could repeat the sequence infinitely many times" or "what happens if it went on and on, but one player had to break out of the loop eventually". (These are often discussed, eg. on toothywiki.)
In magic the situation is complicated by it sometimes mattering how many times you went round the loop (eg. if you can repeatedly put a new creature into play, can you end up with infinite creatures? Or an arbitrarily large amount?) But it occurred to me, the rules are essentially doing the same job as the ko rule in go or the three-repeats-or-fifty-reversible-moves-is-a-draw rules in chess.
In chess or go, going round the loop multiple times is the same as going round it once, so if you ever break out of the loop, it's the same as doing so at once.
How do the actual rules in place compare to what would happen if you could endlessly repeat?
Chess
In an idealised non-timed game of chess, the three-repeats and the fifty-reversible-moves rules are actually equivalent. If you repeat endlessly, you will eventually make fifty reversible moves. If you make make an unlimited number of non-reversible moves, you must eventually (a very, very long time) repeat a board position.
In fact, to prevent a losing or stubborn player dragging a game out, the limits are set at three repeats or fifty moves, which are supposed to be long enough that they should normally only occur if the game has stalled[1]. What would happen in an endlessly repeating cycle of moves if the rules didn't address it?
If one player has an advantage, he ought to be able to force a win by doing something else, so it's in the other player's interest to repeat the loop, and the first player will eventually do something else, unless he has no choice.
If neither player can gain by ending the loop -- eg. if white is a queen down and repeatedly threatened black's king or queen, then white only has a chance by prolonging the loop, and if black cannot move the threatened piece without it being threatened again, (and would be losing without his queen) then black cannot break out either, without losing -- then the loop would go on forever.
In this case, like analysing a chaotic system, we've found a final resting place that isn't static (like a checkmate), but is a repeating sequence. The rules consider starting this sequence to be a draw (since it should only happen if both players are forced to choose it). This is pretty much the only reasonable interpretation in most situations (one exception below).
One exception
What if the two kings are in separate situations on far sides of the board, unable to interfere with each other, and white can repeatedly check black's king, and black can force a checkmate of white's king?
Under the rules, if white moves first, white will force an endless loop, and if black moves first, black will win.
But what would happen if white moved first, but actually considered an infinite number of moves, and then an ω'th move, and an ω+1'th move, etc? One side of the board would end up in a superposition, with the black king and the checking piece in a fuzzy circle.
And whoever moved first afterwards on the other side of the board (if you assume they can't move the fuzzy pieces), black would win, since the white king can't escape.
I think this is equivalent to letting the two independent situations evolve simultaneously.
It doesn't give the same result as in chess, but I think it's equally reasonable -- white has obviously managed to force some equivalence, but black is in a stronger position, so you could justify calling the situation either a draw, or a win for black.
I don't think this sheds any light on chess, but I wonder if it does on go. That had better be a separate post.
[1] They can happen by accident, but the idea is that three repeats normally only occur if a player is committed to repeating forever, and fifty moves should be enough for any sort of checkmate. Apparently some awkward combinations of pieces -- three bishops versus a bishop and the like -- can take more than fifty moves even with perfect play. But the idea is that in any normal situation, more than fifty moves is just taking the piss and not getting anywhere, especially if someone's time is running out.
[2] Ending a game when a king is captured is equivalent to the current rules, if you replace "must move out of check" with "must remind player, when not moving out of check, that he is doing so."
In Magic:TG there are complicated but well-defined set of rules which invite you to compare them to either conceptualised rules "what would happen if you could repeat the sequence infinitely many times" or "what happens if it went on and on, but one player had to break out of the loop eventually". (These are often discussed, eg. on toothywiki.)
In magic the situation is complicated by it sometimes mattering how many times you went round the loop (eg. if you can repeatedly put a new creature into play, can you end up with infinite creatures? Or an arbitrarily large amount?) But it occurred to me, the rules are essentially doing the same job as the ko rule in go or the three-repeats-or-fifty-reversible-moves-is-a-draw rules in chess.
In chess or go, going round the loop multiple times is the same as going round it once, so if you ever break out of the loop, it's the same as doing so at once.
How do the actual rules in place compare to what would happen if you could endlessly repeat?
Chess
In an idealised non-timed game of chess, the three-repeats and the fifty-reversible-moves rules are actually equivalent. If you repeat endlessly, you will eventually make fifty reversible moves. If you make make an unlimited number of non-reversible moves, you must eventually (a very, very long time) repeat a board position.
In fact, to prevent a losing or stubborn player dragging a game out, the limits are set at three repeats or fifty moves, which are supposed to be long enough that they should normally only occur if the game has stalled[1]. What would happen in an endlessly repeating cycle of moves if the rules didn't address it?
If one player has an advantage, he ought to be able to force a win by doing something else, so it's in the other player's interest to repeat the loop, and the first player will eventually do something else, unless he has no choice.
If neither player can gain by ending the loop -- eg. if white is a queen down and repeatedly threatened black's king or queen, then white only has a chance by prolonging the loop, and if black cannot move the threatened piece without it being threatened again, (and would be losing without his queen) then black cannot break out either, without losing -- then the loop would go on forever.
In this case, like analysing a chaotic system, we've found a final resting place that isn't static (like a checkmate), but is a repeating sequence. The rules consider starting this sequence to be a draw (since it should only happen if both players are forced to choose it). This is pretty much the only reasonable interpretation in most situations (one exception below).
One exception
What if the two kings are in separate situations on far sides of the board, unable to interfere with each other, and white can repeatedly check black's king, and black can force a checkmate of white's king?
Under the rules, if white moves first, white will force an endless loop, and if black moves first, black will win.
But what would happen if white moved first, but actually considered an infinite number of moves, and then an ω'th move, and an ω+1'th move, etc? One side of the board would end up in a superposition, with the black king and the checking piece in a fuzzy circle.
And whoever moved first afterwards on the other side of the board (if you assume they can't move the fuzzy pieces), black would win, since the white king can't escape.
I think this is equivalent to letting the two independent situations evolve simultaneously.
It doesn't give the same result as in chess, but I think it's equally reasonable -- white has obviously managed to force some equivalence, but black is in a stronger position, so you could justify calling the situation either a draw, or a win for black.
I don't think this sheds any light on chess, but I wonder if it does on go. That had better be a separate post.
[1] They can happen by accident, but the idea is that three repeats normally only occur if a player is committed to repeating forever, and fifty moves should be enough for any sort of checkmate. Apparently some awkward combinations of pieces -- three bishops versus a bishop and the like -- can take more than fifty moves even with perfect play. But the idea is that in any normal situation, more than fifty moves is just taking the piss and not getting anywhere, especially if someone's time is running out.
[2] Ending a game when a king is captured is equivalent to the current rules, if you replace "must move out of check" with "must remind player, when not moving out of check, that he is doing so."
no subject
Date: 2008-07-17 10:58 pm (UTC)The textbook example of a won game that might take more than 50 moves is mate with bishop, knight and king against king. There are probably some rook and pawn endings that might, too, but there's too much theory for my brain to remember there.
[2] appears to be a floating footnote, but the situation you describe is common in blitz chess, except reminding is not required.
no subject
Date: 2008-07-17 11:22 pm (UTC)