title: NIM game and AI player using Minimax algorithm - AI makes losing moves
body: <p>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?</p>
  
  <p>Consider the following:</p>
  
  <p>NIMBoard board = new NIMBoard(34, 2);</p>
  
  <ul>
  <li>34 = Binary coded positions of the sticks, 2 piles of 2 sticks</li>
  <li>2 = the number of piles</li>
  </ul>
  
  <p>So we start of with this scenario, the * character representing a stick:</p>
  
  <pre><code>Row 0: **
  Row 1: **
  </code></pre>
  
  <p>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.</p>
  
  <p>The AI player should choose to pick one stick from either pile. That leaves this for the human player:</p>
  
  <pre><code>Row 0: *
  Row 1: **
  </code></pre>
  
  <p>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?</p>
  
  <pre><code>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 &gt; 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 &lt; minValue)
              {
                  minValue = calculated;
              }
          }
          if(minValue == 2)
          {
              return 0;
          }
  
          return minValue;
      }
  
      public ArrayList&lt;Move&gt; generateSuccessors(NIMBoard start)
      {
          ArrayList&lt;Move&gt; successors = new ArrayList&lt;Move&gt;();
          for(int i = start.getNumPiles() - 1; i &gt;= 0; i--)
          {
              for(long j = start.getCountForPile(i); j &gt; 0; j--)
              {
                  Move newMove = new Move(i, j);
                  successors.add(newMove);
              }
          }
  
          return successors;
      }
  }
  </code></pre>
  
  <hr>
  
  <pre><code>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 &lt; this.numPiles; i++)
          {
              count += this.getCountForPile(i);
          }
  
          if(count &gt; 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 &amp; (this.pileMask &lt;&lt; (pile * NIMBoard.PILE_BIT_SIZE));
      }
  
      public long getCountForPile(int pile)
      {
          return this.getCountInPile(pile) &gt;&gt; (pile * NIMBoard.PILE_BIT_SIZE);
      }
  
      public void parseMove(Move move)
      {
          this.pos = this.pos - (move.getCount() &lt;&lt; (move.getPile() * NIMBoard.PILE_BIT_SIZE));
      }
  
      @Override
      public String toString()
      {
          String tmp = "";
          for(int i = 0; i &lt; this.numPiles; i++)
          {
              tmp += "Row " + i + "\t";
              for(int j = 0; j &lt; this.getCountForPile(i); j++)
              {
                  tmp += "*";
              }
              tmp += System.lineSeparator();
          }
  
          return tmp.trim();
      }
  
  }
  </code></pre>