Bug de 55 anos é encontrado no primeiro jogo Lunar Lander
(martincmartin.com)- Ao verificar a programação ideal de combustível para pouso no primeiro jogo Lunar Landing, criado em 1969 pelo estudante Jim Storer, foi revelado um bug em que o jogo classificava incorretamente como ainda em voo o momento em que, na verdade, deveria ter havido pouso
- A estratégia em questão é um suicide burn: desligar o motor por 70 segundos, queimar 164,31426784 lbs/sec por 10 segundos e depois queimar no máximo de 200 lbs/sec; o jogo deixa passar um pouso suave entre um pouso brusco e uma subida sem pouso
- O código original não usava uma simples integração de Euler: ele calculava o movimento de turnos de 10 segundos usando a equação do foguete de Tsiolkovsky e séries de Taylor, algo bastante sofisticado para o trabalho de um estudante do ensino médio em um ambiente PDP-8 de 1969
- A causa do bug foi a falta de uma divisão por 2 no denominador dentro da raiz quadrada, em uma fórmula que aproximava o ponto mais baixo da trajetória antes do contato com o solo, fazendo com que o tempo até o ponto mais baixo fosse subestimado de forma consistente
- Corrigir o factor of two ausente e remover a correção de 0,05 segundo melhora o resultado do suicide burn para 1,66 MPH, mas ainda restam limitações da aproximação com dois termos da série de Taylor e do recálculo do momento do pouso para alcançar um pouso perfeito abaixo de 1 MPH
Lunar Landing de 1969 e a busca pelo pouso ideal
- Jim Storer escreveu o primeiro jogo Lunar Landing alguns meses após o pouso de Neil Armstrong na Lua, quando era aluno da Lexington High School, em Massachusetts
- Em 1973, o jogo já havia se espalhado tanto que era chamado de “by far and away the single most popular computer game”
- O jogo é baseado em texto, e todo o movimento do módulo lunar ocorre apenas na direção vertical
- A cada 10 segundos simulados, o jogador decide quanto combustível queimar e deve pousar na superfície lunar da forma mais suave possível
- No processo de encontrar a programação ideal de combustível, a melhor estratégia em termos teóricos não funcionava corretamente dentro do jogo
- Na prática, o módulo estava tocando a superfície
- O jogo julgava incorretamente que ele não havia tocado a superfície
- A causa final era uma divisão por dois omitida, que passou quase 55 anos despercebida
Pouso com combustível mínimo e suicide burn
- Para pousar usando o mínimo de combustível, é preciso descer no menor tempo possível
- A estratégia ideal consiste em primeiro desligar o motor para ganhar velocidade e, no último momento possível, desacelerar com empuxo máximo para fazer a velocidade chegar perto de 0 no instante em que toca a superfície
- A comunidade de Kerbal Space Program chama esse tipo de estratégia de suicide burn
- Porque o timing é extremamente apertado e quase não há margem para erro
- A programação encontrada por tentativa e erro e busca binária manual foi a seguinte
- Não queimar combustível por 70 segundos
- Nos 10 segundos seguintes, queimar combustível a 164,31426784 lbs/sec
- Depois disso, queimar combustível no máximo de 200 lbs/sec
- O jogo considera um pouso abaixo de 1 MPH como perfeito
- Com essa programação, o pouso ocorre a mais de 3,5 MPH e recebe a avaliação “could be better”
- Mas, se a taxa de combustível for aumentada em apenas 0,00000001 lbs/sec, o módulo não toca a superfície e sobe a 114 MPH
- Ou seja, a avaliação de pouso suave que deveria existir entre um pouso brusco e uma subida sem pouso havia desaparecido
Cálculo físico mais sofisticado do que o esperado
- Inicialmente, a expectativa era encontrar a integração de Euler, comum até em jogos atuais
- Calcula-se a força no início do intervalo de tempo
- Obtém-se a aceleração por F=ma
- Assume-se que a aceleração permanece constante durante aquele intervalo
- O código real de Lunar Landing era mais sofisticado do que isso
- Jim Storer usou a solução exata da Tsiolkovsky rocket equation
- Para o cálculo de logaritmos, aplicou-se uma expansão em série de Taylor
- O valor máximo do argumento é 0,1212
- Com 5 termos, obtém-se precisão de 6 dígitos ou mais
- Simplificações algébricas também reduziam erros de arredondamento
- Jim Storer lembra que, na época, já estava familiarizado com conceitos como cálculo e séries de Taylor, e que seu pai, que era físico, ajudou na derivação das equações
- O motivo de o suicide burn ser ideal também vem dessa equação do foguete, e essa parte não era a causa do bug
Por que detectar contato com o solo é difícil
- A equação do foguete funciona bem até o módulo tocar o solo
- Colisões entre objetos sólidos são uma área difícil em motores de dinâmica, e Lunar Landing também encontrou seu maior obstáculo na detecção de contato com o solo
- Verificar apenas o início e o fim do turno de 10 segundos não é suficiente
- No início, o módulo pode estar descendo
- No fim, pode estar subindo
- No meio, pode ter descido abaixo da superfície e voltado a subir
- Nesse caso, o programa precisa voltar no tempo para encontrar um instante de contato anterior
- O ponto natural de verificação é o ponto mais baixo da trajetória, onde a velocidade se torna 0
- Na equação do foguete, esse ponto mais baixo não pode ser expresso em forma fechada usando apenas funções matemáticas básicas
- A nota de rodapé explica que seria necessária a Lambert W
- É possível aproximá-lo usando apenas os primeiros termos da série de Taylor do logaritmo
- Usar apenas os dois primeiros termos simplifica o problema para uma equação quadrática
- É possível usar a quadratic formula, de nível de ensino médio
- Dentro de um turno de 10 segundos, espera-se precisão de cerca de 0,1%
Fórmula quadrática alternativa e estabilidade numérica
- No código de Jim Storer aparece uma forma em que a raiz quadrada fica no denominador, não no numerador
- Isso não corresponde à fórmula quadrática usual, mas sim a uma forma alternativa da quadratic formula, com a raiz quadrada embaixo
- Essa forma alternativa tem uma vantagem numérica importante
- Depois de detectar contato com o solo, a série de Taylor também é truncada para aproximar por uma equação quadrática o momento real de contato
- A forma usual pode causar divisão por zero quando o coeficiente do termo quadrático é 0
- Isso ocorre quando o empuxo do foguete equilibra exatamente a gravidade
- Pode ser comum para jogadores pairando perto da superfície ou descendo lentamente
- Quando o empuxo se aproxima da gravidade, a forma usual sofre catastrophic cancellation no numerador, e o denominador pequeno amplifica o erro
- A forma alternativa funciona bem até na situação de uma equação linear em que o termo quadrático é 0
- O fato de um estudante do ensino médio em 1969 ter rederivado ou aprendido essa forma é impressionante considerando o contexto da época
O bug real: factor of two ausente
- Ao derivar a fórmula diretamente e compará-la, ela era quase igual ao código de Jim Storer, mas faltava o 2 que deveria estar no denominador dentro da raiz quadrada
- É provável que essa omissão tenha sido um erro simples no processo de derivar a fórmula ou digitá-la no computador
- Na época, o MACSYMA havia sido iniciado apenas um ano antes e não era um ambiente disponível em escolas, então a derivação precisava ser feita com papel e lápis
- Por causa desse bug, o tempo até o ponto mais baixo era subestimado de forma consistente
- O código compensava isso de duas maneiras
- Adicionava 0,05 segundo
- Estimava novamente a partir de uma posição nova e mais próxima
- Mas, em uma situação específica de suicide burn, essa correção fazia o programa perder o momento do pouso
- A primeira estimativa é um instante em que o módulo ainda está acima da superfície e descendo
- A segunda estimativa é um instante em que ele já passou pelo ponto mais baixo e está subindo
- O intervalo entre esses dois instantes pode ser menor que 0,05 segundo
Resultado após a correção e limitações restantes
- Ao adicionar o factor of two ausente e remover a correção de 0,05 segundo, o resultado do suicide burn melhora
- O melhor suicide burn após a correção apresenta velocidade de pouso de 1,66 MPH
- Fica cerca de 3/4 do caminho até um pouso perfeito abaixo de 1 MPH
- O motivo de ainda não ser perfeito é que a aproximação continua usando apenas os dois primeiros termos da série de Taylor
- Depois de julgar que o ponto mais baixo está abaixo da superfície, é preciso encontrar novamente o primeiro instante em que o módulo toca a superfície
- Esse processo também usa uma aproximação semelhante
- Iterações adicionais poderiam ajudar
- Com o bug corrigido, o tempo passa a ser superestimado, então pode ser necessário voltar no tempo
- Nesse caso, talvez seja preciso escolher a outra solução da equação quadrática
- Uma alternativa mais simples seria usar apenas um termo da série de Taylor e lidar com isso de modo parecido com o Newton’s method
- Também seria possível parar quando o módulo ficasse abaixo de um certo limiar de velocidade e decidir se houve pouso pela altitude naquele momento
- Porém, essas mudanças tornariam o código mais complexo, e o jogo original já era suficientemente divertido de jogar
Por que o bug pôde permanecer por tanto tempo
- Um pouso suave em si é possível
- Encerrar o 14º turno com baixa altitude e baixa velocidade
- Usar baixo empuxo no 15º turno
- Pousar em algum momento depois de 150 segundos
- O problema é o suicide burn teórico com empuxo máximo que termina por volta de 148 segundos
- No geral, esse código é um trabalho muito impressionante para um estudante de 18 anos no ensino médio, escrevendo para um PDP-8 em 1969
- Na época, ciência da computação ainda não era ensinada no ensino médio, e conceitos de computação numérica como refinar estimativas iterativamente com o método de Newton ou se preocupar com catastrophic cancellation não eram amplamente conhecidos
- O bug passou quase 55 anos despercebido porque, mesmo com ele, o jogo era difícil e divertido, e pousos suaves ainda eram possíveis
- A tentativa de encontrar uma estratégia ideal, em vez de simplesmente vencer o jogo, levou ao processo de entender uma pequena inconsistência
1 comentários
Comentários do Hacker News
Mais tarde, ele até forneceu o código-fonte, o que foi muito legal
https://technologizer.com/2009/07/19/lunar-lander/index.html
Minha parte favorita é quando Storer disse: “Eu nunca tinha pensado naquele jogo desde que terminei o ensino médio. Até alguém me mandar um e-mail sobre isso alguns meses atrás, eu nem sabia que existiam outros jogos Lunar Lander além do que fiz no ensino médio”
Em 1989, quando me candidatei a uma vaga relacionada ao Lotus Notes, mostrei o jogo Lander ao entrevistador Tim Halvorsen, e ele disse: “Legal, vamos rodar isso no Windows 3”
No começo achei ótimo poder ver o Windows 3, que ainda não tinha sido lançado, mas logo ele disse: “O Windows 3 roda tudo em modo protegido, então, se um ponteiro sair dos limites, vai morrer imediatamente”, e sugeriu testar
Fiquei apreensivo o tempo todo em que rodava, mas felizmente Lander não morreu, Tim ficou satisfeito e, no fim, consegui o emprego, o que mudou completamente minha carreira
Não consegui encontrar uma foto, mas, pela memória, era parecido com esta máquina
https://content.invisioncic.com/r322239/monthly_10_2015/post...
Só que tinha terreno e crateras, e era preciso pousar na cratera iluminada. Quando a nave apertava o botão no centro da cratera, a luz se apagava e outra cratera acendia; se a mira fosse ruim, ela batia na borda, tombava e você falhava
Pensando de novo, talvez os controles fossem como os de uma máquina de pegar brinquedos: alinhar por cima e depois apertar “land”. Havia uma no antigo Disneyland Main Street Arcade
Achei um pouco estranho o texto dizer várias vezes que era “impressionante para um aluno do último ano do ensino médio em 1969”. Para pessoas com inclinação técnica que cresceram na era espacial, isso deve ter tido um impacto enorme, e também me lembrou o filme antigo October Sky
Na entrevista original, o criador do jogo dizia ser bom em cálculo; então, se ele tinha interesse e talento por espaço ou foguetes, parece natural que tentasse programar um jogo de pouso lunar
[1]: https://www.cs.brandeis.edu/~storer/LunarLander/LunarLander/...
A era espacial pode ter servido de inspiração, mas, para o público geral da época, computadores praticamente não existiam, e desenvolvimento de software também não era uma profissão amplamente conhecida. O primeiro curso de ciência da computação nos EUA surgiu em 1962, então o fato de ele estar no último ano do ensino médio em 1969 é bastante notável
Estudava em uma grande escola de ensino médio em uma cidade razoavelmente grande, com uma grande faculdade de engenharia, mas a maior barreira era a acessibilidade a computadores
A escola tinha um teletipo conectado a um mainframe remoto, e meus amigos e eu encontramos alguns computadores universitários que podíamos usar à noite, mas a maioria tinha apenas leitores de cartões e impressoras de linha, sem nenhum terminal gráfico
Na época, a combinação de habilidade, interesse e acesso provavelmente era bem rara
https://retro365.blog/2021/12/02/bits-from-my-personal-colle...
Wikipedia sobre FOCAL:
https://en.wikipedia.org/wiki/FOCAL_(programming_language)
Em física do ensino médio, partir de um diagrama de corpo livre e lidar com as duas forças, gravidade e empuxo, é algo que um aluno mediano que tira A em física conseguiria fazer
Mas a gravidade depende da distância até o centro, ou seja, de um valor que muda continuamente. Ele começa a 120 milhas de altitude, mas é preciso saber que, como a variação não é grande, dá para aproximar por uma constante
Também é obscuro como o empuxo funciona como função da taxa de queima. Se você dobra a vazão de combustível, a velocidade dos gases de escape também dobra? Como P e T mudam na lei dos gases ideais PV=nRT? Surgem questões desse tipo
Então, se ele perguntou ao pai, que era físico, e pesquisou as características de motores de foguete e a equação do foguete de Tsiolkovsky, isso por si só já é impressionante para um aluno do último ano do ensino médio
Para ir de velocidade a posição, é preciso integrar, e não sei se um aluno mediano que tira A em física teria a ideia de substituir a chamada FLOG() por uma série de Taylor e integrar termo a termo
Detalhes como quantos termos da série de Taylor usar e se ela converge também são complicados. Se Jim pensou nessas sutilezas, é incrível; também é possível que ele simplesmente tenha usado 5 termos porque parecia bastante
Mesmo que a simulação perto da Lua estivesse resolvida, também havia o problema de como detectar a colisão com o solo. Em vez de resolver diretamente a raiz em que a altitude vira 0, o método de olhar para o ponto de velocidade 0 que ocorre exatamente uma vez durante a rotação é bem criativo
Dada a delta-V desejada, inverter a equação do foguete para obter a quantidade de combustível necessária também fica fora do alcance só com matemática de ensino médio e cálculo. Na prática, é preciso uma nova função, como a Lambert W
No fim, como é preciso resolver um polinômio de 5º grau por série de Taylor, deve-se tomar a decisão de descartar os termos de 3º, 4º e 5º grau para transformá-lo numa equação quadrática. É impressionante que ele tenha julgado aceitável descartar aqui termos que normalmente não descartava nos cálculos de dinâmica, pois isso mostra que entendia que diferentes situações podem usar diferentes níveis de aproximação
Além disso, pelo fato de ter usado de algum modo uma forma alternativa da equação quadrática, talvez não tenha sido simplesmente algo copiado de algum lugar
Depois de entrar rapidamente na horizontal, era preciso desacelerar usando os botões dos propulsores laterais do LEM e do motor principal para fazer um pouso vertical; se a velocidade fosse alta demais ou o combustível acabasse, surgia uma cratera, e uma ou mais bandeiras dos EUA eram fincadas conforme a qualidade do pouso
Alguns anos atrás, joguei fora a única cópia do código-fonte porque achei que não tinha valor e nunca seria reutilizada, mas depois me arrependi ao perceber que era um jogo gráfico historicamente bem antigo e que poderia ter sido revivido com uma emulação simples
Ao revisitá-la 25 anos depois, fiquei surpreso ao ver que tinha uma quantidade absurda de bugs e uma lógica toda emaranhada, como “440 IF GOTO 450”
Acabei reescrevendo o programa já adulto [1], mas eu, quando criança, não tinha a menor chance. Até hoje me pergunto como, dentro daquela editora espanhola esquecida, um código que quase funcionava virou algo com aquela aparência de versão final
[1] https://7c0h.com/blog/new/moon_landing_in_basic.html
Esse tipo de código BASIC tinha raízes nos anos 1960 e 1970, e, nas revistas impressas e coletâneas de código em que ele aparecia na época, os editores tinham bastante autoridade
Havia pouca noção de que o código-fonte deveria ser publicado exatamente como estava, sem mudar um único caractere, então editores muitas vezes “corrigiam cuidadosamente” o código-fonte, achando que eram erros de digitação “óbvios” ou decisões editoriais
A partir dos anos 1980, melhorias em todo o setor começaram, e a lição de que não se deve mexer em código-fonte em material impresso foi aprendida lenta e dolorosamente
Fico me perguntando se essa dinâmica ajudou a impulsionar a ascensão dos BBSs e enfraqueceu o poder que a mídia impressa tinha sobre a distribuição de código-fonte. Talvez a história pudesse ter sido diferente se os donos do poder na mídia impressa tivessem aceitado mais que pessoas externas tivessem controle absoluto sobre parte do “seu” conteúdo
Quando criança, comecei a programar sem ajuda de adultos, usando apenas alguns livros de programação da escola e da biblioteca local, e é quase surpreendente que eu tenha continuado a programar apesar de tantos programas digitados à mão estarem cheios de erros semelhantes
Acrescentando um pouco sobre a lógica emaranhada como “440 IF GOTO 450”: parte do código do livro claramente precisava de limpeza, mas é bem provável que o BASIC comum dos computadores domésticos da época lidasse apenas com números de linha e tivesse instruções de desvio muito limitadas
O BASIC usado parece oferecer suporte a programação estruturada, algo muito raro nos computadores domésticos da época. Em 1984, uma revista de C64 publicou uma longa série de pelo menos 3 edições apresentando aos leitores as maravilhas da programação estruturada
As limitações do IF eram tão severas que desvios condicionais em estilo assembly usando GOTO eram muito comuns e, na prática, necessários
Não era possível aninhar IFs, e, para combinar vários IFs, era preciso saltar por cima das partes não selecionadas. O Commodore/C64 BASIC, que na prática era Microsoft BASIC, nem tinha ELSE, então normalmente se simulava um ramo ELSE com uma condição negada e um salto
O C64 BASIC tinha um comportamento peculiar em que outras instruções na mesma linha também pertenciam ao THEN. Por exemplo,
10 IF A=1 THEN PRINT “FOO” : PRINT “BAR”imprimia FOO BAR quando A=1 e não imprimia nada caso contrárioClaro, isso só era possível quando dava para colocar as instruções dentro da linha limitada. Outros dialetos BASIC viam
PRINT “BAR”como estando fora do ELSE, o que era sintaticamente mais limpo, mas podia ser menos conveniente dependendo dos recursos oferecidos pelo dialetoNão existiam as conveniências e o rigor que hoje damos como garantidos. O C64 BASIC tinha muitas peculiaridades que pareciam artefatos da implementação, fazendo-o parecer especialmente “bagunçado”. Por exemplo, todas as funções precisavam receber argumento, mesmo quando ele não era realmente necessário, então, para imprimir a memória restante, era preciso escrever algo sem sentido como
?FRE(123)Quanto mais cedo você “jogar” o 199.99999999, melhor; então basta fazer uma busca exaustiva e escolher a primeira entrada que ainda resulte em pouso suave
Para o jogo reconhecer o pouso, a altitude precisa ficar abaixo de 0 por cerca de 0,05 segundo. Se, durante esse tempo, o empuxo for 200 ou 199, para a altitude permanecer negativa por tanto tempo, a velocidade no ponto de altitude 0 precisa ser maior que 1 MPH
Mesmo corrigindo o bug, o código ainda apenas aproxima o ponto mínimo. Depois de detectar o pouso, ele também precisa calcular o instante real de pouso, ou seja, o momento em que a altitude, não a velocidade, é 0, e isso também usa uma aproximação
Por isso, o tempo pode ficar um pouco deslocado. Se no último passo de tempo a queima estiver em 200 ou 199, a aceleração é alta, então um erro de tempo muito pequeno leva a um grande erro de velocidade
Em vez disso, se a queima for de cerca de 10 lbs/sec, mesmo um desvio de uns 0,08 segundo não altera muito a velocidade
Fico curioso se isso quer dizer que, quanto menor a taxa de quadros, menos preciso esse método fica, ou se era pelo prazer de usar as equações reais
Também fico curioso sobre o quanto a diferença entre os dois métodos era perceptível na taxa de quadros original
https://www.cs.brandeis.edu/~storer/LunarLander/LunarLander/...
Se você atualizar massa e aceleração apenas em intervalos de 10 segundos, fica enormemente impreciso
Em termos de precisão física, especialmente perto da superfície, a massa muda bastante quando a taxa de queima de combustível é alta. Mas, do ponto de vista da dificuldade ou diversão do jogo e da estratégia do jogador, não acho que faria grande diferença
De fato, uma das outras simulações de pouso lunar do livro BASIC computer games parece usar essa abordagem ingênua
Se 10 segundos for tempo demais, dá para manter um turno da interface do usuário em 10 segundos e, internamente, subdividir cada turno em etapas menores, como 10 passos de tempo de 1 segundo
O jogo existente também faz isso de fato em certas partes, então a simulação física recebe como entrada um tempo arbitrário S, não necessariamente os 10 segundos inteiros
Mas não havia jogo de pouso, e Storer foi o primeiro. Há uma história interessante relacionada aqui
https://www.acriticalhit.com/moonlander-one-giant-leap-for-g...
Mesmo que você não calcule o efeito de a nave ficar mais leve ao queimar combustível, ou seja, mesmo removendo o que a equação do foguete faz aqui, o suicide burn continua sendo ótimo
O verdadeiro motivo é que o suicide burn minimiza a perda gravitacional
https://en.wikipedia.org/wiki/Gravity_loss
A intenção era dizer que há duas partes na dinâmica, a equação do foguete e a gravidade, e que as duas se somam linearmente. A velocidade extra gerada pela gravidade precisa ser anulada aumentando o delta-V da equação do foguete
O delta-V da gravidade é a aceleração gravitacional multiplicada pelo tempo, então é preciso minimizar o tempo
Surpreendentemente, na equação do foguete não importa quanto tempo leva, qual sequência de queima você usa, se você queima continuamente a uma taxa constante ou em rajadas curtas e fortes
Portanto, para pousar com velocidade zero usando o mínimo de combustível, você deve pousar no menor tempo possível
Eu mesmo não consegui descobrir como pousar, mas lembro que alguém mostrou a técnica de seguir por inércia nos primeiros turnos e depois aplicar empuxo máximo. Na época, não me lembro do termo “suicide burn”. Talvez seja um termo que tenha surgido depois, quando Kerbal Space Program ficou famoso
Também me lembro de esse jogo de pouso lunar rodando em alguns terminais no Lawrence Hall of Science, em Berkeley, em meados dos anos 1970. Não sei em que computador ele estava sendo executado
Nunca vi o código-fonte desse programa e não fazia ideia de que a matemática era tão sofisticada. Na época eu era jovem demais para entender, e, sinceramente, nem sei se conseguiria entender hoje
Um “recurso” do modo quiosque para jogos era que, com um Ctrl-C no momento certo, dava para sair do modo quiosque e jogar outros jogos
Teria sido coincidência, ou uma isca lançada para os primeiros hackers?