c++ - 使用 Alpha Beta 剪枝提高此 MiniMax 的性能

Question

我有以下用于黑白棋游戏的 alpha beta minimax 实现。我已经修复了 this 中的一些问题线。这次我想提高这个功能的性能。 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 哈希。有关转换表实现的详细信息可在网上找到。

• 您的程序应该包括的第二件事是移动顺序。这实际上意味着不是按照您生成它们的顺序检查移动，而是按照看起来最有可能产生 alpha beta 截止值的顺序(即首先是好的移动).显然，您无法知道哪些 Action 是最好的，但大多数 Action 都可以使用一种简单的技术来排序。例如，在黑白棋中，应首先检查位于角落或边缘的棋步。排序移动应该导致更多的中断和搜索速度的增加。这对准确性造成零损失。

• 您还可以添加开篇书籍。通常开局需要最长的时间来搜索，因为棋盘上充满了更多的可能性。开局书是一个数据库，它存储了前几回合可以采取的每一个可能的行动，以及对它的最佳 react 。，在奥赛罗, 分支因子低，这对开局特别有帮助

• Procut。我不打算在这里详细介绍，因为这是一种更高级的技术。然而它在 othello 上取得了很好的效果，所以我想我会发布这个链接。 https://chessprogramming.wikispaces.com/ProbCut