O Jogo da Vida

O matemático John Conway faleceu na semana passada, vítima do Coronavírus.

Ele foi o criador do “Jogo da Vida”, o primeiro exemplo de autômato celular. É bastante interessante e lúdico.

O jogo faz a seguinte análise:

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

Um pouco da história

O conceito de autômato celular foi criado pela genial dupla John Von Neumann e Stanislaw Ulam, durante o Projeto Manhattan, que criou a primeira bomba atômica. Von Neumann tinha interesse em entender organismos autorreplicáveis.

John Conway inventou o Jogo da Vida enquanto um estudante de graduação. Ele gostava de jogos, e já tinha dominado vários quando quis criar um novo. Ele se inspirou nos trabalhos de Neumann e Ulam.

Ele fazia simulações num tabuleiro de Go, aquele jogo oriental que tem um tabuleiro de 19 x 19 quadrados e peças pretas e brancas, numa época que não tinha computador.

Dependendo das regras, a população pode explodir para a superpopulação, ou para a extinção total.

As regras do jogo acima foram cuidadosamente escolhidas, para entrar em equilíbrio. Rodando várias iterações, começam a surgir alguns padrões.

O Jogo da Vida ficou famoso em 1970, após artigo de Martin Gardner na Scientific American. Gardner é um dos maiores divulgadores de puzzles de todos os tempos (tenho uns 5 livros dele), e Conway enviava cartas frequentemente para contribuir.

Anos depois, em 2002, o matemático Stephen Wolfram (do Wolfram Alpha) publicou um estudo detalhado de autômatos celulares em geral, com classificação de tipos, regras, etc.

Esta técnica pode ter utilidade em diversas áreas do conhecimento: modelos biológicos, economia, etc. Inclusive, há alguns modelos de transmissão de Coronavírus baseados em autômato celular.

Em homenagem a Conway, fiz duas implementações do Jogo da Vida. Uma em Python e outra em Excel. É um bom exercício, para um nível intermediário de programação. Seguem alguns estudos.

Vide links a seguir.

https://github.com/asgunzi/JogodaVidaExcel

https://github.com/asgunzi/JogoVidaPython

https://mathworld.wolfram.com/CellularAutomaton.html

https://guiadoestudante.abril.com.br/estudo/conheca-john-conway-o-matematico-que-criou-o-jogo-da-vida

https://en.wikipedia.org/wiki/Cellular_automaton

https://mathworld.wolfram.com/ElementaryCellularAutomaton.html

Análise de Monte Carlo e Simulação

O método de Monte Carlo é um método simples de resolver problemas probabilísticos difíceis. Este tutorial é uma introdução bastante simples, didática, deste assunto, uma mistura de história, matemática e mitologia.
A origem do método foi na Segunda Guerra Mundial, proposta pelo matemático americano-polonês Stanislaw Ulam e o matemático americano-húngaro John Von Neumann.

Ulam.JPG
Não é uma coincidência que estes cientistas eram europeus que foram para os Estados Unidos. Vários cientistas de nível mundial fizeram o mesmo, fugindo da dominação europeia dos nazistas.

VonNeumann.JPG
Estes e outros cientistas brilhantes estiveram envolvidos no projeto secreto da Bomba Atômica. Este projeto secreto foi o Projeto Manhattan.


O que a bomba atômica tem haver com simulação?

Esta é uma introdução bem fácil, simplificada, para dar uma ideia do método de Monte Carlo no Projeto Manhattan.

Imagine um átomo de Plutônio.

Um “Átomo” é uma palavra grega para “indivisível”. “A” = não, “tomo” = tomos, divisões. Cientistas acreditavam que estes elementos únicos da natureza eram os blocos de construção de tudo no universo, uma espécie de lego.

Os cientistas da época estavam estudando a recém descoberta fissão nuclear, em que um átomo é quebrado, dividido. O átomo é quebrado em outros elementos e libera uma quantidade espantosa de energia.

Fission1.JPG

O Plutônio enriquecido era um átomo excelente para isto, porque era altamente instável. E o Urânio também, mas fixaremos no Plutônio aqui.

Imagine uma bola no alto de uma montanha. Qualquer empurrãozinho moverá a bola e liberará a energia potencial em energia cinética. Com o Plutônio enriquecido, é o mesmo. Então, o Plutônio era um bom átomo para criar a bomba.

Mas havia uma série de problemas. Processar o mineral natural e enriquecer o Plutônio era um processo bastante doloroso. É como derrubar uma montanha inteira de material, gastando uma quantidade enorme de energia, apenas para obter um miligrama de Plutônio enriquecido. Quanto Plutônio é suficiente? Como poderiam usar isto?


Efeito Dominó

É inofensivo liberar o poder de apenas um átomo. Para criar a bomba, há a necessidade de criar uma reação em cadeia: um átomo libera a energia, e quebra mais um átomo, e mais um: um efeito dominó.

fission2.JPG
A reação subcrítica é quando a bomba não explode: a reação em cadeia não acontece. É como uma cadeia de dominós que é interrompida no caminho.

A reação supercrítica é quando a bomba explode: há uma quantidade exponencial de energia sendo liberada.

Fission3.JPG
A missão dos cientistas era a de encontrar as condições para a reação crítica, que é a divisão entre a bomba explodir ou não.


Não exploda em minhas mãos

O conhecimento da condição crítica tinha dois objetivos principais: eles tinham que assegurar que a bomba explodiria, mas também precisavam ter certeza que isto não explodiria nas mãos deles.

Eles tinham que dividir a quantidade de Plutônio em pequenos pedaços, pequenos o suficiente para não explodir quando eles não quisessem, mesmo se um acidente ocorresse.
E eles tinham que juntar os pedacinhos em uma única peça grande, com material suficiente para causar uma reação em cadeia quando eles quisessem que isto ocorresse (no momento da explosão).

 


Como calcular?

Como calcular se a bomba explodiria ou não?

De forma simplificada, há um modelo para calcular o comportamento de um único átomo: probabilidade de explosão, quantidade de energia liberada para cada átomo fissionado, etc.

Se há um modelo para um único átomo, eles precisavam calcular o comportamento de um grupo de átomos, dado que eles estão a uma certa distância e numa certa densidade. Se há a primeira fissão, o segundo átomo fará o mesmo? E o terceiro?

Em outras palavras, cada átomo é uma variável aleatória. O efeito composto em dois átomos é a soma das duas variáveis aleatórias.

RandomVariables2.JPG
Somar variáveis aleatórias não é uma tarefa fácil. Isto significa resolver uma equação integral (não é fácil nem para gênios como Von Neumann).

Ulam e Von Neumann propuseram duas soluções:

O método de Monte Carlo, com calculadoras humanas. Imagine um modo de dividir os cenários em vários casos pequenos, determinísticos. Cada caso é calculado por uma mulher (homens não são bom na tarefa, porque cometem um monte de erros), usando lápis e papel (consegue imaginar isto?)… e então um matemático agrupava os vários resultados. Isto foi batizado “Monte Carlo” após o nome de um cassino, porque lembra o lançar de dados. Havia uma sala, cheia de mulheres fazendo cálculos. Elas nem sabiam o que estavam calculando, uma vez que o projeto era secreto.

humancomputers.jpg
A segunda solução era usar computadores eletrônicos. O único problema: computadores eletrônicos não existiam. A solução de Von Neumann foi inventar o computador eletrônico! Von Neumann criou a arquitetura conceitual do computador eletrônico (CPU, memória, entradas, saídas, etc), e o computador que usamos hoje ainda usa a arquitetura de Von Neumann.

VonNeumannComputer.jpg

O único problema: não foi completado antes do final da guerra. Portanto, a bomba atômica deveu-se inteiramente aos esforços das calculadoras humanas.

Num mundo probabilístico, usamos variáveis para representar fenômenos estocásticos. Nós escolhemos a variável aleatória certa para representar o que queremos. Se é um evento como a altura de um grupo de pessoas, usamos uma variável aleatória normal. Se é a taxa de chegada de clientes numa fila, normalmente modelamos como uma variável exponencial. Se não temos ideia, mas de alguma forma sabemos o mínimo e o máximo, a distribuição uniforme é uma boa escolha.

RandomVariables.JPG

Um erro muito comum é usar uma função complicada desnecessariamente. Digamos, o analista tem um ano de medições, e ele aprendeu na faculdade que existe uma variável chamada weibull, que fita bem os dados. É uma boa escolha? Não, não é, a menos que ele saiba exatamente o que está fazendo. Isto porque não queremos modelar o passado. Queremos modelar o futuro. E o futuro não necessariamente vai seguir uma weibull complicada. Eu prefiro ser humilde, dizer “Eu não sei exatamente”. O modo que dizemos “Eu não sei”, é usar uma variável aleatória simples, como uma normal, uma uniforme.

Uma vez que sabemos a variável aleatória, podemos usar o método de Monte Carlo. Consiste em jogar um dado. Dependendo do valor que obtemos do dado, obtemos o valor da variável aleatória.

 

Cdfs.JPG

No primeiro exemplo, obtemos 4 do primeiro lançamento, e 0,2do segundo lançamento, resultando em 4,2.

No segundo exemplo, obtemos 6,1 do primeiro lançamento, e 0,7 do segundo lançamento, resultando em 6,7.

Se fizermos isto um milhão de vezes, podemos estimar a distribuição de probabilidades da variável aleatória final. Cada passo é muito muito fácil, determinístico, fácil o suficiente para ser feito por uma calculadora humana, ou um computador eletrônico. Deste modo, podemos modelar um modelo muito complicado de uma forma simples.

RandomVariables4.JPG

Hoje, num simples laptop, temos poder de processamento equivalente a milhões de humanos calculando no braço. E, numa simples planilha do Excel, podemos usar modelos muito, muito complicados, com a ajuda de alguns pacotes computacionais.

Em algum post futuro, mostrarei alguns exemplos.

 



Epílogo.

Plutônio e Urânio

Os cientistas do Projeto Manhattam estavam pesquisando dois átomos: Urânio e Plutônio. No final, eles fizeram duas bombas.

A de Hiroshima era o “Little boy”, “garotinho”, uma bomba de urânio.

A de Nagasaki era o “Fat Man”, “homem gordo”, uma bomba de plutônio.

Urano é o deus do céu, na mitologia grega. Plutão é o deus do inferno. Duas bombas. Céu e Inferno.