實現井字遊戲的算法？

Question

可能重複：
What Algorithm for a Tic-Tac-Toe Game Can I Use To Determine the 「Best Move」 for the AI?

我已經創建了一個井字遊戲2名球員即玩互相反對。現在我已經計劃實施相同的遊戲，但是與電腦對戰。那麼任何人都可以提出一些很好的算法或想法來實現它？

Answer 1

由於遊戲非常簡單，你可以做一個搜索樹。這是一個可以替代「你的動作」和「敵人動作」的樹。敵人總是選擇最適合他們的東西，而且你總是選擇最適合你的東西。對於每個棋盤位置，如果最佳遊戲分別產生贏/輸/平局，則將其評爲「勝利」/「丟失」/「打結」。執行深度優先搜索（或任何搜索）並選擇分支。這基本上是如何打敗大師們的複雜國際象棋程序（儘管它們是高度優化的並且在並行的優秀硬件上運行）。這就是所謂的minimax algorithm。

或者，您可以手動編寫所有最佳動作（使用通過旋轉和翻轉電路板將其與已知動作進行比較的例程）。只有500個可能性。

但是由於tic-tac-toe是一個解決的遊戲，它會相當無聊。如果電腦播放效果最佳，電腦將永遠和你同在。由於tic-tac-toe只對5歲的孩子有挑戰性，所以你可以考慮你的遊戲的觀衆：讓計算機做一個隨機的不失敗的舉動可能是合理的。那麼人類玩家至少有機會。

Answer 2

與ninjagecko一樣，搜索樹已經提出，對於代碼編寫來說，它是直接和最優的。

但就像製作搜索樹比手工編碼所有最佳動作更有趣一樣，我認爲嘗試機器學習方法會更有趣。例如，製作一個使用reinforcement learning的程序將是一件很酷的事情。