Source of 置換表 transposition-table

  # 置換表

置換表は、すでに探索した局面の結果を記録して再利用するための表である。
異なる手順から同じ局面へ到達することがあるため、
その結果を覚えておくことで探索を大きく節約できる。

## 概要

探索中には、別の指し手順から同一局面へ合流することがある。
このような局面の重複を[トランスポジション](/shogi/shogiwiki/search/transposition/)と呼ぶ。

置換表は、その局面に対して

- 何手先まで読んだか
- どの評価値が得られたか
- その値が厳密値か上限か下限か
- どの手が有望だったか

を保存する。

## 何を保存するか

典型的なエントリには次のような情報が入る。

- ハッシュ値
- 探索深さ
- スコア
- bound 種別
  `EXACT`, `LOWERBOUND`, `UPPERBOUND`
- 最善手
- 世代や age

最善手は[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)に使え、
bound 情報は[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)の枝刈りにも使える。

## ハッシュとの関係

置換表は通常、[ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/)のような局面ハッシュをキーにしたハッシュ表として実装される。
将棋では持ち駒や手番も局面の一部なので、ハッシュ値にもそれらを反映する必要がある。

## 実装例

```cpp
enum BoundType {
    BOUND_EXACT,
    BOUND_LOWER,
    BOUND_UPPER
};

struct TTEntry {
    uint64_t key;
    int depth;
    int score;
    BoundType bound;
    Move bestMove;
};
```

検索時は次のように使う。

```cpp
TTEntry* entry = probeTT(hashKey);
if (entry && entry->key == hashKey && entry->depth >= depth) {
    if (entry->bound == BOUND_EXACT) return entry->score;
    if (entry->bound == BOUND_LOWER && entry->score >= beta) return entry->score;
    if (entry->bound == BOUND_UPPER && entry->score <= alpha) return entry->score;
}
```

## 将棋AIでの役割

置換表は次の2つの役割が特に大きい。

### 探索結果の再利用

同じ局面を読み直さずに済むため、ノード数を大きく減らせる。

### 手の並べ替え強化

保存された最善手は `hash move` として最優先で試されることが多い。
これは[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)の効率に非常に強く効く。

## 衝突と置換戦略

ハッシュ表なので、異なる局面が同じ場所に入る衝突は避けられない。
そのため、

- 常に上書きする
- 深い探索結果を優先する
- 古い世代を上書きする

といった置換戦略が必要になる。

## 注意点

- ハッシュ衝突への対策が必要
- 詰み値や千日手値は保存形式を慎重に設計する必要がある
- 表の大きさ、世代管理、並列アクセスの扱いで実装差が出やすい

## 関連項目

- [探索](/shogi/shogiwiki/search/)
- [ゲーム木](/shogi/shogiwiki/search/search-tree/)
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/)

## 参考にしたホームページ

- [Chessprogramming Wiki: Transposition Table](https://www.chessprogramming.org/Transposition_Table)
- [Chessprogramming Wiki: Zobrist Hashing](https://www.chessprogramming.org/Zobrist_Hashing)
- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)
置換表 transposition-table transposition-table
