Est-ce que je mets en œuvre correctement cette fonction Minimax?

Question

Il est pour un jeu de dames. Voir l'historique des révisions pour les anciennes versions de 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));
    }

Je suis en train avec la profondeur 0, et les scores sont corrects pour environ la moitié du jeu, puis tout d'un coup ça commence vissage. L'un des joueurs va commencer son score est proclamait plus élevé qu'il ne l'est vraiment. Pourquoi ne serait-il que le travail d'un demi-jeu!

Answer 1

Trouvé le bug: Que pourrait causer cela commence après un certain temps mauvais calcul?

Nouveau 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));
}

Je ne suis pas convaincu à 100% cela fonctionne parfaitement. Il semble fonctionner pour la profondeur 0, et le plus souvent pour la profondeur 1 ... au-delà, je ne sais pas ce que l'ordinateur est pensée. ne semble toujours pas jouer super intelligemment.

Modifier L'exécution de cette vitesse et max ... Agent NegaMax vs aléatoire. NegaMax gagne toujours. Regarder les scores pour les occurrences de « 1000 ». Il gagne toujours en quelques tours après que, il ne semble fonctionner, enfin!

Answer 2

Approche intéressante, la première fois que je vois MAXIMAX. Mais je vois ici un problème:

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

Dans ce code, move et minMove sont mouvements pour différents côtés et pourtant vous les appliquer également au même niveau ici. devrait être quelque chose comme la deuxième ligne:

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

Vous pouvez de magasin de cours et la réutilisation d'une partie de board.Clone().ApplyMove(move).

Mais alors vous des informations encore en vrac: à la profondeur 100 vous filtrez la meilleure boardScore en profondeur 99 mais vous n'avez pas / utiliser quoi que ce soit par rapport aux niveaux 98..0 sauf quand il n'y avait aucun mouvement (null), mais comme vous vous remarqué qu'une partie ne va pas.

  

Essayé regardant certains pseudo   algorithmes, mais tout semble revenir   un score. Qui confond moi, parce que je   ne veulent pas vraiment d'obtenir un retour de partition,   Je veux obtenir un retour de déplacement.

Pourtant, qui est le chemin à parcourir. Le principal résultat d'une recherche d'arbre est la valeur de la meilleure branche. Le mouvement lui-même est seulement essentiel au niveau de la racine. Laissez-le jusqu'à ce que vous commencer à appliquer alpha / bêta, vous serez alors en mesure de stocker la meilleure branche dans une seule table.

Je vous conseille de passer à une NegaMax régulière,
voir aussi cette question SO .