このMinimax関数を正しく実装しましたか?
-
30-09-2019 - |
質問
それはチェッカーのゲームのためです。コードの古いバージョンのリビジョン履歴を参照してください。
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人は、彼のスコアが実際よりも高いと宣言し始めます。なぜそれは半分のゲームでしか機能しないのですか?!
解決 2
バグを見つけました: これがしばらく後に誤算を開始する原因は何でしょうか?
新しいコード:
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では...それを超えて、コンピューターが何を考えているのかわかりません。まだ知的に演奏しているようには見えません。
編集: これと最大速度を実行します...ネガマックスエージェントvsランダム。ネガマックスは常に勝ちます。 「1000」の発生のためのスコアを視聴します。彼はその後数ターン以内に常に勝ちますので、ついに機能しているように見えます!
他のヒント
興味深いアプローチ、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で最高のボードスコアを除外しますが、動きがなかった場合を除いてレベル98..0から何も持っていません/使用していませんが、あなたが自分に気づいたように、部分がうまくいかない。
いくつかの擬似アルゴリズムを見てみましたが、すべてがスコアを返しているようです。それは私を混乱させます、私は本当にスコアを取り戻したくないので、私は動きを取り戻したいです。
それでも、それが道です。ツリー検索の主な結果は次のとおりです 価値 最高の枝の。動き自体は、ルートレベルでのみ不可欠です。 Alpha/Betaの実装を開始するまで残してください。その後、最高のブランチを1つのテーブルに保存できます。
私は通常のネガマックスに切り替えることをアドバイスします、
また、参照してください これはとても質問です.