Re: O Jogo "Vida"

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Wed, 30 May 2001, Paulo Santa Rita wrote:

> Ola Pessoal,
> 
> O Jogo "Vida" e tambem conhecido por "Jogo de Conway", pois foi este 
> Matematico que divulgou o jogo, descoberto originalmente por Stanislaw Ulam 
> e John Von Newman, em Los Alamos.

Acho que deve haver algum mal entendido aqui.
Pelo que eu sei o jogo "vida" ("life") foi inventado
(criado, descoberto) por Conway. Estou verificando o capítulo
sobre "life" em "Winning Ways" de Berlekamp, Conway e Guy
e não encontrei nenhuma menção de Ulam ou Von Neuman.
 
...

> O jogo e assim :
> 
> 1) Voce coloca num tabuleiro de xadrex quantas pedras quiser nas posicoes 
> que quiser.
> 2) Estabelece um conjunto de "regras de iteracoes"
> 3) Repete indefinidamente as regras e verifica o que acontece.
> 
> Conway estabeleceu inicialmente as seguintes regras :
> 
> 1) Se das casas vizinhas de uma casa exatamente 3 estiverem ocupadas por 
> pedras, a casa deve ser ocupada, isto e : se ele estiver desocupada, deve 
> ser ocupada por uma pedra; se estiver ocupada, deixa-se ela como esta.
> 
> 2) Se das casas vizinhas de uma casa exatamente 2 estiverem ocupadas por 
> pedras, deixa-se a casa como esta, isto e: se ela estiver desocupada, fica 
> desocupada; se estiver ocupada, fica ocupada.
> 
> 3) Em qualquer outro caso, a casa deve ser desocupada.
> 
> Apos escolhermos a configuracao inicial que desejarmos, isto e, apos 
> colocarmos quantas pedras quisermos nas posicoes que quisermos, aplicamos as 
> regras : surgira dai uma nova configuracao. Aplicamos as regras pela segunda 
> vez : surgira uma nova configuracao. E assim sucessivamente.

Está tudo certo, exceto que o jogo é normalmente jogado
em um plano quadriculado infinito.
 
> O interessante do jogo e que nao obstante a rigidez e simplicidade das 
> regras, as figuras que surgem surpreendentes ... Existe uma estrutura ( 
> disposicao de pedras no tabuleiro ) que permanece invariante em sua forma, 
> independente de quantas iteracoes efetuarmos. Esta estrutura e chamada "Asa 
> delta". Existem os "Construtores", em cujas colisoes sao geradas asas deltas 
> invariantes etc, etc

No capítulo de que falava de "Winning ways" demonstra-se que este jogo
é 'universal', i.e., as regras permitem a construção de uma espécie de
'computador'. É portanto um problema indecidível, dada uma configuração
inicial, dizer se ela vai viver para sempre ou não.

Vale a pena dar uma olhada neste capítulo, aliás no livro todo.

...

> Eu faco uma proposta. Considerando que :
> 
> 1) Muitas pessoas aqui sabem programar computadores.
> 2) Fazer um programa do jogo vida, na forma simples e original como Conway o 
> abordou, e facil.
> 3) Podemos imaginar o tabuleiro de xadrex como uma matriz 8 por 8
> 4) Uma casa desocupada pode ser representada por zero. A ocupada, por um.
> 5) numeramos as linhas de cima para baixo, de zero ate sete. As colunas, da 
> esquerda para a direita, tambem de zero ate sete.
> 6) Pascal todo mundo sabe, pois estuda-se em todas faculdades. A linguagem C 
> e um Pascal melhorado.
> 
> Vamos fazer em C o jogo vida ?

Pode ser um projeto interessante escrever um tal programa do zero,
mas eu faço notar que já existem vários programas assim.
Um deles eu acabei de baixar da rede, ou mais explicitamente, de
http://packages.debian.org/testing/games/xlife.html
Compilei, rodei e testei brevemente. O nome dele é xlife e as fontes
e minha compilação do programa estão em
http://www.mat.puc-rio.br/~nicolau/bobo/xlife-5.0.tar.gz

O programa é escrito em C e parece ser feito para Linux
(pelo menos eu compilei em um Linux-Intel). Funciona.

Aliás, a título de curiosidade: não me parece que Pascal
seja obrigatoriamente estudado aqui na PUC.
No primeiro curso de ICC os alunos estudam Scheme (um tipo de Lisp).
Depois disso varia muito, mas acho que C é mais popular do que Pascal.

[]s, N.