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



Breaking down an impartial game into Nim equivalent
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.


