クリアまでに要る手を、ゲームを動かさずに終わりから逆にたどって数える
Counting the moves needed to clear by walking back from the ending, without running the game
D18-3-T35-clearpath-backward-reachability・技術・日本語入力でプレイする仕組み
『霧走町 流氷に眠る』は、最後まで解けるかを、人が遊ぶ前に機械で確かめています。
その一つは、ゲームを 1 手も動かさず、終わりのフラグから「それを立てる手」「その手に要るフラグ」を逆にたどる道具です。全三章で 0.055 秒、要る手は 60 でした。
T01 で書いた三つの約束の三つ目、「最後まで解けるかは、人が遊ぶ前に機械で確かめる」の回です。
昨夜の T34 の lint は、作品データの規則を当てる検査でした。今日の clearpath は、その中の到達性（L2）を、クリアという一点に向けて深くしたものです。
今夜の T36 は、反対に、状態を全部歩いて確かめる道具を書きます。
この回の位置と、前後の回#
区切り: T34〜T49 確かめ方（16 回のうち 2 回目）
先に読むとよい回: T01（全体の構造と、使っている技術と言語）・T34（台本を実行せずに検査する）
次に読む回: T36（全部の状態を探す）
名前 — static reachability analysis#
- うちの名前の対照表での呼び名
- static reachability analysis（静的な到達可能性解析）
- やっていることに近い名前
- backward chaining（後ろ向き推論）・AND/OR graph（AND/OR グラフ）・delete relaxation（自動計画で、効果の打ち消しを無視する緩和）と relaxed plan（緩めた計画）
初出:
static reachability analysis・backward chaining・AND/OR graph という語の初出は、確かめられませんでした。
緩めた計画の取り出しで広く知られているのは Hoffmann & Nebel "The FF Planning System: Fast Plan Generation Through Heuristic Search"（Journal of Artificial Intelligence Research 14, 2001）です。打ち消しを無視する緩和そのものの早い例としては、McDermott（1996）と Bonet ほかの HSP（1997）が挙げられています（二次資料で確かめ、原典は読んでいません）。
一般の解説 — static reachability analysis#
static reachability analysis（静的な到達可能性解析）とは、ゲームを動かさずに、グラフの上で「ある所からある所へ行けるか」を調べることです。
- 到達可能性
グラフの上で「ある所からある所へ行けるか」を問うのが到達可能性です。
初めの所から幅優先で広げる前向き（forward）と、目当ての所から「そこへ来られる所」を逆に広げる後ろ向き（backward）があります。
プログラムの解析では「この文は実行されうるか」、モデル検査では「悪い状態に行けるか」がこの形です。
- 自動計画の言い方
ゲームの進行は、自動計画（AI planning）の言葉で書くと見通しがよくなります。
状態は「成り立っている事実の集合」。行動は、前提（precondition）と、足す事実（add）と、打ち消す事実（delete）を持ちます。
目当ての事実がそろう行動の列を探すのが計画です。
一般の計画は難しい問題ですが、打ち消しを無視すると（delete relaxation）、事実は増える一方になり、ずっと易しくなります。
前向きに「前提を満たした行動の効果を足す」を増えなくなるまで繰り返せば、ゴールに届くかが分かる（T34 の L2 と同じ不動点です）。
そこから後ろ向きに、ゴールの事実ごとに「それを足す行動」を 1 つ選び、その前提をまた同じように選んでいけば、緩めた計画が 1 本取り出せます。FF はこれを探索の手がかり（ゴールまでの距離の見積もり）に使いました。
よく知られた性質があります。
- 打ち消しを無視しているので、緩めた計画で届いても、本当に届くとは限らない
- 立て手の選び方で、取り出した計画の長さが変わる。短い方を選ぶ規則は、手がかりとしては使えても、最短の保証はない
- 前提が「どれか 1 つ（OR）」と「全部（AND）」の入れ子になるので、形は AND/OR グラフになる
うちの進行のデータ#
作品の進行は、フラグの集合です。フラグは立てたら下ろしません。
フラグを立てるのは二通りです。
- 意図の段。前提のフラグ（requires）を満たした段に当たる入力をすると、その段が sets のフラグを立てる
- 場所。入ったときに立つフラグ（enterSets）と、条件を満たして入ると起きる出来事（events。章の終わりなど）
意図には話し手がいて、その人がその場所にいる（在席）条件もフラグで書いてあります。
clearpath は、まずフラグごとに「それを立てうる手」の候補を全部集めます（Tools/adv-sim/main.cpp の BuildClearOrder）。
struct ClearSetter
{
std::string label; // "intent#段" または "場所.enter"
bool bFree = false; // 移動で自動的に立つ（手数に数えない）
std::vector<std::string> prereq; // これを立てる前に要るフラグ
std::string intentId, where, speaker, script;
int stage = -1;
};
段の候補の prereq は、意図の前提 ＋ 段の前提 ＋ その場所に入る前提 ＋ 話し手がそこにいる前提、です。
話せる場所が複数あれば、前提がいちばん少ない場所を採ります。
章が違う意図には「その章に入っている」という擬似フラグ（phase:N）を前提に足します。場所の出来事のうち、章を進めるものが phase:N を立てる手になります。
在席を辿るのは、一度落としたことがあるからです。
// **在席条件を必ず辿ること。** 2026-08-16 に手書きの解析でここを落とし、
// 「ルナは呼ばないと話せない」（call.luna → f_luna_called → presence.requires）を
// 見逃したまま鎖を 35本と数えた。人物への手は「その場所へ行ける」だけでは足りない。
（ルナは別の作品の人物です。）
そして、前提から否定を全部捨てます。
const auto Positive = [](const std::vector<std::string>& V)
{
std::vector<std::string> Res;
for (const std::string& R : V) { if (!R.empty() && R[0] != '!') { Res.push_back(R); } }
return Res;
};
この作品のフラグは下ろさないので、打ち消しの効果はもともとありません。代わりに「まだ X を聞いていない」のような否定の前提があり、フラグが増えると満たせなくなる条件はこれだけです。これを捨てると、前提はフラグが増えるほど満たしやすくなる一方になります。自動計画の delete relaxation と同じく「増える一方」の世界で考えるための緩め方で、うちの緩和はこれです。
第一章にもあります。佐伯に食い違いをぶつける意図には、「佐伯のアリバイをまだ聞いていない（!f_saeki_alibi_10pm）が、ハルの証言は持っている」ときの段があり、clearpath はこの ! の条件を見ません。
同じ意図の段は、入力の中に材料の語（ハルか番屋、と時刻）があることも求めます（requiresEntities）。これはフラグではなく入力の中身の条件なので、clearpath は見ません。
逆にたどる#
集めた候補の上を、終わりのフラグから深さ優先で逆にたどります（写す）。
std::function<void(const std::string&)> Walk = [&](const std::string& F)
{
if (Done.count(F) || Initial.count(F)) { return; }
if (Need.count(F))
{
if (!bQuiet) { std::printf("CLEARPATH: 循環している: %s\n", F.c_str()); }
return;
}
Need.insert(F);
const auto It = Out.Setters.find(F);
if (It == Out.Setters.end() || It->second.empty())
{
if (!bQuiet) { std::printf("CLEARPATH: %s を立てる手が無い（クリア不能）\n", F.c_str()); }
++Out.Missing;
…
return;
}
if (It->second.size() > 1) { ++Out.OrChoices; }
const ClearSetter* Best = &It->second.front();
for (const ClearSetter& S : It->second)
{
if (S.prereq.size() < Best->prereq.size()) { Best = &S; }
}
for (const std::string& P : Best->prereq) { Walk(P); }
Need.erase(F);
Done.insert(F);
Out.Order.push_back({ F, Best });
if (!Best->bFree) { Out.Chosen.insert(Best->label); }
};
for (const std::string& F : D.work.clearFlags) { Walk(F); }
- 立て手が複数あれば（OR）、前提の数がいちばん少ないものを選ぶ。選択肢があった所を or-choices として数える
- 選んだ立て手の前提は全部（AND）、また同じようにたどる
- たどっている途中のフラグにもう一度来たら循環、立て手が 1 つも無ければ「クリア不能」として missing に数える
- 前提を全部たどり終えてから、そのフラグを Order に積む。なので Order は、前提が先に来る順（後ろ向きの深さ優先の帰りがけ順）になる
- 移動で自動的に立つ手（bFree）は、手数に数えない
結果は 1 行の要約と、フラグごとの「どの手で立つか」の列、最後に VERDICT です。missing が 0 なら PASS で、終了コード 0。
今日の値 — static reachability analysis#
全三章のデータです。
CLEARPATH goal=f_end chain=67 steps=60 or-choices=17 missing=0
…
CLEARPATH VERDICT=PASS
鎖に載ったフラグが 67、そのうちプレイヤーの発話で立てる手が 60、選択肢があった所が 17、立て手の無いフラグが 0。0.055 秒でした。
ブラウザ版のサーバに置いている第一章までの写しでは、こうでした。
CLEARPATH goal=f_ch1_clear chain=16 steps=14 or-choices=9 missing=0
…
4. f_saeki_alibi_10pm <- saeki.alibi_night#0
5. f_hal_saeki_8pm <- hal.saeki_that_night#0
6. f_saeki_alibi_broken <- saeki.confront_alibi#1
…
CLEARPATH VERDICT=PASS
写したのは第一章のアリバイの 3 行だけです（ほかの行は第一章の決着に近いので伏せます）。
佐伯の「10時まで番屋」（4）と、ハルの「8時前に帰った」（5）の二つがそろって初めて、佐伯に食い違いをぶつける段（6）の前提が満たされる。鎖はそういう AND の積み重ねです。
--walkthrough を付けると、同じ計算から「どこで・誰に・何と言う手か」を順に並べた順路が出ます。台詞には各意図の言い換えの 1 本目を使い、照合は一切しません。なので「この文なら通る」の保証はありません。それを見るのは、台本を実際に流す play です。
同じ計算は、lint の L40（人物がクリア経路の何手目に初めて出るか・T34）と、作品の検査の design-vs-run（設計の手数 ＝ 最短の台本を実際に流した手数）でも使っています。手数は表示の行を正規表現で削らず、--stats-out の JSON で渡します。表示の書式で合否が変わる、を一度踏んだからです。
今日見つけた食い違い: 60 と 61#
全三章で --walkthrough を付けると、末尾は「計 61 手」でした。steps=60 と 1 つ違います。
調べると、1 つの段（第二章以降。名前は伏せます）が、鎖の 2 つのフラグを同時に立てていました。
- steps は、選んだ手の名前の集合（Chosen）の数なので、同じ段を 1 回と数えて 60
- 順路と L40 は、Order を並べ替えた手の列の長さなので、同じ段を 2 回並べて 61
逆算そのものは同じで、数え方が 2 つありました。遊ぶ人から見れば、その段は 1 回の入力で 2 つとも立つので、60 の方が実際に近いはずです（確かめてはいません）。
今日は、どちらを直すかは決めずに、事実だけを書いておきます。
名前どおりでない所 — static reachability analysis#
名前の対照表は clearpath を static reachability analysis と呼び、「実行を伴わない点も定義どおり」としています。実行しない、の所はそのとおりです。
ただ、ソースを読むと、名前より狭く、また別の物に近い所があります。
一つ目、到達できる状態の全部は出していません。出すのは、終わりのフラグに要る前提を逆にたどった 1 本の鎖です。全部の状態を歩くのは今夜の T36 の reach の仕事です。
二つ目、否定の前提を捨てています。delete relaxation と同じ向きの緩め方で、緩めた分だけ「届く」と言いすぎる側に寄ります。
三つ目、立て手の選び方は、前提の数がいちばん少ないものを選ぶ貪欲です。FF の緩めた計画の取り出しに近い形ですが、FF のように前向きに層を作って「早く立つ方」を選ぶのではなく、前提の数だけで選んでいます。最短の保証はありません。or-choices が 0 の作品なら、選ぶ余地がないので、この数がそのまま厳密になります。
なので、いちばん近い言い方は「AND/OR グラフ上の後ろ向き推論で、否定を無視して緩めた計画を 1 本取り出す」です。static reachability analysis は、その大きな枠の名前として使っています。
弱点と、採らなかった案 — static reachability analysis#
- PASS は「緩めた条件で、立て手の鎖が切れていない」までです。否定の前提で本当に通れない所、照合で通らない入力は、ここでは見えません。前者は reach（T36）、後者は台本を流す play と言い換えの検査（T39）で見ます
- 手数は「フラグを立てる手」の数で、入力の数ではありません。聞き返しに「はい」と答える手、言い直す手、移動は入っていません
- 最短ではありません。17 の選択肢のどれを取るかで、本当の最短は変わりえます
- 数え方が 2 つあり、今日 60 と 61 で食い違っていました（上の節）
採らなかった案:
- 最短の手数を厳密に出す。状態を全部歩けば出せますが、それは reach の重さで、0.055 秒で毎回回す道具ではなくなる
- 逆算をやめて、台本を流す play だけにする。play は「その台本が通るか」しか言わず、台本に無い道に立て手の切れ目があっても黙る。設計のデータだけから言える物を、先に安く言う方を残した
検索語#
static reachability analysis
backward chaining AND/OR graph
delete relaxation relaxed plan FF planner Hoffmann Nebel
h_max h_add heuristic search planning
第一章は 14 手の鎖です。どの順で、どう聞くかは自由です。ブラウザで無料で遊べます。プロフィールのリンクから。