転置表

転置テーブルは、コンピュータゲーム プログラムによって生成されたゲーム ツリー内の、以前に見た位置と関連する評価のキャッシュです。位置が異なる一連の動きによって繰り返される場合、その位置の値はテーブルから取得され、その位置の下のゲーム ツリーの再検索を回避します。転置テーブルは主に、完全情報ゲーム(ゲーム全体の状態が常にすべてのプレーヤーに知られている) で役立ちます。転置テーブルの使用は、基本的にツリー検索に適用されるメモ化であり、動的プログラミングの一種です。

転置テーブルは通常、現在のボードの位置をハッシュ インデックスとしてエンコードするハッシュ テーブルとして実装されます。ゲーム ツリーで発生する可能性のある位置の数は、検索の深さの指数関数であり、数千から数百万、あるいはそれ以上になることもあります。そのため、転置テーブルは使用可能なシステム メモリのほとんどを消費し、通常はゲーム プレイ プログラムの メモリ フットプリントの大部分を占めます。

ゲームプログラムは、ゲームの次の数手で起こり得る何百万もの位置を解析することで機能します。通常、これらのプログラムは深さ優先探索に似た戦略を採用しており、これは、これまでに解析されたすべての位置を追跡しないことを意味します。多くのゲームでは、特定の位置に到達する方法が複数あります。これらは転置と呼ばれます。^[1]たとえば、チェスでは、一連の動き1. d4 Nf6 2. c4 g6 (代数チェス記法を参照) には、どちらのプレーヤーも動きの順序を入れ替えることができるため、4 つの転置が可能です。一般に、n手後、可能な転置の上限は ( n !) ²です。これらの多くは違法な動きのシーケンスですが、プログラムが同じ位置を複数回解析する可能性は依然としてあります。

この問題を回避するために、転置テーブルが使用されます。このようなテーブルは、特定の深さまで分析された各位置のハッシュ テーブルです。新しい位置に遭遇すると、プログラムはテーブルをチェックして、その位置がすでに分析されているかどうかを確認します。これは、償却定数時間で迅速に実行できます。すでに分析されている場合、テーブルにはこの位置に以前に割り当てられた値が含まれます。この値は直接使用されます。そうでない場合は、値が計算され、新しい位置がハッシュ テーブルに入力されます。

コンピュータが検索する位置の数は、コンピュータが稼働するシステムのメモリ制限を大幅に超えることが多く、そのためすべての位置を保存することはできません。テーブルがいっぱいになると、あまり使用されていない位置が削除され、新しい位置のためのスペースが確保されます。これにより、転置テーブルは一種のキャッシュになります。

転置テーブル検索によって節約される計算は、単一の位置の評価だけではありません。代わりに、サブツリー全体の評価が回避されます。したがって、ゲーム ツリーのより浅い深さにあるノードの転置テーブル エントリはより価値が高く (そのようなノードをルートとするサブツリーのサイズが大きいため)、テーブルがいっぱいになり、一部のエントリを破棄する必要がある場合に、より重要視されます。

転置テーブルを実装するハッシュ テーブルには、転置を見つける以外にも用途があります。アルファ ベータ プルーニングでは、最適な動きに対応するノードの子が常に最初に考慮される場合に、検索が最も高速になります (実際、最適です)。もちろん、最適な動きを事前に知る方法はありませんが、反復深化を使用する場合、より浅い検索で最適であると判明した動きが適切な近似値になります。したがって、この動きが最初に試されます。ノードの最適な子を格納するために、転置テーブル内のそのノードに対応するエントリが使用されます。

グラフと履歴の相互作用の問題を慎重に回避しないと、転置テーブルの使用によって誤った結果が生じる可能性があります。この問題は、ポジションの履歴が重要になる可能性がある特定のゲームで発生します。たとえば、チェスでは、キャスリングするキングまたはルークがゲームの進行中に移動した場合、プレーヤーはキャスリングできません。この問題の一般的な解決策は、キャスリング権をゾブリスト ハッシュキーの一部として追加することです。別の例は繰り返しによるドローです。ポジションが与えられた場合、それがすでに発生したかどうかを判断できない場合があります。一般的な問題の解決策は、履歴情報を転置テーブルの各ノードに格納することですが、これは非効率的であり、実際にはめったに行われません。

転置テーブルは、最大サイズが使用可能なシステム メモリによって制限され、いつでもオーバーフローする可能性があるキャッシュです。実際、オーバーフローすることが予想され、いつでもキャッシュ可能な位置の数は、ゲーム ツリー内のノードの数よりもほんのわずか (桁違いに少ない) である可能性があります。ノードの大部分は転置ノード (つまり、繰り返される位置) ではないため、潜在的な転置ノードを保持し、他のノードを置き換える効果的な置換戦略により、ツリーのサイズを大幅に削減できます。置換は通常、ツリーの深さと古さに基づいています。ツリーの上位 (ルートに近い) のノードが優先されます。これは、その下のサブツリーが大きく、より大きな節約につながるためです。また、より新しいノードが優先されます。これは、古いノードは現在の位置と類似しなくなり、それらのノードへの転置の可能性が低くなるためです。

その他の戦略としては、主要なバリエーション内のノード、ツリーの深さに関係なくサブツリーが大きいノード、およびカットオフの原因となったノードを保持することが挙げられます。

転置されるノードの割合は小さいですが、ゲームツリーは指数構造であるため、そのようなノードをごく少数キャッシュするだけで大​​きな違いが生まれます。チェスでは、複雑な中盤のゲームポジションでの検索時間が 0 ～ 50% 短縮され、終盤では最大 5 倍短縮されると報告されています。^[2]

• 同様の技術を使用して、ポジションの特定の機能の評価をキャッシュできます。たとえば、ポーン ハッシュ テーブルを使用して、ポジションのポーン構造の評価を保存できます。検査されるポーン ポジションの数は、検索されるポジションの総数よりも一般にはるかに少ないため、ポーン ハッシュ テーブルはヒット率が非常に高く、ポーン評価が何度も再利用されるため、プログラムは高度なポーン評価に多くの時間を費やすことができます。
• 反駁表は、ルートノードからリーフ ノードへの一連の動きを格納するために使用できます。これには、主なバリエーションと、他のラインが劣っていることを示す他のラインへの応答が含まれます。反駁表は、メモリが限られていたコンピューター チェスの初期の頃には、転置表の代わりに使用されることがありました。最近のチェス プログラムの中には、動きの順序付けに転置表に加えて反駁表を使用するものもあります。
• ボードの各スペースにある各タイプの駒の可能な動きの静的ビットマップは、プログラムの初期化時にキャッシュできるため、駒の有効な動き (または、動きの生成のためのすべての有効な動き) を、シリアルに列挙する代わりに、1 回のメモリ ロードで取得できます。これらは、ビットボードの実装でよく使用されます。

• ミニマックスアルゴリズム
• アルファベータ剪定
• ゾブリストハッシュ

• 転置表 Sigmachess.com
• テクニカル メイン転置テーブル（データ構造と実装に関する情報）
• チェス プログラムの解剖学 TA マースランド、アルバータ大学
• 転置表 チェスプログラミング Wiki