java - 极小极大游戏状态

Question

我正在尝试实现一个 minimax 算法，我掌握了算法的要点，但似乎我需要在算法的某个点“撤消”移动。我找不到这应该在哪里。如果有人能告诉我在哪里以及为什么，我们将不胜感激。

private int minimax(Player[][] state, int r, int c, Player player) {
    if (getWinner(state, r, c) == player) return 10; //returns 10 if player is winner
    Player opponent = (player == Player.PLAYERX ? Player.PLAYERO : Player.PLAYERX);
    if (getWinner(state, r , c) == opponent) return -10; //returns -10 if opponent is winner

    if (getPlays(state, player) > getPlays(state, opponent)) state[r][c] = opponent; //Puts opponent in current spot if player has played more times than opponent
    else state[r][c] = player; //Puts player in current spot if opponent has played more times than player

    for (int column = 0; column < GRID_WIDTH; column++) {
        int row = top(state, column);
        if (row >= 0) {
            return minimax(state, row, column, player);
        }
    }
    return 0; //minimax will only ever return this if there are no plays left to be made, meaning that the scenario resulted in a draw
}

Answer 1

制作假设时需要复制状态，否则“试用”盘仍保持实际状态。

这个

Player[][] hypothetical = state;

应该是

Player[][] hypothetical = (Player[][])state.clone();

或者，您可以使用 state 而不是您的 hypothetical，但在循环后添加磁盘移除:

if (getPlays(state, player) > getPlays(state, opponent))
    state[r][c] = opponent; //Puts opponent in current spot if player has played more times than opponent
else
    state[r][c] = player; //Puts player in current spot if opponent has played more times than player
int best = -10;
for (int column = 0; column < GRID_WIDTH; column++) {
    int row = top(hypothetical, column);
    if (row >= 0) {
        int tmp = minimax(hypothetical, row, column, player);
        if (tmp > best) best = tmp;
    }
}
state[r][c] = null;
return best;