[math-fun] A sandpile game
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
In an old paper, Martin Nilsson and I found a fast algorithm for predicting the final state of this 1-d sandpile from an initial state: https://arxiv.org/abs/cond-mat/9808183 But this algorithm doesn’t tell you how to place Jim’s game… - Cris
On Feb 3, 2017, at 10:22 AM, James Propp <jamespropp@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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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> 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
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> 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:_e(%7B%7D,'cvml','jamespropp@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
participants (2)
-
Cris Moore -
James Propp