reversible pebbling game

可逆小石並べゲーム

計算に必要な「記憶」を、石（ペブル）の置き引きとして遊ぶゲーム。ふつうのペブリングと違い、石を取り除くのにも石を置くのと同じ条件が要る——それだけの違いで、必要な記憶量が劇的に変わる。ルール・空間の壁・時間と空間のトレードオフを、その場の全探索（厳密解）と突き合わせながら学べる。

石の数 p 4 目標 –
手数
0
同時ペブル
0
ピーク
0
上限 p
–
最小手数 M*
–

最適化パネル — 時間と空間のトレードオフ

いまの盤面について、ペブル上限 p ごとの厳密最小手数 M*(p) をブラウザ内の全探索（幅優先探索）で計算した結果。p を増やすほど手数は減り、ある p より下ではそもそも到達できない。

解説

1. ルール

盤面は有向非巡回グラフ（DAG）。頂点はひとつの計算結果、辺 u → v は「v を計算するには u の値が要る」ことを表す。頂点に石（ペブル）が載っている＝その値がいまメモリ上にある。

  • 入力頂点（破線の丸）はいつでも使える。ペブル数には数えない。
  • 置く：頂点 v の先行点がすべてペブル済み（または入力頂点）なら、v に石を置ける。
  • 取り除く：置くのとまったく同じ条件のときだけ、v の石を取り除ける。
  • 開始：盤面は空。目標：二重丸の頂点だけに石がある状態（clean）にする。
  • 制約：同時に置ける石は p 個まで。コスト：置く／取るの合計回数。

可逆性の正体。 「置く」と「取る」の条件が同じということは、ある手が合法ならその逆手も合法ということ。つまり状態遷移グラフは無向グラフになる。クリアした手順を逆から再生すれば、必ず空の盤面に戻れる。この対称性こそが「可逆」という名前の意味であり、ゲームを難しくしている当のものでもある。

ふつうの（非可逆な）ペブリングでは、石はいつでも自由に捨ててよい。ボタン「非可逆モードで試す」で切り替えて、同じ盤面がどれだけ易しくなるかを比べてほしい。

2. なぜ「取り除く」のに条件が要るのか

計算機で値を捨てる（メモリを上書きする）操作は、物理的には情報の消去にあたる。ランダウアーの原理によれば、1 ビットの消去には最低 kT ln2 の熱が出る。逆計算機（可逆計算機）はこの消去をしない設計であり、そこでは「不要になった中間結果を捨てる」ことができない。

できるのは逆計算（uncomputation）だけ——すなわち、その値を作ったときと同じ材料が揃っている状態で、作る操作を逆向きに実行して消す。「取り除くにも先行点が要る」というルールは、この物理的制約をそのまま写したものだ。

同じ構造は量子計算にも現れる。量子回路では中間結果を置いた補助量子ビット（ancilla）を、もつれを解くために必ず逆計算で戻さなければならない。「限られた ancilla で目的の値をどう作るか」は、そのまま可逆ペブリングの最適化問題になる。実際、量子コンパイラのメモリ管理はこのゲームとして定式化され、SAT ソルバで解かれている（下の文献 [5]）。

3. 空間の壁：p 個のペブルで届く距離は 2p−1

長さ n の鎖（一直線の計算）を考える。非可逆なら、石は 2 個あればどんなに長い鎖でも計算できる。ひとつ先へ進むたびに後ろの石を捨てればよい（2n−1 手）。

ところが可逆だと後ろの石を捨てられない。捨てるには、その石を作ったときの材料をもう一度揃え直さなければならない。この再構成の再帰が効いて、次の厳密な壁が生まれる。

長さ n の鎖を p 個のペブルで clean 到達できる ⟺ n ≤ 2p−1。

石を 1 個増やすと、届く距離が2 倍になる。逆にいえば長さ n の鎖には ⌈log₂ n⌉ + 1 個の石が要る。第2章のステージで、この壁のちょうど内側と外側を体験できる。

境界ぴったり（n = 2p−1）での厳密最小手数は次のとおり。石が 1 個増えるたびに距離は倍になるが、手数は約 2.7 倍に膨らむ——これが可逆計算に固有の代償である。

p123456
鎖の長さ n = 2p−112481632
最小手数 M*(n, p)1392571193

※ この表は横山研究室の厳密 BFS エンジンで計算した確定値。

4. 最適化：時間と空間のトレードオフ

可逆ペブリングの面白さは、ぎりぎりの石で解くと手数が爆発するところにある。長さ 8 の鎖の厳密最小手数を、ペブル上限ごとに並べるとこうなる。

上限 p34567
M*(8, p)到達不能25211917

石 4 個は使える最小だが、そのぶん 25 手かかる。石を 3 個足せば 17 手で済む。上のグラフ（最適化パネル）は、遊んでいる盤面についてこの曲線をその場で描いている。

最適戦略の骨格：中点で二分する

長さ n の鎖を p 個で解く定石は、Bennett の再帰スケジュールである。

  1. 中点 m = n/2 まで、石 p−1 個で clean 到達する（m に石が 1 個残る）。
  2. その石を土台にして、m から終点 n まで残り p−1 個で clean 到達する。
  3. 最後に、手順 1 を逆再生して中点の石を取り除く。

「逆再生してよい」のはルールが可逆だからで、ここで可逆性が制約から道具に反転する。到達距離が R(p) = 2R(p−1)、すなわち 2p−1 になるのはこの二分に由来する。手数のほうは手順 1 を 2 回払うため M(p) ≈ 2M(p−1) + M(p−1) 的に膨らみ、上表の 1 → 3 → 9 → 25 → 71 → 193 という増え方になる。

遊びかたのコツ。 まず「最適手順を再生」で答えの形を見て、次に自力で同じ手数を出せるか試す。「ヒント」は最短手順に沿った次の一手を緑で示す（現在の盤面から数え直すので、寄り道した後でも使える）。

自分で動かして確かめる

盤面の下の操作パネルで、石の数と目標の位置をその場で変えられる。どのステージでも、自由モードでも使える。

  • 石の数 p の − / ＋（キーボードの - / + でも可）。押すたびに M* とトレードオフ曲線が引き直される。石を1個増やすと手数がどれだけ落ちるかを、盤面を変えずに比べられる。減らしたとき、いままでの手順が新しい上限を超えていなければ、そのまま続きから遊べる。
  • 目標「盤面で選ぶ」を押してから頂点をクリックすると、そこが新しい目標になる。長さ20の鎖で目標を頂点12にすれば、長さ12の鎖とまったく同じ問題になる。木やピラミッドでは、部分計算だけを取り出して解くことになる。

灰色の頂点について。 目標を手前に移すと、その先の頂点が灰色になって触れなくなる。これらは目標の祖先ではない＝目標の計算に寄与しない頂点であり、石を置いても終わりまでに必ず取り除くことになって、手数もペブルも損をするだけだからである。伏せても p_min と M* は変わらない。

おすすめの実験を3つ。

  1. 崖を探す。 ステージ 3-6（長さ16・石5個）で ＋ を1回押すと71手が51手に落ちる。もう1回押しても49手にしかならない。効くのは最初の1個だけだと分かる。
  2. 壁を動かす。 自由モードで長さ20の鎖を出し、石5個のまま目標を頂点16 → 17と動かす。16までは届き、17で届かなくなる（2⁵⁻¹ = 16）。
  3. 部分問題に分ける。 ピラミッド（高さ4）で目標を中段の頂点に移すと、必要な石が減る。全体を一度に作らず途中で区切れば安く済む——Bennett の再帰スケジュールがやっているのは、まさにこれを再帰的に行うことである。

なぜ「最適」を求めるのが難しいか

石の置き引きを総当たりすると状態数は頂点数に対して指数的に増える。実際、可逆ペブリングの最適値を求める問題は PSPACE 完全であることが知られている（文献 [4]）。このページの全探索が小さな盤面に限られているのはそのためだ。

5. 木・ピラミッドではどうなるか

鎖は一直線だが、実際の計算 DAG は枝分かれする。第4章のステージでは完全二分木とピラミッドを扱う。

  • 完全二分木（葉が入力、根が目標）：高さ h に必要な石は h + Θ(log* h) 個であることが Královič によって示されている（文献 [3]）。log*（反復対数）が出てくるのが面白いところで、鎖の log とはまた違う挙動をする。
  • ピラミッド：標準ペブリングの古典的な難例。可逆にすると必要な石がさらに増える。

非可逆ペブリングでは「切断（cut）が細ければフロンティア DP が効く」という直観が使えるが、可逆ではこれが成り立たない。取り除くのにも先行点条件があるため、最適手順は切断に沿って進まないからである。この点が、可逆ペブリングの厳密解析を難しくしている。

6. 出典と、もっと知りたい人へ

このゲームのルールは、横山研究室の厳密 BFS エンジン revpebble.py のモデル（clean reachability reversible pebbling game）と一致させてある。表示している M* と p_min は、同エンジンが出す確定値と同じものをブラウザ内で計算したものである。

  1. C. H. Bennett. Time/Space Trade-Offs for Reversible Computation. SIAM Journal on Computing 18(4), 1989.
    doi:10.1137/0218053
  2. E. Knill. An analysis of Bennett's pebble game. 1995.
    arXiv:math/9508218
  3. R. Královič. Time and space complexity of reversible pebbling. RAIRO – Theoretical Informatics and Applications 38(2):137–161, 2004.
    doi:10.1051/ita:2004008
  4. S. M. Chan, M. Lauria, J. Nordström, M. Vinyals. Hardness of Approximation in PSPACE and Separation Results for Pebble Games. FOCS 2015.
    doi:10.1109/FOCS.2015.36
  5. G. Meuli, M. Soeken, M. Rötteler, N. Bjørner, G. De Micheli. Reversible Pebbling Game for Quantum Memory Management. DATE 2019.
    doi:10.23919/DATE.2019.8715092
  6. J. Blocki, B. Holman, S. Lee. The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs. TCC 2022.
    doi:10.1007/978-3-031-22318-1_3

南山大学 横山研究室では、鎖の可逆ペブリングについて厳密最小手数 M*(n, p) の構造定理を定理証明系 Lean 4 で機械検証する研究を進めている。