هل قمت بتنفيذ وظيفة minimax هذه بشكل صحيح؟

Question

إنها لعبة الداما.راجع سجل المراجعة للإصدارات الأقدم من التعليمات البرمجية.

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

أحاول ذلك بعمق 0، والنتائج صحيحة لحوالي نصف اللعبة، ثم فجأة يبدأ الفشل.سيبدأ أحد اللاعبين في الإعلان عن أن درجاته أعلى مما هي عليه بالفعل.لماذا يعمل فقط لمدة نصف لعبة؟!

Answer 1

وجدت الخلل: ما الذي يمكن أن يتسبب في حدوث خطأ في الحساب بعد فترة؟

رمز جديد:

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

لست مقتنعًا بنسبة 100٪ أن هذا يعمل بشكل مثالي.يبدو أنه يعمل من أجل العمق 0، وعادةً من أجل العمق 1...أبعد من ذلك، ليس لدي أي فكرة عما يفكر فيه الكمبيوتر.لا يزال لا يبدو أنه يلعب بذكاء فائق.

يحرر: تشغيل هذا والسرعة القصوى ...وكيل NegaMax مقابل عشوائي.NegaMax يفوز دائمًا.مشاهدة الدرجات لتكرار "1000".إنه يفوز دائمًا في غضون بضع دورات بعد ذلك، لذلك يبدو أنه يعمل أخيرًا!

Answer 2

نهج مثير للاهتمام ، في المرة الأولى التي أرى فيها Maximax. لكني أرى مشكلة هنا:

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

في هذا الرمز ، move و minMove هي تحركات لجوانب مختلفة ومع ذلك يمكنك تطبيقها على قدم المساواة على نفس المستوى هنا. يجب أن يكون السطر الثاني مثل:

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

يمكنك بالطبع تخزين وإعادة استخدام board.Clone().ApplyMove(move) جزء.

ولكن بعد ذلك ، لا تزال معلومات فضفاضة: في عمق 100 تقوم بتصفية أفضل لوحات من أفضل اللوحات في العمق 99 ولكنك لا تملك/تستخدم أي شيء من المستويات 98..0 باستثناء عندما لم تكن هناك خطوة (خالية) ، ولكن كما لاحظت نفسك بذلك الجزء يخطئ.

حاول النظر في بعض الخوارزميات الزائفة ، ولكن يبدو أن كل ما يعيد النتيجة. هذا يربكني ، لأنني لا أريد حقًا استعادة النتيجة ، أريد العودة إلى الوراء.

ومع ذلك ، هذا هو الطريق للذهاب. النتيجة الرئيسية من البحث عن الأشجار هي القيمة من أفضل فرع. الخطوة نفسها ضرورية فقط على مستوى الجذر. اترك الأمر حتى تبدأ في تطبيق Alpha/Beta ، ثم ستتمكن من تخزين أفضل فرع في جدول واحد.

أنصح النصيحة إلى negamax العادية ،
انظر أيضا هذا السؤال جدا.