# Breaking down an impartial game into Nim equivalent

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:

1. What do I do about terminal positions?

2. Is this approach of modelling heaps correct or is there something more subtle going on (e.g. the empty slots in the coin game?).

3. 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:

1. Define terminal positions.
2. Decompose tha game into Nim-heap equivalent for this game.
3. Compute Grundy numbers for various heap sizes in the game.
4. 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.

-
What is the question? There are too many terms in your post which either are not defined or are ambiguous. If want an answer please try to reformat this and explain more carefully what you are asking. –  Alan Haynes Dec 12 '11 at 16:28
Did some edits is it more comprehensible now? Please bear with me and point me to the points that need clarification. I will be extremely grateful. –  JanezStupar Dec 12 '11 at 18:04

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.

-
@step 1: I did not forget it I simply don't know how to model them as Nim positions. @step2: I clarified in the question. @step3: I clarified in the question and found out that I made a mistake in computation - Thank you. –  JanezStupar Dec 12 '11 at 18:07
You got me thinking there. When I started recomputing Grundy numbers, I noticed the mistake at g(2) which has concealed that this decomposition does not work. Do you have any idea how to approach the decomposition. Or just look at other "brute force" alternatives? –  JanezStupar Dec 12 '11 at 18:21

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:

1

12

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.

-
I haven't done any more numerical examples, but note that the asymptotic growth of Catalan numbers rules out the existence of $C_{n-1}$ second player wins. Each of the $n!$ permutations is either a second player win, or you can move to a permutation of $n-1$ which is a second player win, and there are $n^2$ ways to invert a move by choosing which number to insert into which position. For $n$ large, $C_{n-1} + n^2C_{n-2} = \Theta(\sqrt{n} 4^n) = o(n!)$. –  Douglas Zare May 28 '13 at 10:58

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.

-
The key is that optimal play is expected of both players. How do I make sure that the particular result is achieved through optimal play? –  JanezStupar Dec 12 '11 at 18:44
@janez: this incorporates the requirement of optimal play –  psd Dec 12 '11 at 19:43