我是否正确地实现了此最小功能?
-
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进行尝试,并且得分是正确的一半,然后突然间它开始搞砸了。其中一位球员将开始宣布自己的分数比实际上更高。为什么只能在半场比赛中起作用?
解决方案 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 ...除此之外,我不知道计算机在想什么。似乎仍然没有聪明地玩。
编辑: 运行此和最大速度... Negamax代理与随机。 Negamax总是获胜。观看出现“ 1000”的分数。此后,他总是在几回合之后获胜,因此它似乎确实在起作用!
其他提示
有趣的方法,第一次看到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的任何东西,除非没有移动(null),但是正如您注意到自己的那样部分出错。
试图查看一些伪算法,但所有人似乎都返回得分。这使我感到困惑,因为我真的不想让分数回来,所以我想回去。
尽管如此,这还是要走的路。树搜索的主要结果是 价值 最好的分支。移动本身仅在根级别至关重要。保留它,直到您开始实现alpha/beta,然后您可以将最佳分支存储在单个表中。
我建议切换到常规的negamax,
也看 这个问题.
不隶属于 StackOverflow