Descubren un bug de 55 años en el primer juego de Lunar Lander
(martincmartin.com)- Mientras verificaban el programa óptimo de combustible para aterrizar en el primer juego de Lunar Landing, creado en 1969 por el estudiante de secundaria Jim Storer, salió a la luz un bug: el juego determina erróneamente que la nave sigue en vuelo en el momento en que en realidad debería aterrizar
- La estrategia en cuestión es un suicide burn: apagar el motor durante 70 segundos, quemar 164.31426784 lbs/sec durante 10 segundos y luego el máximo de 200 lbs/sec; el juego se salta el aterrizaje suave que debería existir entre un aterrizaje brusco y un ascenso sin aterrizar
- El código original no usaba una simple integración de Euler, sino la ecuación del cohete de Tsiolkovsky y series de Taylor para calcular el movimiento en turnos de 10 segundos, algo bastante sofisticado para el trabajo de un estudiante de secundaria en un entorno PDP-8 de 1969
- La causa del bug era la falta de una división entre 2 en el denominador dentro de la raíz cuadrada de la fórmula que aproxima el punto más bajo de la trayectoria antes del contacto con el suelo, lo que hacía que el tiempo hasta ese mínimo se subestimara de forma consistente
- Al corregir ese factor faltante de dos y eliminar una compensación de 0.05 segundos, el resultado del suicide burn mejora hasta 1.66 MPH, pero para lograr un aterrizaje perfecto por debajo de 1 MPH todavía quedan limitaciones por la aproximación de dos términos de la serie de Taylor y el recálculo del momento de aterrizaje
Lunar Landing de 1969 y la búsqueda del aterrizaje óptimo
- Jim Storer escribió el primer Lunar Landing pocos meses después del alunizaje de Neil Armstrong, cuando era estudiante de Lexington High School en Massachusetts
- Para 1973, este juego ya se había difundido tanto que se lo describía como “by far and away the single most popular computer game”
- El juego es de texto y todo el movimiento del módulo lunar ocurre solo en la dirección vertical
- En la simulación, el jugador decide cada 10 segundos cuánto combustible quemar y debe aterrizar en la superficie lunar lo más suavemente posible
- Al buscar el programa óptimo de combustible, la estrategia teóricamente mejor no funcionaba correctamente dentro del juego
- En realidad, la nave sí llegaba a tocar la superficie
- El juego determinaba erróneamente que no había tocado la superficie
- La causa final fue una división entre dos omitida que pasó desapercibida durante casi 55 años
Aterrizaje con combustible mínimo y suicide burn
- Para aterrizar usando la menor cantidad de combustible posible, hay que descender en el menor tiempo posible
- La estrategia óptima consiste en dejar el motor apagado al principio para ganar velocidad y, en el último instante posible, desacelerar con empuje máximo para que la velocidad sea cercana a 0 justo al tocar la superficie
- La comunidad de Kerbal Space Program llama a esta estrategia suicide burn
- Porque el margen de tiempo es extremadamente ajustado y casi no hay lugar para errores
- El programa encontrado mediante prueba y error y búsqueda binaria manual fue el siguiente
- No quemar combustible durante 70 segundos
- Quemar combustible a 164.31426784 lbs/sec durante los siguientes 10 segundos
- Después, quemar combustible al máximo de 200 lbs/sec
- El juego considera un aterrizaje perfecto cualquier valor por debajo de 1 MPH
- Con este programa, la nave aterriza a más de 3.5 MPH y recibe la evaluación “could be better”
- Pero si se quema apenas 0.00000001 lbs/sec más de combustible, ya no toca la superficie y asciende a 114 MPH
- Es decir, había desaparecido el resultado de aterrizaje suave que debería existir entre un aterrizaje brusco y un ascenso sin aterrizar
Un cálculo físico más sofisticado de lo esperado
- Al principio parecía razonable esperar la clásica integración de Euler, común incluso en juegos actuales
- Se calcula la fuerza al inicio del intervalo de tiempo
- Se obtiene la aceleración con F=ma
- Se supone que esa aceleración permanece constante durante ese intervalo
- Pero el código real de Lunar Landing era más sofisticado que eso
- Jim Storer usó la solución exacta de la ecuación del cohete de Tsiolkovsky
- Para calcular logaritmos aplicó una expansión en serie de Taylor
- El valor máximo del argumento es 0.1212
- Con 5 términos lograba una precisión de más de 6 cifras
- También redujo el error de redondeo mediante simplificaciones algebraicas
- Storer recuerda que ya estaba familiarizado con conceptos como cálculo y series de Taylor, y que su padre, que era físico, lo ayudó a derivar las ecuaciones
- La razón por la que el suicide burn es óptimo también surge de esta ecuación del cohete, y esa parte no era la causa del bug
Por qué es difícil determinar el contacto con el suelo
- La ecuación del cohete funciona bien mientras la nave no toque el suelo
- Las colisiones entre cuerpos sólidos son un área difícil en los motores de dinámica, y Lunar Landing también encontraba su mayor complicación al determinar el contacto con la superficie
- No basta con revisar solo el inicio y el final de un turno de 10 segundos
- Al inicio, la nave puede venir descendiendo
- Al final, puede estar subiendo
- En medio, pudo haber bajado por debajo de la superficie y luego volver a subir
- En ese caso, el programa tiene que retroceder en el tiempo para encontrar un momento de contacto anterior
- El punto de verificación natural es el punto más bajo de la trayectoria, donde la velocidad se vuelve 0
- En la ecuación del cohete, ese mínimo no puede expresarse en forma cerrada usando solo funciones matemáticas básicas
- En una nota al pie se explica que hace falta Lambert W
- Sin embargo, sí puede aproximarse usando los primeros términos de la serie de Taylor del logaritmo
- Con solo los dos primeros términos, el problema se simplifica a una ecuación cuadrática
- Entonces se puede usar la fórmula cuadrática de nivel secundaria
- En el rango de un turno de 10 segundos, se puede esperar una precisión de alrededor de 0.1%
Forma alternativa de la fórmula cuadrática y estabilidad numérica
- En el código de Jim Storer aparece una forma donde la raíz cuadrada está en el denominador, no en el numerador
- Eso coincide no con la fórmula cuadrática habitual, sino con una forma alternativa de la fórmula cuadrática, donde la raíz queda abajo
- Esta forma alternativa tiene una ventaja numérica importante
- Después de detectar contacto con el suelo, para encontrar el tiempo real de contacto también se aproxima usando una serie de Taylor recortada que lleva a una ecuación cuadrática
- La forma común tiene un problema de división entre cero cuando el coeficiente cuadrático vale 0
- Eso ocurre cuando el empuje del cohete equilibra exactamente la gravedad
- Puede pasarles con frecuencia a jugadores que quedan flotando cerca de la superficie o bajan muy lentamente
- Cuando el empuje se acerca a la gravedad, la forma usual sufre catastrophic cancellation en el numerador, y un denominador pequeño amplifica el error
- La forma alternativa sigue funcionando bien incluso cuando la ecuación cuadrática se convierte en un caso lineal con término cuadrático 0
- Que un estudiante de secundaria en 1969 haya rederivado o aprendido esta forma resulta impresionante considerando el contexto de la época
El bug real: faltaba un factor de dos
- Al derivar la fórmula y compararla directamente, resultó ser casi igual al código de Jim Storer, salvo que faltaba el 2 que debía estar en el denominador dentro de la raíz cuadrada
- Es probable que esta omisión haya sido un simple error al derivar la fórmula o al transcribirla en la computadora
- En ese momento, MACSYMA apenas tenía un año de existencia y no era algo que pudiera usarse en una secundaria, así que la derivación tuvo que hacerse a mano, con papel y lápiz
- Por este bug, el tiempo hasta el punto más bajo se subestimaba de forma consistente
- El código intentaba compensarlo de dos maneras
- Sumando 0.05 segundos
- Haciendo una nueva estimación desde una posición más nueva y más cercana
- Pero en ciertos casos de suicide burn, esa compensación hacía que se perdiera el momento de aterrizaje
- La primera estimación quedaba en un punto donde la nave todavía descendía por encima de la superficie
- La segunda estimación quedaba después del mínimo, cuando ya estaba subiendo
- El intervalo entre ambos puntos podía ser menor a 0.05 segundos
Resultado tras la corrección y límites que quedan
- Al agregar el factor de dos faltante y eliminar la compensación de 0.05 segundos, el resultado del suicide burn mejora
- Después de la corrección, el mejor suicide burn logra una velocidad de aterrizaje de 1.66 MPH
- Eso lo acerca aproximadamente hasta las tres cuartas partes del camino hacia un aterrizaje perfecto por debajo de 1 MPH
- La razón por la que todavía no es perfecto es que se siguen usando solo los dos primeros términos de la serie de Taylor
- Una vez que se determina que el punto más bajo queda por debajo de la superficie, todavía hay que volver a encontrar el instante en que toca la superficie por primera vez
- Ese proceso también usa una aproximación similar
- Una iteración adicional podría ayudar
- Con el bug corregido, ahora el tiempo tiende a sobreestimarse, así que quizá sea necesario retroceder en el tiempo
- En ese caso, puede ser necesario elegir la otra raíz de la ecuación cuadrática
- Una alternativa más simple sería usar solo un término de la serie de Taylor y tratarlo de una forma parecida al método de Newton
- También sería posible detenerse cuando la magnitud de la velocidad baje de cierto umbral y decidir si aterrizó según la altitud en ese momento
- Pero esos cambios volverían el código más complejo, y el juego original ya era suficientemente divertido y jugable
Por qué el bug pudo pasar tanto tiempo desapercibido
- Sí es posible lograr aterrizajes suaves
- Terminando el turno 14 con baja altitud y baja velocidad
- Usando empuje bajo en el turno 15
- Y aterrizando en algún momento después de los 150 segundos
- Lo problemático es el suicide burn de empuje máximo teóricamente óptimo, que termina alrededor de los 148 segundos
- En conjunto, este código es muy impresionante para haber sido escrito por un estudiante de secundaria de 18 años en una PDP-8 en 1969
- En esa época todavía no se enseñaba informática en la secundaria, y conceptos de cálculo numérico como mejorar una estimación de forma iterativa con el método de Newton o preocuparse por el catastrophic cancellation no eran de conocimiento generalizado
- El bug pudo pasar casi 55 años desapercibido porque, incluso con él, el juego seguía siendo difícil, divertido y permitía aterrizajes suaves
- El intento de encontrar la estrategia óptima, más allá de simplemente ganar, terminó llevando a entender una pequeña discrepancia
1 comentarios
Opiniones en Hacker News
Más tarde incluso le proporcionó el código fuente, lo cual fue realmente genial.
https://technologizer.com/2009/07/19/lunar-lander/index.html
Mi parte favorita es cuando Storer dijo: “No había vuelto a pensar en ese juego desde que me gradué de la secundaria. Hasta que alguien me escribió por correo electrónico sobre esto hace unos meses, ni siquiera sabía que existían otros juegos Lunar Lander aparte del que hice en la secundaria”.
Cuando postulé en 1989 a un trabajo relacionado con Lotus Notes, le mostré el juego Lander al entrevistador, Tim Halvorsen, y él dijo: “Está genial, probémoslo en Windows 3”.
Al principio pensé que era bueno poder ver Windows 3 antes de su lanzamiento, pero enseguida dijo que quería probarlo porque “Windows 3 ejecuta todo en modo protegido, así que si un puntero se sale de rango, morirá de inmediato”.
Estuve con el corazón en la mano todo el tiempo que se ejecutó, pero por suerte Lander no murió, Tim quedó satisfecho y al final conseguí el trabajo, lo que cambió por completo mi carrera.
No pude encontrar una foto, pero por lo que recuerdo se parecía a esta máquina.
https://content.invisioncic.com/r322239/monthly_10_2015/post...
Solo que tenía terreno y cráteres, y había que aterrizar en el cráter iluminado. Cuando la nave presionaba el botón central del cráter, la luz se apagaba y se encendía en otro cráter; si apuntabas mal, chocabas con el borde, se inclinaba y fallabas.
Ahora que lo pienso, quizá el control era como en una máquina de peluches: alineabas desde arriba y luego presionabas “land”. Estaba en el antiguo Main Street Arcade de Disneyland.
Me pareció un poco raro que el artículo dijera varias veces “impresionante para un estudiante de último año de secundaria en 1969”. Para la gente con inclinación técnica que creció en la era espacial, debió haber tenido un impacto enorme, y también me recordó a la vieja película October Sky.
En la entrevista original dicen que el creador del juego era bueno en cálculo, así que si tenía interés y talento para el espacio o los cohetes, parece natural que intentara programar un juego de aterrizaje lunar.
[1]: https://www.cs.brandeis.edu/~storer/LunarLander/LunarLander/...
La era espacial pudo haber servido de inspiración, pero para el público general de la época las computadoras prácticamente no existían, y el desarrollo de software tampoco era una profesión ampliamente conocida. La carrera de ciencias de la computación apareció en Estados Unidos en 1962, así que el hecho de que fuera estudiante de último año de secundaria en 1969 es bastante notable.
Iba a una escuela secundaria grande en una ciudad bastante grande con una universidad técnica importante, pero la mayor barrera era el acceso a computadoras.
La escuela tenía un teletipo conectado a un mainframe remoto, y con amigos encontramos algunas computadoras universitarias que podíamos usar de noche, pero la mayoría solo tenía lectores de tarjetas e impresoras de línea, y no había ninguna terminal gráfica.
En esa época, la combinación de habilidades, interés y acceso probablemente era bastante rara.
https://retro365.blog/2021/12/02/bits-from-my-personal-colle...
Wikipedia sobre FOCAL:
https://en.wikipedia.org/wiki/FOCAL_(programming_language)
Desde un diagrama de cuerpo libre en física de secundaria hasta manejar dos fuerzas, gravedad y empuje, es algo que un estudiante promedio con A en física podría hacer.
Pero la gravedad depende de la distancia al centro, es decir, de un valor que cambia constantemente. Había que darse cuenta de que, aunque se empieza a 120 millas de altura, el cambio no es grande, así que puede aproximarse como una constante.
También es complicado entender cómo funciona el empuje como función de la tasa de combustión. Surgen preguntas como si al duplicar el flujo de combustible también se duplica la velocidad de los gases de escape, o cómo cambian P y T en la ley de los gases ideales PV=nRT.
Así que si le preguntó a su padre, que era físico, y encontró las características de los motores de cohete y la ecuación del cohete de Tsiolkovski, eso por sí solo es impresionante para un estudiante de último año de secundaria.
Para pasar de la velocidad a la posición hay que integrar, y no sé si al estudiante promedio con A en física se le ocurriría reemplazar una llamada a FLOG() por una serie de Taylor e integrar término por término.
También son delicados detalles como cuántos términos de la serie de Taylor usar o si converge. Si Jim pensó en estos matices, es extraordinario; aunque también es posible que simplemente haya usado 5 términos porque parecía bastante.
Aunque la simulación cerca de la Luna ya estuviera resuelta, también estaba el problema de cómo detectar el impacto con el suelo. En vez de resolver directamente la raíz donde la altitud se vuelve 0, es bastante creativo fijarse en el punto de velocidad 0 que aparece exactamente una vez durante la rotación.
Invertir la ecuación del cohete para obtener la cantidad de combustible necesaria a partir de un delta-V deseado también se traba si solo se cuenta con matemáticas de preparatoria y cálculo. En la práctica hace falta una función nueva, como Lambert W.
Al final, como hay que resolver un polinomio de quinto grado con una serie de Taylor, se necesita tomar la decisión de descartar los términos de tercer, cuarto y quinto grado para convertirlo en una cuadrática. Me parece impresionante que haya considerado válido descartar aquí términos que normalmente no descartaba en cálculos de dinámica, porque implica que entendía que se pueden usar distintos niveles de aproximación en situaciones distintas.
Además, por la forma en que usó de algún modo una forma alternativa de la ecuación cuadrática, quizá no fue simplemente algo que buscó y copió.
Había que entrar rápido en horizontal y luego desacelerar con los botones de los propulsores laterales del LEM y el motor principal para aterrizar verticalmente; si ibas demasiado rápido o te quedabas sin combustible, aparecía un cráter, y según la calidad del aterrizaje se plantaban una o más banderas de Estados Unidos.
Hace unos años tiré la única copia del código fuente porque pensé que no tenía valor y que nunca se reutilizaría, pero después me di cuenta de que había sido un juego gráfico bastante temprano en términos históricos y que podría haberse revivido con una emulación simple, así que me arrepentí.
Al volver a verla 25 años después, me sorprendió que tuviera una cantidad absurda de bugs y que la lógica estuviera tan enredada como “440 IF GOTO 450”.
Al final la reescribí ya de adulto [1], pero mi yo de la infancia no tenía ninguna posibilidad. Todavía me pregunto cómo, dentro de aquella editorial española olvidada, un código que casi funcionaba terminó convertido en algo parecido a la versión final.
[1] https://7c0h.com/blog/new/moon_landing_in_basic.html
Este tipo de código BASIC tenía raíces en las décadas de 1960 y 1970, y en las revistas impresas y recopilaciones de código donde se publicaba en esa época, los editores tenían mucha autoridad.
Como no estaba tan arraigada la idea de que el código fuente debía publicarse exactamente igual, sin cambiar ni un solo carácter, los editores solían “corregir cuidadosamente” el código fuente, pensando que eran erratas “obvias” o decisiones editoriales.
Esta lección se aprendió lenta y dolorosamente, desde que empezó la mejora general de la industria en los años 80 hasta que se extendió la idea de que no se debía tocar el código fuente en publicaciones impresas.
Me pregunto si esta dinámica también impulsó el auge de los BBS y debilitó el poder que tenían los medios impresos sobre la distribución de código fuente. Tal vez habría sido posible otra historia si quienes controlaban los medios impresos hubieran estado más abiertos a que personas externas tuvieran control absoluto sobre parte de “su” contenido.
De niño empecé a programar sin ayuda de adultos, solo con unos cuantos libros de programación de la escuela y la biblioteca local, y me sorprende haber seguido insistiendo con la programación a pesar de que muchísimos programas que ingresé a mano estaban igual de llenos de errores.
Para agregar algo sobre la lógica enredada tipo “440 IF GOTO 450”: parte del código del libro claramente necesitaba una limpieza, pero es muy probable que el BASIC típico de las computadoras domésticas de la época solo manejara números de línea y tuviera sentencias de bifurcación muy limitadas.
El BASIC que usó parece admitir programación estructurada, algo muy raro en las computadoras domésticas de entonces. Tan raro que, en 1984, una revista de C64 publicó una larga serie de al menos tres números para presentar a sus lectores las maravillas de la programación estructurada.
Debido a las fuertes limitaciones de las sentencias IF, las bifurcaciones condicionales al estilo ensamblador usando GOTO eran muy comunes y, en la práctica, necesarias.
No se podían anidar IF, y para combinar varios IF había que saltarse con un salto las partes no seleccionadas. Commodore/C64 BASIC, que en la práctica era Microsoft BASIC, ni siquiera tenía ELSE, así que normalmente se imitaba una rama ELSE con una condición negativa y un salto.
C64 BASIC tenía un comportamiento peculiar: otras sentencias en la misma línea también pertenecían al THEN. Por ejemplo,
10 IF A=1 THEN PRINT “FOO” : PRINT “BAR”imprime FOO BAR si A=1, y si no, no imprime nada.Claro, eso solo era posible si alcanzaba el espacio de la línea limitada para meter todas las sentencias. Otros dialectos de BASIC veían
PRINT “BAR”como fuera del ELSE, lo que sintácticamente era más limpio, pero podía ser menos cómodo según las funciones que ofreciera el dialecto.No existían las comodidades y el rigor que hoy damos por sentados. C64 BASIC tenía muchas rarezas que parecían producto de la implementación, por lo que se sentía especialmente “sucio”. Por ejemplo, todas las funciones debían recibir un argumento aunque en realidad no lo necesitaran, así que para imprimir la memoria restante había que escribir algo sin sentido como
?FRE(123).Mientras antes se “juegue” el 199.99999999, mejor, así que basta con hacer una búsqueda exhaustiva y elegir la entrada más temprana que produzca un aterrizaje suave.
Para que el juego reconozca el aterrizaje, la altitud debe ser menor que 0 durante aproximadamente 0.05 segundos. Si durante ese intervalo el empuje es 200 o 199, para que la altitud permanezca negativa ese tiempo, la velocidad en el punto de altitud 0 debe ser mayor a 1 MPH.
Aunque se corrija el bug, el código sigue solo aproximando el punto más bajo. Después de detectar el aterrizaje, aún hay que calcular el instante real del aterrizaje, es decir, el momento en que la altitud, no la velocidad, llega a 0, y eso también usa una aproximación.
Por eso el tiempo puede quedar un poco desfasado. Si en el último paso de tiempo se está quemando a 200 o 199, la aceleración es grande, de modo que incluso un error temporal muy pequeño produce un error grande de velocidad.
En cambio, si se quema a unos 10 lbs/sec, aunque haya un desfase de alrededor de 0.08 segundos, el cambio de velocidad no es grande.
Me pregunto si esto significa que cuanto menor es la tasa de cuadros, menos preciso es este método, o si simplemente era por la gracia de usar las ecuaciones reales
También me pregunto qué tan perceptible habría sido la diferencia entre ambos métodos con la tasa de cuadros original
https://www.cs.brandeis.edu/~storer/LunarLander/LunarLander/...
Si solo actualizas la masa y la aceleración cada 10 segundos, se vuelve tremendamente impreciso
En términos de precisión física, sobre todo cerca de la superficie, la masa cambia bastante si la tasa de consumo de combustible es alta. Pero en cuanto a la dificultad o la diversión del juego, o la estrategia del jugador, no creo que haya una gran diferencia
De hecho, una de las otras simulaciones de alunizaje del libro BASIC Computer Games parece usar ese enfoque ingenuo
Si 10 segundos es demasiado, se puede dejar cada turno de la interfaz de usuario en 10 segundos y, por dentro, subdividir cada turno en 10 pasos de tiempo de 1 segundo
El juego existente de hecho hace eso en ciertas partes, así que la simulación física está hecha para recibir un tiempo S arbitrario, no siempre los 10 segundos completos
Pero no había ningún juego de aterrizaje, y Storer fue el primero. Hay una historia interesante relacionada aquí
https://www.acriticalhit.com/moonlander-one-giant-leap-for-g...
Aunque no calcules el efecto de que la nave se vuelve más ligera al quemar combustible, es decir, aunque quites lo que hace aquí la ecuación del cohete, el suicide burn sigue siendo óptimo
La verdadera razón es que el suicide burn minimiza las pérdidas por gravedad
https://en.wikipedia.org/wiki/Gravity_loss
La intención era decir que en la dinámica hay dos partes, la ecuación del cohete y la gravedad, y que ambas se suman linealmente. La velocidad adicional causada por la gravedad hay que eliminarla aumentando el delta-V de la ecuación del cohete
El delta-V de la gravedad es la aceleración gravitatoria multiplicada por el tiempo, así que hay que minimizar el tiempo
Sorprendentemente, en la ecuación del cohete no importa cuánto tiempo toma, qué secuencia de combustión usas, si quemas continuamente a una tasa constante o con ráfagas cortas e intensas
Por eso, para aterrizar a velocidad 0 con el mínimo combustible, hay que aterrizar en el menor tiempo posible
Nunca descubrí por mi cuenta cómo aterrizar, pero recuerdo que alguien me mostró la técnica de dejarse llevar por inercia durante los primeros turnos y luego aplicar empuje máximo. En ese entonces no recuerdo el término “suicide burn”. Quizá sea un término que apareció más tarde, después de que Kerbal Space Program se hiciera famoso
También recuerdo que a mediados de los 70, en el Lawrence Hall of Science de Berkeley, este juego de alunizaje corría en algunas terminales. No sé en qué computadora se estaba ejecutando
Nunca vi el código fuente de este programa, y no tenía idea de que las matemáticas fueran tan sofisticadas. En esa época era demasiado joven para entenderlo y, sinceramente, no sé si ahora podría entenderlo
Una “función” del modo kiosco para juegos era que, con un Ctrl-C bien sincronizado, podías salir del modo kiosco y jugar otros juegos
¿Habrá sido casualidad, o una carnada lanzada a los primeros hackers?