在我的最小最大值算法中，当计算机呈现玩家有两种赢得计算机的方式时，将只选择棋盘的第一个未平仓位置。下面以为例。X 可以在位置 0,2 和位置 1,0 中获胜。
X | |
__________
| x |
__________
x | o | o
目前我的算法会将 o 放在位置 0,1。我相信它这样做是因为当最小最大值运行并将 o 放在位置 0,1 并且因为这不是胜利，它再次调用最小最大值，这次是 x.X 然后在位置 0,2 移动以获胜。对于此位置，这将返回 -10。如果计算机在位置 0,2 移动，则调用 minimax，x 最终放置在位置 1,0，这也为此操作返回 -10。事实上，无论计算机将 o 放在哪里，-10 都会返回，因为无论玩家会赢什么。因为对于放置的每个位置 o，它返回 -10，所以计算机将 o 放置在第一个可用插槽中，该插槽为 0,1，因为 max 永远不会从第一个位置更新。 我希望它将 o 放在位置 1,0 或 0,2 只是为了表明它识别一个块。
我的算法如下。它适用于 3x3x3，但概念是相同的。
public int MiniMax(int pGameState[][][], int Depth, boolean IsMax){
FunctionCalls++;
if(CheckForWin(2, pGameState)){ //Max Player (since the computer is always 2)
return 10 - Depth;
}
if(CheckForWin(1, pGameState)){ //Player will win therefore we return -10. If this is the first level of the tree
//then the value return is -10. If the second ply then the value returned is -8.
//It is more important for the computer to win sooner than later.
return -10 - Depth;
}
if(Depth >= 2){
return 0;
}
if(IsMax){
int Value = Integer.MIN_VALUE;
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
for(int k=0; k<3; k++){
if(pGameState[i][j][k] == 0){
pGameState[i][j][k] = 2;
int best = MiniMax(CopyArray(pGameState), Depth+1, !IsMax);
if(best > Value)
Value = best;
pGameState[i][j][k] = 0;
}
}
}
}
return Value;
}
else{
int Value = Integer.MAX_VALUE;
for(int i=0; i<3; i++){
for(int j=0; j<3; j++){
for(int k=0; k<3; k++){
if(pGameState[i][j][k] == 0){
pGameState[i][j][k] = 1;
int best = MiniMax(CopyArray(pGameState), Depth+1, !IsMax);
if(best < Value)
Value = best;
pGameState[i][j][k] = 0;
}
}
}
}
return Value;
}
}
我最初这样称呼最小最大值
best = MiniMax(CopyArray(GameState), 0, false);
然后，我将最好的比较与我以前的Max进行比较。如果最好更大，我会将此移动保存为计算机的移动。
处理第一个可用移动选择问题的一种简单方法是在迭代有效移动之前对它们进行排序。考虑您在问题中描述的位置：
X . .
. X .
X O O
在这里O是移动。在以默认方式(从左到右从上到下(迭代棋盘之前，请根据每个移动的好坏对四个有效((0, 1), (0, 2), (1, 0), (1, 2))移动的向量进行排序。一种方法是使用评估功能，该功能将计算在潜在移动后双方有多少威胁。对P块(可以是X或O(的威胁是具有一个空正方形和两个P正方形的行、列或对角线(因此它距离成为获胜线还有P(。让我们看看这个 eval 函数会告诉我们给定位置的四个有效移动中的每一个。我们计算两个部分的威胁数量，并分配定位值S等于差O_threats - X_threats。
如果O做出(0, 1)动作，则O_threats = 0，X_threats = 2，因此分数S = 0 - 2 = -2。
如果O做出(0, 2)动作，那么O_threats = 1，X_threats = 1，所以分数S = 1 - 1 = 0。
如果O做出(1, 0)动作，则O_threats = 0、X_threats = 1，因此分数S = 0 - 1 = -1。
如果O做出(1, 2)动作，则O_threats = 1，X_threats = 2，因此分数S = 1 - 2 = -1。
根据计算出的分数，访问有效移动的顺序应如下：(0, 2), (1, 0), (1, 2), (0, 1)。我们知道，如果打得完美，所有四个动作都是失败的。由于它们的分数相等(与损失值-10(，第一个考虑的移动(0, 2)不会被下一个移动覆盖。这将使程序的动作"更智能"，因为它现在尊重由移动创建/阻止的威胁(并且人类在玩井字游戏时经常使用威胁考虑因素(。您可以通过使用不同的评估函数对有效移动进行排序来强制执行访问有效移动的不同顺序。
另请注意，当与 alpha-beta 修剪结合使用时，移动排序对于增加搜索深度非常有用，因为它允许首先考虑良好的有效移动并增加修剪更多节点的机会。尽管对于如此简单的游戏来说，alpha-beta 修剪可能有点矫枉过正，但它对于更复杂的游戏非常有用。
这里有一种方法。
如果多个可能的动作之间存在联系，请计算期望最大值，该动作使您与随机玩的对手相比获得最高可能分数。
这将导致您阻止其中一种获胜方式，希望另一种方式看不到最佳可用动作。