Minimax算法中的线程化-Java 学习之路

我正在设计一个3D Tic-Tac-Toe游戏，并且找时间限制我的Minimax算法的深度 . 虽然高达6的深度在很大程度上是无关紧要的（<1s），但对于更高的深度，它确实需要时间 .

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

我没有时间（哈！）检查更高的深度 . 最大深度为22，这将让我的AI分析Move 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有多少物理内核相关联？

3 回答

0

首先考虑你可以加速8核系统的速度......这是8倍（除非你的问题是内存限制，在这种情况下，你可以得到更好的） . 阅读Amdahl's law和Gustafson's law

你的问题看起来像是一个问题，它会及时爆炸 . 您需要考虑更改代码以显着剔除选项数量 .

你已经开始使用你的minmax算法进行博弈论 .

一旦你在树的一个深度找到了对方玩家的胜利动作，你就不需要测试剩下的可能移动并且可以返回该部分树的获胜者 .

回复于 2024-04-26T08:24:16+08:00
0
您的解决方案不是多线程 . 试着调查Alpha–beta pruning . 天真的极小极大最终探索了许多冗余节点 .

另外，我的代码错了
```
return score * player
```
全板可能意味着平局，这意味着没有人赢了：
```
oxo
oxx
xox
```
虽然这个位置是一个胜利，所以你必须返回一个分数而不是探索一个分数：
```
xxx
 0 
 0
```
回复于 2024-04-26T08:24:16+08:00
1

Tic Tac Toe有一个完美的策略，clearly described in Wikipedia . 我在javascript游戏中实现了它很容易 . 没有线程，没有alpha beta修剪，没有minimax，没有......

完美的startegy看起来不会超过前面的两个步骤（阻止对手前叉），所以你可以（并且应该）使用它 .

另请注意：tic tac toe的板是高度对称的，因此无论使用何种方法，有效移动的数量都可以大大减少 . 如果你看一下完美的策略，移动的数量会聚集在类中（"Center"，"Opposite corner"，"Empty Corner"，"Empty Side"等等） .

回复于 2024-04-26T08:24:16+08:00

Minimax算法中的线程化

3 回答

相关问题