1

我在做什么:我正在用 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。等等。

我的问题:这是迭代深化应该起作用的方式吗?每次我们增加深度时,我们也搜索所有父节点?我想象每次我们增加深度时,它只会搜索新深度的所有兄弟节点。如果这实际上是迭代深化的工作方式,那么如何只搜索新的深度而不是搜索所有父节点呢?

每次我们增加深度时,我的迭代加深的极小极大值都将整个树搜索到给定深度: 在此处输入图像描述

我期望迭代加深的极小极大只在每次增加深度时才搜索新深度: 在此处输入图像描述

作为参考,这是我使用 alpha beta 剪枝的(草率的)极小极大函数:

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++ 开发人员,所以它可能很糟糕。

4

1 回答 1

1

这是迭代深化应该工作的方式吗?每次我们增加深度时,我们也搜索所有父节点?

是的 - 但由于您在进行迭代深化时保存了先前搜索的最佳移动,并且会在向下的过程中首先尝试这些移动,因此您通常会在每个级别的第一个移动中找到最佳移动,因此修剪将非常有效。

如何只搜索新的深度而不是搜索所有父节点?

如果这就是你想要的,你可以放弃迭代深化,只搜索你想要的深度——但这可能是一个错误。在寻求该解决方案之前,计算您拥有和没有迭代深化的评估板的数量。

于 2020-10-19T17:46:56.540 回答