c++ - 使用 minimax 算法，我如何访问返回最佳值的节点以便可以使用它？

Question

我目前正在完成一份 uni 论文的作业。我正在为跳棋游戏制作 AI。我了解极小极大算法的原理，但是，在实现它时，我很难了解如何以最佳移动方式访问节点，以便实现它。可能是我错误地实现了代码，这让我陷入了这种境地。但是，据我所知，它只返回评估的最佳分数。然后如何获取将其返回给根的节点？

这是包含 minimax 函数的 GameTree 的代码。我希望能够使用在 GetNextMove() 中发送最佳分数的节点

#include "gametree.h"
//Constructor
GameTree::GameTree()
{

}

/* This function is part of the evalutaion of which move is best by looking for the best
 * score in the tree. which is set up by the nodes calling themselves via the Move::PosMove
 *  function. This function was used because it was taught in class and it enables pruning. 
 *  this function goes down the left side to the bottom of the tree first. Because the 
 *  children of each node are stored in a set the highest score is the first to be seen.
 *  this will enable maximum pruning, so will speed up the search for the best move.
 *  Called by Move::AiMove() */
int GameTree::minimax(Node *node, int depth, int alpha, int beta, bool isMaxNode)
{
    int Alpha = alpha;
    int Beta = beta;
    
    if (depth == 0|| endGame ==1)
    {
        nScore= node->score;
        return nScore;
    }
    if (isMaxNode)
    {
        int HighScore = -1000;
        for (int i =0; i< (int)node->children.size(); i++)
        {
            nScore= minimax(node, depth-1, Alpha, Beta, false);
            HighScore= max(HighScore,nScore);
            Alpha= max(Alpha, HighScore);
            if (beta<=alpha)
            {
                break;
            }
        }
        return Alpha;
    }

    else
    {
        int LowScore = 1000;
        for (int i =0; i< (int)node->children.size(); i++)
        {
            nScore= minimax(node,depth-1, Alpha, Beta, true);
            LowScore= min(LowScore,nScore);
            Beta= min(Beta, LowScore);
            if (beta<=alpha)
            {
                break;
            }
        }
        return Beta;
    }
}

/* This function serches for the best move based on teh minimax evaluation by looking at
 *  the children of the root node.
 *  Called By Move::AiMove() */
void GameTree::GetNextMove()
{
    nodeNext = *nodeRoot->children.begin();
    for (Node *n : nodeRoot->children)
    {
        if (n->score > nodeNext->score)
        {
            nodeNext = n;
        }
    }
    nodeNext->UpdateDisplay(4);
    return;

}

提前感谢您的帮助，我从该网站获得了很多帮助，而无需提出任何问题。希望你能再次帮助我。谢谢。

标签： c++minimax

Answer 1

由于您没有显示 AiMove()，因此很难正确回答。然而，一种基本方法是在 AiMove 中编写一个极小极大算法，该算法会在最佳分数被击败时捕获。

void AiMove(){
    //Make all the moves for the ROOT
    //Compute the alpha-beta value of all moves :
    int alpha = -INF, beta = INF;
    Node* nodeNext;
    for(Node* n : nodeRoot->children){
         int cur = minimax(n, depth-1, alpha, beta, false);
         n->score = cur; //Warning, not necessarily the real score for this node
         if(cur > alpha){ //Wow ! new high score
              alpha = cur;
              nodeNext = n; // here you go
         }
    }
    //GetNextMove(); //useless now
}

您的极小极大函数的一些更正：

int GameTree::minimax(Node *node, int depth, int alpha, int beta, bool isMaxNode)
{
    //int Alpha = alpha; No need of Alpha and Beta, alpha and beta are the very one used
    //int Beta = beta;

    if (depth == 0|| endGame ==1)
    {
        nScore= node->score;
        return nScore;
    }

    //Warning : you need to generate all children of node here only

    if (isMaxNode)
    {
        int HighScore = -1000;
        for (int i =0; i< (int)node->children.size(); i++)
        {
            nScore= minimax(node->children[i], depth-1, Alpha, Beta, false); //mistake here
            HighScore= max(HighScore,nScore);
            Alpha= max(Alpha, HighScore);
            if (beta<=alpha)  //mistake here : Alpha or alpha? use the varying variable in the function
            {
                break;
            }
        }
        return Alpha;
    }

    else
    {
        int LowScore = 1000;
        for (int i =0; i< (int)node->children.size(); i++)
        {
            nScore= minimax(node,depth-1, Alpha, Beta, true); //mistake here too
            LowScore= min(LowScore,nScore);
            Beta= min(Beta, LowScore);
            if (beta<=alpha) //Same here
            {
                break;
            }
        }
        return Beta;
    }
}

最后，为了提高效率，您不想使用 Node 结构，因为这样每个 Node 都保存在内存中，并且需要一些时间。一种更快的方法是直接在板上工作。这在 minimax 函数中看起来很像。将没有任何保存。

for each possible move:
    apply(move);
    minimax(depth-1, alpha, beta); //Recursively compute the minimax value
    //Do stuffs on alpha and beta
    undo(move);