如何利用Minimax Algorithem.andαBeta剪枝解决Tic Tac Toe 4x4游戏

Question

我制作了一个Tic Tac脚趾游戏，使用Minimax和Alpha Beta剪枝。我想为Tic (10x10)制作一个电脑人工智能，但它的游戏树的大小却是惊人的大。

我的代码是这样的，我只需要改变两个变量来改变板的大小+连续需要的单元格才能获胜。示例：

boardSize = 3 // This is for 3x3 tic tac toe

boardSize = 4 // This is for 4x4 tic tac toe

boardSize = 10 // This is for 10x10 tic tac toe

和

winStreak = 3 // Need to make 3 cells in a row to win

winStreak = 4 // Need to make 4 cells in a row to win

我希望你能搞定。

所以，我改变了让Tic脚趾从10x10变成3x3的计划，效果很好。

然后，我改变了boardSize = 4和winStreak = 3，使它成为(4x4)抽搐脚趾游戏。

现在，我认为Minimax与Alpha Beta剪枝将足以解决4x4，但惊讶地看到，它不是。

当我第一次移动(人类)时，minimax算法搜索5-10分钟，然后浏览器选项卡崩溃。它连第一步也做不到。

我怎么能提高它的速度？人们甚至可以使用Minimax + Alpha Beta剪枝来解决国际象棋，但是我的代码有什么问题呢？

我的完整代码大约是200-300行，所以我只写伪代码.

humanMakeMove();

Minimax(); // Bot calls Minimax function to make a move

function Minimax(board, player) {
if (checkResult() != 0) // 0 = Game is on
   return checkResult(); // 1 = Win, 0.5 = Draw, -1 = Lose   

   availableMoves = getAvailableMoves();

   for(i = 0; i < availableMoves.length;i++)
   {
        move = availableMoves[i]; 
        removeMoveFromAvailableMovesArray(move);
        if (player == "X")
            score = Minimax(board, "O");
        else
            score = Minimax(board, "X");
        board[i] = "-"; // "-" means empty space


        if (depth of tree is on first level && score == 1)
                return maxScore; //Alpha Beta Pruning is applied here, if we get score of 1, then we don't need to search more. 


   }
}

我还可以应用什么优化来使代码运行得更快？

Answer 1

有几种可能提高您的程序的性能。

1. 评估函数。，似乎目前您只在到达终端游戏节点时应用评估函数。在3x3、toe这样的游戏中，由于搜索树很小，并且可以在短时间内从开始位置到达叶节点，这是一种合理的方法。但在更大的棋盘上玩的游戏(如国际象棋、围棋等)除非到达终端节点，否则无法恢复(这将花费太多的时间)。因此，您需要确定要停止的递归深度，并根据游戏的战术/战略原则尝试评估当前的位置。为了做到这一点，您需要编写一个启发式的评估函数，这将给您的职位价值。然后，可以将此值传播到搜索树上，以确定最佳移动。整个程序的质量在很大程度上取决于eval函数的质量。
2. 移动排序。在生成所有有效移动的列表之后，根据计算函数对它们进行降序排序。这样，该算法将首先考虑好的移动，这更有可能产生高的α-β袖口，导致更多的节点被修剪。
3. 迭代深化与主变差搜索，不再对一定深度的极小极大函数进行初始调用，而是尝试先用深度1，然后2，3，…(每次移动截止时间到达时停止)。存储使用minimax表示深度k的最佳移动，并将其用作深度k + 1的minimax中的第一个候选项。此外，您不仅可以存储最佳移动，还可以存储整个最佳移动序列，这称为主变化。因此，在找到深度k的主变化后，将其提供给深度k + 1上的极小值调用，它通常会产生许多良好的α-β袖口。
4. 的开本书。如果你知道第一对(甚至几十个)的好动作是什么，你可以在开本书中硬编码它们。因此，当您的程序面临一个职位从开本，它将立即检索最好的答案。一本开篇书的一个简单的例子是硬编码第一步移动到中央广场为3乘3抽搐-tic脚趾游戏。这样，您的程序将花费零秒来找到第一步。
5. 转位表。试图重用在搜索位置X时发现的最佳移动，以确定另一个与X对称的位置Y的最佳移动(这意味着Y可以通过旋转/反射从X获得)。在棋盘游戏编程中实现转位表的一种常见的高级技术称为Zobrist散列。
6. 并行算法。试图将您的算法并行，使其在具有多个核的机器上运行得更快。
7. 编程语言.由于您的问题被标记为Javascript标记，所以我假设您正在使用这种语言来实现算法。就性能而言，Javascript并不是最好的语言。因此，如果您熟悉C、C++或Java等语言，那么在其中一种语言中重写程序可以极大地提高性能。

最后，你的话

人们甚至可以用Minimax + Alpha Beta剪枝来解决国际象棋

严格地说不是真的，因为下棋还没有解决。但是有一些国际象棋程序可以轻松击败人类玩家(使用极小值和α-β剪枝以及许多其他更先进的技术)。所以，这个节目可以击败专家球员和世界冠军并不意味着它打得很完美。