編譯 | 鄭麗媛
出品 | 程式人生（ID：coder_life）
在 1969 年 7 月 20 日，阿波羅登月艙着陸月球，第一位踏上月球的美國宇航員 Neil Armstrong，在出艙時說了一句經典：“這是一個人的一小步，也是人類的一大步。”
當時，全球約有 6.5 億觀衆通過電視直播見證了 Neil Armstrong 在月球上邁出第一步，其中就包括 17 歲的美國高中生 Jim Storer——自那時起， 他便産生了編寫一款登月模拟程式的想法。
于是同年 11 月，Jim Storer 學會了 PDP-8（一款迷你電腦）特有的程式設計語言 FOCAL，用不到 50 行的代碼寫出了第一個“登月（Lunar Lander）遊戲”。由于技術限制，這個“登月遊戲”隻能以文字呈現。
總體而言，“登月遊戲”的内容很簡單，就是由玩家扮演的宇航員需要手動操控一個登月器，目标是在月球上實作軟着陸：
（1）每隔 10 秒鐘，螢幕上會顯示一行報告，統計飛船的高度、降落速度，以及剩餘的燃料總量；
（2）報告結尾是一個空格，玩家要輸入 0-200 之間的一個數字，決定接下來 10 秒内的燃料消耗量；
（3）登月艙需以一個極低的速度接觸到月球表面，遊戲才會提示“完美着陸”，期間若撞上障礙物、以高速撞擊天體表面或耗盡燃料，遊戲便會結束。
盡管這款遊戲隻是一個簡單的文字遊戲，沒有畫面、也沒有聲音，這也并不影響它在 1973 年成為當時“最受歡迎的計算機遊戲”，并在後來有了許多衍生版本，風靡了近半個世紀。
近期，一名退休的軟體工程師 Martin C. Martin 也玩上了這個遊戲，想要探索最優燃料方案以實作軟着陸，但他在深入研究遊戲中複雜的實體和數值計算後發現：這個 55 年前開發的遊戲，有一個至今都沒人發現的 Bug！
要求軟着陸，卻從硬着陸變成完全沒有着陸？
根據 Martin 的個人介紹，他自國小六年級起就開始程式設計，是卡内基梅隆大學機器人研究所的研究所學生，又成為了麻省理工學院的博士後。畢業之後，他曾在 Meta 工作，也曾在 Rockstar Games New England 擔任 AI 主管。
已經退休的的他，近來在閑暇時間開始研究“登月遊戲”的最佳方案：在確定安全着陸的前提下， 如何保留最多的剩餘燃料。而他驚訝地發現，從遊戲中推算出的最佳政策并不符合實際：缺少了一個“除以二”的操作，導緻遊戲錯誤地認為已經着陸的登月器還沒有觸地。
從遊戲規則來看，為了在着陸時使用最少的燃料，玩家需要在最短的時間内完成着陸。理想方案是：最初，玩家可以通過關閉發動機來最大限度地提高速度，然後在最後一秒全速燃燒，正好在接觸地面時把速度降為零——Kerbal Space Program 社群把這種方法稱為“自殺式燃燒”，因為準确掌握時機非常難，且沒有任何誤差空間。
話雖如此，通過一些反複試驗和手動二分查找，還是能找到一種恰好讓登月器着陸的燃燒計劃：在前 70 秒不燃燒任何燃料，然後在接下來的 10 秒内以每秒 164.31426784 磅的速率燃燒燃料，之後再以每秒 200 磅的最大速率燃燒：
“登月遊戲”中認為，完美着陸的速度應小于 1 英裡/小時，但在這種情況下，我們以超過 3.5 英裡/小時的速度着陸，遊戲還提示說“可以做得更好”？然而實際情況是，哪怕每秒再多燃燒 0.00000001 磅的燃料，玩家也會完全錯過地面，并以 114 英裡/小時的速度上升：
基于此，Martin 提出一個疑問：“我們是如何從硬着陸變成完全沒有着陸，且中間沒有一個軟着陸的過程呢？”
接觸地面後，方案失效
Martin 本以為，會在這個“登月遊戲”中看到一種在如今電子遊戲中依然很常見的歐拉積分，也就是在每個時間步（timestep）開始時計算力，然後使用公式 F=ma 計算加速度，再假設加速度在 Δt\Delta tΔt 秒的時間步内保持恒定：
由于品質在時間步内不斷變化，加速度也會随之變化，是以假設加速度為常數隻是一個近似值。
但令人驚訝的是，遊戲作者 Jim Storer 使用了精确的解決方案，即齊奧爾科夫斯基火箭方程，并用泰勒展開式對其對數進行計算。此外，Jim Storer 還用了一些代數方法來簡化計算，減少了四舍五入的誤差。對于在 1969 年還是高中生的他來說，這已經非常了不起了。
當 Martin 問他這個問題時，Jim Storer 回答道：“當時我已經熟練掌握微積分、泰勒級數等概念，而且在我的印象中，身為實體學家的父親還在我推導這些方程時幫了我。”
知曉 Jim Storer 設計遊戲的方法後，Martin 很快就懂了：因為用的是火箭方程，是以“自殺式燃燒”成為了最優選擇，而且 Jim Storer 使用泰勒級數的五個項，在參數最大為 0.1212 時，可以達到超過六位小數的精度，是以這“不是我們要找的問題所在”。
理論上來說，在登月艙觸地之前火箭方程的效果确實很好——但 Martin 指出，等接觸地面後這個方法就不成立了，而這也是登月遊戲面臨的最大挑戰。
“想象一下，登月艙在一個 10 秒的回合中開始時下降，但到回合結束時上升。僅僅驗證它在這兩個時間點都在地表上方是不夠的，因為它可能在中間的某個時刻低于地表。當這種情況發生時，程式必須回溯并檢查之前的某個時刻。”
有一個顯而易見的方法，就是檢視軌迹的最低點，即速度為零的時刻。對于火箭方程而言沒有一個合适的表達式來表示這個最低點，是以可以使用實體學家最喜歡的技巧，隻取泰勒級數的前幾項。如果隻使用對數的前兩項，問題就簡化成了一個二次方程，你可以用高中學過的經典二次方程來求解公式。在 10 秒的回合内，這個近似值應該相當不錯，精确度在 0.1% 左右。
但 Martin 發現 Jim Storer 不是這麼做的：在他的公式中，平方根在分母而不是分子，另外誤差也放大了 30 倍。
“他少了平方根内分母中的 2！”
Martin 研究了 Jim Storer 的公式很久，發現怎麼算也不會涉及平方根。直到他更仔細地看了看 Jim Storer 的平方根，它的形式是：
這看起來很像是在平方根内除以 4 的二次方程式，但為什麼會在分母上呢？在嘗試了一些方法後，Martin 重新發現了一個二次方程的替代形式，其中平方根在分母上，也與 Jim Storer 代碼中的公式相符。
盡管如此，Martin 依舊不知道為什麼 18 歲的 Jim Storer 要用這種替代形式。也許他重新推導了二次方程公式，而不是查閱現有公式，結果推導出了這種形式？也許他擔心會出現災難性的抵消（catastrophic cancellation），是以想用正數相加而不是相減的形式？
但是，如果他的公式是等價的，那為什麼近似誤差會高出 30 倍呢？
Martin 嘗試自己推導公式，得到了以下結果：“這與 Jim Storer 的公式幾乎完全相同，隻是......他少了平方根内分母中的 2！”
Martin 指出，這可能是推導公式或輸入計算機時的一個簡單錯誤。畢竟，當時的計算機代數系統 MACSYMA 僅在 Jim Storer 開發前一年才開始使用，并且在 Jim 的高中并不可用，是以他必須用鉛筆和紙完成所有工作。
由于這個 Bug，Jim Storer 始終低估了到達最低點所需的時間。他可以通過兩種方式來補償：增加 0.05 秒，然後從新的、更接近的位置重新估算。這也就解釋了為什麼會錯過着陸時間：第一次估算是在登月艙還在地表上方并持續下降時，第二次估算是在登月艙到達最低點并再次上升之後，而這不到 0.05 秒。
接下來，如果把缺失的 2 倍系數加上并去掉 0.05，會發生什麼呢？現在，“自殺式燃燒”所能達到的最佳效果是：速度降到了 1.66 英裡/小時，離 1 英裡/小時的完美着陸還有将近四分之三的距離。
這并不完美，因為我們仍然隻使用了泰勒級數的前兩項。另外，一旦确定最低點是在地面下，就需要找到首次撞擊地面的時間，這就會涉及到類似的近似計算。平緩着陸也是可行的，隻需在第 14 個回合結束時降低高度和速度，然後在第 15 個回合中使用低推力，150 秒後在某處着陸即可。Martin 補充道，他無法了解的隻是理論上的全推力着陸自殺式燃燒，大約需要 148 秒。
即使有這個 Bug，這仍是一個有趣的遊戲
最後 Martin 評價稱，對于 1969 年使用 PDP-8 的 17 歲高中生來說，Jim Storer 的這個登月遊戲已經是一個非常了不起的作品了。
畢竟，當時的高中還沒有計算機科學課程，數值計算方面的知識也并不是誰都知道的——甚至 Martin 自己，也是攻讀機器人學博士學位時才學到這些知識。令 Martin 驚訝的是，這個錯誤已經存在了将近 55 年，而之前卻沒有人注意到它。
不過，對此 Martin 也表示了解：即使有這個 Bug，這仍然是一個有趣的遊戲。“不僅要赢，還想找到最佳政策，這種追求自然會讓人們試圖了解微小的差異。我想其他人都隻是樂于玩這個遊戲，并從中獲得樂趣。”
參考連結：https://martincmartin.com/2024/06/14/how-i-found-a-55-year-old-bug-in-the-first-lunar-lander-game/
由 CSDN 和 Boolan 聯合主辦的「2024 全球軟體研發技術大會（SDCon）」将于 7 月 4 -5 日在北京威斯汀酒店舉行。
由世界著名軟體架構大師、雲原生和微服務領域技術先驅 Chris Richardson 和 MIT 計算機與 AI 實驗室(CSAIL)副主任，ACM Fellow Daniel Jackson 領銜，BAT、微軟、位元組跳動、小米等技術專家将齊聚一堂，共同探讨軟體開發的最前沿趨勢與技術實踐。