最初の Lunar Lander ゲームで55年前のバグが発見される
(martincmartin.com)- 1969年に高校生の Jim Storer が作った最初の Lunar Landing ゲームで、最適な着陸用燃料スケジュールを検証していたところ、本来は着陸している瞬間をゲームが飛行中だと誤判定するバグが明らかになった
- 問題の戦略は、70秒間エンジンを切り、10秒間は 164.31426784 lbs/sec、その後は最大の 200 lbs/sec で燃焼する suicide burn で、ゲームは激しい着陸と未着陸の上昇の間にあるはずのソフトランディングを見逃していた
- 元のコードは単純な Euler 積分ではなく、Tsiolkovsky rocket equation と Taylor 級数を使って10秒ターンの運動を計算しており、1969年の PDP-8 環境で高校生が作ったものとしてはかなり精巧だった
- バグの原因は、地面接触前の軌道の最下点を近似する式で、平方根の中の分母にあるべき 2 で割る処理 が抜けていたことで、最下点到達時刻が一貫して過小評価されていた
- 欠けていた factor of two を修正し、0.05秒の補正を削除すると suicide burn の結果は 1.66 MPH まで改善するが、1 MPH 未満の完璧な着陸には Taylor 級数2項近似と着陸時点の再計算の限界がなお残る
1969年の Lunar Landing と最適着陸の探索
- Jim Storer は Neil Armstrong の月面着陸から数か月後、Massachusetts の Lexington High School の生徒として最初の Lunar Landing ゲームを作成した
- 1973年には、このゲームは「by far and away the single most popular computer game」と呼ばれるほど広く普及していた
- ゲームはテキストベースで、月着陸船の運動はすべて 垂直方向 のみで進む
- プレイヤーはシミュレーション上、10秒ごとに燃やす燃料量を決め、月面にできるだけ柔らかく着陸しなければならない
- 最適な燃料スケジュールを探す過程で、理論上もっとも良い戦略がゲーム内では正しく動作していなかった
- 実際には着陸船が表面に触れている状況
- ゲームは表面に触れていないと誤判定する
- 最終的な原因は、ほぼ55年間見過ごされていた divide by two の欠落 だった
最小燃料着陸と suicide burn
- 最小燃料で着陸するには、可能な限り 短時間 で降下する必要がある
- 最適戦略は、最初はエンジンを切って速度を上げ、最後に可能な瞬間に最大推力で減速して、表面に触れる瞬間の速度を 0 に近づける方法だ
- Kerbal Space Program コミュニティでは、こうした戦略を suicide burn と呼ぶ
- タイミングが非常にシビアで、ミスの余地がほとんどないためだ
- 試行錯誤と手動の二分探索で見つかったスケジュールは次の通り
- 70秒間は燃料を燃やさない
- 次の10秒間は 164.31426784 lbs/sec で燃料を燃やす
- その後は最大値である 200 lbs/sec で燃料を燃やす
- ゲームは 1 MPH 未満を完璧な着陸とみなす
- このスケジュールでは 3.5 MPH 以上で着陸し、「could be better」と判定される
- ところが、燃料量を 0.00000001 lbs/sec だけ増やすと、表面に触れずに 114 MPH で上昇してしまう
- つまり 激しい着陸 と 未着陸の上昇 の間に存在するはずのソフトランディング判定が消えていた
予想以上に精巧だった物理計算
- 最初は、現代のゲームでもよくある Euler 積分 が使われていると予想していた
- 時間区間の始点で力を計算する
- F=ma で加速度を求める
- その時間区間では加速度が一定だと仮定する
- 実際の Lunar Landing のコードはこれよりずっと精巧だった
- Jim Storer は Tsiolkovsky rocket equation の正確解を使っていた
- 対数計算には Taylor 級数展開 を適用していた
- 引数の最大値は 0.1212
- 5項で6桁以上の精度が出る
- 代数的な簡略化で丸め誤差も抑えていた
- Jim Storer は当時、微積分や Taylor 級数のような概念に慣れており、物理学者だった父親が方程式の導出を手伝ったと記憶している
- suicide burn が最適になる理由もこのロケット方程式から導かれ、この部分はバグの原因ではなかった
地面接触判定が難しい理由
- ロケット方程式は、着陸船が地面に触れるまではうまく機能する
- 固体同士の衝突は動力学エンジンにとって難しい領域であり、Lunar Landing でも地面接触判定が最大の難所だった
- 10秒ターンの開始と終了だけを確認しても十分ではない
- 開始時点では下降中かもしれない
- 終了時点では上昇中かもしれない
- 途中で地表より下に潜って再び上がってきた可能性もある
- この場合、プログラムは時間を巻き戻して、より早い接触時点を探さなければならない
- 自然なチェックポイントは、速度が 0 になる 軌道の最下点 だ
- ロケット方程式では、この最下点を基本的な数学関数だけで閉形式に表すことはできない
- 脚注では Lambert W が必要だと説明している
- 対数の Taylor 級数の最初の数項だけを使えば近似できる
- 最初の2項だけ使うと問題は2次方程式に簡略化される
- 高校レベルの quadratic formula が使える
- 10秒ターンの範囲では約 0.1% 以内の精度が期待できる
代替の2次公式と数値安定性
- Jim Storer のコードには、平方根が分子ではなく 分母 にある形が現れる
- これは一般的な2次公式ではなく、平方根が下に来る 代替形の quadratic formula と一致する
- この代替形には重要な数値的利点がある
- 地面接触を検出した後、実際の接触時刻を求めるときにも Taylor 級数を打ち切って2次方程式で近似する
- 一般形では2次項の係数が 0 のとき 0 除算の問題が生じる
- ロケット推力が重力とちょうど釣り合うと、この状況が発生する
- 地表付近で浮いている、あるいはゆっくり降下するプレイヤーでは起こりやすい
- 推力が重力に近いと、一般形では分子で catastrophic cancellation が起こり、小さな分母が誤差を増幅する
- 代替形は、2次項が 0 の線形方程式の状況でもうまく動作する
- 1969年の高校生がこの形を再導出した、あるいは学んでいたという点は、当時の環境を考えると印象的だ
実際のバグ: 欠けていた factor of two
- 式を直接導出して比較すると Jim Storer のコードとほぼ同じだったが、平方根の中の分母にあるべき 2 が抜けていた
- この欠落は、式の導出過程か、コンピュータに入力する過程で生じた単純なミスである可能性が高い
- 当時 MACSYMA は始まってまだ1年しか経っておらず、高校で使える環境でもなかったため、導出は紙と鉛筆で行うしかなかった
- このバグのせいで、最下点までの時間は一貫して 過小評価 されていた
- コードはこれを2つの方法で補正していた
- 0.05秒を追加する
- 新しく、より近い位置から再推定する
- しかし特定の suicide burn の状況では、この補正のせいで着陸時点を見逃してしまう
- 最初の推定は、着陸船が地表の上でまだ下降中の時点になる
- 2回目の推定は、最下点を過ぎて上昇中の時点になる
- この2時点の間隔は 0.05秒より短くなりうる
修正後の結果と残る限界
- 欠けていた factor of two を追加し、0.05秒の補正を削除すると、suicide burn の結果は改善する
- 修正後の最良の suicide burn は、1.66 MPH の着陸速度を示す
- 1 MPH 未満の完璧な着陸には、およそ 4 分の 3 まで近づく
- 完璧でない理由は、依然として Taylor 級数の最初の2項しか使っていないためだ
- 最下点が地表の下だと判断した後は、最初に地表へ触れる時刻を再び探さなければならない
- この過程でも同様の近似を使う
- 追加の反復が有効かもしれない
- バグを直した状態では時間を 過大評価 するため、時間を巻き戻す必要があるかもしれない
- この場合、2次方程式のもう一方の解を選ぶ必要がある可能性がある
- もっと単純には、Taylor 級数を1項だけ使い、Newton’s method に近い方法で処理することもできる
- 速度の大きさがある閾値以下になったら停止し、その時点の高度で着陸可否を判定する方法も可能だ
- ただし、こうした変更はコードをより複雑にし、元のゲームはすでに十分に楽しく遊べるものだった
バグが長く残り続けた理由
- ソフトランディング自体は可能だ
- 14ターン目を低高度かつ低速度で終える
- 15ターン目で低推力を使う
- 150秒以降のどこかで着陸する
- 問題になるのは、およそ148秒で終わる理論上の 最大推力 suicide burn だ
- 全体として、このコードは1969年の PDP-8 上で18歳の高校生が書いたものとして非常に印象的だ
- 当時は高校でコンピュータ科学を教える前であり、Newton 法で推定を反復改善したり、catastrophic cancellation を気にしたりする数値計算の概念も広く知られていなかった
- バグがほぼ55年間見過ごされていたのは、バグがあってもゲームが難しく面白く、しかもソフトランディング自体は可能だったからだ
- 単に勝つだけでなく、最適戦略 を探そうとした試みが、この小さな不一致を理解する過程につながった
1件のコメント
Hacker Newsのコメント
後に彼がソースコードまで提供してくれて、本当に素晴らしかった。
https://technologizer.com/2009/07/19/lunar-lander/index.html
いちばん好きなのは、Storerが「高校を卒業して以来、そのゲームのことを考えたことはなかった。数か月前に誰かがこの件でメールを送ってくるまで、自分が高校時代に作ったもの以外にLunar Landerゲームがあることすらまったく知らなかった」と語っている部分。
1989年にLotus Notes関連の仕事に応募したとき、面接官のTim HalvorsenにLanderゲームを見せたところ、彼は「いいね、Windows 3で動かしてみよう」と言った。
最初は、まだリリース前のWindows 3を見られるのでいいなと思ったが、すぐに彼は「Windows 3はすべてをプロテクトモードで実行するから、ポインタが範囲外に出たら即死するはずだ」と言って、試してみようとした。
実行中はずっとハラハラしていたが、幸いLanderはクラッシュせず、Timも満足し、結局その仕事を得てキャリアが完全に変わった。
写真は見つけられないが、記憶ではこの機械に似ていた。
https://content.invisioncic.com/r322239/monthly_10_2015/post...
ただし地形と穴があり、ライトの点いた穴に着陸しなければならなかった。宇宙船が穴の中央のボタンを押すとライトが消えて別の穴が点灯し、狙いが悪いと縁にぶつかって傾き、失敗になった。
考え直すと、操作はUFOキャッチャーのように上から位置を合わせてから「land」を押す方式だったかもしれない。昔のDisneyland Main Street Arcadeにあった。
記事で「1969年の高校3年生としては印象的」と何度も言っているのが少し奇妙に感じた。宇宙時代に育った技術志向の人々には大きな影響を与えたはずだし、昔の映画October Skyも思い出す。
元のインタビューでは、ゲーム制作者は微積分が得意だったというので、宇宙やロケットに関心と才能があったなら、月着陸ゲームのプログラミングに挑戦するのも自然に思える。
[1]: https://www.cs.brandeis.edu/~storer/LunarLander/LunarLander/...
宇宙時代が刺激になった可能性はあるが、当時の一般大衆にとってコンピュータは事実上存在しないも同然で、ソフトウェア開発も広く知られた職業ではなかった。米国でコンピュータサイエンス専攻ができたのも1962年なので、1969年に高校3年生だったという点はかなり注目に値する。
大きな工科大学のあるかなり大きな都市の大規模高校に通っていたが、最大の壁はコンピュータへのアクセスだった。
学校にはリモートのメインフレームにつながったテレタイプがあり、友人たちと夜に使える大学のコンピュータを何台か見つけたが、ほとんどはカードリーダーとラインプリンタだけで、グラフィック端末はまったくなかった。
当時は、技術、関心、アクセスがそろう組み合わせはかなり珍しかったはずだ。
https://retro365.blog/2021/12/02/bits-from-my-personal-colle...
FOCALについてのWikipedia：
https://en.wikipedia.org/wiki/FOCAL_(programming_language)
高校物理で自由物体図から始めて、重力と推力という2つの力を扱うところまでは、物理でAを取る平均的な生徒にもできる。
しかし重力は中心までの距離、つまり常に変化する値に依存する。高度120マイルから開始するが変化は大きくないので、定数で近似できると知っている必要がある。
推力が燃焼率の関数としてどう働くかも難解だ。燃料流量を2倍にすると排気速度も2倍になるのか、理想気体の状態方程式PV=nRTでPとTがどう変わるのか、といった問題が出てくる。
そこで物理学者の父親に尋ね、ロケットエンジンの特性とツィオルコフスキーのロケット方程式に行き着いたのだとしたら、それ自体が高校3年生にとっては印象的だ。
速度から位置を得るには積分が必要で、FLOG()呼び出しをテイラー級数に置き換えて項ごとに積分するという発想を、平均的な物理Aの生徒がするかどうかは分からない。
テイラー級数の項をいくつ使うべきか、収束するのかといった細部も厄介だ。Jimがこの微妙な点を考えていたのならすごいし、単に5項なら多く見えると思って使った可能性もある。
月付近のシミュレーションはできたとしても、地面への衝突をどう検出するかも問題です。高度が0になる解を直接解くのではなく、回転中に正確に一度だけ生じる速度0の点を見るという方法は、かなり創造的です
望むデルタVを与えたときに必要な燃料量を求めるためロケット方程式を逆に解くのも、高校数学と微積分だけでは行き詰まります。実際には Lambert W のような新しい関数が必要です
結局、テイラー級数で5次多項式を解かなければならないので、3次、4次、5次の項を捨てて2次式にする判断が必要になります。普段の力学計算では捨てなかった項をここでは捨ててもよいと判断したのは、状況に応じて異なる近似レベルを使えることを理解していたという意味で印象的です
また、二次方程式の代替形を何とか使っているのを見ると、単に探して写しただけではなかった可能性があります
水平方向に高速で進入したあと、LEM の側面スラスターとメインエンジンのボタンで減速し、垂直着陸しなければならず、速すぎたり燃料が尽きたりするとクレーターができ、着陸の出来に応じて1本以上の米国旗が立ちました
数年前、ソースコードには価値もなく再利用されることもないと思って唯一のコピーを捨ててしまいましたが、後になって歴史的にはかなり初期のグラフィックゲームで、簡単なエミュレーションで復活できたはずだと気づき、後悔しました
25年後に見直すと、バグが信じられないほど多く、ロジックも「440 IF GOTO 450」のようにねじれていて驚きました
結局、大人になってから書き直しましたが [1]、子どもの頃の自分に成功の見込みはありませんでした。今でも、あの忘れられたスペインの出版社の内部で、ほぼ動いていたコードがどうやって最終版のような姿に変わったのか気になっています
[1] https://7c0h.com/blog/new/moon_landing_in_basic.html
この種の BASIC コードは1960〜70年代にルーツがあり、当時コードが掲載されていた印刷雑誌やコード集では、編集者が強い権限を持っていました
ソースコードを一文字も変えずにそのまま載せるべきだという認識が弱く、編集者たちは「明白な」誤字や編集上の判断だと思って、ソースコードを「慎重に」修正することがよくありました
1980年代から業界全体で改善が始まり、印刷物でソースコードに手を入れてはいけないという認識が広まるまで、この教訓はゆっくりと、苦痛を伴って学ばれていきました
こうした流れが BBS の台頭を促し、印刷メディアがソースコード配布を握っていた力を弱めたのかもしれない、とも思います。印刷メディアの権力者たちが「自分たちの」コンテンツの一部について、外部の人間が絶対的な制御を持つことをもっと受け入れていたなら、別の歴史もあり得たかもしれません
子どもの頃、大人の助けなしに学校と地域図書館のプログラミング本を数冊見ただけでコーディングを始めたのですが、手で入力した数多くのプログラムが同じようにエラーだらけだったにもかかわらず、コーディングを続けていたのが不思議なくらいです
「440 IF GOTO 450」のようなねじれたロジックについて少し補足すると、本の一部のコードは確かに整理が必要ですが、当時の家庭用コンピュータで一般的だった BASIC は、行番号しか扱わず、分岐文も非常に制限されていた可能性が高いです
使われていた BASIC は構造化プログラミングをサポートしているようですが、当時の家庭用コンピュータでは非常に珍しいものでした。1984年の C64 雑誌が、構造化プログラミングの驚きを読者に紹介する長期連載を少なくとも3号にわたって掲載したほどです
IF 文の制約が厳しかったため、GOTO を使うアセンブリ風の条件分岐は非常に一般的で、事実上必要でした
IF のネストは不可能で、複数の IF を組み合わせるには、選択されなかった部分をジャンプで飛ばす必要がありました。Commodore/C64 BASIC、事実上 Microsoft BASIC には ELSE すらなかったため、通常は否定条件とジャンプで ELSE 分岐をまねていました
C64 BASIC には、同じ行の別の文も THEN に属するという独特の動作がありました。たとえば
10 IF A=1 THEN PRINT “FOO” : PRINT “BAR”は A=1 のとき FOO BAR を出力し、そうでなければ何も出力しませんもちろん、限られた1行に文をすべて入れられる場合に限られました。他の BASIC 方言では
PRINT “BAR”を ELSE の外側と見なすこともあり、文法的にはよりきれいですが、方言が提供する機能によっては不便になることもありました今日では当然と思っている利便性や厳密さはありませんでした。C64 BASIC は実装上の産物のような奇妙な特性が多く、特に「汚く」感じられました。たとえば、すべての関数は実際には不要でも引数を取らなければならず、残りメモリを出力するには意味のない
?FRE(123)のように書く必要がありました199.99999999 を早く「プレイ」するほどよいので、総当たりでソフトランディングになる最も早い入力を選べばよいです
ゲームが着陸を認識するには、約0.05秒間、高度が0未満でなければなりません。その時間中に推力が200または199なら、高度がそれだけ長く負になるには、高度0の地点で速度が1MPHを超えている必要があります
バグを直しても、コードは依然として最低点を近似するだけです。着陸を検出した後でも、実際の着陸時刻、つまり速度ではなく高度が0になる時点を計算する必要があり、これにも近似を使います
そのため時刻は少しずれる可能性があります。最後の時間ステップで200または199で燃焼中なら加速度が大きく、ごく小さな時刻誤差でも大きな速度誤差につながります
代わりに 10 lbs/sec 程度で燃焼すれば、0.08秒ほどずれても速度変化は大きくありません
フレームレートが低いほどこの方式の精度が落ちるという意味なのか、それとも実際の方程式を使う面白さのためなのか気になる
元のフレームレートで、2つの方式の違いがどれほど体感できたのかも気になる
https://www.cs.brandeis.edu/~storer/LunarLander/LunarLander/...
質量と加速度を10秒間隔でしか更新しないと、ものすごく不正確になる
物理的な精度という面では、特に地表近くで燃料燃焼率が高いと質量がかなり大きく変わります。ただ、ゲームの難易度や面白さ、プレイヤーの戦略という面では大きな違いはなさそうです
実際、BASIC computer games本にある別の月着陸シミュレーションの1つは、そうした素朴なアプローチを使っているように見えます
10秒が長すぎるなら、ユーザーインターフェース上の1ターンはそのまま10秒にして、内部的には各ターンを1秒の時間ステップ10個のように、もっと細かく分割できます
既存のゲームも特定の部分では実際にそうしているので、物理シミュレーションは常に10秒全体ではなく、任意の時間 S を入力として受け取るようになっています
しかし着陸ゲームはなく、Storerが最初でした。関連する興味深い歴史はこちらにあります
https://www.acriticalhit.com/moonlander-one-giant-leap-for-g...
燃料を燃やすことで機体が軽くなる効果を計算しなくても、つまりここでロケット方程式が担っている部分を除いても、suicide burnは依然として最適です
本当の理由は、suicide burnが重力損失を最小化するからです
https://en.wikipedia.org/wiki/Gravity_loss
意図していたのは、力学にはロケット方程式と重力という2つの部分があり、この2つは線形に足し合わされるということでした。重力によって生じた追加の速度は、ロケット方程式のデルタVを増やして打ち消す必要があります
重力デルタVは重力加速度かける時間なので、時間を最小化する必要があります
驚くべきことに、ロケット方程式ではどれだけ時間がかかるか、どんな燃焼順序を使うか、一定の速度で燃やし続けるか、短く強い噴射で燃やすかは重要ではありません
だから、最小の燃料で速度0の着陸をするには、可能な限り短い時間で着陸すればよいのです
自分で着陸方法を見つけることはできませんでしたが、最初の数ターンは慣性で進み、その後最大推力をかけるテクニックを誰かが見せてくれたのは覚えています。当時は「suicide burn」という用語は覚えていません。おそらくKerbal Space Programが有名になった後で、後からできた言葉かもしれません
1970年代半ば、バークレーのLawrence Hall of Scienceでも、数台の端末でこの月着陸ゲームが動いていた記憶があります。どのコンピューターで実行されていたのかは分かりません
このプログラムのソースコードは見たことがなく、数学がこれほど洗練されていたこともまったく知りませんでした。当時は幼すぎて理解できなかったでしょうし、正直なところ今でも理解できるかは分かりません
ゲーム用キオスクモードの1つの「機能」は、タイミングよくCtrl-Cを押すとキオスクモードを抜けて別のゲームができたことです
偶然だったのでしょうか、それとも初期のハッカーたちに投げられた餌だったのでしょうか？