Zobrist Hash でパズルの状態管理入門 ~Rubyの例を添えて~

アドベントカレンダー

アルゴリズム

競技プログラミング

松崎令

2024年12月11日

この記事は「BEMA Lab Advent Calendar 2024」の11日目の記事です。

はじめに

allegrogiken と言うIDで日常的に AtCoder のコンテストに参加しています。コンテスト参加のモチベーションは「習慣」に近く、Programming Awareness というイメージで「スキルを鈍らせないようにする」という気持ちでやっています。

とはいえ、毎年同じことを繰り返してるだけだと面白くはありません。「毎年いくつかの新しいアルゴリズムを習得する」くらいの目標を立てておりまして、2024年はハッシュ周りをいくつか履修しました。

ハッシュ自体はWeb開発といった業務でも実用する機会が多い技術だと思いますが、世の中にはいろいろなニーズを満たすための多様なハッシュがあります。今回は、その中でもシンプルな実装ができて、ボードゲームやパズルのシミュレーションで活用できる Zobrist Hash をご紹介します。

Zobrist HashをRubyの簡単な実装で体感！

Zobrist Hash は「値の集合」に対するハッシュを得るものです。下のような手順で計算できます。

要素ごとにランダムな整数を用意して、変換テーブルを作る（値のハッシュ化）
「選んだ数をランダムな整数に変換したもの」全てをXORで繋げる

簡単なお題でイメージをつかんでみましょう。
「1から10までの数があり、この中から好きな数を好きなだけ選ぶ」ことを考えます。

この条件で選ばれた数の集合として {1} や {1, 2}, {2, 3}, {1, 2, 3} を考えてみます。
これらの集合に対して Rubyを使ったZobrist Hashの実装方法を以下に示します。

hash_1 = 1.hash
puts "hash[1] => #{hash_1}"

hash_1_2 = 1.hash ^ 2.hash
puts "hash[1, 2] => #{hash_1_2}"

hash_2_3 = 2.hash ^ 3.hash
puts "hash[2, 3] => #{hash_2_3}"

hash_1_2_3 = 1.hash ^ 2.hash ^ 3.hash
puts "hash[1, 2, 3] => #{hash_1_2_3}"

めちゃくちゃ簡単な実装です。Rubyには Object#hash という便利メソッドがあるので「ある値に対してランダムな値を用意する」代わりにこれを使うだけで済んでいます。

ハッシュは得られたが、何が嬉しい？

ハッシュが計算できたのは良いのですが、実は何が嬉しいのかよくわかりません。例えば、`1,2,3` という文字列でmd5のハッシュを取るだけでも良さそうです。

Zobrist Hash が便利なのは「ハッシュ化した状態で差分計算ができる」という点です。例えば、{1} と {2, 3} それぞれのハッシュを XOR して {1, 2, 3} のハッシュを作れます。また、 {1, 2, 3} のハッシュに {2, 3} のハッシュをXORすれば {1} のハッシュが得られます。

puts "hash[1] XOR hash[2, 3] => #{hash_1 ^ hash_2_3}"
puts "hash[1, 2, 3] XOR hash[2, 3] => #{hash_1_2_3 ^ hash_2_3}"

Rubyのコードに起こして実行した結果も貼っておきましょう。こちらで試せます

Zobrist Hashによる効率的な状態管理を「15スライドパズル」で試す！

図のような盤面の 15スライドパズルを Zobrist Hash でハッシュ化することを考えてみます。

図における左側を「初期状態」とします。まずはこの状態を Zobrist Hash でハッシュ化します。

 # 16種の数 * 16マス で 256 通りの要素が登場する
 NUM_MAX = 16
 
 # マス目 index に、数 num がある場合の要素 (0~255)
 def puzzle_hash(num, index)
   (index * NUM_MAX + num).hash
 end
 
 # 15パズルの初期盤面（空白部分を0として表現)
 grid = [
   13, 4, 1, 2,
   7, 6, 12, 3,
   0, 8, 15, 10,
   5, 9, 14, 11,
 ]
 
 # 初期盤面の Zobrist Hash
 zobrist_hash = grid
   .map.with_index { |num, index| puzzle_hash(num, index) }
   .reduce { |a, b| a ^ b }
 p zobrist_hash

盤面を「マス目Aに数Bがある」という状態の集合として表現してみます。
マス目が16種あり、マス目の中身も16種類あります。これを 16 * 16 = 256 種の状態として扱います。
日本語で状態と整数をマッピングするなら下のような表現になります。

このマッピングで得られた整数をそれぞれハッシュ化すればあとはXORするだけです。
この部分はコード上ではメソッド puzzle_hash として表現されています。

初期状態から「1マス移動」をZobrist Hashで差分計算！

このスライドパズルで「7」だけを動かすと盤面はループします。同じ盤面が現れる場合、ハッシュも同じ値になっているべきです。これを Zobrist Hash で検証してみましょう。

 # 7をマス目4から8に移動, 空をマス目8から4に移動
 swapped_hash = zobrist_hash ^
   puzzle_hash(7, 4) ^ puzzle_hash(7, 8)
   puzzle_hash(0, 8) ^ puzzle_hash(0, 4)
 p swapped_hash
 
 # 7をマス目8から4に移動, 空をマス目4から8に移動
 reswapped_hash = swapped_hash ^
   puzzle_hash(7, 8) ^ puzzle_hash(7, 4)
   puzzle_hash(0, 4) ^ puzzle_hash(0, 8)
 p reswapped_hash # 初期盤面と同じ hash が得られる

このような実装になります。（こちらで試せます）

まとめ

Zobrist Hash で15スライドパズルの盤面をハッシュ化できることを紹介しました。このハッシュを用いて「過去に見たことがある盤面を高速に判定する」ことができます。

今回は「スライドパズルを解く」までのプログラムを書いていませんが、解く場合は「同じ盤面のシミュレーションを繰り返さない」ことが重要です。Zobrist Hash を用いなくても判定すること自体は可能ですが、数回のXOR演算で差分計算できる Zobrist Hash は非常に高速なので、シミュレーションの回数を増やすことに貢献できます。

実は Zobrist Hash は元々チェスの盤面をハッシュ化する目的で考案されたものらしいので、それよりもシンプルなスライドパズルであれば余裕に扱えます。チェスよりもマス目やコマの数が多い将棋のシミュレーターにも活用されている例があります。状態を数値で表現できればなんでもハッシュ化できるのでとても便利です。

そして、そのように便利なアルゴリズムが極めてシンプルな計算で成り立つというところが個人的に好きなところです。XOR を加算・減算に変えるだけでもまた違った特徴のハッシュになり、アレンジによる幅があるのも魅力ですね。ぜひ皆さんも色々なハッシュの世界に飛び込んでみてほしいです。