効率的にツイスティパズルの結果を保存する方法の探求

こんにちは。TIG DXユニットの王紹宇です。
夏の自由研究ブログ連載2022の第9本です。

2021年のクリスマスで発表したフューチャー Advent Calendar 2021の記事に、汎用的にパズルのソルバーを実装してみた話がありました。今回は、それの後編として、パズルの解をどう効率的に保存する方法についての検討です。
まだ完全なプログラムまでは作り出していないですが、現時点の思考を記録しておきたく、有志者の意見や指摘をいただけると助かります。

前篇の振り返り

以下は、汎用パズルのソルバーについて前回の記事の要点を簡単にまとめます。

パズルのデータ構造定義
- 状態の表現
  - 任意のツイスティパズルを、各ピースに順序をつけて、それぞれのピースの色を1次元の配列で表現すれば、状態が表すことが可能
- 操作の定義
  - ツイスティパズルの1操作は、複数個のピースの入れ替わる操作で表現でき、その入れ替りが群論の置換(permutation)の概念と同様に、1次元の配列での表現が可能
ソルバーのアルゴリズム
- 「状態Aから状態Bにどんな操作の組み合わせで辿り着けるの？」というグラフのパス探索問題にとなる
- 以下の探索のテクニックが応用できる
  - ヒューリスティック
  - 双方向探索
  - 2-phase(もしくはn-phase)のゴール設定（前篇の記事に言及していないが、最短パスにこだわらない時に有効）

今回の課題

前述要約のとおりに、具体的なパズルの問題インスタンスを解くには、ブルートフォース的な探索には、CPUとメモリのコストがやや高いです。仮に全く同じ問題でも、2回目で同じような手続きを繰り返さなければならなくて、計算リソース(≒時間と電力)の浪費になりますね。
せっかく1回問題を解いたら、その答えを記録して、次回以降は直接にそのレコードを活用できるように、キャッシング技術が一般的にな対策として考えられます。つまり、自分あるいは他人の計算した結果をチートシートに保存しておいたら、次回以降は同じ計算が省けて、チートシートから引いたほうがもっと効率的ではないでしょうかね。

具体的に下図のように、2×2×2のルービックキューブの1つのランダムの状態（OWGGYOYYROGBBWOGWRWRBRYB）から初期状態（WWWWOOGGRRBBOOGGRRBBYYYY）に戻す操作手順はなにかという問題に、答えはたくさんあるかもしれないが、その1つは（U L U2 R F' U' B2 U' L U）です。

　　 🟫⬜ 　　 　　    →    　　 ⬜⬜
　　 🟩🟩 　　 　　    →    　　 ⬜⬜
🟨🟫 🟨🟨 🟥🟫 🟩🟦    →    🟫🟫 🟩🟩 🟥🟥 🟦🟦
🟦⬜ 🟫🟩 ⬜🟥 ⬜🟥    →    🟫🟫 🟩🟩 🟥🟥 🟦🟦
　　 🟦🟥 　　 　　    →    　　 🟨🟨
　　 🟨🟦 　　 　　    →    　　 🟨🟨

そこに保全しなければならない情報は、1)問題の設定（状態のOWGGYOYYROGBBWOGWRWRBRYB）と2)問題の解（操作のU L U2 R F' U' B2 U' L U）ですね。初期状態は固定値なので、保存する必要はありません。

ただし、そこに状態数爆発の問題があります。2×2×2のルービックキューブのすべての可能な状態の数は、8! * 3^7 / 24 = 3,674,160 (参考Wikipedia)があります。100万レベルですが、それはまだ少ないほうです。一般的な3×3×3のルービックキューブなら、8! * 3^7 * 12! / 2 * 2^11 = 43,252,003,274,489,856,000 ≒ 4.3*10^19の状態数もあります。1状態とその回答のペアが仮に50バイトの容量がかかるとすると、全可能な状態に対して、2.1*10^21バイト（2.1ゼタバイト）も必要ですね。それは全インターネットのデータ総量と同じ単位になります！（CNET Japanによると、2020年全インターネットの情報量は59ゼタバイトである¹）

つまり、ある程度の難しさを超えたパズルにおいて、可能な状態数の解を全部保存しておくことが非現実であることです。それが分かった上で、今回の課題は、限られたストレージ容量（個人PCでも、普通のサーバでも、高々数GBレベル程度）をいかに活用して、できるだけ効率的に多くのケースをカバーできる仕組みを探求することです。

解決案

たまたま十年前の大学時代のセキュリティに関する授業に少しだけ触れた「レインボーテーブル」の概念が頭に浮かんできました。

レインボーテーブル (rainbow table)とは

レインボーテーブル (rainbow table) は、ハッシュ値からパスワードをクラックする攻撃に使われているデータ構造です。Wikipediaでは、ハッシュから平文を得るために使われるテクニックの一つである。特殊なテーブルを使用して表引きを行うことで、時間と空間のトレードオフを実現している²と説明しています。具体的な仕組みの紹介はWikipedia²に割愛しますが、以下は自分の理解したポイントをまとめます。

一般的な辞書攻撃は、総当たり攻撃の結果を辞書として保存しておいたら、効率化できる（事前計算）が、事前計算の結果が膨大になるので、辞書を保存するのに記憶媒体の容量的に厳しい
レインボーテーブルは、事前計算の結果を大量のチェインに保存するが、1つのチェインに対して、頭の要素と末尾の要素、2個のみ保存すればOK、チェインの中間の要素は、コストの低い計算で復元できる
チェインは、平文とハッシュ値を交互に繰り返すの構造となる（平文1、ハッシュ値1、平文2、ハッシュ値2、……）
チェインの長さmは、任意で設定可能で、m個の平文とそれらに対応するm個のハッシュ値の情報は、2個の平文のみ保存することで、ストレージの効率はm倍になる
平文1 → ハッシュ値1の計算はハッシュ関数で、その次のハッシュ値1 → 平文2の生成する関数は「還元関数」(reduction function) と呼ぶ
還元関数は任意で選定してもよいが、なるべく均一で、コンフリクトが少ない（ランダムの特性をもった）ほうが望ましい

時間と空間のトレードオフ、または、時間と記憶域のトレードオフは、コンピュータサイエンスでよく出てくる話題ですね。

レインボーテーブルは、時間と空間のトレードオフの程度がパラメータで調整できることの優れたポイントだと理解しています。
極端にチェインの長さmは1に設定すると、完全な辞書テーブルに退化し、時間効率が最大になり、空間消費量も最大です。
チェインの長さmは、可能な状態数と同じに設定すると、それは完全なブルートフォース探索に退化し、事前の計算も不要ですし、空間もほぼ不要で、その代わりに時間の効率が一番悪いです。適切なチェインの長さmを調整すれば、許容できる範囲の時間と空間のバランスが取れるでしょう。

レインボーテーブル攻撃に対して、ソルト (salt) を使うのが有効な対策で、セキュアな認証認可のフレームワークを使えば心配はないでしょう。
では、なぜわざわざその途方もない古い技術を紹介するのか、今回のパズルの課題にどんな関連性があるのかを説明します。

パズルとの関連性

レインボーテーブルの応用はハッシュ関数のクラックですが、ハッシュ関数の特性と似ている他の方面にも応用できるではないかと思います。

ハッシュ関数は以下の特性を持っています。

ある平文から生成したハッシュ値は常に同じでなければならない（決定性）
平文からハッシュ値を求めるには手順とおりに実施すればよい（低コスト）
逆にハッシュ値から平文を推測することが難しい（原像計算困難性）

上記の文脈から、「ハッシュ値」を「パズルの問題（あるばらした状態）」「平文」を「パズルの解（操作手順）」と読み替えたら辻褄が合う感じはしませんか。

パズルは、初期状態（前述2×2×2ルービックキューブの例WWWWOOGGRRBBOOGGRRBBYYYY）からスタートし、特定の操作手順（U L U2 R F' U' B2 U' L U）を実施したら、必ず決定した状態（OWGGYOYYROGBBWOGWRWRBRYB）になる（決定性）
初期状態から手順とおりにシミュレートすれば、結果の状態が簡単に分かる（低コスト）
（単純なパズルは除く）あるランダムも状態から、どのような手順で復元できるかは単純ではない（原像計算困難性）

そして、パズルを解くには、ブルートフォース的に探索する過程は、ハッシュ値から平文を探す過程と似ていますね。

その関連性を踏まえて、今回の膨大な計算結果は保存しきれない問題をレインボーテーブルの思想で解決してみましょう。

パズルのレインボーテーブル

2×2×2のルービックキューブを例とします。
3,674,160状態を全通り計算するのに、1秒10個程度で換算すれば、4日間もかかってしまうので、インクリメンタルに表を埋めていく形式を採用しましょう。つまり、あるランダムの状態が与えられたら、まずはレインボーテーブルを引いて、あたったら終了、なければ従来の探索計算を実施し、その結果をレインボーテーブルに記録します。

チェインの長さmを適当に1000と設定すると、チェイン間の衝突がほぼない理想の場合、3674160 / 1000 ≒ 3674個のチェインならほとんどのケースはカバーできます。

分かりやすいように、一般的なハッシュ値を保存するレインボーテーブルの1つのチェインが下記のような平文とハッシュ値を交互に繰り返す構造です。実際に保存された値は(平文1, 平文1001)のペアのみです。レインボーテーブルは多数のチェイン（平文の頭と末尾のペア）から構成します。ここのH()は、ハッシュ関数で、R_x()は還元関数のx個目です。還元関数は予め設定する必要がありますが（後述あり）、簡単に「チェイン構造を維持するため、ハッシュ関数から他の無関係の平文にマッピングする関数である」と理解すれば良いです。

平文1
  ↓ H()
ハッシュ値1
  ↓ R_1()
平文2
  ↓ H()
ハッシュ値2
  ↓ R_2()
(...省略...)
  ↓ h()
ハッシュ値999
  ↓ R_999()
平文1000
  ↓ h()
ハッシュ値1000
  ↓ R_1000()
平文1001

同じように、2×2×2ルービックキューブのレインボーテーブルのチェインの1つは下のような「操作手順」と「状態」なります。保存された要素は、頭操作のU L U2 R F' U' B2 U' L Uと末尾操作のL U L U' F' D B' L F' Uです。

ここのh()は、パズルの初期状態から、与えられた操作を実施したら、その結果の状態を返す関数です。ハッシュ関数と少し似ていますね。ここのr_x()は、ハッシュの還元関数と同じように、あるパズル状態からある実施手順に逆方向のマッピングする関数です。

U L U2 R F' U' B2 U' L U
  ↓ h()
OWGGYOYYROGBBWOGWRWRBRYB
  ↓ r_1()
U L' U2 R' U' L F' U F' U
  ↓ h()
ROWGWGROYGWBOWOYRYGBBBYR
  ↓ r_2()
(...省略...)
  ↓ h()
ORWOGRBWBWGYORBYGOWBYRYG
  ↓ r_999()
L F U2 L2 F2 D F' L2 B D
  ↓ h()
OBBGYOWOYRYBGBRRYGORWGWW
  ↓ r_1000()
L U L U' F' D B' L F' U

例えば、ある問題状態のインスタンスORWOGRBWBWGYORBYGOWBYRYGの操作手順を探したい場合、

まずは、結果は今のチェインにあるかどうかを判断する（すべてのチェインに対しての並行でチェック可能）
1. ORWOGRBWBWGYORBYGOWBYRYGにr_1000()をアプライして、その結果がチェイン末尾と一致するか？ →一致しないので続ける
2. ORWOGRBWBWGYORBYGOWBYRYGに順にr_999(), h(), r_1000()をアプライして、その結果がチェイン末尾と一致するか？ →L U L U' F' D B' L F' Uと一致しているので、今のチェインにあると判断できる
3. もし上のステップで一致しなければ、順にr_998(), h(), r_999(), h(), r_1000()をアプライしてチェックし続ける（以降省略）
今のチェインにあることを判明できたら、チェインの頭からh(), r_1(), h(), r_2(), …を相互にアプライし、探す対象のインスタンスORWOGRBWBWGYORBYGOWBYRYGが見つかるまで実施する。それの1個前の操作手順は最終の答えである

還元関数の選定

簡単なバージョンの還元関数は、全体で1個だけでも良いですが、データ量が多くなると、衝突する可能性が極めて高くなります（誕生日のパラドックス³）。例えば、違う2つのチェインの中間要素は、値が被ったら、それ以降のチェインの値が全部同じの値になってしまい、無駄が生じます。ご覧のとおり、それを解決する方法は、複数個の還元関数を用意して、違う場所のコンフリクトは生じても、それ以降の完全重複は避けられます。

衝突をなるべく減らし、分散性の良い関数が理想的です。既存のハッシュ関数（例えばSHA256）を生かして、その特性が満たせるかなと思います。例えば、ORWOGRBWBWGYORBYGOWBYRYGのSHA256が3bca01cb074b9d8fba2b2145c7de945df8d4be29cee1c8397d0413576c9f5654で、それをある長さでちょん切って、3bca01, cb074b9, d8fba2, …になります。それぞれmod nで具体の操作手順にマッピングすれば良いでしょう（nは可能な操作の数）

異なるバージョンの還元関数r_1, r_2, …の取得も簡単で、単純に状態文字列の末尾になにかを加えたら、SHA256の結果がだいぶ違ってきますね（ハッシュ関数の特性）。ORWOGRBWBWGYORBYGOWBYRYG1やORWOGRBWBWGYORBYGOWBYRYG2, …のSHA256の生成からスタートで良いでしょう。

もちろん、生成された手順が冗長したりするケースがあるので、それを集約化標準化する必要があります。例えば、LLが生成されたら、L2に、UUUが生成されたらU'に変換し、R'RやDDDDが生成されたら相殺します。

まとめ

もともとパスワードをクラックするブラックな技術であるが、レインボーテーブルの時間と空間のトレードオフの思想は、他の方面にも貴重な価値があると思います。
見た目関係ない領域（セキュリティとパズルソルバーの性能改善）でもつながりができて、過去勉強した知識を大事にしなければならなくて、いざに他の領域にも活躍できるかもしれません。