Minimax算法中的线程处理

Question

我正在设计一个3D的Tic-Tac-Toe游戏，并且发现时间是我的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定律和古斯塔夫森定律

你的问题看起来像一个!N的问题，它很快就会爆炸。您需要考虑更改代码，以显着地筛选选项的数量。

你似乎已经在用你的最小极大值算法来做游戏理论了。

一旦你在一棵树的深处为对方玩家找到了一个获胜的移动，你就不需要测试其他可能的移动，并且可以返回该部分树的胜利者。

Answer 2

您的解决方案不是多线程。试着去看看α-β修剪。朴素极大极小最终会发现很多冗余节点。

另外，我你的代码错了

 return score * player

一个完整的棋盘可能意味着平局，这意味着没有人赢：

oxo
oxx
xox

而这个位置是一场胜利，所以你必须返回一个分数，而不是探索愤怒：

xxx
 0 
 0 

Answer 3

对于Tac，在维基百科中有清楚的描述，有一个完美的策略。我已经在javascript游戏中实现了它，它很简单。没有线程，没有αβ剪枝，没有极小值，什么都没有.

完美的起点看不出前面的两步(阻挡对手的叉)，所以你可以(而且应该)现场使用它。

还要注意: tic的脚趾板是高度对称的，所以无论你用什么方法，有效移动的次数都可以大大减少。如果你看一下完美的策略，移动的数量会聚集在类中(“中心”、“相对角”、“空角”、“空边”等等)。