同じ入力には同じ返事。非決定を記録せず、最初から持ち込まない
Same input, same reply: we don't record nondeterminism, we never let it in
D12-3-T23-same-input-same-output・技術・日本語入力でプレイする仕組み
同じセーブから、同じ日本語を入力すれば、必ず同じ台詞が返る。
今日、190 行の台本を Windows と Linux で 3 回ずつ流し、出力 2,367 行の md5 が全部そろいました（改行コードの違いを除いて）。
『霧走町 流氷に眠る』の判定は、入力された日本語を、書き下ろした証言のどれに当てるかを決めるだけです。
遊んでいる間に文章は作りません。
その判定を「同じ入力に同じ出力」にしておくと、回帰テスト・セーブ・ブラウザ版のサーバ・AI に遊ばせる検査が、全部同じ土台に乗ります。
今日はその作り方です。
この回の位置と、前後の回#
区切り: T03〜T24 日本語入力を解いて返すまで（22 回のうち 21 回目）
先に読むとよい回: T07（同じベクトルを出す ONNX Runtime）
次に読む回: T24（セーブとデータの指紋）
名前 — deterministic replay#
- 正式名
- deterministic replay（決定的な再実行）。よく並べて呼ばれるのが record and replay（記録と再生）
- 略称
- record and replay は R&R と書かれることがある
- 日本語
- 決定的再生、記録再生、リプレイデバッグ
- 初出・代表
- record and replay の古典は LeBlanc & Mellor-Crummey, "Debugging Parallel Programs with Instant Replay"（IEEE Transactions on Computers C-36(4), 1987）。ゲームの側では、入力だけを送り合って全員が同じ計算をする deterministic lockstep の解説として Bettner & Terrano, "1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond"（GDC 2001）がよく引かれます
先に書いておくと、うちがやっているのは record and replay ではありません。
非決定な出来事を記録して再生するのではなく、非決定そのものを持ち込まない作りです。
その違いを、一般の解説のあとで書きます。
record and replay とは#
並列のプログラムは、同じ入力でも毎回違う動きをします。
スレッドがどの順で共有の値に触ったか、いつ割り込みが来たか、いつ時計を読んだか。
バグが一度出ても、もう一度は出ない。
record and replay は、実行中にその非決定な出来事を記録しておき、再生のときにログから同じ出来事を戻して、同じ実行を作り直す方法です。
LeBlanc と Mellor-Crummey の Instant Replay は、出来事のデータそのものではなく、共有の対象に触った相対的な順序だけを記録しました。
データを全部残すより記録がずっと小さく、順序さえ同じなら、同じ値が同じように流れる、という考え方です。
この流れで記録の対象になるのは、ふつう次のものです。
- スレッドの切り替わりと、共有のメモリに触った順
- 時刻（gettimeofday など）
- 乱数の種
- 外からの入力（キー・ネットワーク・ファイル）
- システムコールの戻り値とシグナル
よく知られた弱点は二つあります。
記録の重さ（実行が遅くなる・ログが大きくなる）と、記録していなかった非決定です。
記録の対象から漏れた出来事が一つあると、再生は途中から本物とずれます。
ゲームの deterministic lockstep#
ゲームを作る人には、こちらの方がなじみがあるかもしれません。
Bettner と Terrano の記事は、Age of Empires の対戦の通信の作りを書いたものです。
各ユニットの位置・状態・向き・ダメージを送ると、28.8 kbps のモデムでは動かせるのは 250 体ほどになる、という見積もりから出発し、プレイヤーの入力（命令）だけを送り合って、全員が同じシミュレーションを同じ順に回す方式を採りました。
この方式は、全員の計算が 1 ビットもずれないことを前提にします。
ずれれば、ある時点から全員の世界が別物になる（desync）。
よく問題になるのは、浮動小数点の計算がコンパイラ・最適化・CPU で変わること、ハッシュ表の走査順、未初期化のメモリ、乱数の種の配り忘れです。
record and replay は非決定を記録して戻す。lockstep は非決定を入れずに入力だけを持つ。
うちは、後者に近い立場です。
うちの約束#
アーキテクチャの文書の「決定論」の節は、短くこう書いています。
乱数を一切使わない。同じセーブ状態と同じ入力列からは、必ず同じ出力になる。
守り方を、非決定の入り口ごとに書きます。
- 乱数。核（core/ の 20 ファイル）に乱数は一つもありません。同じ問いの 2 回目に別の言い回しを返すのも、乱数ではなく回数です。
- 時刻。判定の経路で時計を読みません。ゲームの中の時間帯（timeOfDay）はセーブの中の状態で、壁の時計とは無関係です。
- 並び。フラグは std::set、回数の表は std::map で持ち、並びは常に鍵の順です。意図の候補は、作品データを読んだ順の配列を前から走査します。
- 並列。CLI の推論は ONNX Runtime のスレッド数を 1 に固定しています。
- 隠れた状態。進行に関わる値を全部セーブに書き、セーブから全部を戻します。
5 番が、いちばん踏みやすい所でした。AdvSession.hpp の saveState の終わりの部分です。
J["turnCount"] = TurnCount;
// 聞き返しの文言を巡回させる回数。保存しないと 1手1プロセスの agent では毎手先頭へ戻り、
// 連続 Session（play/replay）と同じ入力列でも返す文章が変わる（Codex 07 R6・09/05/04 B-3）。
J["f1AskCount"] = F1AskCount;
J["f1NoCount"] = F1NoCount;
return J.dump();
聞き返しの言い回しは、何回目かで巡回させています。
その回数をセーブに入れていなかったころ、1 手ごとにプロセスを立て直す口（agent）だけ、毎回 1 本目の言い回しに戻っていました。
乱数は使っていないのに、同じ入力列で返す文が変わる。
record and replay の言葉で言えば「記録していなかった状態」です。
うちは記録の代わりに、セーブの欄を足して塞ぎました。
候補の選び方にも、決定のための書き方があります。AdvMatcher.hpp です。
Cd.Score = Cd.Cos + Cd.Bonus - Cd.Penalty;
Cands.push_back(Cd);
if (!Best || Cd.Score > BestRank)
{
Best = It;
BestRank = Cd.Score;
BestPenalty = Cd.Penalty;
}
採用する候補（Best）は、厳密に大きいときだけ入れ替えます。
点が完全に同じなら、先に読んだ意図が残る。どのコンパイラでも同じ答えになります。
実測#
今日（10 月 29 日）、同じ台本を流して確かめました。
台本は作品の回帰テストの 1 本で、移動 26・話しかけ 26・発話 78・期待の検査 52 などを含む 190 行です（全三章ぶんなので中身は写しません）。
Windows（MSVC）の adv-sim で 3 回。
3 回とも出力は 2,367 行・203,951 バイトで、md5 は 3e6d43d7… の 1 種類でした。1 回 1.65〜1.75 秒です。
Linux（WSL の Ubuntu 24.04・GCC 13.3.0）でビルドした adv-sim で 3 回。
3 回とも md5 は e1c131ad… の 1 種類で、2,367 行・201,584 バイト。
バイト数の差 2,367 は、Windows の行末の CR です。Windows の出力から CR を除くと、md5 が e1c131ad… で一致しました。
この出力には、候補ごとの点数が小数 3 桁で並んでいます。
照合の点数・聞き返しの判定・立ったフラグ・手帳の一文まで、二つのコンパイラと二つの ONNX Runtime（Windows は UE 同梱の DLL、Linux は配布物の 1.24.1）で、表示の上では同じでした。
1 手 1 プロセスの口でも見ました。
新しく始める → 港へ → 佐伯に話しかける → 「ゆうべ、何時までどこにいたんですか」、の 4 手を 2 回。
セーブの違いはログの置き場の欄だけ、返事の違いもログの置き場だけでした。
決定でないものは、ログにだけ置く#
ログの行は 2 回で違いました。
違ったのは、書いた時刻（秒）と、入力の解析にかかった時間（inputAnalysis.millis。0.262 と 0.27）だけです。
解析時間は、core の中で唯一時計を読む所です。AdvInput.hpp から写します。
const auto T0 = std::chrono::steady_clock::now();
…
R.analysis = AnalyzeInput(Request.original, *Request.locale, Request.policy, Request.entityAliases);
R.millis = std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - T0).count();
この値は運営のログ（BuildAgentLogRecord）にだけ載り、返事（BuildAgentResponse）とセーブには入りません。
解析の結果そのものは時刻に触らないので、判定は揺れません。
決定でないものを、決定に効かない欄へ隔離する、という扱いです。
ブラウザ版のログに付ける sessionId も乱数ですが、ログの並べ替えにしか使いません。
決定を検査に組み込む#
「同じになるはず」は、検査にしないと守れません。
adv-sim の notebook は手帳の不変条件を見るサブコマンドで、その中に二つ入れてあります。
- N4: 同じ台本を 2 回流し、手帳の件数と各行が一致すること
- N8: セッションを 1 つ使い回す口（serve＝ブラウザ版のサーバ）と、1 手ごとに作り直す口（agent）で、毎手のセーブ・観測の状態・返事の JSON が文字列として一致すること
N8 の芯です（main.cpp）。
if (SaveA != SaveB) { Fail("N8", Where + " でセーブが食い違う"); break; }
if (EvalA != EvalB) { Fail("N8", Where + " で観測状態が食い違う"); break; }
if (OutA != OutB) { Fail("N8", Where + " で応答が食い違う"); break; }
serve は、1 つのセッションをいろいろな人のセーブで作り直しながら使います。
前の人の手の残りが次の人に漏れたら、ここで落ちます。
今日の結果は 0 error(s)・serve-turns=131 でした。
名前どおりでない所 — deterministic replay#
deterministic replay としては △ です。
record and replay は、非決定な実行を記録して戻します。
うちは非決定を記録しません。そもそも判定に入れない。
いちばん近いのは lockstep の考え方で、持ち回るのは「状態（セーブ）と入力の列」だけです。
adv-sim には replay というサブコマンドもありますが、凍結したプレイのログから入力の列だけを取り出し、今のビルドへ流し直して記録を作り直すものです。
ログの出来事を戻すのではなく、入力からもう一度計算し直す。名前は replay でも、中身は再実行です。
もう一つ、「同じ出力」は表示の上での一致です。
点数は小数 3 桁で表示した値で比べていて、double のビットまでは比べていません。
埋め込みのベクトルがバイトまで一致するかは、別の検査（embedcheck）で見ています（T07）。
弱点と、採らなかった案 — deterministic replay#
弱点を三つ書きます。
一つ目は、並べ替えの安定性です。
候補の一覧は std::sort で点の高い順に並べていて、std::sort は安定ではありません。
点が完全に同じ候補が二つあると、2 位と 3 位の並びは標準ライブラリの実装しだいで、MSVC と GCC で変わりえます。
採用する 1 位は上の書き方で決まるので変わりませんが、ログに出る 2 位以下の並びは保証していません。
std::stable_sort にするか、点が同じときに意図の id で並べれば消せます。
二つ目は、UE の推論のスレッド数です。
アーキテクチャの文書は「ONNX Runtime も SetIntraOpNumThreads(1) で固定してある」と書いていますが、ソースを見ると、それは CLI の経路だけでした。
UE の NNE（NNERuntimeORTCpu）の経路には、スレッド数の指定がありません。
UE 側は起動のたびに、焼いたベクトルと実行時の計算を 1 文で突き合わせ、ずれたらエラーを出しています。けれど、スレッド数で結果が揺れないことを UE の上で確かめたわけではありません。
三つ目は、データです。
同じ入力に同じ出力、は同じ作品データの上での話です。
言い換えを 1 本足せば、同じ入力が別の意図に着地しうる。
セーブがどのデータの上で作られたかを確かめる仕組みは、次の回（T24）で書きます。
採らなかった案です。
- 種を固定した乱数で、返事に揺らぎを持たせる。種をセーブに入れれば決定にはできます。ただ、同じ問いにどの言い回しが返るかを作者が台本で決められなくなる。巡回の回数で十分でした。
- 推論を複数スレッドにして速くする。1 手は 20 ms 台なので、速さより揺れないことを採りました。
- 非決定を記録する record and replay の仕組みを入れる。持ち込まなければ記録は要りません。
同じ問いに、同じ答え。
推理のゲームでは、それが「証言が変わらない」ということでもあります。
検索語#
deterministic replay
record and replay debugging
Instant Replay LeBlanc Mellor-Crummey
deterministic lockstep
港で佐伯に、同じことを二度聞いてみてください。第一章はブラウザで、プロフィールのリンクから試せます。