java - Tic_Tac_Toe_对抗计算机 使用 MiniMax 算法，当计算机轮到 4*4 棋盘时，它玩得不好？

Question

我正在用java构建一个针对AI计算机玩家的tic_tac_toe(棋盘)游戏，我为计算机编写了一个MiniMax算法。板的宽度可以改变，如 3*3 或 4*4。和

when i run the game with 3*3 board the computer player workingvery well, but when i tried 4*4 board, the computer player doesn'twork it's just taking a lot of time in his turn and then nothing justwaiting until i stop the game.And here is a screen shoot what's happening.

这是我编写的 MiniMax 算法:

private Pair<Integer, State> maxMove(State b) {
        if(b.isWin('X') || b.isFinished())
            return new Pair<>(b.eval('X'), b);
        else{
            int max = -222, temp;
            Pair<Integer, State> p = null;
            for (State s : b.allNextMoves('O')){
                temp = minMove(s).getKey();
                if (temp > max){
                    max = temp;
                    p = new Pair<>(s.eval('X'), s);
                }
            }
            return p;
        }
    } 


private Pair<Integer, State> minMove(State b) {
        if(b.isWin('O') || b.isFinished())
            return new Pair<>(b.eval('O'), b);
        else{
            int min = 222, temp;
            Pair<Integer, State> p = null;
            for (State s : b.allNextMoves('X')){
                temp = maxMove(s).getKey();
                if (temp < min){
                    min = temp;
                    p = new Pair<>(s.eval('O'), s);
                }
            }
            return p;
        }
    }

eval函数是评估网格，我只是将其作为样本来遵循，这是函数:

 public int eval(char player) {
  if (isWin(player))
            return -1;
        else
            return 0;
    }

有人知道为什么会发生这种情况吗？

编辑

allNextMoves(char c) 函数将采用该棋盘并尝试通过找到棋盘中的第一个空字符并输入“X”或“O”来找到该棋盘的所有可能的移动根据玩家的回合，返回新棋盘列表，代码如下。

public List<State> allNextMoves(char player) {
        List<State> nextBoards = new LinkedList<>();
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < width; j++) {
                if (board[i][j] == ' ') {
                    State nextBoard = new State(this);
                    nextBoard.play(i, j, player);
                    nextBoards.add(nextBoard);
                }
            }
        }
        return nextBoards;
    }

Answer 1

极小极大算法不响应的原因是，对于 4x4 网格，要访问的板数量要多得多。

首先，我发现您的算法将继续搜索，直到获胜或平局，这意味着大量搜索路径将完全填满棋盘。在你的第一个 Action 之后，还剩下 15 个回合，每个回合分别有 15、14、13、... 1 个替代 Action 可供选择。所以有接近15个!董事会国家参观。由于会发现(非受迫性)胜利，所以这个数字有点少，但仍然是 15!是对尺寸的一个很好的粗略估计。

在 3x3 棋盘中，这个数字只有 8!

比较两个数字:

 8! =            40 230  
15! = 1 307 674 368 000

因此，在 4x4 棋盘中进行搜索将比在 3x3 棋盘中花费大约 3000 万倍的时间。

如何解决？

可以采取多种措施，也可以将这些措施结合起来。这不是完整的列表，而是我将按顺序处理的事情的列表:

1。限制搜索深度

当搜索深度过大时，需要停止搜索。有几种方法可以决定何时停止:

• 以固定的预定义搜索深度
• 当达到最小固定搜索深度时，以及当前状态为“安静”时，即没有直接的获胜威胁。

评估函数

当您限制搜索时，您需要一个评估函数来给出状态值，而无需进行更深入的搜索。这将具有一定的启发值(value)。例如，它可以计算玩家仍然可以获胜的行数(如果对手打得不好)，并将其与对手 View 中的相同数字进行抵消。

2。使用查找表

可以通过不同的移动路径达到相同的棋盘状态。例如，如果两个玩家交换了他们的第一步和第二步，那么您将进入相同的棋盘状态。

此外，多个状态通过沿 X、Y 或对角轴镜像来相互映射。

通过维护先前评估状态的哈希表(还管理镜像方面)，您可以避免进行搜索，这本质上是重复的。

3。 Alpha Beta 修剪

alpha-beta算法进行的剪枝不会影响结果。它给出与极小极大算法相同的结果。

4。首先执行最佳 Action

在极端情况下，当前棋盘可能距离获胜仅一步之遥，但如果这是考虑的最后一步，则需要花费大量时间来寻找其他一步。因此，如果您可以首先以最有希望的 Action 最先完成的方式对 Action 进行排序，您将赢得时间:alpha beta 修剪将更加有效。

您可以根据棋子是否位于被“许多”对手棋子占据的线上来对棋子进行排名，或者当这没有区别时，首先处理中心和角棋子，因为它们比边界棋子可以参与更多的解决方案.

5。 killer 级 Action

如果在采取某种行动后，您发现回复是救命稻草，或者是强制获胜的关键举措，那么首先尝试相同的回复可能会有所返回，而不是最初的行动，而替代行动是玩过。