|
7
|
|
edited Dec 12 2011 at 18:45 |
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.
|
|
|
|
|
6
|
|
edited Dec 12 2011 at 18:32 |
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.
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?). 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.
|
|
|
|
|
5
|
|
edited Dec 12 2011 at 18:25 |
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! Back to the drawing board! *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. *1,*2,*2,*2P=(*1,*2,*2,*2) 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!
|
|
|
|
4
|
|
edited Dec 12 2011 at 18:03 |
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.
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:
*
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! Back to the drawing board!
*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.
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?).
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:
*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]
*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.
|
|
|
|
|
3
|
|
edited Dec 12 2011 at 17:57 |
Edit:*My current approach:* 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(3)={g(2),g(1)^g(1)}=1 <---- I made a mistake here! Back to the drawing board! *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. 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?). 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: *1,*2,*2,*2
|
|
|
|
|
2
|
|
edited Dec 12 2011 at 15:21 |
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.
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.
Here is what I know
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.
ad 2: I form Heaps as decreasing sequences - so for above example I would do [3] [4,1] [6,5] [7,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]
*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.
|
|
|
|
|
1
|
|
asked Dec 12 2011 at 14:56 |
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.
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.
Here is what I know:
- Define terminal positions.
- Decompose tha game into Nim-heap equivalent for this game.
- Compute Grundy numbers for various heap sizes in the game.
ad 1*: I defined the terminal position as a single heap of size 1.
ad 2: I form Heaps as decreasing sequences - so for above example I would do [3] [4,1] [6,5] [7,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]
*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.
|
|
|
