tic-tac-toe - 哪些算法可用于解决井字游戏？

Question

有哪些算法可以解决井字游戏？特别是电路板尺寸为 4 * 4 或更大而不是 3 * 3？我尝试了 4 * 4 与 Minimax 和 alpha-beta 修剪，但 pc 似乎挂起并在堆栈溢出时抛出异常。我看到了这些用 javascript 编写的源代码，但我不知道它使用哪种算法，有人可以为我澄清一下吗？ http://js-x.com/page/javascripts__example.html?view=153

Answer 1

尝试在一定深度进行截断...我认为您不需要超过 4 或 5 的深度即可做出完美的移动。

（java for 3*3 one-dim board with depth）：

int minimax(int turn, int depth) { // turn(side to move) is 1 or -1
    int val = -turn; // worst value for that turn 
    int result = NULVAL;
    if (wins()) return turn; // evaluate board (board is a field)
    if (depth == 0) return DRAW;
    for (int i = 0; i < 9; i++) {
        if (board[i] == EMPTY) {
            board[i] = turn; // make move
            result = minimax(-turn, depth - 1);
            board[i] = EMPTY; // delete move
            if (result == turn) 
                return turn; // sees win
            if (result == DRAW)
                val = result;
        }
    }
    // if result keeps NULVAL: couldn't make a move (board is full)
    if (result == NULVAL) return DRAW;
    return val;
}