實現井字遊戲的最佳算法 - 通用（3X3或4x4或9x9等）

Question

任何人都可以幫助我。這是實現TicTacToe遊戲的最佳算法。我需要以它應該是通用的方式編寫代碼，並且應該能夠以更簡單的方式處理更復雜的級別（通用方式），我可以從哪裏開始？我讀到我們可以使用MiniMax算法。我需要知道的最多。高效的算法

感謝，

Answer 1

「最好」的算法（它總是選擇最好的遊戲）被稱爲是NP完全問題。

因此，真正很難實施「好」的，它使用一些啓發式來提高性能，它是非常寶貴的。

Minimax基本上只是「真正」起作用的方法，所以先從它開始，然後您可以思考並尋找優化。這個想法很簡單，你嘗試每一個動作，然後衡量該動作的「價格」（例如，創建更多相同的「X」或「O」排比創建「X」或「O」更勝於大多數東西，或者阻止敵人的「X」或「O」長線也不錯）。

然後，對於每一個可能的動作，你都會嘗試敵人去做所有可能的動作，並且你會計算出價格。

你到底「越深」，它越珍貴，但性能算法的代價越高。

對於這個例子，我說過，每做一次動作，你都會做每一次敵人的動作 - 你認爲對手會盡可能的發揮出色，所以你從對手所發揮的所有動作中獲得最大（他的最大值） 。 現在對於每一個可能的動作，你都有最好的敵人玩的價值。然後你選擇最低限度 - 這意味着你想爲你選擇最好的，最壞的選擇給敵人。

這就是爲什麼他們稱之爲極小極小。