MiniMax与阿尔法Beta修剪奥赛罗不工作

Question

我有以下奥赛罗（reversi）游戏的阿尔法-贝塔极小值的实现。不知怎的，这永远不会返回正确的行动。它似乎返回了我在函数（0，0）中设置的默认操作和第二个值-32768，这意味着它在MAX子例程中被删减了。关于我可以改进什么以及如何解决这个问题，有什么建议吗？

注意：我已经确定了大部分正确返回的继任者。目前的最大深度是8。电脑玩家的pn（玩家数量）是1，人类玩家的是0。第一阶段，0，是MINIMAX_MAX。阿尔法和贝塔最初分别设置为INT_MIN和INT_MAX。

mm_out minimax(Grid& G, int alpha, int beta, Action& A, uint pn, uint depth, bool stage) {
    if (G.check_terminal_state() || depth == MAX_DEPTH) {
#ifdef DEBUG
        cout << "best action: (" << A.get_x() << ", " << A.get_y() << ")\n";
#endif
        return mm_out(A, G.get_utility(pn));
    }

    // add end game score total here

#ifdef DEBUG
    if (stage == MINIMAX_MAX) {
        cout << "max " << alpha << " " << beta << "\n";
    }
    else {
        cout << "min " << alpha << " " << beta << "\n";
    }
#endif

    set<Action> succ_temp = G.get_successors(pn);
    for (Action a : succ_temp) {

#ifdef DEBUG
        cout << a.get_x() << " " << a.get_y() << '\n';
#endif

        Grid gt(G);
        a.evaluate(gt);
    }
    set<Action, action_greater> successors(succ_temp.begin(), succ_temp.end());

#ifdef DEBUG
    Player p(0, "minimaxtest");
    G.display(p);
    int test;
    cin >> test;
#endif

    // if no successor, that player passes
    if (successors.size()) {
        for (auto a = successors.begin(); a != successors.end(); ++a) {
            Grid gt(G);
            gt.do_move(pn, a->get_x(), a->get_y(), !PRINT_ERR);
            Action at = *a;
            mm_out mt = minimax(gt, alpha, beta, at, pn ^ 1, depth + 1, !stage);
            int temp = mt.val;
//          A = mt.best_move;

            if (stage == MINIMAX_MAX) {
                if (alpha < temp) {
                    alpha = temp;
                    A = *a;
#ifdef DEBUG
                    cout << "Current action: (" << A.get_x() << ", " << A.get_y() << ") alpha = " << alpha << "\n";
#endif
                }
                if (alpha >= beta) {
#ifdef DEBUG
                    cout << "pruned at max\n";
#endif
                    return mm_out(A, beta);
                }
            }
            else {
                if (beta > temp) {
                    beta = temp;
                    A = *a;
#ifdef DEBUG
                    cout << "Current action: (" << A.get_x() << ", " << A.get_y() << ") beta = " << beta << "\n";
#endif
                }
                if (alpha >= beta) {
#ifdef DEBUG
                    cout << "pruned at min\n";
#endif
                    return mm_out(A, alpha);
                }


}
    }
    return mm_out(A, (stage == MINIMAX_MAX) ? alpha : beta);
}
else {
    cout << "no successor\n";
    return mm_out(A, (stage == MINIMAX_MAX) ? (std::numeric_limits<int>::max() - 1) : (std::numeric_limits<int>::min() + 1));
}

}

实用功能：

int Grid::get_utility(uint pnum) const {
    if (pnum)
        return wcount - bcount;
    return bcount - wcount;
}

Answer 1

您应该按值传递alpha/beta参数（而不是通过引用）：

mm_out minimax(Grid& G, int alpha, int beta, Action& A, uint pn, uint depth, bool stage)

每个节点都将alpha和beta值传递给其子节点。然后，子节点根据轮到谁更新自己的alpha或beta值副本，并返回该节点的最终评估。然后用于更新父级的alpha或beta值。