哪些算法可用於解決井字遊戲？

Question

有什麼算法可以解決井字遊戲？特別是對於4 * 4或更大尺寸而不是3 * 3的電路板？我用Minimax & alpha-beta pruning嘗試了4 * 4，但pc似乎掛起並在堆棧溢出時拋出異常。 我看到了這些以javascript編寫的源代碼，但我不知道它使用哪種算法，有誰能爲我澄清它嗎？ http://js-x.com/page/javascripts__example.html?view=153

Answer 1

試圖做一定深度的切斷...我不認爲你需要超過4或5的深度才能做出完美的舉動。

（java的3 * 3的深度一個調光板）：

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; 
}