Apollo 11 landed on the surface of the moon on July 20, 1969, a feat for all humanity that ended the first iteration of the space race. Neil Armstrong stepped into history as the world watched and among the millions of people who were awed was 17-year-old schoolboy Jim Storer.
Based in Massachusetts and with a significant foundation in mathematics thanks in part to his physicist father, Storer was inspired by the concept of a moon landing: the precise calculations and control required to secure a large piece of aluminum to a barren, barren site to let it rest. unknown surface. Storer’s school had one PDP-8the first commercially successful minicomputer, and the young man began writing a new program called “Lunar Landing Game”.
Text-based and written in the early programming language FOCAL, Lunar Landing Game prompted the player for instructions each turn, calculating the lander’s altitude, speed, and remaining fuel over each in-game second of descent. Essentially it’s a game where you use your fuel supply to slow and control the craft’s descent, and when the craft reaches the surface the player gets a report on its landing speed and remaining fuel.
The entire game consists of less than 50 lines of code, but its apparent simplicity belied the calculations underlying the simulation, and over the years the game became very popular as a programming challenge. Even later, several popular commercial versions would add a visual layer (to give an idea of its longevity, Atari is currently developing a visual layer). developing an official sequel).
Software engineer Martin C. Martin made this known in a new blog post that while playing with the original game’s code, he found and fixed a bug that had been dormant for 55 years since the game’s code (first noticed by Ars Technica). Martin is now retired and has had a great career at Rockstar, Meta and as a postdoc research fellow at MIT. He’s exactly the type of person who looks at something like Lunar Lander and decides to build the optimal strategy for a perfect strategy. to land.
“I recently investigated the optimal fuel burn schedule to land as softly as possible and with maximum fuel remaining,” Martin writes. “Surprisingly, the theoretically best strategy didn’t work. The game mistakenly thinks the lander isn’t touching the surface, when in reality it is. When I dug into it, I was amazed at the advanced physics and numerical computing in the game. Eventually I found a bug: a missing ‘divide by two’ that had apparently gone unnoticed for almost 55 years.”
Suicide burn
That is, Martin’s perfect strategy was not registered by the game as a successful landing. The programmer used what Kerbal Space Program players call the “suicide burn,” where you maximize speed by using no fuel and then hit full throttle at the last minute to reduce speed to almost zero just before hitting the surface .
“With some trial and error and a little (manual) binary search, you can find the schedule where you just barely land. You burn nothing for 70 seconds, then 164.31426784 lbs/sec for the next 10 seconds, and then the maximum 200 lbs/sec thereafter,” Martin writes.
“The game considers a perfect landing to be less than 1 MPH, but here we are landing at over 3.5 MPH and being told ‘we can do better’. But if you add another 0.00000001 kg/sec burns more, you miss the surface completely, at a speed of 180 km/h:
“How did we go from a hard landing to not landing at all, with no soft landing in between?”
When the programmer started investigating why, he discovered that instead of “the simple Euler integration common in video games even today,” the game’s logic was supported by more sophisticated equations: “Jim [Storer] used the exact solution, the Tsiolkovsky rocket equation, with a Taylor series expansion for the logarithm,” Martin writes. “He also used some algebra to simplify it and reduce the amount of rounding errors. Very impressive for a high school student in 1969.”
Martin contacted Storer to confirm what he had found, and to ask where this advanced mathematics came from. “I was adept at calculus at the time and familiar with concepts like a Taylor series,” says Storer, “but I also remember my father, who was a physicist, helping me derive the equations.”
In any case, the rocket equation is what should make the suicide combustion optimal, and the accuracy of the Taylor series suggests that this is not the problem either. Instead, the problem was contact: the moment the Lander lands.
“Imagine the lander descends at the beginning of a 10-second turn, but rises again at the end,” Martin writes. “Simply verifying that it is above the surface at both points is not enough. It could have dived below the surface somewhere in between. When this happens, the program must rewind and investigate an earlier moment.”
As Martin goes on to explain, the error creeps in when the game tries to approach the bottom of the trajectory. The programmer presents his full elaboration in the blog post, but essentially it boils down to Storer using an alternate form of a quadratic formula, for whatever reason “missing the 2 in the denominator within the square root! It was probably a simple error, either in deriving the formula or in typing it into the computer.” As Martin is careful to point out, Storer would not have had access to algebra software and did all this with pencil and paper.
The missing “2” means that the game “consistently underestimates the time to the lowest point”, which it then compensates by adding and reestimating a fraction of the time (0.05 sec). “And this explains why it misses the landing time: the first estimate is while the lander is above the surface and still descending, and the second estimate is after it has reached the bottom and taken off again, which is less than 0 takes .05 seconds.”
Martin then explains the effect of fixing the bug, and spitballs about some of the reasoning. Although he unfortunately notes that even if the bug is fixed, there are some optimal landing strategies, but “the theoretical suicide burn at full thrust upon landing, which takes about 148 seconds, eludes us.”
Martin ends with a tribute to the sophistication of Lunar Landing Game, coded in 1969 by a high school student, and to aspects of numerical computing that “I didn’t learn until I was studying for a PhD in robotics.”
As for a bug that has persisted in a popular software program for 55 years?
“That’s probably because, even with the bug, it was a fun game, both difficult and possible to land gently,” Martin writes. “The quest to not only win, but also to find the optimal strategy can certainly lead us to try to understand small discrepancies. I suspect everyone else was just happy to play the game and have fun.”
If you’re interested in the history of Lunar Lander, this 40th anniversary retrospective talks to Storer himself about the game’s creation. And if you just like old bugs, here’s a doozy: the developer who returned to his game after forty years and then discovered and fixed a typo so it actually worked.