MiniMax搜索递归不正确

Question

我正在尝试写一个AI来玩ConnectK (一个连接4的游戏，需要连接k个棋子，重力可以开或关)。这是我的函数，使用Minimax算法获得最佳移动。

struct MoveNode //This struct is defined in header file
{
    MoveNode() {};
    MoveNode(int Score) : score(Score) {}
    Move move;
    int score;
};

MoveNode AIShell::getBestMove(int depth, int player) {//Find the best move using MiniMax
    if (depth <= 0) 
        return MoveNode(heuristic());
    else if (boardIsFull() && getWinner() == 0)//Tie
        return 0;
    else if (getWinner() == AI_PIECE)
        return 100000;
    else if (getWinner() == HUMAN_PIECE)
        return -100000;

    std::vector<MoveNode> mds;

    for (auto i : getMoveList()) {//For each available move
        MoveNode md;
        md.move = i; //i is Move(col,row)
        gameState[i.col][i.row] = player;
        if (player == AI_PIECE) {
            md.score = getBestMove(depth - 1, HUMAN_PIECE).score;
        }
        else {
            md.score = getBestMove(depth - 1, AI_PIECE).score;
        }
        mds.push_back(md);
    }

    //Get the best move after recursion
    int best_move_index = 0;
    if (player == AI_PIECE) {
        int best_score = -1000000;
        for (int i = 0; i < mds.size(); i++) {
            if (mds[i].score > best_score) {
                best_move_index = i;
                best_score = mds[i].score;
            }
        }
    } else if (player == HUMAN_PIECE) {
        int best_score = 1000000;
        for (int i = 0; i < mds.size(); i++) {
            if (mds[i].score < best_score) {
                best_move_index = i;
                best_score = mds[i].score;
            }
        }
    }
    return mds[best_move_index];
} 

getBestMove()函数似乎做了一些我不太期望的事情。该函数将尝试在递归之前获得最佳移动，并且AI转弯和人类转弯并未以递归方式均匀处理。我花了相当多的时间调试这个函数，但仍然不能弄清楚。很抱歉我的英语很差，但我真的很感激在这里能帮上忙。提前谢谢。

Answer 1

您返回的是最佳移动索引。极小极大树必须返回节点值(best_score)，而不是最佳移动。您应该返回最佳移动的唯一时间是在根节点，这样搜索就会通过给出最佳移动而终止。