c++ - Minimax 算法中的线程

Question

我正在设计一款 3D 井字棋游戏，发现时间限制了我的 Minimax 算法的深度。虽然深度达到 6 在很大程度上是无关紧要的时间 (<1s)，但对于更高的深度，它确实需要时间。

>Depth 7 = 6 seconds
>Depth 8 = 49 seconds
>Depth 9 = 314 seconds

我没有时间(哈!)检查更高的深度。最大深度为 22，这将使我的 AI 分析第 1 步的所有可能的游戏状态，并且永远不会导致用户获胜。

我想在我的 Minimax 函数中实现线程化，但我对线程化还比较陌生。我的 Minimax 函数如下所示:

//player is -1 for human, +1 for AI
function minimax(board_state, depth, player)
    if depth <= 0 or board == full //full board means no further states
        return score * player
    bestScore = -1000;
    foreach possible move
        if valid move
            /* */
            make_move()
            bestScore = max(bestScore, minimax(board_state, depth-1, -player)
            undo_move()
            /* */
    return bestScore

我希望 /* */ 之间的位是新线程，但出现了一个问题:即使 depth = 1，也有 8 个线程。对于 depth = 8，这是 16534863 个线程。线程有什么限制？它与我的 CPU 有多少物理内核有关吗？

Answer 1

首先考虑在 8 核系统上可以加速多少……也就是 8 倍(除非你的问题是内存限制，在这种情况下你可以稍微好一点)。继续阅读 Amdahl's law和 Gustafson's law

你的问题看起来像一个 !N 问题，它会及时爆炸。您需要考虑更改代码以显着减少选项数量。

您的 minmax 算法似乎已经走上了博弈论的道路。

一旦您在树的一个深度找到了对面玩家的获胜着法，您就无需测试其余可能的着法并可以返回该部分树的获胜者。