Tic_Tac_Toe_使用MiniMax算法对抗计算机当计算机使用4*4板时，它也不玩了？

Question

我建立了一个tic_tac_toe（板）游戏对AI电脑播放器在java，我写了一个MiniMax算法的电脑

下面是我写的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

minimax算法没有响应的原因是，对于4x4网格，要访问的板的数量要多得多。

首先，我看到你的算法会继续搜索，直到有一场胜利或一场平局，这意味着许多搜索路径会完全填满棋盘。在你第一次移动后，还有15个回合，每个回合都有15, 14, 13, ... 1可供选择的替代移动。所以有将近15个！棋盘状态可供访问。这有点少，因为会找到（非强迫的）胜利，但15！是一个很好的粗略估计。

在3x3板上，这个数字只有8！

比较两个数字：

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

因此，在4x4板上搜索所需的时间比在3x3板上搜索所需的时间多约3000万倍。

可以采取几种措施，并且可以将它们结合起来。这不是一个完整的列表，而是一个我将按顺序工作的列表：

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

• 在固定的预定义搜索深度
• 当达到最小的、固定的搜索深度时，并且当当前状态为"安静"时，即没有获胜的直接威胁。

当你限制搜索时，你需要一个评估函数，它可以给出一个状态的值，而不需要深入搜索。这将是一些启发式的值。例如，它可以计算一个玩家仍然可以获胜的行数（如果对手打得不好），并将其与对手视图中的相同数量进行抵消。

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

此外，几个状态通过沿着X、Y或对角线轴的镜像相互映射。

通过维护一个包含先前评估状态的哈希表（该哈希表还管理镜像方面），可以避免执行本质上是重复的搜索。

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

在极端情况下，当前的董事会可能离胜利只有一步之遥，但如果这是被考虑的最后一步，那么寻找其他举措就会浪费很多时间。因此，如果你能以最有希望的举措最先完成的方式排列举措，你将赢得时间：阿尔法贝塔修剪将会更加有效。

你可以根据移动是否在一条被“许多”对手棋子占据的线上进行排名，或者当这没有区别时，首先处理中间和角落移动，因为它们可以参与比边界移动更多的解决方案。

如果在某一次移动后，你发现一个回复是一个救命稻草，或者是一个朝向强制胜利的关键移动，那么当使用另一个移动而不是最初的移动时，尝试同样的回复可能会有回报。