Found the bug: What could cause this to start miscalculating after awhile?

New code:

private static Move GetBestMove(Color color, Board board, int depth)
{
    var bestMoves = new List<Move>();
    IEnumerable<Move> validMoves = board.GetValidMoves(color);
    int highestScore = int.MinValue;
    Board boardAfterMove;
    int tmpScore;
    var rand = new Random();

    Debug.WriteLine("{0} s Moves:", color);

    foreach (Move 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)
{
    IEnumerable<Move> validMoves = board.GetValidMoves(color);
    int highestScore = int.MinValue;
    Board boardAfterMove;

    if (depth <= 0 || !validMoves.Any())
        return BoardScore(color, board);

    foreach (Move 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 not 100% convinced this works perfectly. It seems to work for depth 0, and usually for depth 1... beyond that, I have no idea what the computer is thinking. Still doesn t appear to play super intelligently.

Edit: Running this and max speed... NegaMax agent vs Random. NegaMax always wins. Watching the scores for occurrences of "1000". He always wins within a few turns after that, so it does appear to be working, finally!

Interesting approach, the first time I see MaxiMax. But I see a problem here:

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

In this 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.

But then you still loose information: At Depth 100 you filter out the best boardScore at depth 99 but you don t have/use anything from levels 98..0 except when there was no move (null), but as you noticed yourself that part goes wrong.

Tried looking at some pseudo algorithms, but all the seem to return a score. That confuses me, because I don t really want to get a score back, I want to get a Move back.

Still, that is the way to go. The main result from a tree-search is the value of the best branch. The move itself is only essential at the root level. Leave it until you start implementing alpha/beta, then you will be able to store the best branch in a single table.

I would advice switching to a regular NegaMax,
also see this SO question.