Ho implementare questa funzione Minimax correttamente?

Question

E 'per una partita a dama. Cronologia delle revisioni per le versioni precedenti di codice.

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

sto cercando con la profondità 0, ed i punteggi siano corretti per circa la metà del gioco, e poi tutto ad un tratto si inizia strizzando. Uno dei giocatori inizierà proclamando il suo punteggio è superiore a quello che è in realtà. Perché dovrebbe funzionare solo per mezzo di un gioco?!

Answer 1

Trovato il bug: che cosa potrebbe causare questo per avviare miscalculating dopo un po '?

Nuovo codice:

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

Non sto al 100% convinto questo funziona perfettamente. E sembra funzionare per la profondità 0, e di solito per la profondità 1 ... al di là di questo, non ho idea di ciò che il computer è il pensiero. Ancora non sembra giocare a Super intelligente.

Modifica L'esecuzione di questo e la velocità massima ... negamax agente vs casuale. Negamax vince sempre. Guardando i punteggi per occorrenze di "1000". Vince sempre nel giro di pochi giri dopo che, in modo che non sembra funzionare, finalmente!

Answer 2

approccio interessante, la prima volta che vedo maximax. Ma io vedo un problema qui:

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

In questo codice, move e minMove sono mosse per lati diversi, eppure li applicano allo stesso modo allo stesso livello qui. La seconda linea dovrebbe essere qualcosa di simile:

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

È possibile memorizzare di corso e il riutilizzo della parte board.Clone().ApplyMove(move).

Ma poi un servizio di informazione ancora sciolto: in profondità 100 si filtrare fuori il meglio boardScore in profondità 99, ma non avete / uso qualsiasi cosa, da livelli 98..0 tranne quando non vi era alcuna mossa (null), ma come si te notato che parte va storto.

  

provato a guardare un po 'di pseudo   algoritmi, ma tutte le sembrano ritorno   un punteggio. Che confonde me, perché io   non si vuole davvero ottenere un punteggio indietro,   Voglio ottenere un ritorno.

Ancora, che è la strada da percorrere. Il risultato principale da un albero-ricerca è il valore del meglio ramo. La mossa in sé è essenziale solo al livello principale. Lasciare fino a quando non avviare l'attuazione di alpha / beta, allora si sarà in grado di memorizzare il miglior ramo in una singola tabella.

Vi consiglio di commutazione ad un regolare negamax,
anche vedere questa domanda SO .