使用AlphaBeta修剪改进此MiniMax的性能

Question

我有以下奥赛罗（reversi）游戏的阿尔法-贝塔极小值的实现。我已经修复了这个线程中的一些问题。这一次我想改进这个函数的性能。MAX_DEPTH=8需要很长的时间。在保持AI有点体面的同时，可以做些什么来加快性能？

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) {
        return mm_out(A, G.get_utility(pn));
    }

    // add end game score total here

    set<Action> succ_temp = G.get_successors(pn);
    for (Action a : succ_temp) {
        Grid gt(G);
        a.evaluate(gt);
    }
    set<Action, action_greater> successors(succ_temp.begin(), succ_temp.end());

    // 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;
                }
                if (alpha >= beta) {
                    return mm_out(A, beta);
                }
            }
            else {
                if (beta > temp) {
                    beta = temp;
                    A = *a;
                }
                if (alpha >= beta) {
                    return mm_out(A, alpha);
                }


}
    }
    return mm_out(A, (stage == MINIMAX_MAX) ? alpha : beta);
}
else {
    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

有几种方法可以加快搜索功能的性能。如果您正确地实现这些技术，那么在修剪许多节点时，它们对算法的准确性几乎不会造成任何损害。

>

您可以实现的第一种技术是换位表。转置表将游戏搜索树中所有先前访问的节点存储在哈希表中。大多数游戏状态，尤其是在深度搜索中，可以通过各种换位或移动顺序到达，从而产生相同的最终状态。通过存储先前搜索到的游戏状态，如果您发现已经搜索到的状态，则可以使用表中存储的数据，并停止在该节点深化搜索。在哈希表中存储游戏状态的标准技术称为Zobrist哈希。有关换位表实施的详细信息可在网上查阅

您的程序应该包括的第二件事是移动排序。这本质上意味着检查移动不是按照你生成移动的顺序，而是按照看起来最有可能产生阿尔法-贝塔截止的顺序（即先检查好的移动）。显然，你不知道哪些动作是最好的，但大多数动作都可以使用简单的技巧来排序。例如，在《奥赛罗》中，应该首先检查在角落或边缘的移动。命令移动应该会导致更多的截止和搜索速度的提高。这对精度造成零损失。

您还可以添加开场书。通常，开局动作需要最长的时间来搜索，因为棋盘上充满了更多的可能性。开场白是一个数据库，它存储了前几圈可能做出的每一个动作，以及对它的最佳反应。，在《奥赛罗》中，分支因子很低，这将在开场比赛中特别有用