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.