Loading article…
転置テーブルとは、コンピュータゲームプログラムによって生成されたゲームツリーにおいて、過去に出現した局面とその評価値をキャッシュしたものです。異なる手順で同じ局面が再び出現した場合、その局面の値はテーブルから取得され、その局面より下のゲームツリーを再検索する必要がなくなります。転置テーブルは、完全情報ゲーム（ゲームの全状態が常にすべてのプレイヤーに既知であるゲーム）において特に有用です。転置テーブルの使用は、本質的にはツリー探索にメモ化を適用したものであり、動的計画法の一種と言えます。
転置テーブルは通常、現在の盤面位置をハッシュインデックスとしてエンコードするハッシュテーブルとして実装されます。ゲームツリーで発生しうる局面の数は、探索深度の指数関数であり、数千から数百万、あるいはそれ以上になることもあります。そのため、転置テーブルは利用可能なシステムメモリの大部分を消費する可能性があり、通常、ゲームプログラムのメモリ使用量の大部分を占めます。
ゲームプレイプログラムは、ゲームの次の数手で発生する可能性のある何百万もの局面を分析することによって機能します。通常、これらのプログラムは深さ優先探索に似た戦略を採用しており、これまでに分析したすべての局面を追跡しません。多くのゲームでは、特定の局面に到達する方法は複数あります。これらは転置と呼ばれます。[ 1 ]たとえば、チェスでは、 1. d4 Nf6 2. c4 g6 (代数式チェス記法を参照)の手順には、どちらのプレイヤーも手順の順序を入れ替えることができるため、4 つの転置が可能です。一般に、n手後には、可能な転置の上限は ( n !) 2です。これらの多くは不正な手順ですが、それでもプログラムが同じ局面を複数回分析することになる可能性はあります。
この問題を回避するために、転置テーブルが使用されます。転置テーブルとは、一定の深さまで解析された各位置のハッシュテーブルです。新しい位置に遭遇すると、プログラムはテーブルをチェックして、その位置が既に解析されているかどうかを確認します。これは償却定数時間で迅速に実行できます。既に解析されている場合は、テーブルにはその位置に以前割り当てられた値が格納されており、この値が直接使用されます。解析されていない場合は、値が計算され、新しい位置がハッシュテーブルに入力されます。
コンピュータが検索する位置の数は、多くの場合、システムが動作するメモリ容量を大幅に超えるため、すべての位置を保存することはできません。テーブルがいっぱいになると、使用頻度の低い位置が削除され、新しい位置のためのスペースが確保されます。このようにして、転置テーブルは一種のキャッシュとして機能します。
転置テーブル参照によって節約される計算量は、単一の位置の評価だけにとどまりません。実際には、サブツリー全体の評価が回避されます。そのため、ゲームツリーの浅い階層にあるノードの転置テーブルエントリは、より価値が高く（そのようなノードを根とするサブツリーのサイズが大きいため）、テーブルがいっぱいになり一部のエントリを破棄する必要が生じた際に、より重要視されます。
転置テーブルを実装するハッシュテーブルは、転置を見つける以外にも様々な用途があります。アルファベータ枝刈りでは、最良移動に対応するノードの子を常に最初に考慮すると、検索が最速（実際には最適）になります。もちろん、最良移動を事前に知る方法はありませんが、反復深化を使用する場合、浅い探索で最良と判明した移動は良い近似値となります。そのため、この移動が最初に試されます。ノードの最良子を格納するには、転置テーブル内のそのノードに対応するエントリが使用されます。
転置テーブルを使用すると、グラフ履歴の相互作用問題を慎重に回避しないと、誤った結果が生じる可能性があります。この問題は、局面の履歴が重要となる特定のゲームで発生します。たとえば、チェスでは、キングまたはキャスリングするルークがゲーム中に動いた場合、プレイヤーはキャスリングできない場合があります。この問題に対する一般的な解決策は、キャスリング権をゾブリストハッシュキーの一部として追加することです。もう1つの例は、繰り返しによる引き分けです。与えられた局面が既に発生したかどうかを判断できない場合があります。一般的な問題に対する解決策は、転置テーブルの各ノードに履歴情報を格納することですが、これは非効率的で、実際にはほとんど行われません。
転置テーブルは、利用可能なシステムメモリによって最大サイズが制限されるキャッシュであり、いつでもオーバーフローする可能性があります。実際には、オーバーフローすることが想定されており、いつでもキャッシュ可能な位置の数は、ゲームツリーのノード数よりもごくわずか（桁違いに少ない）になる可能性があります。ノードの大部分は転置ノード、つまり繰り返される位置ではないため、潜在的な転置ノードを保持し、他のノードを置き換える効果的な置換戦略により、ツリーのサイズを大幅に削減できます。置換は通常、ツリーの深さと経過時間に基づいて行われます。ツリーの上位（ルートに近い）のノードが優先されます。これは、それらの下のサブツリーが大きく、より大きな節約につながるためです。また、より新しいノードが優先されます。これは、古いノードは現在の位置と類似していないため、それらへの転置の可能性が低くなるためです。
その他の戦略としては、主変異内のノード、ツリーの深さに関係なくサブツリーが大きいノード、およびカットオフを引き起こしたノードを保持することが挙げられる。
転置となるノードの割合は小さいものの、ゲームツリーは指数関数的な構造であるため、そのようなノードをごく少数キャッシュするだけで大きな違いが生じる可能性があります。チェスでは、複雑な中盤局面での検索時間の短縮が0～50%、終盤局面での検索時間の短縮が最大5倍に達したという報告があります。[ 2 ]