Jogo da vida

Origem: Wikipédia, a enciclopédia livre.

Nota: Para outros significados de Jogo da vida, ver Jogo da vida (desambiguação).

Glider Gun de Gosper criando "gliders".

O Jogo da vida é um autômato celular desenvolvido pelo matemático britânico John Horton Conway em 1970. É 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.

Índice

1 Origem
2 Regras do Jogo da Vida
3 Descrição
4 O Jogo
- 4.1 A vida sempre segue
5 Exemplos de imagens
6 Algoritmos
7 Variações do Jogo da Vida
8 Filosofia
9 Imagens
- 9.1 125/36
- 9.2 245/3 (245/36)
10 Ver também

[editar] Origem

Um dos problemas matemáticos mais famosos dos anos 40 era o de achar uma máquina que fosse 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. 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, ao campo dos autômatos celulares... Por causa das analogias de Life com a 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, economistas, filósofos e outros a observar o 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 dos anos 70 e no meio dos 80; 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.

[editar] Regras do Jogo da Vida

Conway escolheu suas regras cuidadosamente, após um longo período de experimentos, para satisfazer três critérios:

Não deve haver nenhuma imagem inicial para a qual haja uma prova imediata ou trivial de que a população pode crescer sem limite.
Deve haver imagens iniciais que aparentemente cresçam sem limite.
Deve haver imagens iniciais simples que cresçam e mudem por um período de tempo considerável antes de chegar a um fim das possíveis formas:
1. Sumindo completamente (por superpopulação ou por ficarem muito distantes)
2. Estacionando em uma configuração estável que se mantem imutável para sempre, ou entrando em uma fase de oscilação na qual são repetidos ciclos infinitos de dois ou mais períodos.

Em outras palavras, as regras deviam tornar o comportamento das populações ao mesmo tempo interessante e imprevisível.

As regras são simples e elegantes:

Qualquer célula viva com menos de dois vizinhos vivos morre de solidão.
Qualquer célula viva com mais de três vizinhos vivos morre de superpopulação.
Qualquer célula com exatamente três vizinhos vivos se torna uma célula viva.
Qualquer célula com dois vizinhos vivos continua no mesmo estado para a próxima geração.

É importante entender que todos os nascimentos e mortes ocorrem simultaneamente. Juntos eles constituem uma geração ou, como podemos chamá-los, um "instante" na história da vida completa da configuração inicial.

[editar] Descrição

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 estado 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).

[editar] O Jogo

A idéia 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.

[editar] A vida sempre segue

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 muitos 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 da 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 da $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.

[editar] Exemplos de imagens

A evolução e o movimento de um "glider".

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	Bote	Blinker	Sapo	Glider	LWSS

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:

Glider Gun de Gosper

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 contruções são dadas em Winning Ways de Conway, Elwyn Berlekamp e Richard Guy.)

[editar] Algoritmos

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 freqüê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 computarodes é 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.

[editar] Variações do Jogo da Vida

5678/35678 diamantes (caótico), catástrofes

/2 (explosivo) "Sementes" phoenix, mínima

23/3 (caótico) "Jogo da Vida de Conway"

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 rápidamente
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 se 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 à 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.

[editar] Filosofia

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.