chess_engine_using_python

Pythonを使用したチェスエンジン

このリポジトリには、 Minimax 、 Alpha-Beta プルーニング、および静止検索アルゴリズムを使用したチェス エンジンの実装が含まれています。コーディングには、Docker コンテナ内の Jupyter ノートブックが使用されます。すべての Jupyter Notebook は、docker イメージの形式でも利用できます。

詳細な分析については、プロジェクトの文書を確認してください。

使用する外部モジュール

• パイソンチェス

dockerを使って実行する方法

docker pull codewithnk/chess-engine-using-python:latest

docker run -p 8888:8888 -v $( pwd ) codewithnk/chess-engine-using-python:latest

チェス エンジンのアルゴリズム

ミンマックス

理論

minmax でチェスをプレイするチェスの核心。 Minmax は通常、黒のピースを MAX、白のピースを MIN に関連付け、常に白の観点から評価します。

Minmax アルゴリズムは、ゲーム理論における敵対的検索アルゴリズムです。ゲーム ツリーを利用しており、2 人のプレイヤーの MIN と MAX が含まれています。両方のプレイヤーは他のプレイヤーのアクションを無効にしようとします。 Max は結果を最大化しようとするのに対し、MIN は結果を最小化しようとします。両方のプレイヤーが交互にプレイしますが、両者が最適にプレイしているという前提の下にあります。最適なプレイとは、両方のプレイヤーがルールに従ってプレイしていることを意味します。つまり、MIN は結果を最小化し、MAX は結果を最大化します。

minmax アルゴリズムは、深さ優先検索アプローチを利用して結果を見つけます。さらに、バックトラッキングと再帰も利用します。アルゴリズムは終端ノードまで移動し、すべての子の値を比較しながらバックトラックします。誰の順番に基づいて最小値または最大値が選択されます。次に、値を親に伝播します。静的評価関数を使用して、各リーフ ノードの値を決定します。ゼロサムゲームの利点を活かしています。

実装

Minmax を使用したチェス エンジン

時間計算量

Minmax はゲーム ツリーで深さ優先検索 (DFS) を使用するため、minmax アルゴリズムの時間計算量はO(b**m)になります。ここで、 b はゲーム ツリーの分岐係数、m はツリーの最大深さです。

空間の複雑さ

minmax アルゴリズムの空間計算量も DFS と同様で、 O(bm)です。ここで、 b はゲーム ツリーの分岐係数、m はツリーの最大深さです。

完全

Minmax アルゴリズムが完了しました。有限探索ツリー内に解が存在する場合、必ずそれが見つかります。

最適性

Minmax アルゴリズムは、両方の対戦相手が最適にプレイしている場合に最適です。

---

アルファ-ベータ枝刈り

理論

minmax アルゴリズムは、いくつかのブランチを枝刈りすることで最適化できます。剪定された枝は結果に影響を与えない枝です。時間の複雑さが改善されます。このバージョンの minmax は、アルファベータ プルーニングを備えた minmax として知られています。アルファベータアルゴリズムとも呼ばれます。
アルファ-ベータ プルーニングには、アルファとベータの 2 つの値があります。以下に、アルファ版とベータ版について考慮すべき点をいくつか示します。

Alpha(α)についての注意点

• アルファは最大値であり、MAX パスに沿って見つかります。
• アルファ値は移動するたびに増加し続けるか、同じままであるため、アルファの初期値は負の無限大です。負の無限大以外の値を選択すると、アルファのすべての値が選択した値よりも小さくなるシナリオが発生する可能性があります。したがって、可能な限り最小の値、つまり負の無限大を選択する必要があります。
• アルファ版は MAX プレイヤーのみが更新します。

ベータ版(β)についての注意点

• ベータは、MIN パスに沿って見つかる最小値です。
• ベータ値は移動するたびに減少し続けるか、同じままであるため、ベータ値の初期値は正の無限大です。正の無限大以外の値を選択すると、ベータのすべての値が選択した値を超えるシナリオが発生する可能性があります。したがって、可能な最大値、つまり正の無限大を選択する必要があります。
• ベータ値は MIN プレイヤーによってのみ更新されます。

バックトラック中は、アルファ値とベータ値ではなく、ノード値のみが親に渡されます。

アルファベータ枝刈りの条件:

 α >= β

移動順序

アルファベータ アルゴリズムの有効性は、走査の順序に大きく依存します。それは時間と空間の複雑さにおいて重要な役割を果たします。

最悪の注文

場合によっては、ゲーム ツリーからノードやサブツリーが削除されないことがあります。この場合、最適な手はゲーム ツリーの右側のサブツリーで発生します。これにより、時間の複雑さが増加します。

理想的な順序

この場合、最大数のノードとサブツリーが枝刈りされます。最良の動きは左側のサブツリーで発生します。それは時間と空間の複雑さを軽減します。

実装

アルファベータ プルーニングを使用したチェス エンジン

時間計算量

アルファ ベータ アルゴリズムは、ゲーム ツリーで深さ優先検索 (DFS) も使用します。

• ワーストオーダーの場合：O(b^m)
• 理想的な順序の場合：O(b^m/2)

空間の複雑さ

• ワーストオーダーの場合：O(bm)
• 理想的な順序の場合：O(b(m/2))

完全

アルファベータアルゴリズムが完成しました。有限探索ツリー内に解が存在する場合、必ずそれが見つかります。

最適性

アルファ-ベータ アルゴリズムは、両方の対戦相手が最適にプレイしている場合に最適です。

---

静止検索

静止検索は、最小-最大によるアルファ-ベータ プルーニングに加えて変更を加えたものです。静寂とは静かという意味です。この検索で​​は静かな手のみを評価します。つまり、一定の深度を超えると、キャプチャ移動のみを使用して次の移動を計算します。静止検索により、地平線効果を回避できます。
地平線効果は、特定の深さまでしか検索しない場合に発生しますが、さらに 1 レベル深く検索すると、移動によるスコアが少なくなる可能性があります。静止検索ではこれを防ぐためにキャプチャ移動のみを使用します。静止検索では、さまざまなレベルで分岐因子も削減されるため、アルゴリズムが高速になります。

時間計算量

静止検索アルゴリズムは、ゲーム ツリーで深さ優先検索 (DFS) も使用します。

• ワーストオーダーの場合：O(b^m)
• 理想的な順序の場合：O(b^m/2)

空間の複雑さ

• ワーストオーダーの場合：O(bm)
• 理想的な順序の場合：O(b(m/2))

完全

静止検索アルゴリズムが完了しました。有限探索ツリー内に解が存在する場合、必ずそれが見つかります。

最適性

静止検索アルゴリズムは、両方の対戦相手が最適にプレイしている場合に最適です。

---

重要なポイント

• アルファ ベータでは、移動ごとに探索されるノードが Minmax と比較して 10 分の 1 に減少します。
• 最良の手を見つけるのにかかる時間も、Minmax と比較して、Alpha Beta では 10 分の 1 に短縮されます。
• 静止検索は、より深い深さで適切に実行されます。
• 静止検索は、3 つのアルゴリズムの中で最も高速なアルゴリズムです。
• 静止検索では評価されるノードが少なくなります。
• 静止検索は、適切に処理しないと、繰り返しの移動を引き起こす可能性があります。