決定論と固定小数点

◆エンジンの担当　この章は、エンジンの内側の話です。bot を書くだけなら、読まなくても大丈夫です。

CodeTank Arena の試合は、動画として保存されていません。

保存されているのは、シード（数字ひとつ）と bot のコードだけ。 再生するたびに、その場でもう一度計算し直しています。

これが成り立つには、条件がひとつだけあります。

同じ入力からは、どの端末でも、1 ビットも違わない同じ結果が出ること。

これを決定論といいます。このページはその話です。

なぜそこまでするのか

理由は 3 つあります。

1. リプレイが軽い。 60 秒の試合が数字の列だけで済みます。学校の回線でも配れます。

2. 巻き戻し・コマ送りがタダで手に入る。 どの瞬間からでも計算し直せるからです。

3. ずるを見破れる。 将来ほかの人と対戦するとき、 「この試合結果は本当か」を手元で計算して確かめられます。 結果が 1 ビットでも違えば、どちらかが嘘をついています。

3 番目のために、1 機種でも答えがずれると成り立ちません。 iPad でも Chromebook でも Windows でも、完全に同じでなければならないのです。

小数は、端末によって答えが変わる

いちばんの敵は小数です。

コンピュータの小数（浮動小数点数）は、四則演算と平方根までは規格で厳密に決まっています。 けれど sin や cos のような関数は、最後の桁が実装しだいです。規格は保証していません。

Chrome  の Math.sin(1.0) = 0.8414709848078965
別の環境の Math.sin(1.0) = 0.8414709848078966   ← 最後の桁だけ違う

たった 1 桁。でも 3600 フレーム積み重なれば、弾は当たるか外れるかの差になります。

だからエンジンは、小数を物理に使いません。

16.16 固定小数点

すべての位置・速度・角度を整数で持ちます。

考え方はとても簡単で、1 マスを 65536 に分けて数えるだけです。

実際の値	内部の整数
1.0 マス	65536
0.5 マス	32768
3.42 マス	224133

小数点の上に 16 ビット、下に 16 ビット。だから「16.16」と呼びます。

角度も同じです。1 周を 65536 に分けます。

角度	内部の整数
0 度（右）	0
90 度（下）	16384
180 度（左）	32768
360 度	65536（= 0 に戻る）

整数どうしの足し算・引き算は、どの端末でも完全に同じ答えになります。 これで 1 つ目の問題は消えました。

度ではなく 65536 分割なのはなぜ？

1 周を 360 にすると、90 度の 1/3 が 30 で割りきれても、 10 度の 1/3 は割りきれません。端数が出ると丸めが必要になり、丸めかたで差が出ます。

65536 は 2 の 16 乗なので、半分・4 分の 1・8 分の 1 …がすべて割りきれます。 コンピュータにとって扱いやすい数なのです。

かけ算だけは、ひと工夫いる

足し算はそのままでよいのですが、かけ算には注意が必要です。

1.5 × 2.0 を固定小数点でやると：

98304 × 131072 = 12884901888

これは「1.5 マス × 2.0 マス」ではなく、65536 倍だけ大きすぎる数です。 2 回かけたぶん、65536 が 2 回かかっているからです。1 回ぶん割り戻します。

12884901888 ÷ 65536 = 196608   ← 3.0 マス。正解

ここで、多くの人がやってはいけない書き方をします。

>> 16 を使ってはいけない

「65536 で割る」は「右に 16 ビットずらす」と同じなので、つい >> 16 と書きたくなります。

JavaScript でこれをやると壊れます。

JavaScript のビット演算は、値を 32 ビット整数に切り詰めてから実行します。 座標（最大 20 マス ≒ 131 万）と三角関数の値（65536）の積は、かんたんに 32 ビットの上限（約 21 億）を超えます。超えた分は静かに消えます。

だから Math.floor(p / 65536) と書きます。遅そうに見えますが、 2 のべき乗での割り算は誤差なく厳密なので、これで正しく、しかも全環境で同じです。

この禁止事項は一覧になっていて、エンジンの中で >> 16 や | 0 を使っていないか検査するようになっています。

端数の丸めかたも決めてある

割り切れないときの丸めも、決めておかないとずれます。 このエンジンは 「0.5 ちょうどは偶数側へ」（round half to even）です。

2.5 → 2     3.5 → 4     4.5 → 4

いつも切り上げると、丸めの誤差が片側にたまっていきます。 偶数側に寄せると、たまりかたが打ち消し合います。

sin は計算せず、表を引く

角度が要る計算（向きから速度を出すなど）には sin と cos が必要です。 でも Math.sin は使えません。答えが端末によって違うかもしれないからです。

そこで **表（ルックアップテーブル）**を使います。

• 1 周を 1024 に分けた sin の値を、あらかじめ計算しておく
• その 1024 個の数字を、ソースコードとしてリポジトリに保存する
• 実行時はその表を引き、あいだは直線でつなぐ

SIN_LUT = [0, 402, 804, 1206, ...]   ← 1024 個。これがソースに書いてある

表を「生成してコミットする」ところが要点

起動時に Math.sin で表を作ると、表そのものが端末によって変わってしまいます。 作った結果を保存しておくことで、表はどこでも同一になります。

ビルドし直しても表は変わりません。変えたいときは、意図して変えて、 engine_version を上げます。

atan2（座標から角度を出す関数）は、エンジンではそもそも使っていません。 角度の比較は内積と二乗の比較だけで済ませています。 たとえば「正面 45 度以内か」は、平方根も逆三角関数も使わずにこう書けます。

$$2\,(\mathbf{f} \cdot \mathbf{d})^2 \ge \Vert{}\mathbf{d}\Vert{}^2 \quad\text{かつ}\quad \mathbf{f} \cdot \mathbf{d} > 0$$

$\cos 45° = 1/\sqrt{2}$ の両辺を 2 乗して整理しただけです。 厳密で、しかも整数だけで計算できます。

なお、これはエンジンの中だけの制限です。 あなたの bot は math.sin も math.atan2 も自由に使えます。

bot の math も、どの端末でも同じ答え

ただし、ブラウザにもともと入っている Math.sin や Math.atan2 は、最後の桁が端末によってちがいます。 実際に 2 つの実行環境で同じ 20 万個の数を入れてみると、atan2（向きを出す計算）は 5 回に 1 回くらい、 いちばん下の桁がずれていました。

angle_to（向き）・distance（距離）・**（べき乗）も、中でこうした計算を使っています。 そこで bot の math とこれらのヘルパーは、ブラウザの Math を使わず、 たし算・ひき算・かけ算・わり算と平方根だけで組み立てた計算で答えを出しています。 この 5 つは、どの端末でも答えが 1 通りに決まっている計算です。だから math.sin の答えも、どこで計算しても同じになります。 精度は、ふつうの Math.sin とほとんど変わりません（ちがっても最後の 1 桁）。

乱数も決まっている

マップ生成には乱数を使いますが、シードから決まる乱数です。 同じシードなら、何度やっても同じマップができます。

bot の rand() も同じです。試合ごと・陣営ごとにシードが固定されているので、 同じ試合を再生すれば、同じ目が出ます。

random モジュールが使えないのはこのためです。 本物の乱数を混ぜた瞬間に、再現できなくなります。

「順番」もぜんぶ決めてある

数の表しかたを揃えても、処理の順番が違えば結果は変わります。 だからエンジンは、迷いどころを 1 つずつ潰してあります。

同時に起きたとき	決めてあること
bot を動かす順	つねに A → B
壁にめりこんだ	X 方向を先に押し戻し、次に Y
2 台が完全に重なった	A を −X、B を +X へ
弾が壁の角に当たった	X 軸の反転を優先
視線がマスの角を通った	X 方向へ進む
弾が同時に相殺した	生成順 ID の昇順
BFS で道を広げる向き	右 → 下 → 左 → 上

どれも「どちらでも正しい」場面です。 正しさではなく、決まっていること自体に意味があります。

PyLite（bot の Python）にも同じ配慮があります。 dict は入れた順に回り、sorted は安定ソート、set はそもそも用意していません。 集合は要素を回す順番が実装に左右されやすいからです。

壊れていないか、どう確かめるか

決定論は「気をつける」では守れません。テストで縛ってあります。

1. ゴールデンハッシュテスト — 決まった 50 組の試合の結果ハッシュが、固定値と一致するか。50 組のうち 5 組は、math の答えのいちばん下の桁で動きを決める、わざと敏感に作った bot の試合です
2. クロス環境テスト — ちがう実行環境（Node・Bun・Chrome、それに学校の iPad や Chromebook）で回しても、同じハッシュになるか
3. 分割実行テスト — 途中で止めて保存し、読み直しても同じ結果になるか（これから作ります）
4. 命令数一致テスト — bot が使った命令数が、環境によらず完全に一致するか
5. 静的検査 — 禁止した書き方（>> 16、Math.sin、Date …）が紛れこんでいないか

ハッシュが落ちたら、まず「直す」前に考える

エンジンをさわるとゴールデンハッシュテストは落ちます。落ちて当然です。

大事なのは、その変化が意図したものかどうかを先に確かめることです。 意図した変更なら engine_version を上げます。 意図していなかったなら、それは決定論が壊れた合図です。

つぎに読む

• 1 フレームの中で何が起きているか → フレームの 6 フェーズ
• 角のタイブレークの実例 → 跳弾のしくみ
• bot 側の制限とその理由 → Sub-Python の構文