domingo, 13 de janeiro de 2013

O Jogo do Pi

No último post eu falava de variações em jogos, aí lembrei de uma variação divertida em um jogo bem conhecido. Quem assistia Topa Tudo Por Dinheiro certamente deve se lembrar do Jogo do Pim. O objetivo é enumerar os naturais pelo maior tempo possível, trocando os múltiplos de quatro pela palavra "pim":

1,2,3,pim,  5,6,7,pim, 9,10,11,pim...

Parece simples, mas na prática muita gente se confundia e errava antes mesmo de chegar ao quarenta!


Uma variação mais difícil desse jogo foi inventada pelo Juca uns anos atrás: o Jogo do Pi. Dessa vez você ainda precisa enumerar os naturais, mas precisa falar "π" toda vez que passar um múltiplo inteiro de pi. Os primeiros múltiplos inteiros são aproximadamente 3.14, 6.28 e 9.42, então a sequência começa assim:

1,2,3,π,  4,5,6,π, 7,8,9,π...

Parece o mesmo jogo né? Você conta três números, fala π, conta mais três, fala π, e assim por diante. Mas se você seguir essa estratégia, vai perder! Olha o que acontece se você continuar:

..., 16,17,18,π, 19,20,21,π, 22,23,24,25,π,...

A estratégia de contar de três em três falha! Entre 7π e 8π tem quatro naturais ao invés de só três.

Bem, será que não dá pra melhorar a estratégia? Podemos contar quantos números tem entre os múltiplos de pi. Com sorte, o padrão é 33333334 e depois repete. Nesse caso, o padrão do Jogo do Pi é oito vezes maior que o padrão do Jogo do Pim. Infelizmente, se você fizer as contas, esse padrão também é quebrado após 112π.

Será que devemos procurar um padrão de padrões então? Nessa altura não já compensa fazer as contas na mão, melhor deixar o python achar o período pra gente:

Script em python para tentar achar um período

Más notícias: o script acha padrões maiores e maiores, sem parar. Não tem como concluir se existe ou não um padrão só analisando a saída do programinha.

O jeito de resolver essa dúvida, então, é usando matemática! Se você tem medo de teoria dos números, pule o quadro azul:


Antes de mais nada, vamos colocar nosso problema na notação correta. Nós queremos descobrir se a quantidade de números entre múltiplos inteiros consecutivos de pi formam uma sequência periódica. Vamos primeiro escrever a sequência explicitamente:


Isso gera a sequência que queremos. Agora vamos supor que essa sequência tem um período p. Das duas uma: ou a gente acha o valor de p, ou batemos em uma contradição pelo caminho.

Se nós somarmos todos os primeiros n termos dessa sequência, temos uma soma telescópica e um resultado curto:


Isso vale para todo n, inclusive no caso onde n é um múltiplo inteiro do período p:


Mas, nesse caso, podemos fazer a somatória de outro jeito. Ao invés de somar direto de 0 a kp, podemos somar k vezes o período p. Aí, como a sequência é periódica, um dos termos some:


O termo mais interno da somatória não varia mais com i, então essa somatória está somando k vezes a mesma coisa:


A conclusão é que, quando p é o período da sequência, podemos jogar um k inteiro de dentro para fora do piso. Podemos agora abrir a definição de piso para kpπ:



Dividindo todo mundo por kp, temos:



Agora, para todo real ε > 0, podemos escolher um k grande o suficiente tal que ε seja maior que 1/kp. Logo:



Pelo teorema do sanduíche, concluímos que:



Note que o numerador dessa função é um piso, logo é um inteiro. Sabemos também que p é um inteiro, logo a fração é um racional. Mas pi é irracional, portanto chegamos a uma contradição, e a sequência não tem período.

Ou seja, concluímos matematicamente que o Jogo do Pi não tem período. Outra maneira de dizer a mesma coisa é que o período do Jogo do Pi é infinito, e portanto o Jogo do Pi é infinitamente mais díficil que o Jogo do Pim!

Agradecimentos ao povo do Math Stack Exchange pela ajuda na demonstração

domingo, 6 de janeiro de 2013

Estimule sua Criatividade #2

Nesse segundo post sobre criatividade, vou contar outra história do tempo do colégio técnico. As aulas regulares do curso de Eletrônica começavam à tarde, mas duas vezes por semana tinha aula de Educação Física às 7am. Entre essas aulas tinha um intervalo de várias horas, onde muita gente voltava para casa para almoçar.

Eu ficava lá pelo colégio mesmo. Nesses intervalos sem aula eu adquiri vários hábitos, como ler ficção científica da Editora Aleph, gibis do Conan e dos X-Men, Diários de Bordo da Frota Estelar Brasileira, livros-jogos do Steve Jackson, jogar RPG (desde Tagmar até AD&D), ir ao fliperama da esquina jogar Street Fighter 2, enfim, aprendi tudo que não presta.

E quando não tinha mais nada para fazer, eu jogava Jogo da Velha.


O Jogo da Velha


Qualquer um que tenha se dedicado um pouquinho ao Jogo da Velha sabe que é um jogo chato. Se o primeiro jogador começar no centro, ele pode forçar um empate. Mas nós éramos sobreviventes do Atari, então conhecíamos o jogo 3-D Tic-Tac-Toe, criado pela Carol Shaw (a programadora mulher do sexo feminino que também foi responsável pelo clássico River Raid).

3-D Tic-Tac-Toe no Atari 2600

O Jogo da Velha 3D é como o tradicional, mas agora você joga em um tabuleiro cúbico. O objetivo ainda é completar uma linha antes do seu oponente. Note que o jogo do Atari era 4x4x4, e não 3x3x3. No jogo 3x3x3, o primeiro jogador sempre pode forçar a vitória, então é uma variação sem graça.

Depois de algum tempo jogando o Jogo da Velha 3D, tivemos uma idéia: se a versão 3D é mais divertida que a 2D, será que o Jogo da Velha 4D não seria mais legal ainda? Nós desenhamos um tabuleiro 4D no papel e, realmente, era divertido mesmo! Nós desenhávamos o tabuleiro a caneta e jogávamos com lápis, assim era só apagar com borracha para jogar de novo. No fim, ficamos tão viciados que os papéis rasgaram de tanto apagar!

Hora da segunda idéia: os alunos de Eletrônica tinham acesso à sala dos computadores, cheio de PC-XTs rodando DOS. Eu aproveitei que tinha acabado de aprender Pascal, e fiz um tabuleiro eletrônico para jogar direto no computador, sem ter que ficar apagando o tabuleiro a cada jogo. (Você pode pegar esse source no github: 4dvelha.pas)

Jogo da Velha 4D, rodando no PC-XT

Essa versão nos divertiu um monte. Eventualmente tivemos outra idéia: por que não jogar o Jogo da Velha 5D? Essa idéia não foi para frente, depois de algumas partidas nós percebemos que o 5D tinha o mesmo problema do 3D, o primeiro jogador conseguia forçar a vitória.

E o 6D? Um dos amigos usou o plotter do pai para desenhar um monstruoso tabuleiro de Jogo da Velha 6D, que só coube em um papel A2. Mas esse também não tinha graça: o jogo era muito esparso, sempre acabava antes que conseguíssemos utilizar todas as seis dimensões.

No fim, o Jogo da Velha 4D era o ponto ótimo, e jogamos essa variação até o fim do colégio. Mas quando eu entrei na faculdade, topei com um problema diferente.

O Jogo da Velha Minimax


A biblioteca da Poli era enorme e cheia de cheia de títulos legais, como o livro de Inteligência Artificial do Peter Norvig. Ali eu conheci o algoritmo minimax para jogos competitivos, e naturalmente bateu a vontade de implementá-lo no meu Jogo da Velha 4D. (A versão com minimax também está no github: 4dvelha2.pas)

Infelizmente, o branching factor do Jogo da Velha 4D é muito alto: começa em 256, quase a mesma dificuldade do jogo de Go. Nos computadores da época (isso foi por volta de 1994), eu conseguia no máximo descer um único nível da árvore. Eu fiquei bastante frustrado com isso. Será que eu conseguiria bolar alguma variação do Jogo da Velha que tivesse um branching factor menor?

Alguns anos depois eu consegui uma solução: ao invés de mudar o número de dimensões, eu mudei a geometria do tabuleiro! Se você pegar um Jogo da Velha 3D, esticar as pontas, e depois torcer o tabuleiro sobre si mesmo, o resultado é um Jogo da Velha 3D não-Euclideano.


Essa versão eu implementei como um applet Java, então você pode jogar online, ou pegar o source no github. Com o branching factor menor, deu para colocar três níveis de dificuldade, desde o Easy (abre um nível da árvore), até o Hard (abre três níveis da árvore).

Jogo da Velha não-Euclideano

Ganhar do computador no Hard não é impossível, mas você vai precisar de muito treino para conseguir :)

A Criatividade


Dessa vez quem cantou a moral da história foi o Douglas Hofstadter. Em um dos seus livros ele conclui que "variações sobre um tema são o ponto crucial da Criatividade". Pode parecer anti-intuitivo para a maioria: ser criativo não é o mesmo que ser original? Então como pode a criatividade estar baseada na variação?

O problema é que quem está de fora só vê uma pessoa girando um botãozinho: esse Jogo da Velha está na posição 2D, eu giro o botão aqui e tenho 3D, giro mais e tenho 4D. Mas criatividade não é girar o botão, criatividade é achar um botão que não estava lá! Quando eu notei que tinha um botão que girava a geometria, aí sim eu estava sendo criativo.

Em resumo, para expandir a sua criatividade você precisa achar variáveis onde antes só haviam constantes. E isso vale tanto para arte quanto para computação :)