4

チェッカーのゲーム用です。古いバージョンのコードについては、改訂履歴を参照してください。

    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でそれを試しています、そしてスコアはゲームの約半分で正しいです、そしてそれから突然それは台無しになり始めます。プレーヤーの1人は、自分のスコアが実際よりも高いと宣言し始めます。なぜそれは半分のゲームでしか機能しないのでしょうか？！

4

2 に答える 2

2

興味深いアプローチ、MaxiMaxを初めて見たとき。しかし、ここで問題が発生します。

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

このコードではmove、minMoveはさまざまな側面に移動しますが、ここでは同じレベルで等しく適用します。2行目は次のようになります。

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

もちろん、部品を保管して再利用することもできますboard.Clone().ApplyMove(move)。

しかし、それでも情報は失われます。深さ100では、深さ99で最高のboardScoreを除外しますが、移動がなかった場合（null）を除いて、レベル98..0からは何も使用しませんが、気付いたように一部がうまくいかない。

いくつかの疑似アルゴリズムを調べてみましたが、すべてがスコアを返すようです。それは私を混乱させます、私は本当にスコアを取り戻したくないので、私はムーブを取り戻したいです。

それでも、それは進むべき道です。ツリー検索の主な結果は、最良のブランチの値です。移動自体は、ルートレベルでのみ不可欠です。アルファ/ベータの実装を開始するまでそのままにしておくと、最適なブランチを1つのテーブルに格納できるようになります。

通常のNegaMaxに切り替えることをお勧めします。このSOの質問
も参照してください。

于 2010-09-04T07:57:01.043 に答える
0

バグが見つかりました：しばらくすると、これが誤算を開始する原因は何ですか？

新しいコード：

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」の発生のスコアを監視します。彼はその後数ターン以内に常に勝つので、ついにそれは機能しているように見えます！

于 2010-09-06T19:52:47.647 に答える