Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one? (This is the way my 8-year-old son likes to play tic-tac-toe against me: he puts down two X's, then I put down two O's, then he puts down two X's and wins. Fair, right?) Note that this form of two-player game can be seen as a four-player game in which players #1 and #2 collaborate and players #3 and #4 collaborate. Jim Propp
studied variants
I play "Basque Chess" with my son, but is this a real "Double-move game"? We set the clock for, say, 10 minutes each (with increment of 10 seconds per move) and play. On two adjacent boards -- one with White for me and Black for him, the other with Black for me and White for him. My full move is completed when I've played on both boards and pressed the clock. The game starts with a single move made by one of the White pieces, and goes on with "double-moves" by the opponent, in turns. This variant is known to "level" the advantage of starting a game (a tournament) with the White pieces. Best, É. -----Message d'origine----- De : math-fun [mailto:math-fun-bounces@mailman.xmission.com] De la part de James Propp Envoyé : mardi 30 décembre 2014 14:02 À : math-fun Objet : [math-fun] Double moves Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one? (This is the way my 8-year-old son likes to play tic-tac-toe against me: he puts down two X's, then I put down two O's, then he puts down two X's and wins. Fair, right?) Note that this form of two-player game can be seen as a four-player game in which players #1 and #2 collaborate and players #3 and #4 collaborate. Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
for those of you who play chess, consider the variant where black gets two moves for every one move for white. black can move into check on his first move as long as he moves out of check on his second move. in case it matters, do away with the stalemate move, so that one player wins by capturing the opponent's king. in particular, consider in which endgames white has enough power to force a mate. KR vs K is now a win for black! i believe KRR vs K is a draw, but KQQ vs K is a win. i wonder about KQR vs K. i also wonder how black played so poorly to get in these situations. :) erich
Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one?
In Go, ko-threats are effectively saying "I dare you to give me two moves in succession here", i.e. with the first of the two specified. On 12/30/2014 08:02 AM, James Propp wrote:
Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one?
I have mused before (I believe in this forum, but it would have been years ago) on the possibility of games where there were two winning conditions, one based on reaching a point target, and one based on board configuration. A player wins upon achieving either of the two conditions. The novel mechanism was inspired by Go ko-fights exactly as John describes them. After making a move on the board, a player is permitted to offer the opposition a deal: skip your move and earn some points instead. "I'll buy your next move for 4 points." Probably such a game would be hard to tune to make it interesting. In response to Jim Propp's original question: Permitting double moves doesn't affect the basic nature of the two classes of combinatorial games with the most complete theories, namely impartial games and partisan games. That is, "doubling" an impartial game gives another impartial game, still amenable to Sprague-Grundy analysis, and "doubling" a partisan game gives another partisan game, amenable to Berlekamp-Conway-Guy analysis. The vast ocean of games between these two extreme islands remains vast and oceanic upon doubling :) On Tue, Dec 30, 2014 at 9:24 AM, John Aspinall <j@jkmfamily.org> wrote:
In Go, ko-threats are effectively saying "I dare you to give me two moves in succession here", i.e. with the first of the two specified.
On 12/30/2014 08:02 AM, James Propp wrote:
Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Allan Wechsler writes: In response to Jim Propp's original question: Permitting double moves
doesn't affect the basic nature of the two classes of combinatorial games with the most complete theories, namely impartial games and partisan games. That is, "doubling" an impartial game gives another impartial game, still amenable to Sprague-Grundy analysis, and "doubling" a partisan game gives another partisan game, amenable to Berlekamp-Conway-Guy analysis.
Yes and no. There are still game trees, P-positions, and N-positions. But the whole apparatus of disjunctive sums and equivalence (sometimes called equality) falls apart when you try to make it work in this context, so nimbers and surreal numbers can't be applied. That's because the induction arguments that make the theory work are sensitively tuned to the fact that when you make a move in a disjunctive sum, you make a move in exactly ONE of the summands --- whereas, when you are faced with the game G+H and you want to make a double-move, you can make a double-move in G, a double-move in H, or a single move in each of the two sub-games. Which is not to say things are hopeless; after all, BC&G do consider (and prove things about) conjunctive sums, in which a player must move in EVERY component. But that's a different theory. If anyone thinks I'm missing something, I hope they'll tell me how to apply Sprague-Grundy theory to Nim when doubled moves are allowed! Jim Propp
The vast ocean of games between these two extreme islands remains vast and oceanic upon doubling :)
On Tue, Dec 30, 2014 at 9:24 AM, John Aspinall <j@jkmfamily.org> wrote:
In Go, ko-threats are effectively saying "I dare you to give me two moves in succession here", i.e. with the first of the two specified.
On 12/30/2014 08:02 AM, James Propp wrote:
Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
So is there an interesting theory of adding games/numbers with double moves? or k moves for general k? On Dec 30, 2014, at 8:44 PM, James Propp <jamespropp@gmail.com> wrote:
That's because the induction arguments that make the theory work are sensitively tuned to the fact that when you make a move in a disjunctive sum, you make a move in exactly ONE of the summands --- whereas, when you are faced with the game G+H and you want to make a double-move, you can make a double-move in G, a double-move in H, or a single move in each of the two sub-games.
Let's begin by noting that for double-moves, 1+1+1 (a sum of three Nim heaps of size 1) is not equal to 1 (a heap of size 1): the former is a second-player win while the latter is a first-player win. Let's say that G is equivalent to H (maybe that's not the standard word to use in this context; I forget) if G+X has the same outcome (in terms of whether it's a first-player win or a second-player win) as H+X, for all X. My guess is that for double-move play, Nim has small equivalence classes (many of them singletons), as opposed to the usual Nim theory, which has big congruence classes (corresponding to the nimbers). Jim Propp On Tuesday, December 30, 2014, Cris Moore <moore@santafe.edu> wrote:
So is there an interesting theory of adding games/numbers with double moves? or k moves for general k?
On Dec 30, 2014, at 8:44 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
That's because the induction arguments that make the theory work are sensitively tuned to the fact that when you make a move in a disjunctive sum, you make a move in exactly ONE of the summands --- whereas, when you are faced with the game G+H and you want to make a double-move, you can make a double-move in G, a double-move in H, or a single move in each of the two sub-games.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Right. Both 0 and 1 are losses for the first player. But clearly these are not equivalent, since 0+1 is a loss for the first player, while 1+1 is a win. Clearly we need distinguish running out of moves on your first turn (like 0) from running out of moves on your second turn (like 1). These are two distinct ways to lose, which should be regarded as different values. Cris On Dec 30, 2014, at 9:25 PM, James Propp <jamespropp@gmail.com> wrote:
Let's begin by noting that for double-moves, 1+1+1 (a sum of three Nim heaps of size 1) is not equal to 1 (a heap of size 1): the former is a second-player win while the latter is a first-player win.
Let's say that G is equivalent to H (maybe that's not the standard word to use in this context; I forget) if G+X has the same outcome (in terms of whether it's a first-player win or a second-player win) as H+X, for all X.
My guess is that for double-move play, Nim has small equivalence classes (many of them singletons), as opposed to the usual Nim theory, which has big congruence classes (corresponding to the nimbers).
Jim Propp
On Tuesday, December 30, 2014, Cris Moore <moore@santafe.edu> wrote:
So is there an interesting theory of adding games/numbers with double moves? or k moves for general k?
On Dec 30, 2014, at 8:44 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
That's because the induction arguments that make the theory work are sensitively tuned to the fact that when you make a move in a disjunctive sum, you make a move in exactly ONE of the summands --- whereas, when you are faced with the game G+H and you want to make a double-move, you can make a double-move in G, a double-move in H, or a single move in each of the two sub-games.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
By the way, we could also consider the case where you can play one or two moves, i.e. where you can pass on the second one... Cris On Dec 30, 2014, at 9:35 PM, Cris Moore <moore@santafe.edu> wrote:
Right. Both 0 and 1 are losses for the first player. But clearly these are not equivalent, since 0+1 is a loss for the first player, while 1+1 is a win.
Clearly we need distinguish running out of moves on your first turn (like 0) from running out of moves on your second turn (like 1). These are two distinct ways to lose, which should be regarded as different values.
Cris
On Dec 30, 2014, at 9:25 PM, James Propp <jamespropp@gmail.com> wrote:
Let's begin by noting that for double-moves, 1+1+1 (a sum of three Nim heaps of size 1) is not equal to 1 (a heap of size 1): the former is a second-player win while the latter is a first-player win.
Let's say that G is equivalent to H (maybe that's not the standard word to use in this context; I forget) if G+X has the same outcome (in terms of whether it's a first-player win or a second-player win) as H+X, for all X.
My guess is that for double-move play, Nim has small equivalence classes (many of them singletons), as opposed to the usual Nim theory, which has big congruence classes (corresponding to the nimbers).
Jim Propp
On Tuesday, December 30, 2014, Cris Moore <moore@santafe.edu> wrote:
So is there an interesting theory of adding games/numbers with double moves? or k moves for general k?
On Dec 30, 2014, at 8:44 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
That's because the induction arguments that make the theory work are sensitively tuned to the fact that when you make a move in a disjunctive sum, you make a move in exactly ONE of the summands --- whereas, when you are faced with the game G+H and you want to make a double-move, you can make a double-move in G, a double-move in H, or a single move in each of the two sub-games.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
When I said that the Sprague-Grundy and Berlekamp-Conway-Guy theories could be "deployed", I didn't mean anything as grandiose as the way James Propp read me. All I meant was that a move-doubled impartial game was still impartial, and its nim-values would be a good place to start investigating; similarly, I *think* a move-doubled partisan game is still partisan, and in that case investigating its numerical value per BCG-theory would be useful. For move-doubled Nim, the sequence of nim-values for single piles is 0, 0, 1, 1, 2, 2, ..., that is, [n/2]. I'm sure other families of positions could be analyzed, though it's not clear whether the whole class of starting positions has an easy analysis. This transformation reminds me of another recalcitrant one, the "misère" transformation, in which one plays to lose. Misère impartial games are still impartial, but their Nim-values bear no relation to those of the normal games, and the disjunctive-sum rules break down because all the components are coupled by that final ring-grabbing move that is only legal after the game proper has been played out. The impartial-game theory is still useful in analyzing many misère games. On Tue, Dec 30, 2014 at 11:39 PM, Cris Moore <moore@santafe.edu> wrote:
By the way, we could also consider the case where you can play one or two moves, i.e. where you can pass on the second one...
Cris
On Dec 30, 2014, at 9:35 PM, Cris Moore <moore@santafe.edu> wrote:
Right. Both 0 and 1 are losses for the first player. But clearly these
are not equivalent, since 0+1 is a loss for the first player, while 1+1 is a win.
Clearly we need distinguish running out of moves on your first turn
(like 0) from running out of moves on your second turn (like 1). These are two distinct ways to lose, which should be regarded as different values.
Cris
On Dec 30, 2014, at 9:25 PM, James Propp <jamespropp@gmail.com> wrote:
Let's begin by noting that for double-moves, 1+1+1 (a sum of three Nim heaps of size 1) is not equal to 1 (a heap of size 1): the former is a second-player win while the latter is a first-player win.
Let's say that G is equivalent to H (maybe that's not the standard word
to
use in this context; I forget) if G+X has the same outcome (in terms of whether it's a first-player win or a second-player win) as H+X, for all X.
My guess is that for double-move play, Nim has small equivalence classes (many of them singletons), as opposed to the usual Nim theory, which has big congruence classes (corresponding to the nimbers).
Jim Propp
On Tuesday, December 30, 2014, Cris Moore <moore@santafe.edu> wrote:
So is there an interesting theory of adding games/numbers with double moves? or k moves for general k?
On Dec 30, 2014, at 8:44 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
That's because the induction arguments that make the theory work are sensitively tuned to the fact that when you make a move in a disjunctive sum, you make a move in exactly ONE of the summands --- whereas, when you are faced with the game G+H and you want to make a double-move, you can make a double-move in G, a double-move in H, or a single move in each of the two sub-games.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Can we make this more precise? Can we define the kind of game this applies to, and how the winner of the double-move is version determined? Or at least how the winner is determined for a large class of double-move candidate games? --Dan On 12/30/2014 08:02 AM, James Propp wrote: ----- Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one? -----
My interpretation was this: suppose G is a game. The Left options of Double(G) are exactly the set of Left options of Left options of G, and similarly with Right. (In this interpretation, one *must* move twice; you aren't allowed to pass on either of the two moves.) The definitions of "game" and "option", and the convention about who wins, are all exactly as in Winning Ways. On Wed, Dec 31, 2014 at 11:49 AM, Dan Asimov <dasimov@earthlink.net> wrote:
Can we make this more precise? Can we define the kind of game this applies to, and how the winner of the double-move is version determined? Or at least how the winner is determined for a large class of double-move candidate games?
--Dan
On 12/30/2014 08:02 AM, James Propp wrote:
----- Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one? -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
How would that read if you included the parts you left out? --Dan
On Dec 31, 2014, at 10:28 AM, Allan Wechsler <acwacw@gmail.com> wrote:
My interpretation was this: suppose G is a game. The Left options of Double(G) are exactly the set of Left options of Left options of G, and similarly with Right. (In this interpretation, one *must* move twice; you aren't allowed to pass on either of the two moves.) The definitions of "game" and "option", and the convention about who wins, are all exactly as in Winning Ways.
On Wed, Dec 31, 2014 at 11:49 AM, Dan Asimov <dasimov@earthlink.net> wrote:
Can we make this more precise? Can we define the kind of game this applies to, and how the winner of the double-move is version determined? Or at least how the winner is determined for a large class of double-move candidate games?
Cris Moore writes: Right. Both 0 and 1 are losses for the first player. But clearly these
are not equivalent, since 0+1 is a loss for the first player, while 1+1 is a win.
Clearly we need distinguish running out of moves on your first turn (like 0) from running out of moves on your second turn (like 1). These are two distinct ways to lose, which should be regarded as different values.
I like this suggestion. Does X+1+1+1+1 always have the same outcome as X (in Cris' sense) for every Nim position X? Jim
Hm. but then do we need to distinguish several kinds of winning: being able to force your opponent to lose on her first turn, her second turn, or whichever you like?
Cris Moore writes:
Right. Both 0 and 1 are losses for the first player. But clearly these are not equivalent, since 0+1 is a loss for the first player, while 1+1 is a win.
Clearly we need distinguish running out of moves on your first turn (like 0) from running out of moves on your second turn (like 1). These are two distinct ways to lose, which should be regarded as different values.
I like this suggestion.
Does X+1+1+1+1 always have the same outcome as X (in Cris' sense) for every Nim position X?
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
And of course there's the famous `checkmate in omega moves' scenario, where Alice can ensure that Bob eventually loses (after finite time), but for any N it is possible for Bob to ensure he survives for at least N iterations. (c.f. the MathOverflow post entitled `checkmate in omega moves' and accompanying paper by Joel David Hamkins) Sincerely, Adam P. Goucher
Sent: Thursday, January 01, 2015 at 9:28 PM From: "Cris Moore" <moore@santafe.edu> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Double moves
Hm. but then do we need to distinguish several kinds of winning: being able to force your opponent to lose on her first turn, her second turn, or whichever you like?
Cris Moore writes:
Right. Both 0 and 1 are losses for the first player. But clearly these are not equivalent, since 0+1 is a loss for the first player, while 1+1 is a win.
Clearly we need distinguish running out of moves on your first turn (like 0) from running out of moves on your second turn (like 1). These are two distinct ways to lose, which should be regarded as different values.
I like this suggestion.
Does X+1+1+1+1 always have the same outcome as X (in Cris' sense) for every Nim position X?
Jim _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Cristopher Moore Professor, Santa Fe Institute
The Nature of Computation Cristopher Moore and Stephan Mertens Available now at all good bookstores, or through Oxford University Press http://www.nature-of-computation.org/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Ha. Reminds me of the paradox of the symmetric random walk on the integers: The expected number of returns to the origin is infinite, but the expected time between one return and the next is also infinite. (Cf. Feller, vol. 1.) --Dan
On Jan 1, 2015, at 1:34 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
And of course there's the famous `checkmate in omega moves' scenario, where Alice can ensure that Bob eventually loses (after finite time), but for any N it is possible for Bob to ensure he survives for at least N iterations.
(c.f. the MathOverflow post entitled `checkmate in omega moves' and accompanying paper by Joel David Hamkins)
[Standard terminology: a P-position is a win for the previous player, an N-position is a win for the next player] If you allow players to make either 1 or 2 moves, so that a single heap with one object in it is an N-position, a modified version of the standard Sprague-Grundy theory still works. Calculate the Grundy number of each heap in the usual way (If there are legal moves to positions with Grundy numbers of 0,1,2,...n-1, but not to n, then the position had Grundy number n). Given k heaps, with Grundy numbers n_1, n_2, ... n_k, write the n_i in binary, and add them without carry. The resulting position is an P-position if the total of each place in the "sum" of the binary expansions is a multiple of 3. If you want to make the rule that you must make two moves, so that a single heap with 1 object is a P-position, then as with misere nim, a trivial modification of the standard strategy still works for nim, but not for arbitrary impartial games. As long as a position has at least 1 heap with more than one object, it is a P-position in "make exactly two moves" iff it is a P-position in the "make one or two moves" game. (and analysis of positions where every heap has a single object is trivial). But as with misere nim, I think this is no longer true when you replace a nim-heap with 1 object with an arbitrary impartial game position with Grundy number 1. All this works with making N moves, where the "sum" of the binary Grundy values must be divisible by N+1 in each place. I don't have my copy of Winning Ways handy, but I think this is all in there, mostly because I don't think I would have been able to work this out this easily if I hadn't seen it before. Here's a problem that might be interesting that I think isn't solved by the above theory; the two-move version of Lasker's nim. You have a bunch of piles, and a move is to either diminish a heap, or split a heap in two, and you can make one or two moves. Andy On Tue, Dec 30, 2014 at 8:02 AM, James Propp <jamespropp@gmail.com> wrote:
Has anyone studied variants of standard combinatorial games (such as Nim) in which each player makes two standard moves in succession on each turn instead of just one?
(This is the way my 8-year-old son likes to play tic-tac-toe against me: he puts down two X's, then I put down two O's, then he puts down two X's and wins. Fair, right?)
Note that this form of two-player game can be seen as a four-player game in which players #1 and #2 collaborate and players #3 and #4 collaborate.
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
participants (10)
-
Adam P. Goucher -
Allan Wechsler -
Andy Latto -
Cris Moore -
Dan Asimov -
Daniel Asimov -
Eric Angelini -
Erich Friedman -
James Propp -
John Aspinall