使用迭代深化实现 Minimax 搜索
Implementing Minimax search with Iterative Deepening
我在做什么:我正在用 C++ 编写国际象棋引擎。我最近更新了我的引擎的 minimax 搜索算法,该算法使用 alpha-beta 修剪来利用迭代加深,以便它可以在时间限制下播放。这是它的样子:
//I return a string, int pair. The string represents the best move found, while the int represents the engine evaluation for the node after said move is made
static std::pair<string, int> iterativeDeepeningSearch(Board initialPosition, int maxDepth, milliseconds maxSearchTime)
{
std::pair<string, int> bestMove;
milliseconds startTime = duration_cast<milliseconds>(
system_clock::now().time_since_epoch());
for (int currentDepth = 1; currentDepth <= maxDepth; currentDepth++)
{
milliseconds currentTime = duration_cast<milliseconds>(
system_clock::now().time_since_epoch());
if (currentTime > startTime + maxSearchTime)
{
return bestMove;
}
std::pair<string, int> bestMoveFoundFromMinimax = minimax(initialPosition, currentDepth, INT_MIN, INT_MAX, "", "", startTime + maxSearchTime);
if (bestMoveFoundFromMinimax.first != "") {
bestMove = bestMoveFoundFromMinimax;
}
}
return bestMove;
}
我的问题:这个实现的问题是,当搜索任何大于 1 的深度时,它会在搜索所需深度之前搜索所有先前的深度。也就是说,这个迭代加深搜索首先搜索深度 1 的所有移动。然后,在下一次搜索时不再选择深度 2,而是再次搜索深度 1 ,然后搜索深度 2 .然后它会搜索深度1和2,然后搜索深度3。依此类推。
我的问题:这是迭代深化的工作方式吗?每次我们增加深度时,我们也搜索所有父节点?我想象每次我们增加深度时,它只会搜索新深度的所有兄弟节点。如果这实际上是迭代加深的工作方式,那么如何只搜索新深度而不是搜索所有父节点?
每次我们增加深度时,我的迭代加深的 minimax 都会搜索整棵树到给定的深度:
我希望迭代加深的 minimax 每次增加深度时只搜索新的深度:
作为参考,这是我使用 alpha beta 修剪的(草率的)minimax 函数:
static std::pair<string, int> minimax(Board node, int depth, int alpha, int beta, string move, string firstMove, milliseconds breakOffTime)
{
if (breakOffTime != std::chrono::milliseconds(0))
{
milliseconds currentTime = duration_cast<milliseconds>(
system_clock::now().time_since_epoch());
if (currentTime > breakOffTime)
{
return std::make_pair("", 0);
}
}
Moves &moves = Moves::getInstance();
if (moves.isCheckmate(node))
{
if (node.getWhiteToMove())
{
return std::make_pair(firstMove, INT_MIN);
}
else
{
return std::make_pair(firstMove, INT_MAX);
}
}
if (depth == 0)
{
return std::make_pair(firstMove, Rating::getCentipawnValue(node));
}
if (node.getWhiteToMove())
{
string bestMove = firstMove;
int bestValue = INT_MIN;
string pseudoLegalMoves = moves.pseudoLegalMovesW(node);
if (pseudoLegalMoves.length() == 0)
{
return std::make_pair(firstMove, 0);
}
for (int i = 0; i < pseudoLegalMoves.length(); i += 4)
{
string individualMoveString;
individualMoveString += pseudoLegalMoves[i];
individualMoveString += pseudoLegalMoves[i + 1];
individualMoveString += pseudoLegalMoves[i + 2];
individualMoveString += pseudoLegalMoves[i + 3];
Board tNode = moves.makeMoveAll(node, individualMoveString);
if ((moves.unsafeForWhite(tNode) & tNode.getWK()) == 0)
{
std::pair<string, int> ab;
if (firstMove == "")
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, individualMoveString, breakOffTime);
}
else
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, firstMove, breakOffTime);
}
int val = ab.second;
string move = ab.first;
if (val > bestValue || (val == bestValue && bestMove == ""))
{
bestValue = val;
bestMove = move;
}
alpha = max(alpha, bestValue);
if (alpha >= beta)
{
break;
}
}
}
return std::make_pair(bestMove, bestValue);
}
else
{
string bestMove = firstMove;
int bestValue = INT_MAX;
string pseudoLegalMoves = moves.pseudoLegalMovesB(node);
if (pseudoLegalMoves.length() == 0)
{
return std::make_pair(firstMove, 0);
}
for (int i = 0; i < pseudoLegalMoves.length(); i += 4)
{
string individualMoveString;
individualMoveString += pseudoLegalMoves[i];
individualMoveString += pseudoLegalMoves[i + 1];
individualMoveString += pseudoLegalMoves[i + 2];
individualMoveString += pseudoLegalMoves[i + 3];
Board tNode = moves.makeMoveAll(node, individualMoveString);
if ((moves.unsafeForBlack(tNode) & tNode.getBK()) == 0)
{
std::pair<string, int> ab;
if (firstMove == "")
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, individualMoveString, breakOffTime);
}
else
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, firstMove, breakOffTime);
}
int val = ab.second;
string move = ab.first;
if (val < bestValue || (val == bestValue && bestMove == ""))
{
bestValue = ab.second;
bestMove = ab.first;
}
beta = min(beta, bestValue);
if (alpha >= beta)
{
break;
}
}
}
return std::make_pair(bestMove, bestValue);
}
}
此外,如果有人有兴趣检查它,这是我的完整项目:https://github.com/ChopinDavid/Maestro-cpp
我不是 C++ 开发人员,所以它可能很烂。
Is this the way iterative deepening is supposed to work? Each time we increment depth, we search all parent nodes as well?
是 - 但由于您在进行迭代深化时保存了之前搜索中的最佳动作,并且会在下降过程中首先尝试这些动作,因此您通常会在每个级别的第一个动作中找到最佳动作,因此修剪会非常有效。
how would one go about only searching the new depth rather than searching all parent nodes as well?
如果那是您想要的,您可以放弃迭代加深,只进行一次搜索到您想要的深度 - 但这可能是一个错误。在寻求该解决方案之前,计算您有和没有迭代深化的评估板的数量。
我在做什么:我正在用 C++ 编写国际象棋引擎。我最近更新了我的引擎的 minimax 搜索算法,该算法使用 alpha-beta 修剪来利用迭代加深,以便它可以在时间限制下播放。这是它的样子:
//I return a string, int pair. The string represents the best move found, while the int represents the engine evaluation for the node after said move is made
static std::pair<string, int> iterativeDeepeningSearch(Board initialPosition, int maxDepth, milliseconds maxSearchTime)
{
std::pair<string, int> bestMove;
milliseconds startTime = duration_cast<milliseconds>(
system_clock::now().time_since_epoch());
for (int currentDepth = 1; currentDepth <= maxDepth; currentDepth++)
{
milliseconds currentTime = duration_cast<milliseconds>(
system_clock::now().time_since_epoch());
if (currentTime > startTime + maxSearchTime)
{
return bestMove;
}
std::pair<string, int> bestMoveFoundFromMinimax = minimax(initialPosition, currentDepth, INT_MIN, INT_MAX, "", "", startTime + maxSearchTime);
if (bestMoveFoundFromMinimax.first != "") {
bestMove = bestMoveFoundFromMinimax;
}
}
return bestMove;
}
我的问题:这个实现的问题是,当搜索任何大于 1 的深度时,它会在搜索所需深度之前搜索所有先前的深度。也就是说,这个迭代加深搜索首先搜索深度 1 的所有移动。然后,在下一次搜索时不再选择深度 2,而是再次搜索深度 1 ,然后搜索深度 2 .然后它会搜索深度1和2,然后搜索深度3。依此类推。
我的问题:这是迭代深化的工作方式吗?每次我们增加深度时,我们也搜索所有父节点?我想象每次我们增加深度时,它只会搜索新深度的所有兄弟节点。如果这实际上是迭代加深的工作方式,那么如何只搜索新深度而不是搜索所有父节点?
每次我们增加深度时,我的迭代加深的 minimax 都会搜索整棵树到给定的深度:
我希望迭代加深的 minimax 每次增加深度时只搜索新的深度:
作为参考,这是我使用 alpha beta 修剪的(草率的)minimax 函数:
static std::pair<string, int> minimax(Board node, int depth, int alpha, int beta, string move, string firstMove, milliseconds breakOffTime)
{
if (breakOffTime != std::chrono::milliseconds(0))
{
milliseconds currentTime = duration_cast<milliseconds>(
system_clock::now().time_since_epoch());
if (currentTime > breakOffTime)
{
return std::make_pair("", 0);
}
}
Moves &moves = Moves::getInstance();
if (moves.isCheckmate(node))
{
if (node.getWhiteToMove())
{
return std::make_pair(firstMove, INT_MIN);
}
else
{
return std::make_pair(firstMove, INT_MAX);
}
}
if (depth == 0)
{
return std::make_pair(firstMove, Rating::getCentipawnValue(node));
}
if (node.getWhiteToMove())
{
string bestMove = firstMove;
int bestValue = INT_MIN;
string pseudoLegalMoves = moves.pseudoLegalMovesW(node);
if (pseudoLegalMoves.length() == 0)
{
return std::make_pair(firstMove, 0);
}
for (int i = 0; i < pseudoLegalMoves.length(); i += 4)
{
string individualMoveString;
individualMoveString += pseudoLegalMoves[i];
individualMoveString += pseudoLegalMoves[i + 1];
individualMoveString += pseudoLegalMoves[i + 2];
individualMoveString += pseudoLegalMoves[i + 3];
Board tNode = moves.makeMoveAll(node, individualMoveString);
if ((moves.unsafeForWhite(tNode) & tNode.getWK()) == 0)
{
std::pair<string, int> ab;
if (firstMove == "")
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, individualMoveString, breakOffTime);
}
else
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, firstMove, breakOffTime);
}
int val = ab.second;
string move = ab.first;
if (val > bestValue || (val == bestValue && bestMove == ""))
{
bestValue = val;
bestMove = move;
}
alpha = max(alpha, bestValue);
if (alpha >= beta)
{
break;
}
}
}
return std::make_pair(bestMove, bestValue);
}
else
{
string bestMove = firstMove;
int bestValue = INT_MAX;
string pseudoLegalMoves = moves.pseudoLegalMovesB(node);
if (pseudoLegalMoves.length() == 0)
{
return std::make_pair(firstMove, 0);
}
for (int i = 0; i < pseudoLegalMoves.length(); i += 4)
{
string individualMoveString;
individualMoveString += pseudoLegalMoves[i];
individualMoveString += pseudoLegalMoves[i + 1];
individualMoveString += pseudoLegalMoves[i + 2];
individualMoveString += pseudoLegalMoves[i + 3];
Board tNode = moves.makeMoveAll(node, individualMoveString);
if ((moves.unsafeForBlack(tNode) & tNode.getBK()) == 0)
{
std::pair<string, int> ab;
if (firstMove == "")
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, individualMoveString, breakOffTime);
}
else
{
ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, firstMove, breakOffTime);
}
int val = ab.second;
string move = ab.first;
if (val < bestValue || (val == bestValue && bestMove == ""))
{
bestValue = ab.second;
bestMove = ab.first;
}
beta = min(beta, bestValue);
if (alpha >= beta)
{
break;
}
}
}
return std::make_pair(bestMove, bestValue);
}
}
此外,如果有人有兴趣检查它,这是我的完整项目:https://github.com/ChopinDavid/Maestro-cpp
我不是 C++ 开发人员,所以它可能很烂。
Is this the way iterative deepening is supposed to work? Each time we increment depth, we search all parent nodes as well?
是 - 但由于您在进行迭代深化时保存了之前搜索中的最佳动作,并且会在下降过程中首先尝试这些动作,因此您通常会在每个级别的第一个动作中找到最佳动作,因此修剪会非常有效。
how would one go about only searching the new depth rather than searching all parent nodes as well?
如果那是您想要的,您可以放弃迭代加深,只进行一次搜索到您想要的深度 - 但这可能是一个错误。在寻求该解决方案之前,计算您有和没有迭代深化的评估板的数量。