极小极大算法——当我有两种获胜方式时，计算机不会阻止我。

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，因为最大值永远不会从第一个位置更新。我希望它将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);

然后，我将best与之前的最大值进行比较。如果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距离成为获胜线很短）。让我们看看这个评估函数会告诉我们给定位置的四个有效移动中的每一个。我们计算两个棋子的威胁数量，并分配给位置值S等于差O_threats-X_threats。

如果O移动（0,1），则O_威胁=0，X_威胁=2，因此分数S=0-2=-2。

如果O移动（0,2），则O_威胁=1，X_威胁=1，因此分数S=1-1=0。

如果O移动（1,0），则O_威胁=0，X_威胁=1，因此分数S=0-1=-1。

如果O移动（1,2），则O_威胁=1，X_威胁=2，因此分数S=1-2=-1。

根据计算出的分数，访问有效移动的顺序如下：（0,2）、（1,0）、（1,2）、（0,1）。我们知道，在完美的比赛中，所有四个动作都是失败的。由于他们的分数相等（等于损失值-10），第一个考虑的移动（0,2）不会被下一个移动覆盖。这将使程序的动作“更加智能”，因为它现在尊重由动作产生/阻止的威胁（人类在玩tic-tac-toe游戏时经常使用威胁考虑）。通过使用不同的评估函数对有效移动进行排序，可以强制执行不同的访问顺序。

还要注意，移动排序对于增加与αbeta修剪相结合的搜索深度是非常有用的，因为它允许首先考虑好的有效动作，并增加修剪更多节点的机会。虽然alpha-beta修剪对于这样一个简单的游戏来说可能是一种过度的杀伤力，但对于更复杂的游戏来说，它确实很有用。