使用Alpha迭代深化Negamax
我的程序中有一个有效的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）上的每个迭代来解决此问题。 您也可以使用希望窗口来限制alpha-beta范围。
请注意，由于您没有使用先前的迭代来改进下一次迭代的移动排序，所以迭代加深会导致稍差的结果。 理想情况下，您需要移动排序以从换位表和/或前一次迭代的主要变化中选择最佳移动。
链接地址: http://www.djcxy.com/p/56395.html