Loading article…
指し手順序とは、ゲームツリー探索（特にコンピュータチェス）において、最も有望な指し手を最初に選択する手法を指します。 [ 1 ] [ 2 ]アルファベータ枝刈りを用いたミニマックス探索では、適切な指し手順序が重要であり、より強力な指し手を早期に検討することで、部分木を排除するカットオフが発生し、探索されるノード数が大幅に減少します。理想的な指し手順序の場合、探索の複雑さはおよそ実効分岐係数を実質的に半分に減らすまた、与えられた計算努力に対して、探索深度を約2倍にすることができる。 [ 3 ]クロード・シャノンは、典型的なチェスの局面には約30の合法的な手があるかもしれないが、効果的な枝刈りとヒューリスティクスによって、有用な分岐係数はわずか数個にまで減少すると指摘した。[ 4 ]
駒の順番を決めるというアイデアは、コンピュータが登場する以前から存在していました。1950年の画期的な論文「チェスをプレイするためのコンピュータのプログラミング」[ 5 ]の中で、クロード・シャノンは、ゲームツリー全体の膨大なサイズ（推定で約1000,ノード）を単純に評価し、固定深度まで全てのバリエーションを探索するという方法は非現実的であるとシャノンは考えた。シャノンは、チェスプログラムが有用であるためには、選択された手に焦点を当て、積極的に枝刈りする必要があると考えた。正式なアルファベータアルゴリズムは、ミニマックスの結果を変えずに枝刈りする方法として、1950年代後半から1960年代にかけて登場した。アルファベータの枝刈り能力は、手を調べる順序に完全に依存することが早い段階で指摘された。1963年、アレクサンダー・ブルドノは独自にアルファベータに似た探索を記述し、手が正しい順序で試されたときに最良のノード数が発生することを指摘した。1970年代までに、ドナルド・クヌースやロナルド・ムーアなどの研究者がアルファベータを数学的に分析し、完全な順序付けの下ではその時間が[ 6 ]
1970年代と1980年代には、指し手の順序付けに関する主要な実用的なヒューリスティックが導入されました。反復深化の使用はチェス プログラムで再発見され、より深い探索の指し手の順序付けを大幅に改善することが分かりました。浅い深度で見つかった最良の指し手を、次のより深い探索の最初の指し手として使用するというアイデアでした。[ 7 ]転置テーブル（ 1966年にリチャード グリーンブラットによるMac Hackがハッシュを初めて使用）により、プログラムは各局面の最良の指し手を保存し、後続の訪問でそれを最初の選択肢として再利用することができました。[ 8 ] 1968年にバーバラ リスコフらは、ベータカットオフを引き起こす指し手を保存することを独自に提案しました。これは最終的にキラー ヒューリスティックとして知られるようになりました。1983年にジョナサン シェーファーは履歴ヒューリスティックを提案しました。シェーファーは、履歴スコアがより単純なヒューリスティックよりも優れていることを示しました。
チェスエンジンの探索効率は、可能な限り早く「悪い」手を無視する能力にほぼ完全に依存している。理論的には、エンジンが常に最善の手を最初に調べることができれば、探索空間は実質的に平方根に縮小される。[ 1 ]これは、ゲーム理論とヒューリスティックに基づく枝刈りの組み合わせによって実現される。 [ 9 ]
純粋なミニマックスゲームツリー探索では、固定深度まで全ての手を探索するため、指数関数的にコストがかかります。[ 10 ]アルファベータ枝刈りでは、アルファ（α）とベータ（β）という2つの境界を設けることで、このコストを改善します。[ 11 ]アルファは最大化プレイヤーが確実に得られる最小スコアであり、ベータは最小化プレイヤーが許容できる最大スコアです。ノードの値が、以前に調べた手よりも悪いため最終決定に影響を与えることができない場合、その枝は切り捨てられます。これにより、完全なミニマックスと同じ結果が得られる確率がありますが、ノード数は少なくなります。
反復深化深さ優先探索は一般的に用いられます。エンジンは深さ制限を徐々に増やしながら繰り返し探索を行い、深さから最適な移動を選択します。深層部を攻める最初の動きとして[ 12 ]これにより、最初の動きに対して強力な初期境界 (アルファまたはベータ) がほぼ生成され、残りの探索のウィンドウが狭まります。反復深化は、過去の結果を活用することで、深さ優先探索を最良優先探索に似たものに変換します。転置テーブルに現在の局面のエントリが含まれている場合、保存されている最良の動きが最初に試されます。[ 13 ]転置の動きが考慮された後、典型的な順序付けヒューリスティックは、戦術的な動きを強制すると大きな利点または即時のカットオフにつながることが多いため、キャプチャとチェックを優先します。[ 14 ]
エンジンは、最も価値の高い犠牲者-最も価値の低い攻撃者 (MVV-LVA) ヒューリスティックによってキャプチャーの動きをソートします。[ 8 ]明らかに損失となる取引を避けるため、静的交換評価 (SEE) が、物質的バランスを低下させるキャプチャーを剪定するためによく適用されます。強制的な動きがカットオフを生み出さない場合、エンジンは保存されているキラーの動きを試します。キラーではない動きがカットオフを引き起こした場合、それは新しいキラーになります。最後に、残りの静かな動きは、動きがカットオフを引き起こすとボーナスが蓄積される履歴ヒューリスティック スコアによって順序付けられます。[ 15 ]動きが検索のどこかでカットオフを引き起こすたびに、その履歴スコアが増加します。したがって、過去にカットオフを引き起こした動きは、将来の順序付けで上位にランクされます。
研究者たちは、基本的なスキームを超えていくつかの改良を開発しました。カウンタームーブヒューリスティックは、実際の局面に関係なく、多くの手には「自然な」応答があると仮定しています。[ 16 ] 「バタフライボード」 [ 17 ]や「最後のベストレスポンス」ヒューリスティックなどのその他のさまざまなテクニックは、ローカル検索履歴を利用する関連アイデアです。一部のエンジンは機械学習を使用しており、Kocsis らと Greer による初期の研究では、ニューラルネットワークを使用して手の値や順序を予測しました。ほとんどの強力なエンジンは、依然として単純な PV ムーブ、ハッシュムーブ、MVV-LVA キャプチャソート、キラー、履歴テーブルに依存しています。
