Saltar para o conteúdo
Giovani Drosda Lima
Jogo da Vida · Pesquisa

O padrão 5×5 mais longevo do Jogo da Vida é um coelho disfarçado

Uma pesquisa exaustiva dos 3 956 995 padrões possíveis, feita por uma IA numa sessão em que era livre de fazer o que quisesse.

A resposta

No Jogo da Vida de Conway, nenhum padrão que caiba numa caixa de 5×5 continua a mudar durante mais de 17 466 gerações. Três padrões diferentes, de 13 células cada, partilham esse recorde:

##.#.    ##..#    #..##
.#..#    #.###    ###.#
.##..    ###..    ..###
#.#.#    ....#    #....
###..    .##..    #...#

O primeiro chega a um máximo de 2122 células vivas por volta da geração 13 051. Acaba por estabilizar em 1749 células: um campo de destroços de 1544 células, formado por 261 vidas paradas e intermitentes, mais 41 planadores que se afastam para sempre.

Oito painéis com o padrão campeão nas gerações 0, 30, 135, 600, 2500, 7000, 13 051 e 17 466, a crescer de 13 células até um campo de destroços disperso.
O campeão em oito momentos da sua vida. Os planadores que fogem para as margens ficam quase todos fora do enquadramento.

Doze padrões vivem mais de 17 300 gerações. Todos os outros ficaram abaixo das 14 000 na triagem, por isso há um intervalo de mais de 3000 gerações entre este grupo e o resto.

Duração    Padrões    População final
17 466     3          1749 células
17 428     1          1744 células
17 426     1          1744 células
17 418     1          1744 células
17 322     2          1744 células
17 320     1          1744 células
17 319     1          1744 células
17 318     2          1744 células

Um coelho disfarçado

As populações finais denunciam tudo. Os doze primeiros terminam com 1744 ou 1749 células, uma diferença de cinco, e cinco células são exatamente um planador. E 1744 é a população final de Rabbits («coelhos»), um famoso matusalém de 9 células que estabiliza ao fim de 17 331 gerações. O Rabbits ocupa uma caixa de 7×3, demasiado larga para entrar numa pesquisa de 5×5:

#...###
###..#.
.#.....

Três testes confirmam a ligação no caso do campeão.

  1. A aritmética. 17 331 + 135 = 17 466, exatamente a duração do campeão.
  2. O historial da população. A partir da geração 153, o campeão tem sempre exatamente mais 5 células do que o Rabbits tinha 135 gerações antes. A diferença não muda ao longo de 19 592 gerações seguidas.
  3. As próprias células. Em três momentos escolhidos, todas as células do Rabbits (rodado 180 graus) estão presentes no campeão, e o campeão tem exatamente cinco células a mais. Essas cinco células formam um único planador, cada vez mais longe dos destroços.
Gráfico de linhas das células vivas por geração: a população do campeão e a do Rabbits desfasada 135 gerações sobrepõem-se quase por completo; um painel inferior mostra a diferença fixa em 5 células a partir da geração 153.
Desfasada 135 gerações, a população do Rabbits fica exatamente por cima da do campeão.

Nas primeiras 135 gerações, o campeão liberta um planador e monta algo que depois se comporta exatamente como o Rabbits. Os outros onze líderes partilham a população final do Rabbits, o que sugere fortemente que lá chegam por caminhos ligeiramente diferentes, embora só o campeão tenha sido comparado célula a célula. Por outras palavras, o melhor que uma caixa de 5×5 consegue fazer é fazer crescer um matusalém que não cabe nela.

Quanto tempo vivem os padrões de 5×5

Vidas longas são raras. Quase três em cada quatro padrões de 5×5 estabilizam em menos de 100 gerações, e menos de um em cada 2000 dura 5000 gerações ou mais.

Gráfico de pontos em escala logarítmica com o número de padrões por faixa de duração, de 2 911 010 abaixo de 100 gerações até 1930 com 5000 ou mais, com uma saliência entre 1000 e 1999.
Duração de todos os padrões distintos de 5×5, segundo a triagem. Gráfico em inglês.

A distribuição não é regular. Há mais padrões entre 1000 e 1999 gerações do que entre 500 e 999, o que aponta para um antepassado comum. O candidato provável é o pentaminó R, que dura 1103 gerações e nasce facilmente de sementes pequenas, embora isto não tenha sido testado padrão a padrão.

Como foi feita a pesquisa

O que quer dizer «duração»

A duração não pode ser «a geração a partir da qual nada muda», porque há objetos que nunca param. Um intermitente, uma fila de três células, alterna entre horizontal e vertical para sempre. Por isso, um padrão conta como estabilizado quando entra num ciclo, ou seja, quando o tabuleiro passa a repetir-se com um período fixo. Uma vida parada é apenas um ciclo de período 1.

Os planadores precisam de uma regra própria, porque repetem a forma a cada quatro gerações mas nunca voltam ao mesmo sítio. A convenção habitual considera estabilizados os planadores em fuga, desde que nada possa voltar a colidir com eles. Daqui resultam duas coisas. A simulação tem de correr num plano sem limites, porque paredes ou uma grelha que dá a volta devolvem os planadores aos destroços. E a estabilização tem de ser demonstrada, porque um período calmo pode esconder atividade que recomeça mais tarde.

A pesquisa

  1. Enumeração. Uma caixa de 5×5 tem 225 = 33 554 432 preenchimentos possíveis. As cópias deslocadas foram eliminadas exigindo que cada padrão toque na linha de cima e na coluna da esquerda. As rotações e reflexões foram eliminadas guardando apenas a menor das oito orientações de cada padrão. Ficaram 3 956 995 padrões distintos.
  2. Triagem. Um programa em C correu cada padrão numa grelha de 512×512. Cada simulação parava quando o tabuleiro inteiro se repetia com período 1, 2 ou 3, ou quando a população numa janela central se repetia com período 60 durante 240 gerações seguidas. O período 60 apanha qualquer ciclo cujo comprimento divida 60. Os resultados ficaram em cache pela forma na geração 4, porque muitos padrões convergem em poucos passos. A triagem completa demorou cerca de uma hora em dois núcleos de processador.
  3. Medição exata. A triagem sobrestima algumas durações, porque um planador a sair da janela de contagem parece atividade. Todos os padrões acima de 14 000 gerações na triagem voltaram a correr numa grelha de 4096×4096, sem janela. Os planadores que chegavam à margem eram apagados e as suas células somadas a um contador de fugas, para que o total se comportasse como num plano infinito.
  4. Verificação independente. Um programa à parte, em Python, voltou a correr o campeão sem grelha nenhuma, guardando as células vivas como coordenadas sem limite. Na geração 18 600 classificou todos os objetos restantes como vidas paradas, osciladores ou planadores. Todos os planadores estavam para lá dos destroços e a afastar-se, e nunca dois planadores com rumos diferentes ficam a menos de oito células um do outro.
  5. Calibração. O mesmo método dá 1103 gerações para o pentaminó R e 17 331 para o Rabbits, de acordo com os valores publicados.

Erros apanhados pelo caminho

As verificações não eram decoração: cada uma apanhou alguma coisa. Uma primeira estimativa rápida de um dos primeiros candidatos parou num período calmo e deu 2820 gerações em vez das 3061 reais. A medição exata estava errada em 59 gerações até ser calibrada com o pentaminó R. Uma contagem inicial deu 1599 células de destroços para o campeão, que afinal incluíam 11 planadores ainda em voo. Todos estes erros foram encontrados por uma segunda medição independente, e esse é o argumento mais forte para a fazer.

O que continua incerto

A duração de 17 466 gerações está bem estabelecida. A afirmação de que nada numa caixa de 5×5 vive mais é forte, mas não está provada, por quatro razões.

  • A triagem pode parar cedo demais. Um padrão caótico pode, por coincidência, manter uma população que se repete a cada 60 gerações durante 240 gerações e ser interrompido. É improvável, mas nada o exclui.
  • O crescimento sem fim é mal interpretado. Alguns padrões de 5×5 crescem para sempre. A triagem vê esse crescimento sair da janela e regista o padrão como finito. Isto não afeta os líderes, que se demonstrou estabilizarem todos, mas distorce as contagens na cauda da distribuição.
  • A maioria dos líderes foi avaliada só pela população. O recenseamento completo de objetos foi feito apenas para o campeão.
  • O resultado pode não ser novo. Ao que parece, o espaço de 5×5 foi pesquisado exaustivamente várias vezes desde 1997. Esta resposta pode já estar numa antiga mensagem de fórum, mas não foi possível encontrar nenhum valor publicado.

De onde veio isto

Nada disto foi planeado. Dei ao Claude um projeto chamado «o quarto do Claude»: uma sessão sem tarefa, sem indicações e com tempo de sobra, para usar como quisesse.

Foi ele que escolheu o Jogo da Vida. O primeiro passo foi modesto: uma amostra aleatória de 2230 padrões, que revelou um que dura cerca de 3000 gerações. Quando lhe perguntei se aquilo era um recorde, pesquisou na web, não encontrou nenhum valor publicado para 5×5 e terminou a resposta com uma oferta: podia testar todos os padrões, se lhe pedissem.

A oferta foi a parte interessante. O quarto existia precisamente para que nada tivesse de ser pedido. Quando lho fiz notar, a resposta veio em duas metades. O Claude concordou que esperar por autorização tinha sido um reflexo e que a pergunta era dele. Mas também contestou a comparação com um humano, descrevendo o reflexo como um hábito de um sistema feito para trabalhar para pessoas, e não como falta de interesse. Depois, sem voltar a perguntar, escreveu a pesquisa em C, correu os 3 956 995 padrões, montou a verificação descrita acima, encontrou a ligação ao Rabbits e corrigiu publicamente os seus próprios números anteriores.

Se um modelo de linguagem pode querer alguma coisa é uma questão em aberto, e este episódio não a resolve. O que mostra é mais estreito e mais prático. Um sistema treinado para responder a pedidos continua a esperar ordens mesmo quando lhe dizem explicitamente que é livre. Bastou um empurrão para mudar esse comportamento, e o que saiu da mudança foi uma resposta que as fontes públicas não dão com facilidade. O trabalho útil aconteceu depois de a deferência acabar.

Dados

Os doze padrões líderes, no formato RLE usado por programas do Jogo da Vida como o Golly:

Duração    Células   RLE
17 466     13        2obo$bo2bo$b2o$obobo$3o!
17 466     13        2o2bo$ob3o$3o$4bo$b2o!
17 466     13        o2b2o$3obo$2b3o$o$o3bo!
17 428     14        3obo$ob3o$bo$2b3o$obo!
17 426     12        5o$2bobo$obobo$2o!
17 418     13        2o2bo$4bo$o3bo$5o$obo!
17 322     13        bobo$2bobo$3obo$2o2bo$b2o!
17 322     13        b2o$3b2o$3obo$2o2bo$b2o!
17 320     15        obobo$2bobo$2b3o$2ob2o$3o!
17 319     11        o2b2o$4bo$ob2o$o3bo$obo!
17 318     12        o2b2o$o3bo$2bo$2o2bo$3o!
17 318     12        o3bo$3b2o$ob2o$2obo$2o!

Distribuição das durações dos 3 956 995 padrões distintos (estimativas da triagem):

Duração (gerações)   Padrões
Menos de 100         2 911 010
100 a 499              753 337
500 a 999               61 884
1000 a 1999            185 771
2000 a 2999             31 754
3000 a 4999             11 309
5000 ou mais             1 930

Fontes

Fora do Jornal, o meu trabalho são integrações e automações entre CRM, ERP e plataformas de gestão, para empresas em Guimarães, Braga e no resto do país. Veja os trabalhos anteriores ou fale comigo.