java - Java 中用于 TicTacToe AI 的最简单 MiniMax 算法

Question

我试图掌握 MiniMax 算法，并且已经阅读了它。我最初的方法是实现一个简单的 MiniMax 算法，然后添加 alpha-beta 剪枝。但是这是我当前的代码:

public int miniMax(char[] node, int playerNum)
{
    int victor = checkWin(node); // returns 0 if game is ongoing, 1 for p1, 2 for p2, 3 for tie.
    if(victor != 0) //game over .
        return score(victor);   

    if(playerNum == 2) //AI
    {
        int bestVal = Integer.MIN_VALUE;
        int bestSpot = 0;
        for(int i = 0; i < node.length; i++)
        {
            if(node[i] != '-')
                continue;
            node[i] = getSymbol(playerNum);
            int value = miniMax(node, 1); 
            if(value > bestVal)
            {
                bestVal = value;
                bestSpot = i;
            }

            node[i] = '-';
        }
        return bestSpot;
    }
    else
    {
        int bestVal = Integer.MAX_VALUE;
        int bestSpot = 0;
        for(int i = 0; i < node.length; i++)
        {
            if(node[i] != '-')
                continue;
            node[i] = getSymbol(playerNum);
            int value = miniMax(node, 2); 
            if(value < bestVal)
            {
                bestVal = value;
                bestSpot = i;
            }
            node[i] = '-';
        }
        return bestSpot;
    }
}

还有我的评分函数

private int Score(int gameState)
{
    if(gameState ==2) //O wins.
        return 10;
    else if(gameState==1) //X wins
        return -10;
    return 0;
}

现在，我有一个工作的 AI 试图阻止我的移动并获胜，但有时它会做出非智能选择，例如，如果我从控制台读取的输入是 6、7、8，这就是我得到的输出命令。它不会试图阻止我的胜利。但在其他情况下确实如此。

---

|欧 |欧 | |

---

| | | |

---

| × | × | × |

---

在我的第二次尝试中，我尝试了 4,3，但它阻止了我的获胜 Action 。

---

| |欧 | |

---

| × | × |欧 |

---

| | | |

---

我想知道有人能指出我的实现有什么问题吗？

Answer 1

所示示例的代码行为是正确的!

那么为什么下面位置的威胁没有被挡住呢？为什么程序下的是 1 步而不是 6 步？

O . .                                    O 1 2
. . .     numbering available moves:     3 4 5
X X .                                    X X 6

这是因为如果游戏在完美游戏中输了，程序只会执行第一个可用的移动。

算法只关心输赢，不关心步数。

看看如果威胁被阻止会发生什么:

O . .     O . .
. . .     . X .     and X wins on his next move
X X O     X X O