- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我的程序中有一个有效的 negamax 算法。但是,我需要程序在 kMaxTimePerMove
时间内找到最佳可能的着法。我做了一些研究,似乎使用迭代加深和我的 negamax 算法是最好的方法。现在,我启动搜索的函数如下所示:
// this is a global in the same scope as the alpha-beta functions, so they can check the elapsed time
clock_t tStart;
int IterativeDeepening(Board current_state)
{
bool overtime = false;
int depth = 0;
tStart = clock();
MoveHolder best_move(-1, kWorstEvaluation);
while ((static_cast<double> (clock() - tStart)/CLOCKS_PER_SEC) < kMaxTimePerMove)
{
MoveHolder temp_move = AlphaBetaRoot(kWorstEvaluation, -best_move.evaluation_,++depth, current_state, overtime);
if (!overtime)
best_move = temp_move;
}
return best_move.column_;
}
我想我也应该将之前的最佳移动重新排序到子列表的前面,但是,我正在等待实现它,直到我获得基本版本。实际的 Alpha-Beta 函数如下所示:
MoveHolder AlphaBetaRoot(int alpha, int beta, int remaining_depth, Board current_state, bool &overtime)
{
MoveHolder best(-1, -1);
if (overtime)
return MoveHolder(0,0);
std::vector<Board> current_children;
current_state.GetBoardChildren(current_children);
for (auto i : current_children)
{
best.evaluation_ = -AlphaBeta(-beta, -alpha, remaining_depth - 1, i, overtime);
if ((static_cast<double> (clock() - tStart)/CLOCKS_PER_SEC) > kMaxTimePerMove)
{
overtime = true;
return MoveHolder(0,0);
}
if (best.evaluation_ >= beta)
return best;
if (best.evaluation_ > alpha)
{
alpha = best.evaluation_;
best.column_ = i.GetLastMoveColumn();
}
}
return best;
}
int AlphaBeta(int alpha, int beta, int remaining_depth, Board2 current_state, bool &overtime)
{
if (overtime)
return 0;
if ((static_cast<double> (clock() - tStart)/CLOCKS_PER_SEC) > kMaxTimePerMove)
{
overtime = true;
return 0;
}
if (remaining_depth == 0 || current_state.GetCurrentResult() != kNoResult)
{
return current_state.GetToMove() * current_state.GetCurrentEvaluation();
}
std::vector<Board> current_children;
current_state.GetBoardChildren(current_children);
for (auto i : current_children)
{
int score = -AlphaBeta(-beta, -alpha, remaining_depth - 1, i, overtime);
if (score >= beta)
{
return beta;
}
if (score > alpha)
{
alpha = score;
}
}
return alpha;
}
当我尝试调试时,一切似乎都在按预期工作。然而,当我让迭代深化版本与常规 alpha-beta 实现对战时,它总是输。有时它似乎被“卡住了”,并返回一个可怕的举动。
例如,如果此程序“被迫”在下一回合采取行动,否则对手将获胜,它不会阻止获胜。在那一步,它报告说它正在搜索 38 的深度。我发现该算法极难调试,因为如果我中断执行,就会破坏计时。
我不确定我是否错误地实现了算法,或者只是这里有一个棘手的错误。如果有人能指出正确的方向,我将不胜感激。
最佳答案
您正在使用 -best_move.evaluation_
作为搜索的 beta 值,其中 best_move
是之前深度的最佳移动。这是不正确的:假设一个移动在深度 = 2 时看起来不错,但在更大的深度时结果很糟糕。这种方法将继续认为它是好的,并导致在其他移动中不应该发生的 beta 截止。
您应该在 (-infinity, infinity) 上搜索每个迭代来解决此问题。您也可以使用 aspiration windows限制 alpha-beta 范围。
请注意,由于您不使用上一次迭代来改进下一次迭代的移动顺序,因此迭代加深会导致稍微更差的结果。理想情况下,您希望移动顺序从换位表和/或前一次迭代的主要变化中选择最佳移动。
关于c++ - 通过 Alpha-Beta 修剪迭代加深 Negamax,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13549594/
TLDR:我有一个用于 negamax 实现的非对称评估函数 - 这可以接受吗?还是我需要使其对称? 更长:我正在编写一个游戏 AI(用于类似国际象棋的棋盘游戏“Hive”),它使用带有 alpha-
我有一个尽可能简单的 negamax 算法,用于评估 Tic Tac Toe 中的位置。游戏状态在 numpy 中存储为一个数组,X 的棋子用 1 表示,O 的棋子用 4 表示。 我刚才正在测试这个,
如果满足条件,同一个玩家移动,您如何处理游戏? 我试过这样的东西,但我觉得不太对: function negamax(node, depth, α, β, color) if node is
我已经实现了 Negamax,因为它可以在 wikipedia 上找到,其中包括 alpha/beta 剪枝。 但是,它似乎倾向于失败的一步,据我所知这是无效的结果。 这款游戏是井字游戏,我已经抽象了
这段代码是为计算井字游戏中某个位置的最佳移动而构建的。我几乎得到了代码的每一部分,除了 for 循环中的条件,它表示 minRating != LOSING_POSITION。此代码来自给定伪代码的实
注意:如果您认为这篇文章对您没有足够的详细信息(例如,代码,结果和其他内容;我将相应地编辑帖子。 注意2:我自己编写了这个程序。 我有一个negamax实现,其结果对我来说似乎是非常错误的,我尝试了许
嗨! 我正在尝试为我的国际象棋引擎编写一个 negamax 搜索算法,但我似乎无法让它工作。我以 wikipedias 伪代码为例,但不知何故它没有产生预期的结果。当我用 2 层运行它时,它改变了我的
我一直在使用 negamax 玩连连四。我注意到的是,如果我添加 alpha-beta,它有时会给出“错误”的结果,因为在进行失败操作时,我认为它不应该与我正在搜索的深度相匹配。如果我删除 alpha
我正在上我的第一个 AI 类(class),并尝试在我的 c 代码中实现 NegaMax 算法。我正在使用这个算法来玩简单的 Nim 游戏,每个玩家在轮到他们时移除 1-3 个匹配项。计算机在这里与自
好吧,我先承认这个会有点长。我正在为 C# 编写国际象棋引擎,最终目标包括 UCI 实现。我已经做到了,给定一个棋盘,引擎将生成所有有效 Action 的列表;然而,我的评估代码似乎很挣扎,因为在与自
我对 Negamax 算法以及如何在实际案例中应用它有点困惑。在网上我找到了以下 C/C++ 代码(引用:https://chessprogramming.wikispaces.com/Unmake+
我是游戏树算法的新手,我尝试实现一个简单的井字棋游戏,该游戏利用 NegaMax 算法为计算机 AI 玩家评估拼贴分数。然而,AI 的行为并不聪明(我可以一直赢,因为 AI 不会阻止我的 Action
我为黑白棋游戏编写了 AI 播放器,我决定使用 NegaMax 或 MiniMax 来实现。伪代码: function negamax(node, depth, α, β, color) if
Negamax 通常如下所示: function negamax(node, depth, α, β, color) is if depth = 0 or node is a terminal
我正在尝试为 tic-tac-toe 应用程序实现 negamax 搜索函数,但它不会返回最佳值,而是似乎半随机猜测。这是我的代码的相关部分: public int negamax(Result re
我无法识别 negamax(alpha - beta)实现中的错误。 我可以使简单的 negamax 版本正常工作,但是我无法将其转换为 negaMax 的 alpha-beta 版本。 首先是正在运
我的程序中有一个有效的 negamax 算法。但是,我需要程序在 kMaxTimePerMove 时间内找到最佳可能的着法。我做了一些研究,似乎使用迭代加深和我的 negamax 算法是最好的方法。现
我正在制作黑白棋玩家,并实现了一个带有 alpha-beta 剪枝的极小极大算法。然后我在网上对最好的算法进行了一系列研究,并不断听到他们都使用的“negamax”算法。似乎大多数人认为 negama
关于非递归、基于迭代的 negamax 算法的任何想法或伪代码? 我使用 negamax 作为我的国际象棋 AI 的搜索核心。 我的引擎是用 JavaScript 编写的,根据文献,如果使用迭代而不是
我正在尝试构建国际象棋 AI。我的带 alpha-beta 修剪 (ABP) 的 negamax 函数运行速度比单独的 min 和 max 函数也用 ABP 慢得多(大约 8 倍),尽管返回的移动是相
我是一名优秀的程序员,十分优秀!