Grundy's game extended to more than two heaps

Question

How can In break a heap into two heaps in the Grundy's game?

What about breaking a heap into any number of heaps (no two of them being equal)?

Answer 1

Games of this type are analyzed in great detail in the book series "Winning Ways for your Mathematical Plays". Most of the things you are looking for are probably in volume 1.

You can also take a look at these links: Nimbers (Wikipedia), Sprague-Grundy theorem (Wikipedia) or do a search for "combinatorial game theory".

My knowledge on this is quite rusty, so I'm afraid I can't help you myself with this specific problem. My excuses if you were already aware of everything I linked.

Edit: In general, the method of solving these types of games is to "build up" stack sizes. So start with a stack of 1 and decide who wins with optimal play. Then do the same for a stack of 2, which can be split into 1 & 1. The move on to 3, which can be split into 1 & 2. Same for 4 (here it gets trickier): 3 & 1 or 2 & 2, using the Spague-Grundy theorem & the algebraic rules for nimbers, you can calculate who will win. Keep going until you reach the stack size for which you need to know the answer.

Edit 2: The website I was talking about in the comments seems to be down. Here is a link of a backup of it: Wayback Machine - Introduction to Combinatorial Games.

Answer 2

Grundy's Game, and many games like it, can be solved with an algorithm like this:

//returns a Move object representing the current player's optimal move, or null if the player has no chance of winning
function bestMove(GameState g){
    for each (move in g.possibleMoves()){
        nextState = g.applyMove(move)
        if (bestMove(nextState) == null){
            //the next player's best move is null, so if we take this move, 
            //he has no chance of winning. This is good for us!
            return move;
        }
    }

    //none of our possible moves led to a winning strategy.
    //We have no chance of winning. This is bad for us :-(
    return null;
}

Implementations of GameState and Move depend on the game. For Grundy's game, both are simple.

GameState stores a list of integers, representing the size of each heap in the game.

Move stores an initialHeapSize integer, and a resultingHeapSizes list of integers.

GameState::possibleMoves iterates through its heap size list, and determines the legal divisions for each one.

GameState::applyMove(Move) returns a copy of the GameState, except the move given to it is applied to the board.

---

GameState::possibleMoves can be implemented for "classic" Grundy's Game like so:

function possibleMoves(GameState g){
    moves = []
    for each (heapSize in g.heapSizes){
        for each (resultingHeaps in possibleDivisions(heapSize)){
            Move m = new Move(heapSize, resultingHeaps)
            moves.append(m)
        }
    }
    return moves
}

function possibleDivisions(int heapSize){
    divisions = []
    for(int leftPileSize = 1; leftPileSize < heapSize; leftPileSize++){
        int rightPileSize = heapSize - leftPileSize
        if (leftPileSize != rightPileSize){
            divisions.append([leftPileSize, rightPileSize])
        }
    }
    return divisions
}

Modifying this to use the "divide into any number of unequal piles" rule is just a matter of changing the implementation of possibleDivisions.

---

I haven't calculated it exactly, but an unoptimized bestMove has a pretty crazy worst-case runtime. Once you start giving it a starting state of around 12 stones, you'll get long wait times. So you should implement memoization to improve performance.

For best results, keep each GameState's heap size list sorted, and discard any heaps of size 2 or 1.