Compile | Zheng Liyuan
Produced by | Program Life (ID: coder_life)
On July 20, 1969, when the Apollo lunar module landed on the moon, Neil Armstrong, the first American astronaut to set foot on the moon, said the classic phrase: "It's a small step for a man, and a giant leap for humanity." ”
At the time, some 650 million viewers around the world watched live TV to see Neil Armstrong take his first steps on the moon, including Jim Storer, a 17-year-old American high school student who came up with the idea of writing a lunar landing simulation.
So in November of the same year, Jim Storer learned FOCAL, the programming language unique to PDP-8 (a mini computer), and wrote the first "Lunar Lander" game in less than 50 lines of code. Due to technical limitations, this "moon landing game" can only be presented in words.
Overall, the idea of "Moonlanding" is simple, with the player playing as an astronaut who manually controls a lunar lander with the goal of achieving a soft landing on the moon:
(1) Every 10 seconds, a line of reports will be displayed on the screen, counting the altitude of the spacecraft, the landing speed, and the total amount of fuel remaining;
(2) At the end of the report is a space where the player enters a number between 0-200 to determine the fuel consumption in the next 10 seconds;
(3) The lunar module needs to touch the lunar surface at a very low speed before the game prompts a "perfect landing", during which the game will end if it hits an obstacle, hits the surface of a celestial body at high speed, or runs out of fuel.
Even though the game was a simple play on words, with no graphics and no sound, that didn't stop it from becoming the "most popular computer game" of the time in 1973 and many spin-offs that went on for nearly half a century.
Martin C. Martin, a retired software engineer, recently played the game to explore the optimal fuel solution for a soft landing, but after digging deeper into the game's complex physics and numerical calculations, he discovered that the game, developed 55 years ago, had a bug that no one had discovered to this day!
Asking for a soft landing, but going from a hard landing to no landing at all?
According to Martin's profile, he has been programming since sixth grade, a graduate student at Carnegie Mellon University's Robotics Institute, and a postdoctoral fellow at the Massachusetts Institute of Technology. After graduating, he worked at Meta and also served as head of AI at Rockstar Games New England.
Now retired, he has recently spent his spare time researching the best way to play the moonshot: how to retain the most remaining fuel while ensuring a safe landing. To his surprise, the best strategy deduced from the game was not realistic: a "divide by two" operation was missing, causing the game to mistakenly believe that the landed lunar lander had not yet touched the ground.
Judging by the rules of the game, in order to use the least amount of fuel when landing, the player needs to complete the landing in the shortest possible time. Ideally, the player can initially maximize their speed by turning off the engine, then burn at full speed at the last second, reducing the speed to zero just when it hits the ground – a method that the Kerbal Space Program community calls "suicide burning" because timing is so difficult and there is no room for error.
That being said, with some trial and error and manual binary searching, a burning plan was found that landed the moon landing: burn no fuel for the first 70 seconds, then burn fuel at a rate of 164.31426784 pounds per second for the next 10 seconds, and then burn at a maximum rate of 200 pounds per second after that:
In the "Moon Landing Game", it is believed that a perfect landing should be less than 1 mph, but in this case, we landed at a speed of more than 3.5 mph, and the game also hints that "it could be done better"? However, the reality is that even if you burn an additional 0.00000001 pounds of fuel per second, the player will miss the ground altogether and go up at 114 mph:
Based on this, Martin asks the question: "How did we go from a hard landing to no landing at all, and there was no soft landing in between?" ”
After touching the ground, the protocol fails
Martin would have expected to see in this "moon landing game" an Euler integral that is still common in video games today, where the force is calculated at the beginning of each timestep, and then the acceleration is calculated using the formula F=ma, and then the acceleration is assumed to remain constant for the time step of Δt\Delta tΔt seconds:
Since the mass changes over time steps, so does the acceleration, so assuming that the acceleration is constant is just an approximation.
But surprisingly, the game's author, Jim Storer, used the exact solution, the Tsiolkovsky rocket equation, and calculated its logarithm with the Taylor expansion. In addition, Jim Storer uses some algebraic methods to simplify calculations and reduce rounding errors. For him in 1969, when he was still a high school student, this was already quite remarkable.
When Martin asked him this question, Jim Storer replied, "I was already familiar with calculus, Taylor series, and I remember my father, who was a physicist, helping me derive these equations." ”
After learning Jim Storer's approach to designing the game, Martin quickly understood that "suicide burning" was the best choice because he was using the rocket equation, and that Jim Storer was using five terms of the Taylor series to achieve an accuracy of more than six decimal places at a maximum parameter of 0.1212, so this was "not the problem we were looking for."
Theoretically, the rocket equation works well before the module touches the ground – but Martin points out that this doesn't work when it touches the ground, and that's the biggest challenge for the moon landing game.
"Imagine a lunar module descending at the beginning of a 10-second round, but ascending at the end of the round. It is not enough to verify that it is above the surface at both points in time, as it may be below the surface at some point in between. When this happens, the program has to go back and check some point before. ”
An obvious way to do this is to look at the lowest point of the trajectory, which is the moment when the velocity is zero. There is no suitable expression for the rocket equation to represent this nadir point, so one can use the physicist's favorite trick and take only the first few terms of the Taylor series. If you use only the first two terms of logarithms, the problem is reduced to a quadratic equation, and you can use the classical quadratic equations you learned in high school to solve the formula. In a 10-second round, this approximation should be pretty good, with an accuracy of around 0.1%.
But Martin found that Jim Storer didn't do that: in his formula, the square root was in the denominator instead of the numerator, and the error was magnified by a factor of 30.
"He's missing 2 in the denominator in the square root!"
Martin studied Jim Storer's formula for a long time and found that it didn't involve square roots. That was until he looked more closely at the square root of Jim Storer, which was in the form of:
This looks a lot like a quadratic equation divided by 4 within the square root, but why is it on the denominator? After experimenting with a few things, Martin rediscovered an alternative form of a quadratic equation where the square root was on the denominator, which also matched the formula in Jim Storer's code.
Still, Martin didn't know why 18-year-old Jim Storer was using this alternative format. Perhaps he re-derived the formula for quadratic equations, instead of consulting the existing formulas, and as a result, derived this form? Maybe he's worried about catastrophic cancellation, so he wants to add positive numbers instead of subtracting?
But if his formula is equivalent, then why is the approximation error 30 times higher?
Martin tried to derive the formula himself, and got the following result: "It's almost exactly the same as Jim Storer's formula, except that ...... He's missing 2 in the denominator in the square root! ”
Martin points out that this can be a simple mistake when deriving a formula or entering it into a computer. After all, MACSYMA, the computer algebra system at the time, had only been in use a year before Jim Storer was developed and wasn't available in Jim's high school, so he had to do everything with pencil and paper.
Because of this bug, Jim Storer has always underestimated the time it takes to reach the nadir. He can compensate in two ways: by adding 0.05 seconds and then re-estimating from a new, closer position. This explains why the landing time was missed: the first estimate was when the lunar module was still above the surface and continued to descend, and the second estimate was after the lunar module reached its lowest point and ascended again, which was less than 0.05 seconds.
Next, what happens if you add and remove 0.05 from the missing 2x factor? Now, the best that "Suicide Burning" can achieve: the speed is reduced to 1.66 mph, which is nearly three-quarters of a way from a perfect 1 mph landing.
It's not perfect, because we still only use the first two items of the Taylor series. In addition, once it is determined that the lowest point is under the ground, it is necessary to find the time of the first impact on the ground, which involves a similar approximate calculation. A gentle landing is also doable, just reduce the altitude and speed at the end of the 14th round, then use low thrust in the 15th round, and land somewhere after 150 seconds. Martin added that all he could understand was the theoretical full-thrust landing suicide burn, which would take about 148 seconds.
Even with this bug, it's still a fun game
Finally, Martin commented that Jim Storer's moon landing game was a remarkable work for a 17-year-old high school student who used PDP-8 in 1969.
After all, there were no computer science courses in high school at the time, and not everyone knew anything about numerical calculations – even Martin himself learned it while pursuing a PhD in robotics. To Martin's surprise, the bug had been around for almost 55 years without anyone noticing it before.
However, Martin understands this: even with this bug, it is still a fun game. "The quest to not only win, but also to find the best strategy naturally leads people to try to understand the small differences. I think everyone else is just happy to play the game and have fun with it. ”
Reference Link: https://martincmartin.com/2024/06/14/how-i-found-a-55-year-old-bug-in-the-first-lunar-lander-game/
The 2024 Global Software R&D Conference (SDCon), co-hosted by CSDN and Boolan, will be held on July 4-5 at The Westin Beijing.
Led by Chris Richardson, a world-renowned software architect and technology pioneer in the field of cloud native and microservices, and Daniel Jackson, associate director of MIT's Computer and AI Lab (CSAIL) and ACM Fellow, technical experts from BAT, Microsoft, ByteDance, Xiaomi and other technical experts will gather to discuss the latest trends and technical practices of software development.