title: Did I implement this minimax function correctly?
body: <p>It's for a game of checkers. See revision history for older versions of code.</p>
  
  <pre><code>    private static Move GetBestMove(Color color, Board board, int depth)
      {
          var bestMoves = new List&lt;Move&gt;();
          var validMoves = board.GetValidMoves(color);
          int highestScore = int.MinValue;
          Board boardAfterMove;
          int tmpScore;
          var rand = new Random();
  
          Debug.WriteLine("{0}'s Moves:", color);
  
          foreach (var move in validMoves)
          {
              boardAfterMove = board.Clone().ApplyMove(move);
  
              if(move.IsJump &amp;&amp; !move.IsCrowned &amp;&amp; boardAfterMove.GetJumps(color).Any())
                  tmpScore = NegaMax(color, boardAfterMove, depth);
              else
                  tmpScore = -NegaMax(Board.Opposite(color), boardAfterMove, depth);
  
              Debug.WriteLine("{0}: {1}", move, tmpScore);
  
              if (tmpScore &gt; highestScore)
              {
                  bestMoves.Clear();
                  bestMoves.Add(move);
                  highestScore = tmpScore;
              }
              else if (tmpScore == highestScore)
              {
                  bestMoves.Add(move);
              }
          }
  
          return bestMoves[rand.Next(bestMoves.Count)];
      }
  
      private static int NegaMax(Color color, Board board, int depth)
      {
          var validMoves = board.GetValidMoves(color);
          int highestScore = int.MinValue;
          Board boardAfterMove;
  
          if (depth &lt;= 0 || !validMoves.Any())
              return BoardScore(color, board);
  
          foreach (var move in validMoves)
          {
              boardAfterMove = board.Clone().ApplyMove(move);
  
              if(move.IsJump &amp;&amp; !move.IsCrowned &amp;&amp; boardAfterMove.GetJumps(color).Any())
                  highestScore = Math.Max(highestScore, NegaMax(color, boardAfterMove, depth));
              else
                  highestScore = Math.Max(highestScore, -NegaMax(Board.Opposite(color), boardAfterMove, depth - 1));
          }
  
          return highestScore;
      }
  
      private static int BoardScore(Color color, Board board)
      {
          if (!board.GetValidMoves(color).Any()) return -1000;
          return board.OfType&lt;Checker&gt;().Sum(c =&gt; (c.Color == color ? 1 : -1) * (c.Class == Class.Man ? 2 : 3));
      }
  </code></pre>
  
  <p>I'm trying it with depth 0, and the scores are correct for about half the game, and then all of a sudden it starts screwing up. One of the players will start proclaiming his score is higher than it really is. Why would it only work for half a game?!</p>