Objetivosprofessor.ufabc.edu.br/~graca.marietto/HomePage/... · 2020. 6. 6. · É governado por regras simples que definem nascimentos, mortes e sobrevivências de células. 9 Cada

Jogo da Vida

Profa. Maria das Graças Bruno Marietto

Centro de Matemática, Computação e Cognição (CMCC)

[email protected]

Vida Artificial na Computação


Objetivos

O objetivo desta aula é:

Analisar o Jogo da Vida, como um estudo de caso de simulação de um sistema complexo

2Vida Artificial na Computação

Jogo da Vida


JOGO DA VIDA DEJOHN CONWAY: APRESENTAÇÃO

Jogo da Vida

Em 1968, o matemático John Conway desenvolveu um importante autômato celular chamado Jogo da Vida, tendo como objetivo projetar um conjunto de regras matemáticas simples, capaz de gerar padrões complexos de vida.

Conway mostrou como um conjunto de regras básicas pode orientar um sistema complexo.


Conway explorava a ideia do construtor universal, de forma que uma máquina hipotética pudesse construir cópias de si mesma.

Este assunto foi estudado por John Von Neumann, que criou um modelo matemático baseado em um autômato celular, com as células podendo assumir 29 estados.

John Conway

Jogo da Vida

Conway simplificou o modelo de Von Neumann para apenas dois estados, criando o autômato celular Jogo da Vida.

O Jogo da Vida é um exemplo simples de sistema auto-organizável, recebendo a atenção de cientistas de diversas áreas, em estudos sobre como padrões elaborados e comportamentos podem emergir de regras muito simples.


Por exemplo, o Jogo da Vida ajuda a entender como as pétalas de uma flor, ou as listras de uma zebra, podem aparecer de um tecido de células vivas crescendo juntas.

John Conway

Jogo da Vida

A primeira divulgação do Jogo da Vida de Conway foi na revista Scientific American número 223, de Outubro de 1970, na coluna sobre jogos matemáticos de Martin Gardner (1914-2010).

O Jogo da Vida trataria de apenas um jogo superficial, ou haveria algum real significado por trás de suas regras aparentemente simples?


No próximo slide está colocado o que Gardner escreveu a respeito da simplicidade encontrada na natureza em relação ao jogo, em um de seus artigos para a Scientific American.

Martin Gardner

Jogo da Vida


“Uma questão intimamente relacionada é se as próprias leis naturais são simples ou complexas.A maioria dos biólogos, particularmente os que trabalham com o cérebro e o sistema nervoso, estão impressionados com a complexidade da vida. Por outro lado, embora a teoria quântica

tenha se tornado imensamente mais complicada com a descoberta de novas partículas e suas

estranhas interações, a maioria dos físicos mantêm uma forte fé na simplicidade final das leis básicas. Isso era especialmente verdadeiro para Albert Einsten, que escreveu: ‘Nossa experiência

justifica que acreditemos que a natureza é a realização das mais simples ideias matemáticas

concebíveis’”.

Martin Gardner

Jogo da Vida


O JOGO DA VIDA

Jogo da Vida

O Jogo da Vida é um autômato celular que se desenvolve em um espaço de duas dimensões, dividido em células quadrangulares.

É governado por regras simples que definem nascimentos, mortes e sobrevivências de células.

9

Cada uma das células do universo bidimensional pode estar em dois estados possíveis: viva ou morta.

No Jogo da Vida da figura acima, a cor preta indica que a célula está morta, e a cor verde/branca indica que a célula está viva.

Se uma célula sobrevive, morre ou nasce será determinado pelo número de vizinhos vivos ao redor de uma célula.


Jogo da Vida


Na dinâmica do jogo, coloca-se um ou mais organismos, sempre um em cada célula, e a cada instante do tempo/período/geração, aplicam-se as leis gerais para cada célula do quadriculado.

Um organismo em uma célula pode sobreviver ou morrer, e uma célula vazia pode receber um organismo no próximo instante. E assim sucessivamente, a cada geração.

t=0

t=0

t=1

t=1

t=2

t=2

t=3

t=3

t=4

t=4


Jogo da Vida


JOGO DA VIDA:COMPORTAMENTOS

DESEJADOS

Jogo da Vida

12

Comportamentos Desejados no Jogo da Vida


Conway chegou às regras do Jogo da Vida por meio do estudo empírico das mesmas, após ter tentado inúmeras possibilidades, até que se chegasse a um universo onde os autômatos celulares alcançassem um determinado equilíbrio entre nascimento e morte de células.

Jogo da Vida

13



As regras de Conway foram escolhidas para se adequar a três condições:

Não deverá haver nenhum teste inicial com uma prova simples de que a população possa crescer sem limitesDevem ser aplicados testes padrões iniciais que, aparentemente, façam crescer sem limiteDeve haver configurações iniciais que no decorrer do tempo cheguem a um resultado que pode ser:

Sumir completamente (seguindo as regras do jogo, ou por solidão ou sufocamento);Assumir uma configuração estável, onde se permaneça constante com o passar do tempo;Entrar em ciclo por dois ou mais períodos de tempo.

Jogo da Vida



As regras do Jogo da Vida devem ser de tal modo que faça o comportamento da população

imprevisível.

Jogo da Vida


JOGO DA VIDA:REGRAS

Jogo da Vida

16

Regras


Cada célula pode ter oito células vizinhas, que a circundam. Esta é a vizinhança e Moore.

O limite do autômato celular é periódico.

O estado de uma célula é representado por dois valores binários:

(0) se a célula está morta

(1) se a célula está viva

As regras definidas para o Jogo Vida envolvem três tópicos: sobrevivência, nascimentos e mortes.

Jogo da Vida

17

Regras


Tais regras definem o estado de uma determina célula qualquer na próxima iteração, com base no estado atual das células vizinhas.

As regras do jogo são:

Uma célula viva com 2 ou 3 vizinhos vivos, permanece viva (sobrevivência);

Uma célula viva com apenas 1 ou 0 vizinhos vivos, morre por solidão (morte);

Uma célula viva com 4 ou mais vizinhos, morre sufocada (morte);

Uma célula morta com exatamente 3 vizinhos vivos, nasce/renasce (nascimento).

Jogo da Vida

18

Regras


Ilustrando as regras, a figura abaixo mostra quatro (04) gerações (iterações) ao decorrer do tempo.

Os números na figura não fazem parte do jogo e são apenas para exemplificar qual regra do jogo foi aplicada para que ocorresse tal transição.

t=0

t=0

t=1

t=1

t=2

t=2

t=3

t=3

t=4

t=4

Jogo da Vida

19

Jogo da Vida no Passo N


Jogo da Vida no Passo N+1



Jogo da Vida


JOGO DA VIDA:TEMPO DISCRETO

Jogo da Vida

Tempo Discreto

Um AC em duas dimensões é uma grade retangular dividida em células, seus elementos básicos.

Tais células possuem um conjunto finito de estados predefinidos e um conjunto de regras para a mudança de estados.

Os estados das células são alterados conforme a aplicação das regras de transição. Tais regras de transição são baseadas no estado atual da célula e de suas vizinhas.

21

Jogo da Vida

Tempo Discreto

A atualização dos estados das células da matriz/grade é uma operação que ocorre de forma simultânea, em todas as posições da grade/matriz, levando à substituição desta por uma nova grade, com novos valores.

As regras de transição são aplicadas síncrona e paralelamente a todas as células, em cada passo de tempo. Cada estado novo da matriz gerado pela regra é chamado de geração.

Ou seja, os estados das células da matriz são alterados ao mesmo tempo para todas as células.

22

Jogo da Vida

Abaixo, na figura da esquerda no Passo N, cada célula está no estado morto ou vivo.

Tendo como base esta configuração inicial da matriz, para que haja uma mudança da configuração do passo N para a configuração do passo N+1, duas ações devem ser executadas.

23





Tempo Discreto

Jogo da Vida

Primeira Ação

As regras do Jogo da Vida são aplicadas em cada célula da matriz, na iteração N.

Nesta ação são calculados os novos estados das células da matriz. Mas estes novos estados não são atualizados neste momento.

Os estados das células da matriz só serão atualizados após todas as regras do Jogo da Vida terem sido aplicadas em todas as células, e já se saber o valor de cada novo estado.

24





Tempo Discreto

Jogo da Vida

Segunda Ação

Já sabendo os valores dos novos estados das células do AC, agora é possível atualizar a matriz.

E esta atualização do estado de cada célula é realizado de maneira simultânea, ou seja, de uma única vez é atribuído um novo valor para cada célula da matriz. Assim, todos os nascimentos e mortes ocorrem simultaneamente.

25





Tempo Discreto

Juntos, eles constituem uma única geração (iteração), a partir da configuração inicial (ou anterior). Após esta atualização, o AC agora está no passo N+1.

Jogo da Vida

Segunda Ação

Essa atualização é considerada como um evento em um instante discreto no tempo (do passo N passou para o passo N+1), de forma que o AC é visto como uma entidade que evolui ao longo do tempo, em instantes discretos de tempo.

Por exemplo, da configuração do AC do Passo N, depois de calculado todos os novos estados da matriz, o AC insere os novos valores na matriz (de uma única vez), conforme ilustrado na parte direita na figura abaixo.

26





Tempo Discreto

Jogo da Vida


t=0

t=0

t=1

t=1

t=2

t=2

t=3

t=3

t=4

t=4


Observe que o tempo no Jogo da Vida passa, de unidade em unidade

(discretamente), em forma de iterações (gerações).

Tempo Discreto

Jogo da Vida


No Jogo da Vida, todos os nascimentos, mortes e sobrevivências ocorrem simultaneamente.

Juntos constituem um movimento, na hipótese da vida.

Tempo Discreto


t=0

t=0

t=1

t=1

t=2

t=2

t=3

t=3

t=4

t=4

Jogo da Vida


JOGO DA VIDA:PADRÕES DE

COMPORTAMENTO

Jogo da Vida

30

Padrões de Comportamento


Durante a execução do Jogo da Vida as células organizam-se seguindo alguns padrões, formando objetos visuais.

Padrões no Jogo da Vida são definidos pelo comportamento dos objetos durante sua execução.

Existem vários tipos de padrões detectados, dentre eles:

Padrões que desaparecem

Tipo I: estáveis, vidas paradas, still-alive

Tipo II: oscilatórios, osciladores

Tipo III: estruturas que se movimentam

Jogo da Vida


PADRÕES DE COMPORTAMENTO:

PADRÕES QUE DESAPARECEM

Jogo da Vida

32

Padrões de Comportamento: Padrões que Desaparecem


Há estruturas de células que desaparecem em poucas interações.

Ou seja, com o passar do tempo as células vão morrendo.

Por exemplo, a cruz suástica desaparece por completo a partir da sexta geração.

Jogo da Vida



PADRÕES ESTÁVEIS (STILL-LIFE)

Jogo da Vida

Padrões de Comportamento: Padrões Estáveis


Os objetos do padrão Tipo I (estáveis, vidas paradas) são aqueles que não se alteram, que ficam parados, após um determinado número de interações.

Como exemplo tem-se os seguintes objetos: block, beehive, boat, ship, loaf.

Objeto Block

34

Jogo da Vida

35



Objeto Boat

Objeto Ship

Objeto Loaf

Objeto Beehive

Boats

Loafs

Jogo da Vida

36



Objeto Spiral Objeto Hat

Objeto Pond

Jogo da Vida

37



Jogo da Vida



PADRÃO OSCILATÓRIO

Jogo da Vida

39

Padrões de Comportamento: Padrão Oscilatório


Os objetos oscilatórios são definidos de tal maneira que, com o passar do tempo ficam oscilando entre a forma inicial e uma forma final, alternando entre elas.

Objeto Blinker Objeto Toad

Jogo da Vida



ESTRUTURAS QUE SE MOVIMENTAM

Jogo da Vida

41

Padrões de Comportamento: Estruturas que se movimentam


Há padrões que se movimentam, como as naves espaciais (spaceships) e os planadores (gliders).

Spaceships se movimentam para cima, para baixo, para a esquerda ou para a direita, enquanto gliders se movimentam horizontalmente.

Padrões que se repetem depois de uma determinada sequência (depois de uma certa quantidade de gerações):

se transformam no espaço

retornam a seus estado original

a medida que as interações se sucedem, temos a sensação de movimento do objeto, que se desloca através da matriz de células do AC

Jogo da Vida

42



Exemplo de evolução de uma spaceship.

Exemplo de evolução de um glider.

Jogo da Vida

43



É interessante observar que as regras do Jogo da Vida não falam nada sobre objetos que se movem e, apesar disso, padrões de movimentação emergem na execução do Jogo da Vida.

Esse fenômeno de objetos em movimento é uma boa demonstração de como padrões complexos podem surgir a partir de regras simples.

Jogo da Vida


JOGO DA VIDA E MÁQUINA DE TURING

Jogo da Vida


Definição: uma máquina de Turing é um modelo abstrato de um computador

O Jogo da Vida é uma máquina de Turing universal. Basicamente, ela pode calcular qualquer coisa

calculável.

Outra característica fundamental do Jogo da Vida é ser um computador universal. Isto é, ele atende ao Halting Theorem (teorema do travamento), o qual assegura que não existe um algoritmo geral que

possa prever quando um programa de computador irá parar ou continuar a rodar indefinidamente.

Jogo da Vida


JOGO DA VIDA:VARIAÇÕES DO JOGO

Jogo da Vida

47

Variações do Jogo da Vida


Tentativas de mudar as regras estabelecidas inicialmente por Conway foram feitas, objetivando se chegar a algum resultado interessante.

Esses autômatos celulares foram chamados de Life-Like. Alguns possuem resultados semelhantes aos de Life, e outros resultados curiosos, mas nenhum foi estudado tanto como como o Life original.

Golly é um software livre que funciona como uma plataforma de aplicação para explorar o Jogo da Vida de

Conway e outros autômatos celulares. Inicialmente desenvolvida por Andrew Trevorrow e Tom Rokicki,

encontra-se disponível em http://golly.sourceforge.net/

Jogo da Vida

48



Uma forma bastante conhecida para definirmos a regra de um determinado AC é utilizar a notação do software Golly.

Uma regra segue o seguinte padrão:

Bx,y...z/Sx‘y‘...z‘Onde os algarismos imediatamente seguintes à letra B (no caso, representados po x,y,...z) referem-se a quantas células vivas vizinhas são necessárias para que uma célula atualmente morta nasça na geração seguinte.

E os algarismos imediatamente depois da letra S (no caso, x ‘, y’,...,z‘) referem-se a quantas células vivas vizinhas são necessárias para que uma célula viva sobreviva na geração seguinte.

Podemos notar que a letra B refere-se a birth, e S à survival (nascimento e sobrevivência em inglês, respectivamente).

Jogo da Vida


Como exemplo, pensemos no próprio Jogo da Vida de Conway.

Ele segue a regra: B3/S23, pois uma célula precisa ter exatos 3 vizinhos vivos para nascer e possuir 2 ou 3 vizinhos vivos para sobreviver.

Logicamente, são 2 ou 3 vizinhos vivos, e não 23.

Qualquer outra combinação de vizinhos vivos resulta na morte (ou não nascimento) da célula.


Jogo da Vida


VARIAÇÕES DO JOGO DA VIDA:HIGH LIFE

Jogo da Vida


Uma das variantes do jogo de Conway é o chamado HighLife, concebido por Nathan Thompson em 1994. Suas regras podem ser expressas pela notação vista anteriormente, por B36/S23.

Por ter se originado a partir do Jogo da Vida, muitos de seus padrões mais simples são semelhantes como osciladores, beehive, blinkers, gliders.

Contudo, quando os padrões começam a ficar mais complicados já não são encontradas mais semelhanças.

Variações do Jogo da Vida: High Life

Jogo da Vida


Um dos interesses especiais, gerados pelo HighLife, vem do padrão chamado replicador.

Replicator é uma imagem que, após chegar em um estado final bem conhecido, entra em loop adotando comportamento de se autoclonar em determinados períodos de tempo.

Um comportamento como esse não foi encontrado no Jogo da Vida.

O comportamento replicante tem seu início após 12 gerações, então reproduz outras duas cópias após a 24ª geração, seguida por mais quatro clones após a 48ª geração e assim por diante.

Generalizando, temos 2^n cópias do replicador na geração 12(2^n -1).


Jogo da Vida



O mesmo replicante após 3, 12 e 36 gerações, respectivamente.

Jogo da Vida


VARIAÇÕES DO JOGO DA VIDA:SEED

Jogo da Vida


Outro Life-Like é o Seed, que pode ser descrito por B2/S.

Ou seja, segundo suas regras uma célula precisa de duas células vizinhas para nascer, mas nunca permanece viva.

Apesar de parecer inusitada, essa regra é relativamente comum nas variantes do Jogo da Vida. As variantes os Life-Like deste tipo recebem o nome de phoenix ou fênix.

Inicialmente investigado por Brian Silverman e nomeado por Mirek Wójtowicz, ainda que as células vivas morram constantemente, há um “equilíbrio” pois os requisitos para que uma célula nasça são mínimos.

Variações do Jogo da Vida: Seed

Jogo da Vida


Uma configuração com poucas células dá origem a uma espécie de desenho dinâmico, que se assemelha a uma explosão caótica que se projeta de maneira a cobrir todo o grid.

Apesar da aparente desordem são encontrados padrões no Seed, como os gliders.

Variações do Jogo da Vida: Seed

Documents

Objetivosprofessor.ufabc.edu.br/~graca.marietto/HomePage/... · 2020. 6. 6. · É governado por regras simples que definem nascimentos, mortes e sobrevivências de células. 9 Cada