Qhapaq Lab

ゾブリストハッシュ

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

概要

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

  • 同一局面を高速に識別する
  • 置換表のキーにする
  • 千日手などの反復局面を検出する

ことである。

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

将棋では少なくとも、

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

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

差分更新できるのが強み

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

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

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

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

実装例

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;
}

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

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

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

衝突

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

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

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

将棋AIでの注意点

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

  • 打つ手
  • 成る手
  • 千日手

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

関連項目

参考にしたホームページ