我是否正确实施了这个极小极大功能?
这是一款跳棋游戏。请参阅旧版代码的修订历史记录。我是否正确实施了这个极小极大功能?
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,分数对于大概一半的游戏是正确的,然后突然它开始搞砸了。其中一名球员将开始宣称他的得分高于实际得分。为什么它只能用于半场比赛?!
发现的bug:What could cause this to start miscalculating after awhile?
新代码:
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代理vs随机。 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处过滤掉最好的boardScore,但是你不必使用98..0中的任何东西,除非没有移动(null)你注意到自己那部分出问题了。
尝试看看一些伪 算法,但所有似乎返回 得分。这使我困惑,因为我 不想真的想要得分, 我想要得到回归。
不过,这是要走的路。树搜索的主要结果是最佳分支的值。此举本身只是在根本层面上至关重要。直到你开始实施alpha/beta,那么你将能够将最好的分支存储在一张表中。
我会建议切换到一个普通的NegaMax,
也见this SO question。
“在这段代码中,移动和移动minMove会移动到不同的边,然而您在这里的平面上同样适用它们。“它应该为对方球员找到最好的举动,然后计算*当前球员的得分,如果其他球员做出了很好的举动,那么这可能会变得更低......但是,我最大化了这个得分。 。这是否意味着我*实际上*假设玩家会做出不好的举动,因为我最大化了错误的东西?当我明天有机会的时候,我会看看NegaMax,谢谢 – mpen 2010-09-04 23:34:14
“但是你仍然宽松的信息:在深度100处,您可以在深度99处筛选出最佳boardScore,但是您没有/使用98..0级别的任何数据“ - 这不就是我最后关注的分数吗?假设两位玩家做出最好的举动,你想最大限度地达到最终状态,而不是在两者之间? – mpen 2010-09-04 23:36:34
你的Move类实际上是一个完整的分支吗? – 2010-09-05 09:56:28
现在这是一个maximax。对于你的对手,你需要瞄准最低分。你也可以不使用浮点数,你可以使用整数乘以2的值(浮点数较慢而且不精确) – 2010-09-04 06:27:14
@lmre:没想到使用浮点数的影响会产生很大的影响,但我猜如果这样运行几十亿次,可以加起来。 – mpen 2010-09-04 23:29:02