Minimax 算法 - 当我有两种获胜方式时，计算机不会阻止我。

Question

在我的 minimax 算法中，当计算机出现一个有两种方法来赢得计算机的玩家时，他只会选择棋盘上的第一个空位。以下面为例。X 可以在位置 0,2 和位置 1,0 中获胜。

X |   |   

__________

  | x |

__________

x | o | o

目前我的算法会将 o 放在 0,1 的位置。我相信它这样做是因为当 minimax 运行并将 o 放置在位置 0,1 并且因为这不是胜利时，它再次调用 minimax，这次是 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;

        }

我最初这样称呼 minimax

best = MiniMax(CopyArray(GameState), 0, false);

然后我将最好的与我以前的 Max 进行比较。如果最好是更大的我把这个动作保存为我的电脑的动作。

Answer 1

处理第一个可用移动选择问题的一种简单方法是在迭代之前对有效移动进行排序。考虑您在问题中描述的立场：X&nbsp;.&nbsp;. .&nbsp;X&nbsp;. X&nbsp;O&nbsp;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).&nbsp;我们知道，鉴于完美的发挥，所有四个动作都是失败的动作。并且由于它们的分数相等（与损失值相同-10），第一个考虑的移动(0, 2)不会被下一个覆盖。这将使程序的移动“更加智能”，因为它现在尊重由移动创建/阻止的威胁（并且人类在玩井字棋时经常使用威胁考虑）。您可以通过使用不同的评估函数对有效动作进行排序来强制访问有效动作的不同顺序。另请注意，当与 alpha-beta 修剪结合使用时，移动排序对于增加搜索深度非常有用，因为它允许首先考虑好的有效移动并增加修剪更多节点的机会。尽管 alpha-beta 修剪对于这样一个简单的游戏来说可能是一种矫枉过正，但它对于更复杂的游戏确实很有用。

Answer 2

这是一种方法。如果多个可能的移动之间存在平局，请计算expectimax，即与随机游戏的对手相比，为您提供最高可能分数的移动。这将导致您阻止其中一种获胜方式，希望另一种方式看不到最佳可用棋步。