NIM game and AI player using Minimax algorithm - AI makes losing moves

Question

I've got an assignment to write a NIM game with a human player and an AI player. The game is played "Misere" (last one that has to pick a stick loses). The AI is supposed to be using the Minimax algorithm, but it's making moves that make it lose faster and I can't figure out why. I've been on a dead end for days now. The point of the Minimax algorithm is to not lose, and if it's in a losing position, delay losing as much moves as possible, right?

Consider the following:

NIMBoard board = new NIMBoard(34, 2);

• 34 = Binary coded positions of the sticks, 2 piles of 2 sticks
• 2 = the number of piles

So we start of with this scenario, the * character representing a stick:

Row 0: **
Row 1: **

In this particular board situation, the Minimax algorithm always comes up with the move "Remove 2 sticks from Row 1". This is clearly a bad move as it leaves 2 sticks in row 0, where the human player can then pick 1 stick from row 0 and win the game.

The AI player should choose to pick one stick from either pile. That leaves this for the human player:

Row 0: *
Row 1: **

So no matter which move the human player makes now, when the computer makes the next move after that, the human player will always lose. Clearly a better strategy, but why isn't the algorithm suggesting this move?

public class Minimax
{

    public Move nextMove;

    public int evaluateComputerMove(NIMBoard board, int depth)
    {
        int maxValue = -2;
        int calculated;
        if(board.isFinal())
        {
            return -1;
        }
        for(Move n : this.generateSuccessors(board))
        {
            NIMBoard newBoard = new NIMBoard(board.getPos(), board.getNumPiles());
            newBoard.parseMove(n);
            calculated = this.evaluateHumanMove(newBoard, depth + 1);
            if(calculated > maxValue)
            {
                maxValue = calculated;
                if(depth == 0)
                {
                    System.out.println("Setting next move");
                    this.nextMove = n;
                }
            }

        }

        if(maxValue == -2)
        {
            return 0;
        }
        return maxValue;
    }

    public int evaluateHumanMove(NIMBoard board, int depth)
    {
        int minValue = 2;
        int calculated;
        if(board.isFinal())
        {
            return 1;
        }
        for(Move n : this.generateSuccessors(board))
        {
            NIMBoard newBoard = new NIMBoard(board.getPos(), board.getNumPiles());
            newBoard.parseMove(n);
            calculated = this.evaluateComputerMove(newBoard, depth + 1);
            // minValue = Integer.min(this.evaluateComputerMove(newBoard, depth + 1), minValue);
            if(calculated < minValue)
            {
                minValue = calculated;
            }
        }
        if(minValue == 2)
        {
            return 0;
        }

        return minValue;
    }

    public ArrayList<Move> generateSuccessors(NIMBoard start)
    {
        ArrayList<Move> successors = new ArrayList<Move>();
        for(int i = start.getNumPiles() - 1; i >= 0; i--)
        {
            for(long j = start.getCountForPile(i); j > 0; j--)
            {
                Move newMove = new Move(i, j);
                successors.add(newMove);
            }
        }

        return successors;
    }
}

---

public class NIMBoard
{
    /**
     * We use 4 bits to store the number of sticks which gives us these
     * maximums:
     * - 16 piles
     * - 15 sticks per pile
     */
    private static int PILE_BIT_SIZE = 4;
    private long pos;
    private int numPiles;
    private long pileMask;

    /**
     * Instantiate a new NIM board
     * @param pos Number of sticks in each pile
     * @param numPiles Number of piles
     */
    public NIMBoard(long pos, int numPiles)
    {
        super();
        this.pos        = pos;
        this.numPiles   = numPiles;

        this.pileMask   = (long) Math.pow(2, NIMBoard.PILE_BIT_SIZE) - 1;
    }

    /**
     * Is this an endgame board?
     * @return true if there's only one stick left
     */
    public boolean isFinal()
    {
        return this.onePileHasOnlyOneStick();
    }

    /**
     * Figure out if the board has a pile with only one stick in it
     * @return true if yes
     */
    public boolean onePileHasOnlyOneStick()
    {        
        int count = 0;

        for(int i = 0; i < this.numPiles; i++)
        {
            count += this.getCountForPile(i);
        }

        if(count > 1)
        {
            return false;
        }

        return true;
    }


    public int getNumPiles()
    {
        return this.numPiles;
    }

    public long getPos()
    {
        return this.pos;
    }


    public long getCountInPile(int pile)
    {
        return this.pos & (this.pileMask << (pile * NIMBoard.PILE_BIT_SIZE));
    }

    public long getCountForPile(int pile)
    {
        return this.getCountInPile(pile) >> (pile * NIMBoard.PILE_BIT_SIZE);
    }

    public void parseMove(Move move)
    {
        this.pos = this.pos - (move.getCount() << (move.getPile() * NIMBoard.PILE_BIT_SIZE));
    }

    @Override
    public String toString()
    {
        String tmp = "";
        for(int i = 0; i < this.numPiles; i++)
        {
            tmp += "Row " + i + "\t";
            for(int j = 0; j < this.getCountForPile(i); j++)
            {
                tmp += "*";
            }
            tmp += System.lineSeparator();
        }

        return tmp.trim();
    }

}

Answer 1

You are not supposed to have a different function for the human player. You should assume both players use the best strategy and since you're implementing it it should be the same code for both players.

The idea of the algorithm is not to assign a state id to the current state equal to the minimum state id that doesn't overlap any state id of the states that you could end up. If you can make a move and reach state with ids 0, 1, and 3 then the current state should have state id 2. Any losing state should have id 0.

If your current state has state id 0 you lose no mater what move you make. Otherwise you can find a move that moves the board into a state with id 0 which means the other player will lose.

Answer 2

The move that you suppose is a better move for the AI is not actually a better move. In that board situation, the human player would take two sticks from Row 1, and the computer is still stuck taking the last stick. That doesn't guarantee your program is working correctly, but I think you should try some different test cases. For example, see what the AI does if you give it the situation where you supposed the human player would lose.