by Apollo 11 touched down on the surface of the moon on July 20, 1969, a feat accomplished by all of mankind that brought the first iteration of the space race to a close. Neil Armstrong made history as the world watched and among the millions who were in awe was 17-year-old schoolboy Jim Storer.
Born in Massachusetts and with a significant background in mathematics, thanks in part to his physicist father, Storer was inspired by the concept of the moon landing: the calculations and precise control required to safely bring a huge chunk of aluminum to its to lie on the sun, an uncommon surface. There was a warehouse school PDP-8the first successful commercial minicomputer, and the young man began writing a new program called “Luna Landing Game”.
Based on the text and written in the early programming language WORD, Lunar Landing Game asked the player for instructions on each turn, while calculating the altitude, velocity, and remaining fuel of the landing over every in-game second of the descent. It’s basically a game about using your fuel supply to slow down and control the craft’s descent, and when the craft reaches the surface the player gets a report of its landing speed and remaining fuel.
The whole game is less than 50 lines of code, but its apparent simplicity belied the calculations at the base of the simulation, and over the years the game became widely popular as a programming challenge. Even after that, various popular commercial versions would add visual series (to give an idea of its longevity, Atari is currently in the visual process. develop an official sequence).
It has been announced by software engineer Martin C. Martin in a new blog post that while playing around with the original game code, he found and fixed a bug that had been dormant for 55 years since the game was coded (which was first spotted by Ars Technica). Now retired, Martin’s had a stellar career at the likes of Rockstar, Meta, and as a postdoctoral research fellow at MIT, and he’s exactly the kind of person who looks at something like the Lunar Lander and decides to work out the best strategy. for perfection. landing
“I recently explored the best fuel burn schedule to land as smoothly as possible with the maximum amount of fuel remaining,” Martin writes. “Surprisingly, the best theoretical strategy didn’t work. The game falsely thinks the lander doesn’t go down to the surface when it does. I found a bug: a missing ‘divide by two’ which had not been noticed for almost 55 years.”
suicidal burn
That is, Martin’s brilliant strategy was not being registered by the game as a successful landing. The coder was using what Kerbal Space Program players call the “suicide drift”, whereby you maximize speed by not using fuel, then a full-throttle burn at the last minute to bring the speed down as close as possible. your zero just before you hit the surface.
“With some trial and error and a bit of binary (hand) search, you can come up with the schedule that you barely land on. You burn nothing for 70 seconds, then 164.31426784 lbs/sec for the 10 another second, then the maximum 200 lbs/sec after that,” Martin wrote.
“The perfect landing game is considered to be less than 1 MPH, but here we land at over 3.5 MPH and we’re told ‘could be better.’ But burn even 0.00000001 pounds/second more, and you lose the surface completely, going up at 114 MPH:
“How did we go from a hard landing to no landing at all, with no soft landing in between?”
When the coder started to look into why, he discovered that the game’s logic was underpinned by “simple Euler integration that is common in video games even today”, with more sophisticated equations: “Jim . [Storer] used the exact solution, Tsiolkovsky’s rocket equation, to expand Taylor’s series for the logarithm,” Martin wrote. “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 had found, and to ask him where this sophisticated math came from. “I was trained in calculus at the time and familiar with concepts like the Taylor series,” says Storer, “but I also remember that my father, who was a physicist, helped me derive the equations.”
Either way, the rocket equation is what should be done for the best burn suicide, and the accuracy of the Taylor series suggests that’s not the issue either. Instead there was the contact problem: the moment the lander lands.
“Imagine the lander descending at the start of a 10-second turn but going up at the end,” Martin wrote. “It is not enough to simply verify that it is above the surface at both points. It could be submerged somewhere in between. When this happens, the program must rewind and examine an earlier moment .”
As Martin explains, the error comes in when the game tries to approximate the bottom of the trajectory. The coder presents his entire work in the blog post but, basically, it comes down to Storer using an alternate form of a quadratic formula where for whatever reason “It’s missing the 2 in the denominator inside the root square! It was probably a simplicity! error, while getting or typing the formula into the computer.” As Martin is careful to point out, Storer would not have had access to algebra software and was doing all of this 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 seconds) and reestimating it. “And this explains why he misses the landing time: the first estimate is that while the lander is above the surface and still descending, then the second one has reached the bottom and is going up 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. Although he sadly notes that even with the bug fixed, there are some optimal landing strategies but that “we have avoided a theoretical full-throttle suicide burn on landing, which takes about 148 seconds.”
Martin concludes by paying tribute to the sophistication of the Lunar Landing Game, coded in 1969 by a high school student, and incorporating elements of numerical computing “I didn’t learn until I was studying for a Ph.D. in robotics.”
About a bug that lives in a popular piece of software for 55 years?
“That’s probably because, even with the bug, it was a fun game, both difficult and possible to land smoothly,” Martin wrote. “Certainly trying to understand small inconsistencies can result in trying not only to win, but to find the best strategy. I doubt everyone else was willing to play the game and have fun.”
If you’re interested in the history of Lunar Lander, this 40-year retrospective talks with Storer himself about the creation of the game. And if you like old bugs, here’s a doozy: the developer who returned to his game after four decades, found and fixed a typo so that it actually worked.
