java - 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 获胜。这将为此职位返回 -10。如果计算机在位置 0,2 移动，则调用 minimax 并将 x 最终放置在位置 1,0，这也会为此移动返回 -10。事实上，无论计算机将 o 放在哪里，都会返回 -10，因为无论玩家将赢得什么。因为对于放置 o 的每个位置，它返回 -10，计算机将 o 放置在第一个可用插槽中，即 0,1，因为 max 永远不会从第一个位置开始更新。我希望它把 o 放在位置 1,0 或 0,2 只是为了表明它识别一个 block 。

我的算法如下。它适用于 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

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

X . .
. X .
X O O

这里O是移动。在以默认方式(从左到右从上到下)遍历棋盘之前，对四个有效移动的 vector 进行排序 ((0, 1), (0, 2), (1, 0) , (1, 2)) 根据每个 Action 的好坏。做到这一点的一种方法是使用评估函数，该函数将计算在潜在移动后每一方有多少威胁。 P(可以是 X 或 O)的威胁是一行、一列或对角线，其中有一个空方 block 和两个 >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 剪枝对于如此简单的游戏来说可能有点矫枉过正，但它对于更复杂的游戏来说确实很有用。