Did I implement this minimax function correctly?

Question

It's for a game of checkers. See the revision history for older versions of code.

  private static Move GetBestMove(Color color, Board board, int depth)

    {

        var bestMoves = new List<Move>();

        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 && !move.IsCrowned && 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 > 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 <= 0 || !validMoves.Any())

            return BoardScore(color, board);

        foreach (var move in validMoves)

        {

            boardAfterMove = board.Clone().ApplyMove(move);

            if(move.IsJump && !move.IsCrowned && 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<Checker>().Sum(c => (c.Color == color ? 1 : -1) * (c.Class == Class.Man ? 2 : 3));

    }

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 is. Why would it only work for half a game?!

Answer 1

Right now this is a maximax. For the opponent, you need to aim for min score. Also, you rather not use floats, you can use ints instead with values multiplied with 2 (floats are slower and not precise).

I think this part of your code is not correct.

var minMove = GetBestMove(... board.Clone().ApplyMove(move), ...);

float score = ... BoardScore(color, board.Clone().ApplyMove(minMove));

In this piece of code, move and minMove are moves for different sides and yet you apply them equally at the same level here. The second line should be something like:

float score = ... BoardScore(... board.Clone().ApplyMove(move).ApplyMove(minMove));

You can of course store and re-use the board.Clone().ApplyMove(move) part.