Breaking down an impartial game into Nim equivalent - MathOverflow

Breaking down an impartial game into Nim equivalent

2011-12-12T14:56:29Z

This is the game:

The playing field consists of permutation of numbers. The players take turns playing the game. Each player removes single number from the sequence. The game is finished when the remaining sequence is in increasing order. Starting sequence is never ordered. Both players use an optimal strategy.

Example of a starting position: 3 4 1 6 5 7 2

This game is a part of coding challenge, which I want to do alone to the maximum extent possible so please try not to reveal too much.

What I have figured out so far: This is an example of impartial combinatorial game. The optimal solution to the game should be found via Sprague-Grundy Theorem.

But the position where I got stuck is how do approach breaking down the game into Nim equivalent.

Edit:

Questions:

What do I do about terminal positions?
Is this approach of modelling heaps correct or is there something more subtle going on (e.g. the empty slots in the coin game?).
As the prevalent opinion is that finding the Nim heap within this game is not trivial. What would be good candidates? How does one go about ratting it out?

OLD POST BELOW

My current approach:

Define terminal positions.

Decompose tha game into Nim-heap equivalent for this game.

Compute Grundy numbers for various heap sizes in the game.

Play it as a game of Nim using the Nim optimal strategy.

ad 1*: I defined the terminal position as a single heap of size 1.

clarification: ad 2: I form Heaps as decreasing sequences - so for above example I would group [3] [4,1] [6,5] [7,2] together - which gives us game: P=(*1,*2,*2,*2)

ad 3*: This is the computed Grundy sequence for this game [0,0,1,1,0,1,2,3,4,1,0,3,1,5,0,1] NOTE: Will be updated when I compute a correct sequence.

clarification: This is how I computed this sequence:

g(0)=0

g(1)=0

g(2)={g(0),g(1)}=1

g(3)={g(2),g(1)^g(1)}=1 <---- I made a mistake here! This decomposition attempt is Fail - Thank you Alfonso!

*I did not include the varying length of terminal positions in my computation, since I don't know how would one go about that.

So the game either plays out until there is only one number left in the sequence OR until a player stumbles upon a endgame sequence as a possible next move (this is a manual kludge in the algorithm).

After spending a lot of time on this problem I am certain that the general approach is right (results are not completely off base), however I cannot fathom how to correctly decompose the game into Nim-Heaps and how to handle terminal positions.

Answer by Alfonso Gracia-Saz for Breaking down an impartial game into Nim equivalent

2011-12-12T17:05:08Z

On step 1, you forget that a single heap of size 1 is not the only terminal position in this game. Any increasing sequence is a terminal position.

On step 2, your decomposition does not work. For example, the game [3,4,1] is not the sum of the games [3] and [4,1], because when you put those numbers together, they do not form two independent games. To be more precise, the game [3] has nim-value 0; the game [4,1] has nim-value 1; but the game [3,4,1] has nim-value 2. The difficulty of this game (and its interest) lies in the fact that you cannot (at least not at first sight) decompose it as sum of various smaller games.

Finally, on step 3, how did you calculate that "Grundy sequence"? If you have a game whose positions are defined by a single integer, then the n-th term of the Grundy sequence is the nim equivalent for position n. This is not the case here, so I have no idea what that sequence means or how you calculated it.

Answer by psd for Breaking down an impartial game into Nim equivalent

2011-12-12T17:13:59Z

You can solve this with semi-brute force by considering that there are at most 2^n game states; this is the number of possible ways that a subset of the numbers can be removed. You can use dynamic programming to find the value (win vs. loss) of each game state. If you want to solve games where n is so big that 2^n is intractable then you will need a more clever algorithm than this one -- partitioning the sequence into decreasing subsequences, as you have done, would be an example of the basis of a more clever algorithm.

Answer by Hugh Thomas for Breaking down an impartial game into Nim equivalent

2011-12-12T17:43:46Z

The fact that an impartial game is equivalent to a nim-heap doesn't necessarily mean that it's easy to find the heap in the combinatorics of the game. If all you want to do is determine whether a position is a first-player win or a second-player win, though, you don't need the nim-heap size anyway: a position is a second-player win if there are no moves from it to a second-player win position; otherwise, it's a first-player win.

I'd suggest looking at a bunch of permutations, determining which is a first-player win and which is a second-player win, and then trying to guess and prove a pattern.

Answer by Barry Cipra for Breaking down an impartial game into Nim equivalent

2011-12-12T19:18:07Z

I think you might do well to first analyze the game from the ground up, by listing all the losing positions among the permutations of $1,...,n$ for small values of $n$. For one thing, after removing a number $h$, one might as well "renormalize" the remaining numbers by subtracting 1 from all values $k>h$. For example, if you remove the 3 from 3 4 1 6 5 7 2, leaving 4 1 6 5 7 2, you can rewrite this as 3 1 5 4 6 2. Note that removing the 4 instead, leaving 3 1 6 5 7 2, rewrites to the same permutation of 1-6.

Doing the first few cases by hand, I get the following list of losing positions:

123, 321

1234, 3142, 3412, 2143, 2413

I may have made a mistake in the last line, and I certainly don't trust myself to do the permutations of 1-5 correctly by hand, but it does look like the number of losing positions grows relatively slowly compared to $n!$. It would be of interest if the number of losing positions for $n=5$ turns out to be 14.