定義
再帰・入れ子構造(recursion / nesting)とは、盤面の中に同じ種類の盤面が入っている状態そのものを、パズルの素材にする機構である。プレイヤーの動詞は「入る」「押す」「持ち運ぶ」といった既存のものでよい。手番ごとに変わるのは駒の位置だけではなく、どの階層のどの盤面がいま実体化しているかという入れ子の形である。ゴールへ到達すれば面は解けるが、その道筋が階層をまたぐとき、この機構が働いている。
鍵になるのは自己相似である。どの深さを覗いても同じ規則が通っている。だからプレイヤーは規則を一つ覚えるだけでよく、設計者は規則を増やさずに問題を増やせる。深さは足し算ではなく掛け算で効く。少ない語彙で状態空間を跳ね上げられる、きわめて効率のよい発明である。
初出と系譜
入れ子を自覚的にパズルへ使った最初期の例は、デジタルではなく玩具である。1883年、数学者エドゥアール・リュカがパリで売り出したハノイの塔がそれにあたる。n枚の塔の移動は、n−1枚の同じ問題二つと、最大の一枚を動かす一手に分解できる。最短手数は T(n)=2·T(n−1)+1、解けば 2ⁿ−1 となる。規則二つで自己相似を成立させた設計だった。
もっと古い系譜としてリング状の知恵の輪がある。九連環では、ある輪を外すために手前の輪をいったん戻す必要が生じる。手順が自分自身へ折り返す。どちらの玩具も「自分をひと回り小さくして呼び出す」という形を、言葉ではなく指で教えていた。
デジタルで再帰そのものを主題に据えた代表作は、2016年9月30日に Steam で公開された Recursed(Portponky)である。宝箱に飛び込むと箱の中の部屋へ入り、箱を運べば部屋ごと運べる。同じ箱でも入り直せば中身は初期状態に戻る。計算機科学でいう関数呼び出しと変数のスコープを、ジャンプアクションの語彙に置き換えた設計だった。機構としての初出をこの一作に特定することはできないが、再帰を主題とする作品として繰り返し参照されるのはここである。
変奏
2022年3月29日の Patrick's Parabox(Patrick Traynor)は、同じ入れ子を倉庫番系ブロック押しの上に載せ直した。できるのは押すことだけで、押す対象の箱の中にまた盤面が広がっている。箱を別の箱へ押し込めるし、箱を自分自身の中へ押し込むこともできる。Recursed が入れ子を縦の出入りで見せたのに対し、こちらは横の押し引きへ畳んでいる。
2023年9月29日の COCOON(Geometric Interactive)は、入れ子を身体の感覚へ翻訳した。背負った球の中が一つの世界で、球を持ち歩くことで世界の入れ子を組み替える。難度は低めに抑えられ、解けた快感より「世界ごと運んでいる」手応えが主役になる。同じ機構でも、難しさを目的にしない使い方があることを示した例である。
2021年3月2日の Maquette(Graceful Decay)は、入れ子を潜らず内と外で同時に見せる。台座の小さな模型が外の広い世界と一対一で対応し、手元の立方体が外では橋になる。入れ子にできる物は少なく、組み合わせの深さではなく尺度の比喩として再帰を使う。Maquette への反論が検証したとおり、この射程の狭さは欠陥ではなく選択である。
設計上の落とし穴
第一の穴は、深さをそのまま難しさへ変えてしまうことである。入れ子は一段増やすだけで状態空間が跳ね上がる。実際、壺(継続に相当する仕組み)を備えた Recursed の一般の面については、解けるかどうかが計算理論的に決定不能であることが証明されている(Demaine・Kopinsky・Lynch、ISAAC 2020)。作れる問題は無尽蔵でも、人が頭の中で同時に追える深さは二、三段までである。深さを足すのは簡単で、抑えるほうが難しい。
第二は、教える順序の失敗である。入れ子・自己参照・無限後退・反転は、それぞれ別の性質だ。Traynor はこれを一つずつ面に切り分けて提示した。GDC 2024 の講演で本人が語ったとおり、面は「難しくするため」ではなく「システムを見せるため」に作られている。複数の性質をまとめて出すと、プレイヤーは何が分かっていないのかを言葉にできなくなる。
第三は、詰みが読めなくなることである。階層をまたいで物を動かす機構では、取り返しのつかない一手が「どの階層で」起きたのかが分かりにくい。読める失敗が論じたとおり、詰みは起きること自体より、起きたと気づけないことが問題になる。巻き戻しの単位を階層の単位に揃えておく必要がある。
見分け方
非ユークリッド空間との違いは、繰り返しに階層があるかどうかである。Manifold Garden の世界は無限に続くが、同じ空間が平らに並んでいるだけで、内と外の関係がない。再帰は「Aの中にA」であって、「Aの隣にA」ではない。
空間接続ポータルは離れた二点をつなぐが、つないだ先が元の場所を含むとは限らない。ルール書き換えは規則そのものを動かすのに対し、再帰は規則を固定したまま盤面の奥行きだけを増やす。紛れやすいのは Maquette のような尺度ものだが、見え方だけが変わるなら視点・遠近トリック、大小が別の階層として実際に存在するなら再帰である。
さらに読む
サイト内の関連記事。機構全体の見取り図は再帰をパズルにする — Patrick's Parabox と Recursed の入れ子文法。設計者像はPatrick Traynor の哲学、動詞を入れ子にするという発想の広がりはAndrew Plotkin の「動詞が、動詞でできている」。歴史はハノイの塔(1883)。音の側からはPatrick's Parabox のサウンドトラックとCOCOON のサウンドトラック。批判的な読みはCOCOON への反論、解けない側からの体験記は解けない私が、Aliensrock さんの『Patrick's Parabox』を見た話。
サイト外の一次資料。Erik D. Demaine, Justin Kopinsky, Jayson Lynch「Recursed is not Recursive: A Jarring Result」(ISAAC 2020)は、壺を備えた Recursed が RE 完全であることを Post の対応問題からの帰着で示し、しかも 15×20 という実際の部屋サイズで成立する面を構成している。ハノイの塔の事実関係はWikipedia: Tower of Hanoi。
卓上・紙での姿
- ハノイの塔(1883) — n枚の塔を動かす問題が、n−1枚の同じ問題二つに分解される。再帰という構造を、木の杭と円盤だけで体現した最古級の玩具である。
- 九連環(バグヌーディエ) — ある輪を外すには、手前の輪をいったん元へ戻さなければならない。手順そのものが入れ子に折り返す金属パズルである。
隣接する機構
倉庫番系ブロック押し / 非ユークリッド空間 / 空間接続ポータル / 視点・遠近トリック / ルール書き換え
