java - Minimax 算法 tic tac toe 错误

Question

at TicTacToe.minvalue(TicTacToe.java:184)
    at TicTacToe.maxvalue(TicTacToe.java:197)
    at TicTacToe.minvalue(TicTacToe.java:184)
    at TicTacToe.maxvalue(TicTacToe.java:197)
    at TicTacToe.minvalue(TicTacToe.java:184)
    at TicTacToe.maxvalue(TicTacToe.java:197)
    at TicTacToe.minvalue(TicTacToe.java:184)
    at TicTacToe.maxvalue(TicTacToe.java:197)
    at TicTacToe.minvalue(TicTacToe.java:184)
    at TicTacToe.maxvalue(TicTacToe.java:197)
    at TicTacToe.minvalue(TicTacToe.java:184)

我看不到错误，因为它太长了。这是函数 maxValue() 和 minValue()

 private int minvalue(char [] brd){
    int m = (int) Integer.MAX_VALUE;
    int v;
    for(int a : actions(brd)){
        char [] nextbrd = result(brd, a, human);
        if(status(nextbrd)=='C') v = maxvalue(nextbrd); //line 184
        else v = utility(nextbrd);
        m = Math.min(m, v);

    }
    return m;
}

private int maxvalue(char [] brd){
    int m = (int) Integer.MAX_VALUE;
    int v;
    for(int a : actions(brd)){
        char [] nextbrd = result(brd, a, agent);
        if(status(nextbrd)=='C') v = minvalue(nextbrd); //line 189
        else v = utility(nextbrd);
        if(v==Math.max(m, v))   nextAction = a;
        m = Math.max(m, v);

    }
    return m;
}

如果获胜者是代理人，utility function() 仅返回 1。否则-1。如果游戏尚未结束，则状态返回“C”。我不知道出了什么问题。

更新:我将 maxValue() 函数中的 m 更改为 MIN_VALUE 但仍然遇到相同的错误。

Answer 1

一旦您的代码达到 maxvalue 方法，您将收到 StackOverflow 错误，因为您的 nextAction 值将永远不会再改变。改变nextAction的条件如

if(v==Math.max(m, v))   nextAction = a;

但是一开始你就已经初始化了

int m = (int) Integer.MAX_VALUE;

因此，根据您的代码，if 语句永远不会为真。以下更正看起来是避免 StackOverflow 错误的明显方法。

   private int maxvalue(char [] brd){
    int m = (int) Integer.MIN_VALUE;
    int v;
    for(int a : actions(brd)){
        char [] nextbrd = result(brd, a, agent);
        if(status(nextbrd)=='C') v = minvalue(nextbrd); //line 189
        else v = utility(nextbrd);
        if(v==Math.max(m, v))   nextAction = a;
        m = Math.max(m, v);

    }
    return m;
}