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

Question

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

X |   |   
__________
  | x |
__________
x | o | o

目前我的算法会将 o 放在位置 0,1。我相信它这样做是因为当 minimax 运行并在位置 0,1 放置一个 o 并且因为这不是胜利，它再次调用 minimax，这次是 x。 X 然后移动到位置 0,2 获胜。这个 returns -10 为这个位置。如果计算机在位置 0,2 移动，则调用 minimax 并且 x 最终被放置在位置 1,0，对于此移动也 returns a -10。事实上，无论计算机将 o 放在哪里，都会返回 -10，因为无论玩家将赢得什么。因为对于 o 放置的每个位置 returns -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;
        }
    }

我最初是这样调用minimax的

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

然后我将最好的与我以前的 Max 进行比较。如果 best 更大，我将此移动保存为我的计算机移动。

Answer 1

这是一种方法。

如果多个可能的走法相同，则计算 expectimax，即让您对随机下棋的对手可能得分最高的走法。

这将导致您阻止一种获胜方式，希望另一种方式看不到最佳可用移动方式。

Answer 2

处理第一个可用着法选择问题的一个简单方法是在迭代之前对有效着法进行排序。考虑您在问题中描述的位置：

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) 不会被下一个覆盖。这将使程序的移动 "more intelligent"，因为它现在尊重所做移动的威胁 created/blocked（人类在玩井字游戏时经常使用威胁考虑因素）。您可以通过使用不同的评估函数对有效移动进行排序来强制执行不同的访问顺序。

另请注意，移动顺序与 alpha-beta 修剪结合使用时对于增加搜索深度非常有用，因为它允许首先考虑好的有效移动并增加修剪更多节点的机会。虽然 alpha-beta 剪枝对于如此简单的游戏来说可能有点矫枉过正，但它对于更复杂的游戏来说确实很有用。

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

Minimax Algorithm - Computer doesn't block me when I have two ways to win.

java

algorithm

minimax