我用Minimax和Alpha Beta修剪制作了一个Tic Tac Toe游戏。我想为Tic-Tac-Toe(10x10)游戏制作一个计算机AI，但它的游戏树大小大得离谱。
我的代码是这样的，我只需要改变两个变量来改变棋盘尺寸+连续获胜所需的单元格。示例：
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-Tac Toe的计划，从10x10改为3x3，效果很好。
然后我改变了boardSize = 4和winStreak = 3，使其成为(4x4)井字游戏。
现在，我认为使用阿尔法-贝塔修剪的Minimax足以解决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.
}
}
我还可以应用哪些优化来使代码运行得更快？
有几种方法可以提高程序的性能。
- 评估函数目前似乎只有当您到达终端游戏节点时才应用评估功能。在像3x3井字游戏这样的游戏中，这是一种合理的方法，因为搜索树很小，并且可以在短时间内从起始位置到达叶节点。但对于在较大的棋盘上进行的游戏(如国际象棋、围棋等)，在到达终端节点之前无法递归(这将花费太多时间)。因此，您需要决定停止哪种递归深度，并尝试根据游戏的战术/战略原则评估当前位置。为了做到这一点，你需要编写一个启发式评估函数，它将为你提供职位的价值。然后，您可以将该值向上传播到搜索树中，以确定最佳移动。整个程序的质量在很大程度上取决于eval函数的质量
- 移动排序生成所有有效移动的列表后，根据评估函数按降序对其进行排序。这样，算法将首先考虑好的移动，这些移动更有可能产生高的α-β截止，从而导致更多的节点被修剪
-
主变分搜索迭代深化与其初始调用具有固定深度的minimax函数，不如尝试先调用深度为1的函数，然后调用深度为2、3。。。(达到每次移动的时间截止值时停止)。存储用深度
k的极小值最大值找到的最佳移动，并将其用作深度k + 1的极小值极大值中的第一个候选移动。此外，你不仅可以存储最佳移动，还可以存储整个最佳移动序列，这被称为主变化。因此，在找到深度k的主要变化后，将其输入深度k + 1的minimax调用，它通常会产生很多好的α-β截止值 - 打开书本如果你知道前几圈(甚至几十圈)的好动作是什么，你可以在开场白中对它们进行硬编码。因此，当你的程序面对开篇中的一个位置时，它会立即检索到最佳答案。开场白的一个微不足道的例子是，先硬编码移动到中心广场，进行3乘3的井字游戏。这样，你的程序将花费零秒来找到第一步
- 换位表尝试重复使用在位置X的最小最大搜索过程中找到的最佳移动，以确定与X对称的另一个位置Y的最佳移动(意味着可以通过旋转/反射从X获得Y)。在棋盘游戏编程中实现换位表的一种常见的高级技术叫做Zobrist哈希
- 并行算法尝试并行化您的算法，使其在具有多核的机器上运行得更快
-
编程语言由于您的问题用
Javascript标记，我假设您正在使用这种语言来实现算法。就性能而言，Javascript并不是最好的语言。因此，如果你熟悉C、C++或Java等语言，用其中一种语言重写程序可以大大提高性能
最后，你的短语
人们甚至可以使用Minimax+Alpha-Beta修剪解决国际象棋问题
严格来说不是真的，因为国际象棋还不是一个解决问题的游戏。但也有一些国际象棋程序可以轻松击败人类棋手(使用极小极大值和阿尔法-贝塔修剪以及许多其他更先进的技术)。所以，事实上，该程序可以击败专家球员和世界冠军，并不意味着它发挥完美。