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(a)gmail.com> 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(a)gmail.com> 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(a)gmail.com>
>> 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
>>>
>>
>>
