Apollo 11 touched down on the moon's surface on July 20, 1969, an achievement for all humankind that put a full stop on the first iteration of the space race. Neil Armstrong stepped into history as the globe watched and among the millions in awe was 17 year-old schoolboy Jim Storer.
Based in Massachusetts and with a considerable grounding in mathematics, thanks partly to his physicist father, Storer was inspired by the very concept of a moon landing: the precise calculations and control required to safely bring a huge chunk of aluminium to rest on a barren, unfamiliar surface. Storer's school had a PDP-8, the first commercially successful minicomputer, and the young man set about writing a new program called "Lunar Landing Game".
Text-based and written in the early programming language FOCAL, Lunar Landing Game would ask the player for instructions on each turn, with the height, velocity, and remaining fuel of the lander calculated over each in-game second of the descent. Essentially it's a game about using your fuel supply to slow and control the craft's descent, and when the craft reaches the surface the player gets a report on their landing speed and remaining fuel.
The whole game is less than 50 lines of code, but its apparent simplicity belied the calculations underlying the simulation, and over the years the game became widely popular as a programming challenge. Even later, various popular commercial versions would add a visual layer (to give an idea of its longevity, Atari is currently in the process of developing an official sequel).
Software engineer Martin C. Martin has announced in a new blogpost that, while playing around with the original game's code, he found and fixed a bug that's lain dormant over the 55 years since the game was coded (first spotted by Ars Technica). Now retired, Martin's had a stellar career at the likes of Rockstar, Meta, and as a postdoc research fellow at MIT, and is exactly the type of individual who looks at something like Lunar Lander and decides to work out the optimal strategy for a perfect landing.
"I recently explored the optimal fuel burn schedule to land as gently as possible and with maximum remaining fuel," writes Martin. "Surprisingly, the theoretical best strategy didn’t work. The game falsely thinks the lander doesn’t touch down on the surface when in fact it does. Digging in, I was amazed by the sophisticated physics and numerical computing in the game. Eventually I found a bug: a missing 'divide by two' that had seemingly gone unnoticed for nearly 55 years."
Suicide burn
That is, Martin's perfect strategy wasn't being registered by the game as a successful landing. The coder was using what Kerbal Space Program players call the "suicide burn", whereby you maximise speed by not using fuel, then burn full-throttle at the last moment to reduce the speed to as close to zero just before you hit the surface.
"With some trial and error and a bit of (manual) binary search, you can find the schedule that just barely has you landing. You burn nothing for 70 seconds, then 164.31426784 lbs/sec for the next 10 seconds, then the max 200 lbs/sec after that," writes Martin.
"The game considers a perfect landing to be less than 1 MPH, but here we land at over 3.5 MPH and are told we 'could be better.' Yet burn even 0.00000001 more lbs/sec, and you miss the surface entirely, ascending at 114 MPH:
"How did we go from a hard landing to not landing at all, without a soft landing in between?"
When the coder started looking into why, he found that rather than "the simple Euler integration that's common in video games even today", underpinning the game's logic were more sophisticated equations: "Jim [Storer] used the exact solution, the Tsiolkovsky rocket equation, with a Taylor series expansion for the logarithm," writes Martin. "He also used some algebra to simplify it and reduce the amount of round off error. Very impressive for a high school senior in 1969."
Martin contacted Storer to confirm what he'd found, and ask about where this sophisticated math had come from. "I was skilled at calculus at the time and familiar with concepts like a Taylor series," says Storer, "but also my recollection is that my father, who was a physicist, helped me in the derivation of the equations."
Either way, the the rocket equation is what should make the suicide burn optimal, and the accuracy of the Taylor series suggests that's not the issue either. Instead the problem was contact: the moment where the Lander lands.
"Imagine the lander descending at the start of a 10-second turn but ascending by the end," writes Martin. "Simply verifying that it’s above the surface at both points isn’t enough. It might have dipped below the surface somewhere in between. When this happens, the program has to rewind and examine an earlier moment."
As Martin goes on to explain, the error creeps in when the game is trying to approximate the bottom of the trajectory. The coder presents his full working out in the blog post but, essentially, it comes down to Storer using an alternate form of a quadratic formula where for whatever reason "he’s missing the 2 in the denominator inside the square root! It was probably a simple error, either when deriving the formula or typing it into the computer." As Martin is careful to point out, Storer wouldn't have had access to algebra software and was doing this all with pencil and paper.
The missing "2" means that the game "consistently underestimates the time to the lowest point", which it then compensates for by adding a fraction of time (0.05 sec) and re-estimating. "And this explains why it misses the time of landing: the first estimate is while the lander is above the surface and still descending, then the second one is after reaching the bottom and ascending again, which takes less than 0.05 sec."
Martin goes on to explain the effect of fixing the bug, and spitball about some of the reasoning. Though he does note sadly that, even with the bug fixed, there are some optimal landing strategies but "the theoretical full-thrust-on-landing suicide burn, that takes around 148 seconds, eludes us."
Martin ends by paying tribute to the sophistication of Lunar Landing Game, coded in 1969 by a high-school student, and incorporating aspects of numeric computing that "I didn't learn until I was studying for a Ph.D. in robotics."
As for a bug surviving in a piece of popular software for 55 years?
"That’s probably because, even with the bug, it was a fun game, both difficult and possible to land gently," writes Martin. "The quest to not just win, but find the optimal strategy, can certainly lead to trying to understand small discrepancies. I suspect everybody 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 speaks 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 four decades, then found and fixed a typo so it actually worked.
