Jogo da vida

Esta página cita fontes, mas que não cobrem todo o conteúdo. Ajude a inserir referências (Encontre fontes: ABW  • CAPES  • Google (N • L • A)). (Março de 2016)

O jogo da vida é um autómato celular desenvolvido pelo matemático britânico John Horton Conway em 1970.^[1] É o exemplo mais bem conhecido de autômato celular.

O jogo foi criado de modo a reproduzir, através de regras simples, as alterações e mudanças em grupos de seres vivos, tendo aplicações em diversas áreas da ciência.

As regras definidas são aplicadas a cada nova "geração"; assim, a partir de uma imagem em um tabuleiro bi-dimensional definida pelo jogador, percebem-se mudanças muitas vezes inesperadas e belas a cada nova geração, variando de padrões fixos a caóticos.

O jogo da vida se passa em um arranjo bidimensional infinito de células que podem estar em um de dois estados, vivo ou morto. Cada célula interage com suas oito vizinhas, as células adjacentes horizontal, vertical e diagonalmente. O jogo evolui em unidades de tempo discretas chamadas de gerações.^[2] A cada nova geração, o estado do jogo é atualizado pela aplicação das seguintes regras:

1. Toda célula morta com exatamente três vizinhos vivos torna-se viva (nascimento).
2. Toda célula viva com menos de dois vizinhos vivos morre por isolamento.
3. Toda célula viva com mais de três vizinhos vivos morre por superpopulação.
4. Toda célula viva com dois ou três vizinhos vivos permanece viva.^[3]

As regras são aplicadas simultaneamente em todas as células para chegar ao estado da próxima geração.^[4]

Um dos problemas matemáticos mais famosos dos anos 40, do século XX, era o de achar uma máquina capaz de construir cópias de si mesma, que teve uma solução baseada em um autômato celular extremamente engenhoso e complicado inventado pelo renomado matemático John von Neumann. Conway inventou o Jogo da Vida (ou Game of Life) ao utilizar suas descobertas anteriores relacionadas com o problema de encontrar um grupo simétrico de esferas em 24 dimensões, proposto por John Leech para simplificar a solução de von Neumann.

O jogo fez sua primeira aparição na edição de Outubro de 1970 da Scientific American, na coluna de jogos matemáticos de Martin Gardner. De um ponto de vista teórico, ele é interessante, pois tem o poder de uma máquina de Turing universal: tudo pode ser computado através de algoritmos no Jogo da Vida de Conway.^[5][6] Também era dito desde 1970 que foi destinado mais tempo de computação ao Jogo da Vida do que a qualquer outra atividade. Gardner escreveu:

"O jogo fez Conway famoso instantaneamente, mas ele também abriu um novo campo na pesquisa matemática, o campo dos autômatos celulares... Por causa das analogias de Life com o aumento, redução e alteração de uma sociedade de organismos vivos, isto pertence a uma classe crescente que é chamada "jogos de simulação" - jogos que recriam processos do mundo-real."

Desde sua publicação, ele tem atraído muito interesse devido aos caminhos surpreendentes que pode tomar. Life é um exemplo de auto-organização. Ele é interessante para biólogos, matemáticos, estatísticos, economistas, filósofos e artistas por permitir a observação do modo como imagens complexas podem surgir de implementações de regras muito simples.

O Jogo da Vida tem um número de imagens reconhecidas que emergem de posições iniciais particulares. Antes da publicação, muitas imagens interessantes já haviam sido descobertas, incluindo o sempre envolvente R-pentomino (mais conhecido como "F-pentomino" fora do jogo), o auto propulsionado "glider", e várias "guns" (armas) que geravam um fluxo sem fim de novas imagens, todas aumentando o interesse no jogo. Sua popularidade foi ajudada pelo fato de ele ter vindo justo no momento em que uma nova geração de minicomputadores de baixo custo estavam sendo disponibilizados no mercado, significando que o jogo poderia ser rodado por horas nessa máquinas que não eram utilizadas de noite. Isto escondeu a popularidade posterior dos fractais gerados por computador. Para muitos aficcionados, Life era simplesmente um desafio de programação, um método divertido de gastar os ciclos da CPU. Para alguns, no entanto, Life tinha conotações mais filosóficas. Ele desenvolveu um culto através da década de 1970 e no meio da década de 1980; os desenvolvimentos atuais foram tão longe a ponto de criar emulações teóricas de sistemas de computadores com as regras de um tabuleiro de Life.^[7][8]

Este "jogo" é na realidade um jogo sem jogador, o que quer dizer que sua evolução é determinada pelo seu estado inicial, não necessitando de nenhuma entrada de jogadores humanos. Ele é jogado em um conjunto de células quadradas que seguem ao infinito em todas as direções. Cada célula tem oito "vizinhos", que são as células adjacentes, incluindo as diagonais. Cada célula pode estar em dois estados: "viva" ou "morta". (Também são usados os termos "ligado" e "desligado".) O estado do tabuleiro evolui e se modifica em pequenas passagens de tempo. Os estados de todas as células em um instante são considerados para calcular o estado de todas as células no instante seguinte. Todas as células são atualizadas simultaneamente. As transições dependem apenas do número de vizinhos vivos (ver as regras acima).

A ideia básica do "jogo" é começar com uma configuração simples de células vivas (organismos) que são colocadas em um tabuleiro 2D de vários métodos. Isto constitui a primeira geração. As "leis genéticas" de Conway para nascimentos, mortes e sobrevivência (as quatro regras acima) são então aplicadas e a nova geração é então colocada de acordo. Geração a geração os "jogador(es)" observam as várias imagens que surgem.

De uma imagem inicial de células vivas no tabuleiro, percebe-se que, conforme passam as gerações, a população anda constantemente de modo não usual, algumas vezes belo e quase sempre inesperado, porém muda. Em muito poucos casos a sociedade eventualmente morre (todas as células se tornam células mortas), apesar de que isso pode não acontecer até que ocorram uma série de novas gerações. A maioria das imagens iniciais chegam a figuras estáveis - Conway chama-as de "vida parada" - que não podem mudar ou imagens que oscilam para sempre. Imagens sem simetria inicial tendem a se tornar simétricas. Uma vez que isto ocorre, a simetria não pode mais ser perdida, apesar de poder crescer em riqueza.

Conway originalmente supôs que nenhuma imagem poderia crescer ilimitadamente. Em outras palavras, qualquer configuração com um número finito de células não pode crescer além de um limite finito superior ao número de células do campo. Esta foi provavelmente a mais profunda e mais difícil questão colocada pelo jogo atualmente. Conway ofereceu um prêmio de $50 à primeira pessoa que pudesse provar a afirmação ou seu contrário antes do fim de 1970. Um caminho para provar seu contrário era ser capaz de descobrir imagens que continuassem adicionando contadores ao campo: Uma "gun" (uma configuração que constantemente atira objetos que se movimentam, como o "glider") ou um "puffer train" (uma configuração que se move mas deixa atrás uma trilha de "fumaça"). O prêmio foi ganho em Novembro do mesmo ano por um time do MIT, a configuração inicial (mostrada no topo da página) cresce como um gun, emitindo seu primeiro glider na 40a geração. A gun emite então um novo glider a cada 30 gerações.

Existe uma série de diferentes imagens que podem ocorrer no Jogo da Vida, incluindo imagens paradas ("vidas paradas"), imagens repetitivas ("osciladores" - o conjunto de vidas paradas), e imagens que se movimentam através do tabuleiro ("naves espaciais"). Os exemplos mais simples dessas classes são mostrados abaixo, com as células vivas em preto, e as células mortas em branco.

Bloco (block)	Bote (boat)	Piscador (blinker)	Sapo (toad)	Planador (glider)	Espaçonave peso-leve (lightweight spaceship)

O "bloco" e o "bote" são vidas paradas, o "blinker" e o "sapo" são osciladores, e o "glider" e o "lightweight spaceship" ("LWSS") são naves espaciais que seguem seu caminho no tabuleiro conforme o tempo passa.

Imagens chamadas "Matusalens" podem evoluir por longos períodos de tempo antes de se repetir. "Diehard" é uma imagem que eventualmente desaparece após 130 gerações, ou passos. "Acorn" leva 5206 gerações para criar 13 gliders depois se estabiliza como vários osciladores.

Diehard	Acorn

Na aparição original do jogo em "Jogos Matemáticos", Conway ofereceu um prêmio em dinheiro para quem descobrisse qualquer imagem que crescesse indefinidamente. A primeira dessas foi encontrada por Bill Gosper em novembro de 1970. Ela incluía "guns (armas)", que eram estacionárias e atiravam gliders ou outras nave espaciais; "puffers", que se movem deixando atrás uma trilha de fumaça; e "rakes", que se movem e emitem naves espaciais. Gosper também descobriu depois uma imagem com uma taxa de crescimento quadrática, chamada de "breeder", que trabalhava deixando atrás uma trilha de guns. Desde então, uma série de construções complicadas têm sido feitas, incluindo portas lógicas de gliders, um somador, um gerador de números primos e uma unidade de célula que emula o Jogo da Vida em uma escala muito maior e a passos lentos.

O primeiro glider gun encontrado é ainda o menor conhecido:

Posteriormente, foram encontradas imagens mais simples que tinham crescimento infinito. Todas as três imagens a seguir possuem crescimento infinito. As duas primeiras criam uma chave com um bloco, enquanto a terceira cria dois. A primeira tem apenas dez células vivas (o que se provou que é o mínimo). A segunda cabe em um quadrado de 5x5. A terceira possui apenas 1 célula de altura:

É possível que gliders interajam com outros objetos de modos interessantes. Por exemplo, se dois gliders são atirados na direção de um bloco, o bloco irá se aproximar da fonte dos gliders. Se três gliders são atirados no mesmo lugar, o bloco irá se afastar. Esta "memória de bloco deslizante" pode ser usada para simular um contador. É possível construir portas lógicas AND, OR e NOT usando gliders. É possível construir uma imagem que aja como uma máquina de estado finito conectada a dois contadores. Isto possui o mesmo poder computacional de uma máquina de Turing universal (veja contador para a prova), Jogo da Vida é tão poderoso quanto qualquer computador com memória ilimitada: é o Turing completo. Além disso, uma imagem pode conter um conjunto de guns que se combina para construir novos objetos, incluindo cópias da imagem original. Um "construtor universal" pode ser construído que contenha um computador Turing completo, e que pode construir uma série de objetos complexos, incluindo mais cópias de si mesma. (Descrições destas construções são dadas em Winning Ways de Conway, Elwyn Berlekamp e Richard Guy.)

Os primeiros resultados no Jogo da Vida foram obtidos sem o uso de computadores. As vidas paradas e os osciladores mais simples foram descobertos enquanto desenvolvendo várias configurações pequenas iniciais usando folhas de gráfico, quadros negros ou tabuleiros e peças. Durante as pesquisas iniciais, Conway descobriu que o R-pentomino não se estabiliza em um número pequeno de gerações.

Estas descobertas inspiraram os programadores de computador do mundo todo a escreverem programas para acompanhar a evolução das imagens de Life. A maioria dos primeiros algoritmos era muito similar. Eles representavam as imagens em grades bidimensionais na memória do computador. Tipicamente duas grades eram usadas, uma para segurar o estado atual, e outra para calcular seu sucessor. Com frequência 0 e 1 representavam células mortas e vivas, respectivamente. Um loop duplo considera cada elemento da grade atual, contando os vizinhos vivos de cada célula para decidir se o elemento da grade seguinte deve ser 0 ou 1. No final deste processo, o conteúdo da grade sucessora é copiado para a grade atual, a grade sucessora é apagada, e a grade atual é mostrada.

Uma variedade de pequenas melhoras para este esquema básico são possíveis, e existem muitas formas de reduzir a computação desnecessária. Uma célula que não se modificou no último passo, e cujos vizinhos não foram modificados, é garantida de que não vai mudar seu estado nesta geração, então um programa que considera isto antes de efetuar seu processamento pode economizar tempo não atualizando tais zonas.

A princípio, o campo de Life é infinito, porém a memória dos computadores é finita, e geralmente o tamanho das grades deve ser declarado antes de ser usado. Isto leva a problemas onde a área ativa se aproxima das bordas da grade. Os programadores têm usado uma série de estratégias diferentes para resolver esses problemas. A estratégia mais simples é considerar que todas as células fora da grade estão mortas. Isto é fácil de programar, mas leva a resultados imprecisos quando a área ativa atravessa este limite.

Uma saída mais sofisticada é considerar os extremos direito e esquerdo do campo como se estivessem juntos, assim como o topo e a parte de baixo. O resultado é que as áreas ativas que se movem através dos limites do campo reaparecem no outro lado. A imprecisão ainda pode aparecer se as imagens ficarem muito grandes, mas ao menos não existem efeitos patológicos nos limites da grade. Técnicas de armazenamento dinâmico também podem ser usadas, criando grades cada vez maiores para poderem sustentar o crescimento das imagens.

Alternativamente, o programador pode abandonar a noção de representar o campo do Jogo da Vida com um grade bidimensional, e usar estruturas para a informação diferentes, como um vetor de pares coordenados representando células vivas. Esta aproximação permite que a imagem se mova pelo campo indefinidamente, desde que a população não exceda o tamanho da grade de coordenadas. Podem-se contar os vizinhos vivos através do método de busca, reduzindo a velocidade de simulação. Com estruturas de armazenamento mais sofisticadas, este problemas pode ser largamente resolvido.

Para explorar imagens muito grandes a grandes profundidades de tempo, algoritmos sofisticados como o Hashlife podem ser úteis.

Em 18 de maio de 2010, Andrew J. Wade anunciou um padrão de auto-construção apelidado Gêmeos que cria uma cópia de si mesmo, enquanto vai destruindo seu pai.^[9][10] Este padrão se replica em 34 milhões de gerações, e usa uma fita de instrução feita de gliders que oscilam entre duas configurações estáveis ​​feitos de armas de construção Chapman-Greene. Estes, por sua vez, criam novas cópias do padrão, e destroem a cópia anterior. Gêmeos é uma nave espacial. ^[11]

A partir de um padrão inicial aleatório de células vivas no grid, os observadores vão encontrar a população em constante mutação à medida que as gerações vão passando. Os padrões que emergem das regras simples pode ser considerado uma forma de beleza. Pequenos subpadrões isoladas sem simetria inicial tendem a se tornar simétricos. Uma vez que isto acontece, a simetria pode aumentar em riqueza, mas não pode ser perdida, a menos que um sub-padrão disponível venha perto o suficiente para perturbá-lo. Em alguns poucos casos, a sociedade eventualmente morre, com todas as células vivas desaparecendo, embora isso não pode acontecer para um grande número de gerações. Padrões mais iniciais, eventualmente, "viram cinzas", produzindo ou figuras estáveis ​​ou padrões que oscilam sempre entre dois ou mais estados; ^[12][13] muitos também produzem um ou mais gliders ou naves espaciais que viajam por tempo indeterminado para longe do local inicial. Naves espaciais podem viajar no máximo um celular por unidade de tempo: assim esta velocidade é definida para ser a velocidade da luz da celular do autômato denominada ${\displaystyle c}$.

Desde a criação do Jogo da Vida original, novas regras têm sido desenvolvidas. O jogo padrão, em que uma célula "nasce" se tem exatamente 3 vizinhos, e permanece viva se tem apenas 2 ou 3 vizinhos vivos, e morre em qualquer outro caso, é simbolizado como "23/3". O primeiro número, ou lista de números, é o necessário para uma célula se manter viva. O segundo conjunto é o necessário para um nascimento. Portanto "16/6" significa "uma célula nasce se tiver 6 vizinhos, e se mantém viva se tiver 1 ou 6 vizinhos". HighLife tem regras 23/36, porque tendo 6 vizinhos, em adição à regra original 23/3 do jogo, causa um nascimento. HighLife e muito conhecido por causa de seus replicators. Variações adicionais do Jogo da vida existem, apesar da grande maioria ser muito caótica ou muito solitária.

• /3 (estável) quase tudo é uma faísca
• 5678/35678 (caótica) diamantes, catástrofes
• /2 (explosiva) "Sementes" phoenix, mínima
• /234 (explosiva) phoenix, imagens lacey
• 12345/3 (explosiva) imagens semelhantes a labirintos
• 125/36 (caótica) Regra de blocos 2x2 semelhante ao Jogo da Vida
• 1357/1357 (explosiva) tudo é um replicador
• 1358/357 (caótica) regra balanceada da améba
• 23/3 (caótica) "Jogo da Vida de Conway"
• 23/36 (caótica) "HighLife" (com replicador)
• 235678/3678 (estável) mancha de tinta, estabiliza rapidamente
• 235678/378 (explosiva) coagulações no caos
• 238/357 (caótica) life quebrado
• 245/3 (caótica) imagens diferente para o Jogo da Vida
• 245/368 (estável) morta mais puffers e naves
• 34/34 (explosiva) "34 Life" inicialmente se pensava ser estável, mas algumas imagens simples não têm fim. Posteriormente, com computadores modernos, isto provou-se regra mas não exceção.
• 34678/3678 (explosiva) "Dia & Noite"
• 4567/35678 (explosiva) crescimento rápido - resultados interessantes quando as regras são mudadas para 456/35678
• 456/35678 (estável) decaimento surpreendentemente lento quando 4567/35678
• 45678/3 (explosivo) crescimento lento em coral
• 5/346 (estável) "Vida Longa"

Fonte destas regras: Life32

Perceba que nenhum dos autômatos acima contém o elemento /1 (como 78/17 ou 34/145) que seria sempre explosivo para qualquer imagem finita - considerando ao menos uma única célula viva e seus oito vizinhos (também conhecidos como a vizinhança de Moore) irão entrar no estado vivo na próxima geração, pois estão adjacentes a uma única célula. Não é possível construir uma imagem finita de modo que todas as células mortas tenham zero (exceto a imagem em que todas as células estão mortas), ou mais de dois vizinhos vivos.

Variações adicionais foram desenvolvidas modificando-se outros elementos do universo. As variações acima podem ser pensadas em um quadrado 2D, porque o mundo é bidimensional e se passa em um espaco quadrado. Variações com quadrados 3D e 1D tem sido desenvolvidas, assim como variações 2D hexagonais onde o campo é hexagonal ou triangular ao invés de quadrado.

O Jogo da Vida de Conway cria um universo complicado a partir de poucas regras. É imaginável que todo o universo real seja um jogo similar, jogado em alguma dimensão mais alta. Esta possibilidade pode influenciar o debate de vivermos em um universo perfeitamente ajustado que requer um projeto inteligente..

Alguns jogos com fins de entretenimento foram desenvolvidos a partir do jogo da vida. Um desses jogos é para dois jogadores, onde cada interação acontece uma vez por tick, baseia-se diretamente no Jogo da Vida de Conway. Células vivas têm uma das duas cores, e um jogador ganha quando todas as células da cor do adversário são eliminadas. Quando uma célula morta tem três vizinhos vivos, ela torna-se viva na mesma cor que a maioria dos seus vizinhos. O jogo começa com um padrão aleatório de ou pré-escolhido com metade das células vivas de cada cor. Depois de uma iteração, o primeiro jogador pode adicionar uma célula de sua própria cor e retirar uma célula sua ou do seu oponente. Após a próxima iteração, o outro jogador pode fazer o mesmo, e assim por diante. ^{[carece de fontes?]} Outras variantes de dois jogadores do Jogo da Vida também foram desenvolvidos.^[14]

Em Populous II, um dos efeitos da "intervenção divina" é um fungo que cresce de acordo com as regras do jogo da vida. O aclamado desenvolvedor de jogos Jonathan Blow cita o jogo da vida como uma grande influência em sua filosofia de design.^[15]

Várias técnicas de composição musical usam o Jogo da Vida de Conway, especialmente no seqüenciamento MIDI. ^[16] Existe uma variedade de programas para a criação de sons a partir de padrões gerados pelo Jogo da Vida. (ver referências para exemplos).^[17][18][19] O pacote de software modulador de som da Native Instruments para geração e processamento chamado Reaktor possui uma bateria eletrônica com um sequenciador integrado que implementa o Jogo da Vida.

Os computadores foram usados ​​para seguir as configurações do Jogo da Vida desde o surgimento do jogo. Quando John Conway estava começando a investigar como diferentes configurações se desenvolviam, ele as rastreou à mão usando um tabuleiro de Go e suas pedras pretas e brancas. Essa simulação era tediosa e propensa a erros. O primeiro programa do Jogo da Vida da história foi escrito por John Francis (um estudante de graduação na Universidade de Cambridge) em um IBM 360, e foi usado para automatizar esse processo e acompanhar o destino do R-pentomino para 1000 gerações.^{[carece de fontes?]} [Carece de fontes ] O primeiro programa do Jogo da Vida interativo foi escrito em ALGOL 68 para o PDP-7 por MJT Guy e SR Bourne. Os resultados foram publicados na edição de outubro de 1970 da Scientific American ^[20] e - com relação ao uso do programa - Relata que "Sem a sua ajuda,algumas descobertas sobre o jogo teriam sido difícil de serem feitas." Existem hoje milhares de programas do Jogo da Vida online, e por isso uma lista completa não pode ser fornecida aqui. A seguir temos uma pequena seleção de programas com ênfase para os mais notáveis, tais como de popularidade ou características incomuns. A maioria destes programas incorporam uma interface gráfica para a edição do padrão de simulação, a capacidade de simular várias regras do jogo, e uma grande biblioteca de padrões interessantes no jogo outras regras.

• Jogo da Vida de Conway, por Alan Hensel . Um applet pop-up em Java web com algoritmos de simulação rápida e uma grande biblioteca de padrões interessantes.
• Golly. Um sistema multi-plataforma (Windows , Macintosh e Linux) open-source de simulação do jogo e outros autômatos celulares, por Andrew Trevorrow e Tomas Rokicki. Ele inclui o algoritmo hashlife para geração extremamente rápida, e scrips em Perl ou Python para edição e simulação.
• Mirek's Cellebration. Grátis 1-D e 2-D para visualização dos autômatos celulares, exploração e edição para Windows. Inclui ferramentas poderosas para simulação e visualização de uma grande variedade de regras, incluindo a do Jogo da Vida, e um editor de scripts.
• Xlife. Um laboratório de autômatos celulares por Jon Bennett. Vem sendo o aplicativo de simulação padrão UNIX X11 Jogo da Vida por um longo tempo, e também foi portado para o Windows. Pode lidar com regras de autômatos celular com a mesma sociedade do Jogo da Vida, e até oito estados possíveis por célula.

• Vida artificial
• Formiga de Langton
• Autômato celular de von Neumann
• Auto-organização

Referências

• Adamatzky, A., ed. (2010). Game of Life Cellular Automata (em inglês) 1 ed. [S.l.]: Springer-Verlag London. 579 páginas. ISBN 9781849962179. doi:10.1007/978-1-84996-217-9 

• O Jogo da Vidae outros autómatos celulares bidimensionais (Ou Exclusivo, Gerador de padrões) - aplicação JAVA.
• Dicionário do Jogo da Vida
• Jogo LazBactérias - criado no Lazarus/FPC