如何寫棋類AI程序
學習如何寫棋類AI程序，需要掌握以下幾個方面的知識：
1. 算法基礎：了解 Minimax，Alpha-Beta 剪枝等基礎算法。
2. 數據結構：了解數組、棧、樹等主要的數據結構，以及如何使用它們，將有助於編寫高效的棋類AI程序。
3. 博弈樹：學習如何構建博弈樹。從當前棋盤狀態開始，遞歸地生成所有可能的下一步操作。
4. 局面評估函數：學習如何設計局面評估函數，以評估當前局面的價值。對棋類游戲的獲勝技巧要有深入的了解，才能編寫出準確和高效的局面評估函數。
5. 著法排序：著法排序是寫棋類AI程序的重要組成部分。通過著法排序，可以確定程序該如何遍歷博弈樹上的結點，從而使得搜索過程更加高效。正確的著法排序能夠使得程序在盡可能短的時間內找到最優解，從而提高棋類AI程序的效率。
6. 編程語言：掌握編程語言，如C++或Python，並熟練掌握代碼實現。一般情況下，使用C++寫棋類程序比使用Python寫棋類程序要快，因為C++是一種靜態編譯語言，運行時速度快得多，而Python是一種解釋性語言，運行時速度較慢。
對於一種新的棋類游戲，編寫一個高效的局面評估函數是關鍵。 Alpha-Beta算法有現成的實現，但它只是一種搜索算法，並不能決定遊戲的最佳走法。局面評估函數是決定每一步最佳走法的關鍵因素，它需要根據遊戲的規則和特點來編寫，而這是需要棋類專業知識和經驗的。因此，對於新的棋類游戲，編寫局面評估函數的工作量往往是最大的。
華容道
華容道和棋類游戲的算法思想是存在差異的，主要在於問題的不同性質。
華容道是一種移動拼圖遊戲，主要是通過移動拼圖來達到狀態的轉換，因此它是一種狀態空間搜索問題。通過廣度優先搜索或深度優先搜索，可以快速找到最終的最優解。
華容道要求玩家將一個堆積的錯排的棋子移動到目標位置。在寫一個華容道的 AI 程序時，深度優先算法在解決華容道問題時存在一些問題，比如容易陷入死胡同中並需要很長時間才能找到解，遞歸深度受到一定限制，可能會超過系統的最大遞歸深度限制。因此，廣度優先算法是一種更合適的算法，適用於解決華容道問題。
而棋類游戲，是一種兩人博弈遊戲，具有明顯的決策樹結構，因此它們是一種博弈樹搜索問題。 Minimax 算法和Alpha-Beta 算法是用來解決棋類游戲的算法，它們通過對博弈樹的遍歷和剪枝，來快速找到最優的決策。
總的來說，華容道的算法主要是針對狀態空間搜索的，而棋類游戲的算法主要是針對博弈樹搜索的。雖然兩者都是搜索問題，但在實現上有很大的差異。
棋類程序使用的算法
廣度優先搜索是從根節點開始，按層序遍歷所有子節點，直到找到目標狀態為止。廣度優先搜索通常用於在圖中求最短路徑，或求最少步數解決問題。
深度優先搜索是從根節點開始，沿著一條分支直到搜索完所有節點為止，再回溯，繼續搜索另一條分支，直到找到目標狀態為止。深度優先搜索通常用於求解所有解的問題，但不保證求出的解是最優解。
Minimax 算法是一種博弈論算法，用於解決具有博弈性質的問題，例如各種棋類游戲等。 Minimax 算法通過模擬每一步可能的走法，判斷當前狀態是否是最優狀態，從而決定下一步該如何走。 Minimax 算法通常是基於深度優先搜索的，原因在下面詳述，並且通過極小化極大值的思想，來選擇最優的走法。
Minimax 算法會遞歸地搜索遊戲樹，直到某一層葉節點，並對每個狀態評估其價值，再回溯到上一層，更新每個內部結點的價值，最終更新根節點的價值，得出最佳策略。由於Minimax 算法是遞歸地搜索遊戲樹，並在每一層結點選擇價值最高的策略。
Alpha-Beta 算法是在 Minimax 算法的基礎上進行優化的，主要思想是剪枝，即剪去不必要的搜索分支。它通過記錄當前搜索分支的 Alpha 值和 Beta 值來控制搜索的范围，剪去更深層的不必要搜索，從而提高算法的效率。
總之，Minimax 算法通過遍歷每一個遊戲狀態，並評估每個狀態的價值，從而得到最優解。 Alpha-Beta 算法是Minimax 的優化版本，它可以在某些情況下剪掉一些不必要的搜索，加快搜索速度。
Minimax 和 Alpha-Beta 算法都是很有效的算法，它們在很多情況下可以獲得最優解。但是，要獲得最優解，還需要考慮其他因素，比如算法的實現，搜索深度，以及評估函數的設計等。
Minimax 和 Alpha-Beta 算法都是通過預測對手的決策來尋找最優解的。舉個例子，假設你是一個棋類的 AI 程序，你需要在下一步走棋前決定哪一步最有可能獲得勝利。Minimax 和 Alpha-Beta 算法都可以幫助你實現這個目標。它們通過模擬你和對手的決策，並通過比較預測結果，來決定哪一步最有可能獲得勝利。
Minimax 算法通過不斷模擬，在每一步預測對手的決策，直到指定層數或者棋局結束的最後一步為止，最後選擇使得最壞情況最小的那一步走棋。 Alpha-Beta 算法則是在 Minimax 算法的基礎上進行了優化，它通過剪枝的方法，在不影響最終結果的情況下減少了搜索的次數，從而提高了效率。
廣度優先搜索 (BFS) 和深度優先搜索 (DFS) 算法是用於遍歷圖或樹的兩種算法。博弈樹是一個樹形數據結構，其中每個節點代表某個遊戲狀態，每條邊代表遊戲狀態的轉移。在博弈樹上，每個狀態都是相互獨立的，可以分別考慮。
廣度優先搜索 (BFS) 算法從根節點開始，按層次依次遍歷整張博弈樹，保證了每個狀態都被遍歷到。深度優先搜索(DFS) 算法則是從根節點開始，遞歸地遍歷整棵樹，直到找到葉子節點。
Minimax算法是一種專門為博弈樹問題設計的算法，它考慮了博弈樹上每一步對整體的影響。 Minimax算法通過在整個博弈樹上模擬雙方的決策，通過計算每一步的最壞結果，最終確定最優決策。因此，Minimax算法是解決博弈樹問題的基礎算法。
Minimax算法主要是為了保證算法的正確性。 Minimax算法通過遞歸搜索博弈樹（因此也無所謂深度還是廣度優先）並評估每一步的最壞情況，來決策出最佳的落子方案。它的正確性在於，如果對手在某一步拿到最大的得分，那麼Minimax算法會在前一步盡可能選擇最小的得分，以確保最終得分最大。
關於如何對一顆博弈樹進行搜索，我們面臨著以下幾種選擇：
1. 是在記憶體中生成整個樹進行搜索，還是在搜索的過程中僅僅產生想要搜索的節點？
2. 廣度優先搜索還是深度優先搜索？
3. 有必要生成整棵樹嗎？那樣可能會耗費大量系統資源。
所以權衡利弊，幾乎任何人使用Minimax算法時都會去選擇深度優先搜索，這樣在過程中僅僅生成樹的一小部分，之後搜索過的部分立即被刪去，這樣更加節省內存。
因為Minimax算法是通過遞歸搜索博弈樹來評估每一步的最優解，而博弈樹的大小是指數級別的，隨著搜索深度的增加，計算量也會急劇增加。因此，Minimax算法需要使用Alpha-Beta 剪枝算法來降低時間複雜度。
Alpha-Beta剪枝算法就是在當知道一個節點的評估情況後，如果處理到後面的節點，有的情況比上一個節點更加糟糕的話，則停止處理，停止深度搜索，開始搜索同層的另外節點。所以說這個算法和MiniMax結果相同，只是時間上的不同。
在“混亂時鐘”的C++程序實現中，使用了 Alpha-Beta 剪枝算法，具體可以參見 search.cpp 文件。
局面評估
在沒有局面評估函數的情況下，Alpha-Beta算法仍然可以使用，但它將無法利用評估函數的估價結果，從而剪枝搜索樹。
Minimax和Alpha-Beta算法依賴於局面評估函數來進行決策。如果沒有局面評估函數，Minimax和Alpha-Beta算法將無法返回任何有意義的結果，因為它無法評估哪個決策是最優的。因此，在沒有局面評估函數的情況下，算法是不能良好運行的。
局面評估函數寫得太複雜，會影響算法效率，因為評估函數是在每一步搜索中都要被調用的，如果評估函數的運算量太大，會導致算法的時間複雜度變高。
雖然將搜索深度加深可以獲得更多的信息，但是也會增加算法的時間複雜度，因此一般而言，將局面評估函數寫得簡單，與將搜索深度加深是相對的，如果評估函數過於簡單，那麼搜索深度就要加深，反之，如果評估函數太複雜，那麼搜索深度就可以減小。最終決策應該根據問題的具體情況和算法的時間限制來決定。
tips: gitauthe