chess_engine_using_python
1.0.0
該儲存庫包含使用Minimax 、 Alpha-Beta 剪枝和靜止搜尋演算法的國際象棋引擎實作。 Docker 容器內的 Jupyter Notebook 用於編碼。所有 Jupyter Notebook 也都以 docker 映像的形式提供。
查看專案論文以查看詳細分析。
docker pull codewithnk/chess-engine-using-python:latestdocker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest西洋棋的核心是以minmax下棋。 Minmax通常將黑棋與MAX聯繫起來，將白棋與MIN聯繫起來，並且總是從白棋的角度進行評估。
Minmax演算法是博弈論中的一種對抗搜尋演算法。它利用博弈樹並包括兩個玩家 MIN 和 MAX。兩名玩家都試圖抵消對手的行動。 Max 嘗試最大化結果，而 MIN 嘗試最小化結果。假設雙方都處於最佳狀態，兩名玩家交替進行遊戲。最佳遊戲意味著兩個玩家都按照規則進行遊戲，即 MIN 使結果最小化，MAX 使結果最大化。
minmax 演算法利用深度優先搜尋方法來找出結果。此外，它還利用回溯和遞歸。演算法將遍歷直到終端節點，然後在比較所有子值的同時回溯。它將根據輪到誰來選擇最小值或最大值。然後它將將該值傳播回其父級。它使用靜態評估函數來確定每個葉節點的值。它利用了零和博弈的優勢。
使用 Minmax 的國際象棋引擎
Minmax 在博弈樹上使用深度優先搜尋（DFS），因此 minmax 演算法的時間複雜度為O(b**m) ，其中 b 是博弈樹的分支因子，m 是樹的最大深度。
minmax演算法的空間複雜度也與DFS類似，為O(bm) ，其中b為賽局樹的分支因子，m是樹的最大深度。
最小最大演算法已完成。如果存在的話，它肯定會在有限搜尋樹中找到解決方案。
如果兩個對手都處於最佳狀態，則最小最大演算法是最佳的。
最小最大演算法可以透過修剪少量分支來優化。修剪的枝條是不會影響結果的枝條。它將提高時間複雜度。這個版本的 minmax 被稱為帶有 alpha-beta 剪枝的 minmax。它也稱為 alpha-beta 演算法。
在Alpha-Beta剪枝中，有兩個值：Alpha和Beta。以下是關於 alpha 和 beta 需要考慮的幾點：
回溯時，僅將節點值傳遞給父級，而不是 alpha 和 beta 值。
α-β剪枝的條件：
α >= β
alpha-beta 演算法的有效性很大程度取決於遍歷的順序。它在時間和空間複雜性中起著至關重要的作用。
在某些情況下，博弈樹中不會刪除任何節點或子樹。在這種情況下，最佳移動發生在博弈樹的右子樹。這將導致時間複雜度增加。
在這種情況下，節點和子樹的最大數量被修剪。最佳移動發生在左子樹。它將降低時間和空間複雜度。
使用 Alpha-Beta 剪枝的西洋棋引擎
Alpha Beta 演算法，也在博弈樹上使用深度優先搜尋（DFS）。
Alpha-Beta 演算法已完成。如果存在的話，它肯定會在有限搜尋樹中找到解決方案。
如果兩個對手都處於最佳狀態，則 Alpha-Beta 演算法是最佳的。
靜止搜尋是對最小-最大 α-β 剪枝的修改。靜就是安靜的意思。此搜尋僅評估安靜的動作。換句話說，在一定深度之後，它只使用捕獲動作來計算下一步的動作。靜止搜索可以避免地平線效應。
當我們只搜尋到一定深度時，就會出現地平線效應，但如果我們再深入一層，那麼移動得分可能會更少。靜止搜尋僅使用捕獲移動來防止這種情況。靜止搜尋也減少了不同等級的分支因子，從而產生快速演算法。
靜止搜尋演算法，也在博弈樹上使用深度優先搜尋（DFS）。
靜止搜索演算法已完成。如果存在的話，它肯定會在有限搜尋樹中找到解決方案。
如果兩個對手都處於最佳狀態，則靜止搜尋演算法是最佳的。
