トランスポジションは、異なる手順で進んでも同じ局面へ到達する現象である。 置換表が有効に働く根拠のひとつであり、 ゲーム木を実際には単純な木ではなくグラフに近いものにしている。
たとえば、
のように、順序が違っても同じ局面になることがある。
このような合流があるため、探索では 「同じ局面を別の経路から何度も読む」ことが起こる。
もしトランスポジションを再利用しなければ、 同一局面を毎回一から読み直すことになる。 そこで、
ことで、再利用を可能にする。
説明上はゲーム木と呼ぶが、 トランスポジションがあるため、実態は有向グラフに近い。
そのため、
という二段構えで理解すると分かりやすい。
将棋では持ち駒や打つ手があるため、局面空間は非常に大きい。 一方で、合流そのものも普通に起こる。 そのためトランスポジションの再利用は重要である。
特に、
とも密接に関係する。