title: Conversion of minimax with alpha beta pruning to negamax
body: <p>I've written a <a href="http://en.wikipedia.org/wiki/Minimax">minimax</a> algorithm with <a href="http://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning">alpha beta pruning</a> for the game Checkers, and now I'm trying to rewrite it using the <a href="http://en.wikipedia.org/wiki/Negamax">negamax</a> approach. I'm expecting the two to be equivalent, since negamax is just a technique to write the minimax. But for some reason my two algorithms behave differently. When I run them both on the same input, the negamax version seems to evaluate more states, so I think something must be wrong with the alpha beta pruning.</p>
  
  <p>The code below shows both algorithms (<code>minimax</code> and <code>negamax</code> functions), and at the bottom the <code>play</code> function from which I call them. The <code>evaluate</code> function is the basic heuristic which I use to evaluate states in both algorithms.</p>
  
  <p>Any help with spotting the error would be much appriciated.</p>
  
  <pre><code>#include "player.hpp"
  #include &lt;algorithm&gt;
  #include &lt;limits&gt;
  #include &lt;cstdlib&gt;
  
  namespace checkers
  {
  
  int evaluatedStates = 0;
  
  int evaluate(const GameState &amp;state)
  {
      // FIXME: Improve heuristics.
      int redScore = 0;
      int whiteScore = 0;
      int piece = 0;
      for (int i = 1; i &lt;= 32; ++i)
      {
          piece = state.at(i);
          if (piece &amp; CELL_RED) {
              ++redScore;
              if (piece &amp; CELL_KING)
                  redScore += 2;   // King bonus.
          } else if (piece &amp; CELL_WHITE) {
              ++whiteScore;
              if (piece &amp; CELL_KING)
                  whiteScore += 2; // King bonus.
          }
      }
      return state.getNextPlayer() == CELL_RED ? whiteScore - redScore : redScore - whiteScore;
  }
  
  int minimax(const GameState &amp;state, int depth, int a, int b, bool max)
  {
      if (depth == 0 || state.isEOG()) {
          ++evaluatedStates;
          return evaluate(state);
      }
      std::vector&lt;GameState&gt; possibleMoves;
      state.findPossibleMoves(possibleMoves);
      if (max) {
          for (const GameState &amp;move : possibleMoves) {
              a = std::max(a, minimax(move, depth - 1, a, b, false));
              if (b &lt;= a)
                  return b; // β cutoff.
          }
          return a;
      } else {
          for (const GameState &amp;move : possibleMoves) {
              b = std::min(b, minimax(move, depth - 1, a, b, true));
              if (b &lt;= a)
                  return a; // α cutoff.
          }
          return b;
      }
  }
  
  int negamax(const GameState &amp;state, int depth, int a, int b)
  {
      if (depth == 0 || state.isEOG()) {
          ++evaluatedStates;
          return evaluate(state);
      }
      std::vector&lt;GameState&gt; possibleMoves;
      state.findPossibleMoves(possibleMoves);
      for (const GameState &amp;move : possibleMoves) {
          a = std::max(a, -negamax(move, depth - 1, -b, -a));
          if (b &lt;= a)
              return b; // β cutoff.
      }
      return a;
  }
  
  GameState Player::play(const GameState &amp;pState, const Deadline &amp;pDue)
  {
      GameState bestMove(pState, Move());
  
      std::vector&lt;GameState&gt; possibleMoves;
      pState.findPossibleMoves(possibleMoves);
  
      int a = -std::numeric_limits&lt;int&gt;::max();
      int b = std::numeric_limits&lt;int&gt;::max();
      for (const GameState &amp;move : possibleMoves) {
          int v = negamax(move, 10, a, b);
          //int v = minimax(move, 10, a, b, false);
          if (v &gt; a) {
              a = v;
              bestMove = move;
          }
      }
      std::cerr &lt;&lt; "Evaluated states: " &lt;&lt; evaluatedStates &lt;&lt; std::endl;
      return bestMove;
  }
  
  /*namespace checkers*/ }
  </code></pre>