O Jogo da Vida

Conversa típica com um amiguinho computeiro:

“Você conhece o jogo da vida?”

“Ahn? Acho que sim.”

“Tem certeza?”

“Como assim?”

“Ah, quero dizer, aquele autômato celular turing-completo em um tabuleiro infinito, que tem células com dois estados, e regras locais super simples.. conhece?”

“….”

O Jogo da Vida é um autômato celular bidimensional criado pelo matemático John Conway. Ao contrário do jogo homônimo da Hasbro publicado aqui no Brasil pela Estrela, ele é jogado em um tabuleiro quadrado infinito. Cada casa do tabuleiro é chamada de célula, e pode estar em dois estados: viva ou morta. Normalmente se representa uma célula morta por um quadradinho branco (com ou sem borda), e uma célula viva por um quadradinho preto.

O termo “jogo” talvez cause certa confusão, já que este é um jogo de zero jogadores. Como muitos outros jogos matemáticos, depois de certo estado inicial, ele evolui sozinho. Uma configuração de células em determinado momento é chamada de geração. Cada jogo possui uma geração inicial, e evolui ao longo do tempo de forma determinística: cada geração depois da primeira é completamente determinada pela geração anterior. Portanto, em última análise, a geração inicial determina o comportamento de todo o jogo.

gospers_glider_gun.gif

A figura ao lado demonstra a evolução de um padrão conhecido do jogo da vida, o Glider Gun (Ou Atirador de Gliders) de Gosper. Ele é chamado assim porque atira em uma direção um fluxo contínuo de gliders, que são esses bichinhos andam na diagonal, sempre cabem em um quadrado 3×3 e sempre possuem 5 células vivas. Para entender como ele se move, note que a cada 4 gerações ele faz uma cópia de si mesmo idêntica à original, mas deslocado uma casa na diagonal. Em mais quatro gerações, ele vai estar idêntico mas deslocado na mesma direção denovo, etc.

Quem observa o jogo dessa forma, não imagina o quanto ele é simples. O novo estado de cada célula depende somente de seu estado anterior e o estado anterior de seus 8 vizinhos. As regras podem ser resumidas por essa lista:

  • Se uma célula possuir 3 vizinhos vivos, ela vive na próxima geração (Se estiver viva, continua viva. Se estiver morta, volta a vida).
  • Se uma célula possuir 2 vizinhos vivos, ela não muda de estado.
  • Se uma célula possuir menos de 2 ou mais de 3 vizinhos vivos, ela morre na próxima geração (Se estiver viva, morre. Se estiver morta, continua morta).

Se pode abreviar as regras do jogo da vida como 23/3, isto é, uma célula viva continua viva com 2 ou 3 vizinhos, e uma célula morta volta a vida com 3 vizinhos, e em qualquer outra situação a célula morre. É possível construir jogos semelhantes ao jogo da vida mudando as regras de evolução.

O jogo da vida possui várias características interessantes. Um “bloco de tetris” 2×2, se isolado, irá permanecer parado, já que cada célula viva dele tem 3 vizinhos vivos (e por isso continua viva) e cada célula morta nos arredores tem 1 ou 2 vizinhos, e por isso continuam mortas. Isso é chamado de vida parada no jogo da vida. Um bloco 1×3, chamado blinker, vai ficar oscilando entre um bloco 1×3 e 3×1, e por isso é chamado de oscilador. O glider, como se movimenta no tabuleiro, é chamado de nave espacial. Existem muitos outros exemplos de vida parada, osciladores e naves espaciais no jogo da vida.

De fato, como um glider gun emite um fluxo de gliders, se tratarmos o glider como uma unidade de informação, um glider gun emite um fluxo de informação constante – um clock. Se um glider colidir com um bloco 2×2, eles irão se aniquilar; mas se dois deles passarem próximos a um bloco, ele irá se aproximar da fonte dos gliders. Se, ao invés de dois, três passarem, ele irá se afastar da fonte dos gliders. Com isso, é possível escrever um contador unário. A interação entre gliders e certos padrões, pode implementar portas lógicas, e com isso simular uma máquina de estados. Isso é poder computacional suficiente pra simular qualquer computador, por isso ele é dito turing completo.

Isso entra na parte realmente interessante do jogo da vida: Simulações! O meu pobre simulador ainda não consegue simular padrões que façam algo de útil: este é o meu projeto para esse semestre. Quer dizer, assim que eu aprender a simular portas lógicas 🙂

Alguns links legais: Wikipédia PT, Wikipédia EN, Commons, Enciclopédia do Jogo da Vida.

Anúncios

5 Responses to O Jogo da Vida

  1. Daniel Hortiz disse:

    ELIIIIIIIIIIIAS hehehe massa esse jogo da vida, mostra como a evolução não precisa de regras complexas. (obs: eu me “vi” naquele diálogo inicial) kkkkkkkkk vlw

  2. Elias disse:

    Com a diferença que vc faz medicina e portanto teoricamente imagina-se que, na teoria, não é computeiro =D (se bem que vc é meio geek..)

  3. rafaela disse:

    Nem queriaa sbaer disso nao
    e o jogo
    da vida e nao
    esse doido

  4. Casper disse:

    Estou em meio a um trabalho de faculdade para implementar portas lógicas no jogo da vida (simular)

    Tem algum matéria para indicar?
    Grato

  5. Elias disse:

    Oi

    Heh, o post deu a entender que eu eventualmente iria aprender isso, mas eu acabei abandonando.

    E bom, detalhes assim parecem meio escondidos em algum paper 😦

    Tem um simulador chamado golly, http://golly.sourceforge.net/

    Ele tem uma maquina de turing, e pode ser util pra testar algo que você tenha feito

    http://www.radicaleye.com/lifepage/patterns/sbm/sbm.html tem um pouco sobre como funcionam memorias

    e esse livro tem uma seção onde descreve como construir portas logicas no jogo da vida (E muitas outras coisas!)

    http://www.ilachinski.com/ca_book.htm
    http://www.google.com.br/search?q=CELLULAR+AUTOMATA+A+Discrete+Universe+pdf

    ps: seu email de contato é inválido

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: