If you add a rule that when all but one pile is non-zero, you must play in the zero pile, winning the game, does that eliminate all loops, yielding a game that has Grundy values? Playing a different move when there is an immediately-winning move available makes no sense if you are playing the game alone, though might be the best move when playing as part of a sum of games. Andy On Tue, Feb 7, 2017 at 11:40 AM, James Propp <jamespropp@gmail.com> wrote:
These games do not have Grundy values of the ordinary kind because they are loopy. 01 and 10 should have the same Grundy value by symmetry, but each of them is an option of the other.
(Right?)
Jim
On Tuesday, February 7, 2017, Andy Latto <andy.latto@pobox.com> wrote:
Knowing what the P-positions are is not all one would want to know about a combinatorial game. How do you calculate the Grundy number of an arbitrary position in the sand-pile game?
Andy
On Tue, Feb 7, 2017 at 7:24 AM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
What the winning strategy amounts to in practice (after you've seized a P-position) is that when your adversary puts a token in box i, you respond by putting a token in box 10-i. Pretty soon she'll catch on to what you're up to, even if it's not immediately clear why you're doing it!
Jim
On Monday, February 6, 2017, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
The right move is to add a token to the already-occupied seventh box (causing it to fire to its two neighbors), turning 0 1 0 0 0 0 1 0 1 into 0 1 0 0 0 1 0 1 1; any other move loses against an ideal adversary.
The general strategy is guided by the numerical sum of the “place-values” of the tokens, where a token in the 1st (leftmost) box has place value 1, a token in the 2nd box has place value 2, etc. You can check that when a firing occurs, the total value of the configuration doesn’t change, except when the 9th box fires, in which case the total value goes down by 10. So the winning strategy is, compute the value v of the current position, and then place a token in the unique position i such that v+i is congruent to 45 mod 10. (Why 45? Because it’s the value of 1+2+3+…+8+9, which is the value of the goal-position.) In combinatorial game-theory terms, the “P-positions” are those whose last decimal digit is a 5.
It’s easy to show that if you follow this strategy (assuming that you aren’t faced with a position whose value already ends in a 5 when it’s your first turn to move) your opponent can’t win.
But is there an easy way to show that the game must eventually end? One could cite lemmas from sandpile-theory, but that’d be cheating for my purposes. One needs to show that eventually there must be at least n-1 tokens on the board, no matter what the players do. From there, it’s easy to win in 1 move (unless someone has already won). I know a self-contained proof, but it’s not as simple as I’d like.
Anyway, once you show that the game eventually ends, and you show that your opponent can’t win if you follow the place-value strategy (starting from a position whose value doesn't end in a 5), it follows that the strategy lets you win!
I’m curious how hard it is to figure all this out. I never had a chance to figure it out for myself, because I reverse-engineered the game from my knowledge of the theory of sandpiles. My guess is that it would be fun and satisfying to work this out (by piecing together small patterns into larger ones), but I could be wrong.
On Mon, Feb 6, 2017 at 7:39 AM, James Propp <jamespropp@gmail.com <javascript:;> <javascript:_e(%7B%7D,'cvml','jamespropp@gmail.com <javascript:;>');>> wrote:
Here's a hint: Find a numerical function of the state of the board that doesn't change when you fire, and changes in a predictable way when you add a token (depending only on the location of the added token).
Jim
On Friday, February 3, 2017, James Propp <jamespropp@gmail.com <javascript:;> <javascript:_e(%7B%7D,'cvml','jamespropp@gmail.com <javascript:;>');>> wrote:
Since some people (myself included!) relish a specific challenge rather than a diffuse one, let me ask who can figure out the unique right move to make when the state of the board is
0 1 0 0 0 0 1 0 1
and it's your turn to move.
I'll post an answer (and an explanation) on Monday if nobody beats me to it.
(One feature of this game is that when there's a winning move, it's always unique. Is there a general theory of games having that property?)
Jim
On Fri, Feb 3, 2017 at 12:22 PM, James Propp <jamespropp@gmail.com <javascript:;>> wrote:
> I’ve devised a combinatorial game based on the theory of the abelian > sandpile model and I’m trying to come up with a good name for it. > > The game is played using identical tokens on a board consisting of nine > consecutive boxes, each of which is capable of holding one or two tokens. > Players take turns. When it’s your turn to move, you add a token to any of > the nine boxes; if the box already contains a token, then the box “fires” > (by sending one token to the left and one token to the right), and if that > leads one or more boxes to contain more than one token, then those boxes > fire (by sending one token to the left and one token to the right), and so > on; when the leftmost or rightmost box fires, the token that gets fired off > the board disappears from the game. Eventually the board stabilizes so that > each box contains at most one token. > > Example: If the state of the board is > > 1 1 1 0 1 0 0 1 0 > > and a player adds a token to the second square from the left, the state > of the board evolves as follows: > > 1 2 1 0 1 0 0 1 0 > 2 0 2 0 1 0 0 1 0 > 0 2 0 1 1 0 0 1 0 > 1 0 1 1 1 0 0 1 0 > > The goal of the game is to be the player who achieves the configuration > > 1 1 1 1 1 1 1 1 1 > > (I’ll post a video sometime soon that will make the nature of game-play > much clearer than the above, but I’d like to have a good name for the game > first.) > > There’s a very nice (but non-obvious) numerical way to look at the game > that makes it quite easy to recognize, from any given starting position, > whether it’s a win for the first player or the second player, and the > winning strategy is also quite simple. > > I’m pretty sure this is new. Can anyone think of a good name for it? > > Please give me feedback on this game. (It might be more apt to call it > a puzzle in which the goal is to figure out how to play the game well.) > > Jim Propp >
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com <javascript:;>
_______________________________________________ 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
-- Andy.Latto@pobox.com