¿He implementar esta función Minimax correctamente?

Question

Es para un juego de damas. Ver historial de revisión para versiones anteriores de código.

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

Estoy tratando con profundidad 0, y los resultados son correctos para aproximadamente la mitad del juego, y luego, de repente, que se inicia meter la pata. Uno de los jugadores comenzará proclamando su puntuación es mayor de lo que realmente es. ¿Por qué sólo trabajo para la mitad de un juego?!

Answer 1

encontrado el error: ¿Qué podría causar esto para iniciar calcular mal después de un tiempo?

Nuevo código:

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

No estoy 100% convencido de que esto funciona perfectamente. Parece que funciona para la profundidad de 0, y por lo general para la profundidad 1 ... más allá de eso, no tengo idea de lo que está pensando el ordenador. Aún así, no parece jugar súper inteligente.

Editar La ejecución de este y la velocidad máxima ... Agente negamax vs aleatoria. Negamax siempre gana. Viendo las puntuaciones de las apariciones de "1000". Él siempre gana dentro de un par de vueltas después de eso, por lo que no parece estar funcionando, por fin!

Answer 2

enfoque interesante, la primera vez que veo MaxiMax. Pero veo un problema aquí:

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

En este código, move y minMove son movimientos para diferentes lados y sin embargo se les aplican por igual al mismo nivel aquí. La segunda línea debe ser algo como:

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

Puede, por supuesto, la tienda y la reutilización de la parte board.Clone().ApplyMove(move).

Pero entonces la información todavía sueltos: En Profundidad 100 a filtrar la mejor boardScore a una profundidad de 99 pero no tiene / usa cualquier cosa, desde los niveles 98..0 excepto cuando había ningún movimiento (nulo), pero a medida que notado usted que parte va mal.

  

intentado buscar en algún seudo   algoritmos, pero todo el retorno parecen   una puntuacion. Que confunde a mí, porque yo   no realmente desea obtener una copia de la puntuación,   Quiero conseguir una vuelta Mover.

Sin embargo, ese es el camino a seguir. El resultado principal de un árbol de búsqueda es el valor de la mejor rama. La medida es en sí sólo es esencial en el nivel raíz. Dejarlo hasta que empezar a aplicar alfa / beta, entonces usted será capaz de almacenar la mejor rama en una sola tabla.

Yo aconsejaría conmutación a un habitual negamax, España ver también esta pregunta SO .