Source of ゾブリストハッシュ

  # ゾブリストハッシュ

ゾブリストハッシュは、局面を固定長の整数値へ高速に写像するハッシュ方式である。
[置換表](/shogi/shogiwiki/search/transposition-table/)や局面再訪判定で広く使われる。

## 概要

局面をハッシュ化する目的は、

- 同一局面を高速に識別する
- [置換表](/shogi/shogiwiki/search/transposition-table/)のキーにする
- [千日手](/shogi/shogiwiki/search/repetitions/)などの反復局面を検出する

ことである。

ゾブリストハッシュでは、局面の各特徴に乱数を割り当て、
それらを XOR して局面キーを作る。

将棋では少なくとも、

- 盤上の駒配置
- 手番
- 持ち駒

をハッシュに含める必要がある。

## 差分更新できるのが強み

XOR は同じ値をもう一度 XOR すると元に戻るので、
指し手ごとに全局面を作り直さなくてもよい。

たとえば駒が移動したら、

- 元の位置の駒キーを外す
- 先の位置の駒キーを足す
- 手番キーを反転する

といった差分更新で済む。

## 実装例

```cpp
uint64_t zobrist[PIECE_NB][SQ_NB];
uint64_t sideKey;

uint64_t computeHash(const Position& pos) {
    uint64_t key = 0;

    for (Square sq = SQ_11; sq <= SQ_99; ++sq) {
        Piece pc = pos.pieceOn(sq);
        if (pc != NO_PIECE) {
            key ^= zobrist[pc][sq];
        }
    }

    if (pos.sideToMove() == WHITE) {
        key ^= sideKey;
    }

    return key;
}
```

差分更新は次のようになる。

```cpp
key ^= zobrist[piece][from];
key ^= zobrist[piece][to];
key ^= sideKey;
```

将棋では持ち駒の増減や成りもハッシュ更新に含める必要がある。

## 衝突

ハッシュなので、異なる局面が同じキーになる衝突は理論上避けられない。
そのため実装では、

- 64 bit を使う
- 部分キーではなくフルキーも照合する
- 置換表で key を保存する

といった対策を取ることが多い。

## 将棋AIでの注意点

将棋ではチェスと違って持ち駒があるので、
その分ハッシュ設計が少し複雑になる。
また、

- 打つ手
- 成る手
- 千日手

もあるため、差分更新のバグが起きやすい。

## 関連項目

- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [トランスポジション](/shogi/shogiwiki/search/transposition/)
- [千日手](/shogi/shogiwiki/search/repetitions/)

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

- [Chessprogramming Wiki: Zobrist Hashing](https://www.chessprogramming.org/Zobrist_Hashing)
- [Chessprogramming Wiki: Transposition Table](https://www.chessprogramming.org/Transposition_Table)
ゾブリストハッシュ zobrist-hashing
