# トランスポジション トランスポジションは、異なる手順で進んでも同じ局面へ到達する現象である。 [置換表](/shogi/shogiwiki/search/transposition-table/)が有効に働く根拠のひとつであり、 [ゲーム木](/shogi/shogiwiki/search/search-tree/)を実際には単純な木ではなくグラフに近いものにしている。 ## 概要 たとえば、 - 先に右の銀を動かしてから歩を突く - 先に歩を突いてから右の銀を動かす のように、順序が違っても同じ局面になることがある。 このような合流があるため、探索では 「同じ局面を別の経路から何度も読む」ことが起こる。 ## なぜ重要か もしトランスポジションを再利用しなければ、 同一局面を毎回一から読み直すことになる。 そこで、 - 局面を[ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/)で識別し - 結果を[置換表](/shogi/shogiwiki/search/transposition-table/)に保存する ことで、再利用を可能にする。 ## ゲーム木との関係 説明上は[ゲーム木](/shogi/shogiwiki/search/search-tree/)と呼ぶが、 トランスポジションがあるため、実態は有向グラフに近い。 そのため、 - 木として説明する - 実装ではグラフ的な合流をハッシュで処理する という二段構えで理解すると分かりやすい。 ## 将棋AIでの位置づけ 将棋では持ち駒や打つ手があるため、局面空間は非常に大きい。 一方で、合流そのものも普通に起こる。 そのためトランスポジションの再利用は重要である。 特に、 - [反復深化](/shogi/shogiwiki/search/iterative-deepening/) - [手の並べ替え](/shogi/shogiwiki/search/move-ordering/) - [並列探索](/shogi/shogiwiki/search/parallel-search/) とも密接に関係する。 ## 注意点 - 同じ局面でも履歴依存のルール差がある場合は扱いに注意が必要 - ハッシュ衝突を完全には避けられない - repetition や千日手の判定には、単なる局面一致以上の情報が必要な場合がある ## 関連項目 - [ゲーム木](/shogi/shogiwiki/search/search-tree/) - [置換表](/shogi/shogiwiki/search/transposition-table/) - [ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/) - [千日手と反復局面](/shogi/shogiwiki/search/repetitions/) ## 参考にしたホームページ - [Chessprogramming Wiki: Transposition](https://www.chessprogramming.org/Transposition) - [Chessprogramming Wiki: Transposition Table](https://www.chessprogramming.org/Transposition_Table) - [Chessprogramming Wiki: Search TREE](https://www.chessprogramming.org/Search_Tree)