quinta-feira, 12 de maio de 2016

Ontem eu ganhei acesso a um computador quântico real da IBM! Eles tem agora um website onde você pode submeter remotamente jobs para esse computador quântico, e mandam os outputs por email. Esse website é de acesso restrito, mas eu falei que era blogueiro de ciência e podia divulgar os resultados para os brasileiros em português (colou hehe).

Pois bem, o computador tem 5 qubits e é quântico para valer. Você não programa com linguagens de programação, ao invés disso, a interface é tipo um pspice, mas com portas lógicas quânticas ao invés de portas binárias. (Mas eu já aviso que se você tiver medo de álgebra linear com números complexos, não vai passar do básico).

O computador em si é bem rústico: além de ter que lidar com superposição e entrelaçamento, você ainda tem que pensar que saída é probabilística e tem ruído. Na prática, para ver resultados consistentes você precisa rodar o mesmo algoritmo 1024 vezes e ver na média o resultado.

Dos algoritmos que eu rodei, o mais fácil de entender é o algoritmo de Grover. Ele é o equivalente à busca linear (dado um vetor não ordenado, achar o índice do elemento procurado). Ele é O(n) em um comptador clássico, mas no quântico é O(sqrt(n)). O funcionamento é curioso, você começa com os qubits entrelaçados em todas as soluções possíveis, e rotaciona o espaço de modo que a solução desejada fica um pouco mais provável que o aleatório puro. Se você rodar esse bloco sqrt(n) vezes, dá para provar que a solução correta fica muito mais provável que todas as outras, aí você aplica o threshold e corta. Na wiki tem os detalhes:

https://en.wikipedia.org/wiki/Grover%27s_algorithm

No fim de semana eu quero tentar o algoritmo de Shor de fatoração quântica (ele é muito parecido com o Pollard Rho, mas a detecção de ciclo é feita com entrelaçamento).




sexta-feira, 6 de maio de 2016

O Euclides era foda pra caralho mesmo. Eu estava aqui de boa tomando banho quando me caiu a ficha de que os cinco postulados deles na verdade são propriedades do espaço. Olha só, na forma original eles são assim:
1. Por dois pontos passa um reta.
2. Uma reta sempre pode ser estendida indefinidamente.
3. Dado um ponto e um raio, você pode construir um círculo.
4. Todos os ângulos retos são congruentes.
5. Dado uma reta e um ponto fora dela, você pode construir uma paralela.
O Heath fala que o quarto postulado é esquisito, tinha outras afirmações equivalentes que ele poderia ter usado. Mas ele precisava do quarto nessa formulação exata, senão não tinha como descrever o quinto de forma não-ambígua.
Aí eu fiquei pensando se existem outras maneiras, e achei uma equivalente só com proposições sobre o espaço:
1. O espaço é contínuo.
2. O espaço é infinito.
3. O espaço é métrico.
4. O espaço é invariante a rotações.
5. O espaço tem curvatura zero.
Esses cinco postulados alternativos que eu bolei são equivalentes aos postulados do Euclides, você pode usar esses para provar os dele e vice-versa.
Para mim mostra que o Euclides manjava muito, ele não tinha essas noções modernas sobre o espaço mas achou uma maneira grega de dizer a mesma coisa!

terça-feira, 12 de abril de 2016

Mindfuck do dia: ninguém sabe qual é a área do conjunto de Mandelbrot. Ninguém conseguiu calcular analiticamente, mas os melhores bounds colocam a área entre 1.66 e 1.71. Agora, se você usar um método numérico, a área é 1.506591884 com precisão no último dígito. Cadê esse 0.16 que falta? Ninguém sabe, mas a melhor teoria até agora é que...

(dramatic chipmunk)

... o contorno contribui para a área! A dimensão hausdorff do contorno do conjunto é 2, então ele é área-like, pode ser isso que os métodos numéricos não estão capturando.

(sim, eu fiquei estudando fractais enquanto não dava meia-noite)


segunda-feira, 11 de abril de 2016

Parece inacreditável, mas existe uma meta-máquina universal de Turing, capaz de computar *qualquer* função f:N->N, *incluindo as não-computáveis*, desde que você ache um universo paralelo apropriado!
A demonstração em si não é difícil, mas eu vou dar uma simplificada aqui para ficar mais fácil de entender. Quem quiser ver a versão original, é só pegar no link acima que tem os detalhes (thx Joao Kogler pelo link):
Passo 1: Vamos relembrar o "teorema do reirom": existe um emulador capaz de emular qualquer sistema. Formalmente: as máquinas de Turing são enumeráveis, ou seja, para cada máquina você atribuir um número inteiro único. Com isso, você consegue construir uma máquina universal que tem como input o número da máquina que você quer emular, e o input original do problema que você quer resolver. Assim, você emula qualquer função computável.
Passo 2: Vamos relembrar que nenhum sistema formal é completo. Pelo teorema de Gödel, sempre existem proposições de um sistema que não admitem demonstração. E mais, mesmo que você pegue uma proposição e adicione com axioma ao sistema, ele continua sendo incompleto. Você pode adicionar infinitas proposições, sempre vai faltar uma.
Passo 3: Vamos relembrar que um sistema formal admite proposições que são independentes do sistema. Ou seja, tanto faz se você adiciona p ou não-p ao sistema, ele continua consistente. Exemplos conhecidos são o teorema das paralelas em relação aos outros axiomas do Euclides, ou a hipótese do continuum em relação à teoria dos conjuntos (ZFC).
Passo 4 (a pegadinha): Se você tem um sistema formal S onde tanto faz adicionar a proposição p ou a não-p, isso significa que, depois de adicionar a proposição, os sistemas S+p e S+não-p tem *um bit a mais de informação*. Para checar o valor desse bit, é só verificar qual proposição foi adicionada, se foi p o bit é 1, se foi não-p o bit é 0.
Passo 5 (a parte técnica): Se você conseguir construir uma sequência ordenável de proposições p_i, onde todas são independentes entre si, então você consegue adicionar ao sistema S uma string infinita de bits. Essa é a parte complicada da demonstração original, onde ele mostra como construir essa sequência. Mas o fato é que é possível, em qualquer caso.
Passo 6: Se você adicionou uma string infinita de bits ao sistema, então você codificou uma função binária f:N->{0,1} dentro do sistema. Agora é só escrever um algoritmo que, dado n, calcula f(n) através da enumeração das propriedades que você construiu dentro do sistema. Esse é um algoritmo universal que calcula qualquer função binária, até as não-computáveis!, dado que você codificou a função na unha, valor a valor. Assim como o input da máquina universal era o problema + o código da máquina que tem que ser emulado, nessa aqui o input é o problema + o sistema formal acrescido dos p_i que você codificou.
Passo 7: Obviamente, se você tem uma função f:N->{0,1}, então você também tem uma função f:N->N, é só usar um código de comprimento variável, tipo UTF-8.
Pronto, agora você tem um meta-algoritmo que calcula qualquer função. É só levar o algoritmo para um universo onde as regras são S+p_i que ele computa sozinho a função para você! Achar um universo paralelo fica como exercício para o leitor.
Agora as implicações do teorema:
1. Utilidade prática: nula
2. Você consegue codificar f:N->N, mas não consegue codificar f:R->R (Como você adiciona um bit por vez, o máximo que você consegue colocar é aleph-zero. Para suportar os reais precisaria colocar c).
3. Uma das funções não-computáveis que você pode computar é a parada de Turing. Então tem um universo aí onde você pode determinar exatamente quais das nossas máquinas de Turing param, e quais não param! Mas nesse universo, eles não conseguem calcular a parada das máquinas deles, só das nossas.
4. Se você estiver criando um universo do zero, é um jeito bacana de esconder um easter egg dentro da matemática que rege seu universo. Fica a dica aí pra quem for onipotente.

quinta-feira, 7 de abril de 2016

Você acha que o Euclides é grego ou que a Cleopatra é egípcia? Precisa escolher um, os dois ao mesmo tempo não dá.
Ambos viveram em Alexandria, que pelos critérios de hoje é claramente Egito. Se você levar em conta exclusivamente os critérios de geolocalização, os dois são claramente egípcios.
Mas Alexandria foi fundada por um grego e sempre teve cultura grega. Euclides viveu na época do rei Ptolomeu I, a Cleopatra era filha do Ptolomeu XII, são 200 anos de diferença mas ainda é o mesmo império fundado pelo Alexandre (que era discípulo de Aristóteles, grego de raiz). Se você levar em conta os critérios culturais, os dois eram claramente gregos.
Acho que a treta só existe porque a Cleopatra era populista e queria muito ser a rainha do povo, inclusive ela foi a única da dinastia inteira que aprendeu a falar egípcio (todos os outros Ptolomeus só falavam grego). Ela se vendia como egípcia, mas era só propaganda para ganhar confiança da massa. Na minha cabeça, tanto o Euclides como a Cleopatra são gregos.


Comprei um kit grego: régua, compasso, lapiseira, prancheta e papel de gramatura alta.
Essa é a parte legal de ser adulto, você pensa "puxa estou com vontade de comprar um compasso", aí vai ali na esquina, compra, e pode passar o resto da noite feliz agregando conhecimento.


Pausa para o estudo de grego arcaico. O substantivo "cinco" é πεμπασ, e o verbo "contar" é πεμπαζειυ. Daí você deduz que no tempo do Homero, "contar" era "cincar", e portanto é uma boa evidência de que eles usavam base 5 ao invés de base 10!
(O Heath concorda com o raciocínio então deve ser isso mesmo).


Desenho da noite da Ila Fox: porque todos gostamos de emus! Na real só não gosta de emus quem ainda não conhece, o bracinho dele é igual ao do T-Rex, então se você gosta de dinossauros provavelmente vai gostar de emus também.
(E eu estou falando como especialista em emus, já até escrevi alguns)



segunda-feira, 14 de março de 2016



O Sedol ganhou uma partida! Não vai ser 5-0 !
Essa eu não assisti ao vivo, mas pelo replay ficou claro para mim que o maior problema do Alphago é que ele não tem a capacidade de levantar e sair da sala de vez em quando.
A partida começou bizarramente igual ao segundo match. O Sedol já tinha dito em entrevista que o opening dele na segunda partida estava bom, e ele tinha estragado na frente. Então ele simplesmente repetiu as jogadas, e o Alphago também. As primeiras 10 jogadas foram repetidas, até que na 11 o Sedol saiu da script.
Quem está acompanhando as partidas sabe que o Alphago tem essa mania de fazer aparecer território "magicamente". O que ele faz é atacar os grupos dos inimigos por fora, e enquanto o oponente defende, as peças de ataque do Alphago acabam formando um paredão que define o território.
Ontem aconteceu isso de novo, o Sedol fez um grupo na borda esqueda, o Alphago fez um paredão. Depois o Sedol fez outro grupo na borda direita, o Alphago fez paredão. Se continuasse assim, o Alpha teria o centro inteiro para ele, que foi mais ou menos o que aconteceu nas outras partidas.
Mas dessa vez o Sedol cortou o paredão no B56. O Alphago tentou bloquear, mas não percebeu uma jogada matadora do Sedol no B78. Quando o Alphago se deu conta de que o B78 era um tesuji sinistro, a partida já estava perdida. Eles se meteram num semeai na borda, e incrivelmente o Sedol ganhou o semeai (o que é bizarro porque supostamente computadores são muito bons de semeai). O resultado é que o Sedol *comeu um grupo inteiro do Alphago*, 8 pedras, e três jogadas depois o Alphago desistiu.
E o que aconteceu? Na minha opinião, o problema do Alphago é que ele não pensou o suficiente. Quando ele fez a jogada lendária na segunda partida, o Sedol levantou da cadeira, ficou 10min longe, e quando voltou ainda ficou mais 15min pensando antes de continuar. Agora foi o oposto, o Sedol fez uma jogada louca, mas o Alphago não se tocou disso. Pensou só 1 min na resposta, que é o padrão dele, ao invés de perceber que era uma jogada crítica e que valia a pena investigar mais.
O que eu acho que aconteceu foi o seguinte: essa pedra que o Sedol jogou no B78 é localmente ruim. Ela só funciona num contexto muito especial, e você precisa fazer uma sequencia especifica de dez jogadas para ver a utilidade dela.
Mas o Alphago é monte carlo né. Ele não analisa TODAS as possibilidades, só faz um sampling do espaço de busca e tira a média das jogadas. Na média, aquela pedra era ruim. Provavelmente o monte carlo não simulou aquela sequencia especial de dez jogadas que é a única que funciona (a chance de aparecer é 1/360^10 after all). Como a sequencia não apareceu, ele não percebeu, e o Sedol ganhou.
Tem solução? Claro, é só simular mais! Eventualmente a sequencia iria aparecer. O Alphago ainda tinha muito tempo sobrando. Se ficasse 25min simulando, como o Sedol fez na partida dois, ele teria achado a sequencia e protegido. Mas ele não tem um algoritmo para decidir quando precisa pensar mais e quando precisa pensar menos, joga sempre 1min por pedra, e isso foi o que o levou à derrota.
Sobre a partida de ontem: consta que na quarta-feira, depois de perder a segunda partida, o Lee Sedol juntou os amigos, e ficaram até as seis da manhã estudando os jogos do Alphago, para ver se achavam alguma fraqueza. Então eu já fui assistir curioso para ver qual técnica o Sedol ia usar.
Todo mundo estava esperando que ele fosse fazer uma abertura bem sólida, o que de fato aconteceu, mas por algum motivo o Sedol acabou deixando o Alphago tomar um território enorme na borda inferior. Mas tipo enorme mesmo, com base na sexta linha. Eu até comentei na hora que estava só esperando o Sedol desistir, seria bem dificil invadir e viver.
Mas o Sedol invadiu. E eu descobri o plano dele, não era invadir e viver, era invadir e matar!
O que ele e os amigos notaram é que o Alphago foge de ko. Se tem duas jogadas igualmente boas, mas uma delas envolve um ko, então o Alphago joga a outra. Talvez ele seja fraco em ko e por isso foge (mas não dava para ter certeza porque não tinha tido nenhum ko fight até agora).
E o plano do Sedol era esse, invadir e forçar um ko lá embaixo. Um ko tão poderoso que quem ganhasse levava a partida. Eu não consigo fazer outra comparação que não seja com Dragon Ball. Foi como se o Sedol tivesse ficado com cabelo amarelo, concentrado toda a energia numa jogada, e então jogou o ko!
O Alphago, quando viu o ko... bem, ele ignorou e fez tenuki no outro lado do tabuleiro. Desculpe Sedol, mas na hora ‪#‎euri‬.
O Sedol insistiu, fez mais dois kos naquela área, e ficou uma briga super complicada. A Ila Fox perguntava pra mim quem estava ganhando e eu não conseguia dizer, o jogo já estava num nível além da minha compreensão.
No fim o Sedol tomou o primeiro ko, mas o Alphago tomou o segundo, e quando ficou claro que ia tomar o terceiro também, o Sedol desistiu.


Tem gente que fala que seria mais feliz vivendo em outra época. Pode ser na época dos ninjas, na época dos piratas, whatever. Eu adoro a época em que estamos vivendo!
Pensa só, em um único lifetime, nós vamos passar por *duas* revoluções históricas. A primeira foi quando a gente presenciou a internet nascendo. A segunda começou ali no B37 da segunda partida, quando o Alphago fez uma jogada não-humana e o Lee Sedol ficou tão nervoso que levantou e ficou dez minutos longe do tabuleiro. Nós estamos vendo o começo da era das máquinas.
O Go era a barreira que faltava, agora já dá pra dizer com segurança que nós somos piores que os computadores. Para mim, é hora de começar seriamente a pensar se a sua profissão tem futuro, porque daqui a dez anos você pode estar ultrapassado. Os motoristas de táxi já eram, e eu acredito seriamente que em 20 anos os próximos vão ser os jornalistas, e, se não fizerem uma reserva de mercado para humanos, em seguida os médicos.
Matemáticos e programadores estão relativamente seguros com proteção divina de São Gödel e São Turing, mas tirando isso corre o risco de sobrar só babás. As profissões que sobram são aquelas que existiam antes da agricultura, e que foram moldadas por milhões de anos de evolução, ao invés de milhares de anos de inteligência. O resto vai capitular.

Repostando o link para o B37 só para vocês verem a cara de incredulidade dos comentaristas: 





Outro dia me perguntaram por que raios o alphago usa as regras chinesas para jogar Go. Eu respondi que é porque essas regras são mais fáceis de implementar computacionalmente.

Ninguém botou fé, falaram o time do alphago não ia precisar de atalhos assim e tal. Mas olha aqui uma entrevista de ontem com o Hassabis dizendo que foi por isso mesmo:

http://www.cnbeta.com/articles/482067.htm

A explicação é esse caso do jogo na imagem. As regras japonesas tem um negócio chamado Seki, que é quando dois grupos não podem se matar. Na figura, se o branco joga em A, o preto mata. Se o preto joga em A, então o branco mata. Logo, ninguém joga em A e fica um buraco que não é território de ninguém.

Só que detectar seki é NP-Completo, e a última coisa que você quer é colocar um NP-Completo no rabo do seu monte carlo. Compensa mais usar a regra chinesa onde você não precisa detectar o seki (a contagem de pontos é por área, então o seki é irrelevante).

(eu estou meio monotemático essa semana, mas é porque vivemos exciting times)



sexta-feira, 11 de março de 2016

O momento da partida em que passou um rabo de gato na frente da câmera!
Esse é o conhecido tesuji do gato preto. Em alguns sistemas de regras, se o gato anda em cima do tabuleiro, a partida é considerada empate (por exemplo, no sistema de regras aqui de casa).
Para quem quiser ver no video:


quinta-feira, 10 de março de 2016


Olha, eu já acho que o Sedol não tem mais chance. Fiquei convencido de que o Alphago é sobre-humano, deve ser 10p ou até mesmo 11p. Ninguém entendeu o W172 do Sedol ontem, mas eu saquei, foi pirraça. Ele pensou "vou perder mesmo, mas pelo menos eu tomo o canto de você, seu filho da mãe!"

Eu só consigo ver uma saída para não ser 5-0, e a saída é explorar a meta-informação que a gente tem. Tradicionalmente, computadores são bons de yose porque a árvore de busca é menor no fim do jogo. O Alphago é um nível acima, ele é bom midgame também. Daí, parece que a única alternativa é abrir muito no opening.

Pois bem, a minha sugestão é perder o opening de propósito!

A lógica é assim: está bem claro que o Alphago é matador quando está atrás, e que joga mais-ou-menos quando está na frente. Isso faz sentido quando você pensa que a função objetivo usada para treinar a rede é "ganhar o jogo". Não é "ganhar o jogo de lavada", é "ganhar o jogo". Por isso, se ele está na frente, qualquer jogada mantém o gradiente constante, porque a função objetivo não muda, fala que ele vai ganhar. Daí as jogadas esquisitas, dado que qualquer uma ganha, tanto faz o que você joga.

Então o meu truque seria assim: você começa com preto (dando 7.5 komi para ele), e perde um canto no opening de propósito, deixando ele consolidar território ali. Ele vai achar que está uns 20-30 pontos na frente. Mas você concede o canto de modo que ele fique over-concentrated ali, e de um jeito que você fique jogando influência pros lados. Aí é só ficar construindo moyo, o alphago vai achar que está na frente então vai jogar mais-ou-menos; e você consolida seus grupos de uma vez só, pegando um monte de pontos de uma vez. Aí é se preparar pra briga, porque o alphago vai vir com tudo.

Parece difícil, mas acho que se não for assim, não tem jeito.

(A foto sou eu com o Deep Blue. Pena que o Alphago vive na nuvem, não dá pra tirar foto com ele.)



quarta-feira, 9 de março de 2016


Eu tinha falado que era como final de copa do mundo, mas o Demis tem razão, é mais como o homem pousando na Lua. É o triunfo da tecnologia, caiu o último jogo onde o homem ainda ganhava da máquina. I, for one, welcome our new machine overlords.

(Ainda não mudo para 5-0. Se o Sedol tivesse tenukado no começo, tinha impedido aquele moyo gigante do branco no canto. Aposto que ele joga menos agressivo hoje.)


BOLÃO DO ALPHAGO
Coloque aqui sua aposta!
(Eu acho que vai ser Lee Sedol 4x1 AlphaGo.)
Pretendo assistir ao vivo, começa hoje um pouco depois da meia noite, a partida tem 2h para cada jogador + um minuto por pedra extra. Deve acabar por volta das 5am.
(Não sei descrever como esse evento é para mim, mas imagino que seja o mesmo que final da copa do mundo para o povo do futebol).

domingo, 6 de março de 2016

Filmes de cientistas estão na moda, depois do Hawking e do Turing, agora vai ter um do Ramanujan!

(O próximo tem que ser do Feynman please)


sexta-feira, 4 de março de 2016


Chegou minha fantasia de pinguim azul!

Agora é só cantar umas músicas, colocar no youtube, e fazer mais sucesso que a galinha pintadinha.

(Naturalmente a Luvinha não entendeu nada).


terça-feira, 1 de março de 2016

A Carranca Chifruda do Coisa-ruim está quase aparecendo! Usei o método do winding number para fazer o painter's algorithm, e melhorou bastante (mas parece que ele não gostou da estrela no E1M5. O ruim de algoritmo geométrico é que sempre tem quinhentos casos especiais para tratar).
Agora falta aprender como mover as coordanadas da textura dentro do svg para alinhar a figura. Note que todas as texturas de chão do Doom são 64x64, para fazer um desenho mais complexo de 128x128 eles alinharam quatro polígonos.