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 and Gustafson's law

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

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

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

Answer 2

您的解决方案不是多线程。请尝试查看 Alpha–beta pruning。朴素的 minimax 最终探索了很多冗余节点。

此外，我的代码在

处有误

 return score * player

全场可能意味着平局，这意味着没有人赢：

oxo
oxx
xox

虽然这个位置是一个胜利，所以你必须 return 得分而不是进一步探索：

xxx
 0 
 0

Answer 3

Tic Tac Toe 有一个完美的策略，clearly described in Wikipedia。我已经在 javascript 游戏中实现了它，而且很简单。没有线程，没有 alpha beta 修剪，没有 minimax，什么都没有...

完美的 startegy 不会超过两步（阻止对手叉子），因此您可以（并且应该）实时使用它。

另请注意：井字棋的棋盘是高度对称的，因此无论您使用哪种方法，有效着法的数量都会大大减少。如果你看一下完美的策略，移动次数汇总在类 ("Center", "Opposite corner", "Empty Corner", "Empty Side", 等等...).

Minimax 算法中的线程

Threading within Minimax algorithm

c++

algorithm

multithreading

tic-tac-toe

minimax