Em 2006, depois de visitar a exposição sobre xadrez do Museu de História da Computação, opinei:
Talvez tenhamos chegado a um ponto de inflexão. O espaço problemático do xadrez é tão surpreendentemente grande que é improvável que aumentos incrementais na velocidade do hardware e nos algoritmos resultem em ganhos significativos daqui para frente.
Então. Sobre isso. Acontece que eu estava meio que … totalmente errado. O número de movimentos possíveis, ou “espaço do problema”, do xadrez é de fato surpreendentemente grande, estimado em 1050:
100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
https://www.youtube.com/watch?v=iSnAiXKU7h8
Azul profundo era interessante porque previa um tipo particular de futuro, um futuro em que o o hardware especializado possibilitou o ataque de força bruta ao enorme espaço de problemas do xadrezpois seu hardware de xadrez desenvolvido para esse fim superou o desempenho das CPUs de uso geral da época em muitos ordens de magnitude. Quantas ordens de magnitude? Nos dias de glória de 1997, o Deep Blue podia avaliar 200 milhões de posições de xadrez por segundo. E isso foi suficiente para derrotar Kasparov, o jogador humano mais bem classificado de todos os tempos – até que o 2014 pelo menos. Embora um de seus melhores movimentos tenha sido o resultado de um bug.
200,000,000
Em 2006, cerca de dez anos depois, de acordo com o benchmark do Fritz Chessmeu PC poderia avaliar apenas 4,5 milhões de posições de xadrez por segundo.
4,500,000
Hoje, cerca de vinte anos depois, esse mesmo benchmark diz que meu PC pode avaliar apenas 17,2 milhões de posições de xadrez por segundo.
17,200,000
Dez anos, quatro vezes mais rápido. Nada mal! Parte disso se deve ao fato de eu ter passado de dual core para quad core, e esses cálculos de xadrez são escalonados quase linearmente com o número de núcleos. Uma CPU de oito núcleos, que não é mais particularmente exótica, provavelmente poderia atingir cerca de 28 milhões nesse benchmark atualmente.
28,000,000
Não tenho certeza se a escala é exatamente linear, mas é justo dizer que mesmo agora, vinte anos depois, uma CPU moderna de 8 núcleos ainda é cerca de uma ordem de magnitude mais lenta na tarefa de força bruta de avaliar posições de xadrez do que o hardware especializado em xadrez do Deep Blue alcançou em 1997.
Mas a questão é a seguinte: nada dessa força bruta veloz importa hoje. Programas de xadrez muito aprimorados executados em meros dispositivos portáteis podem executar além do nível de grão-mestre.
Em 2009, um mecanismo de xadrez executado em um hardware mais lento, um telefone celular HTC Touch HD de 528 MHz executando o Pocket Fritz 4, atingiu o nível de grão-mestre – ele venceu um torneio de categoria 6 com uma classificação de desempenho de 2898. O Pocket Fritz 4 pesquisa menos de 20.000 posições por segundo. Isso contrasta com os supercomputadores, como o Deep Blue, que pesquisou 200 milhões de posições por segundo.
No que diz respeito ao xadrez, apesar do que eu pensava de forma tão otimista em 2006, ele tem sido fim de jogo para os seres humanos já há alguns anos. Os melhores programas de xadrez para computador, muito mais eficientes do que o Deep Blue, combinados com CPUs modernas que agora estão finalmente dentro de uma ordem de magnitude do que o hardware de xadrez especializado do Deep Blue poderia oferecer, jogam em níveis muito além do que os humanos podem alcançar.
Xadrez: arruinado para sempre. Obrigado, computadores. Seus idiotas.
Apesar dessa derrota retumbante, ainda havia esperança para os humanos no jogo de Go. O número de movimentos possíveis, ou “espaço de problemas”, do Go é estimado em 10170:
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
Lembre-se de que o xadrez teve um mero cinquenta zeros lá? O Go tem mais movimentos possíveis do que o número de átomos no universo.
O senhor pode se convencer disso.
O Deep Blue foi uma declaração sobre a inevitabilidade do eventualmente ser capaz de fazer força bruta para contornar um problema difícil com o vento constante da Lei de Moore nas costas do senhor. Se o xadrez é o jogo europeu por excelência, o Go é o jogo asiático por excelência. O Go exige uma estratégia completamente diferente. Go significa lutar com um problema que é essencialmente impossível para os computadores resolverem de qualquer maneira tradicional.
Uma avaliação simples de material para o xadrez funciona bem: cada tipo de peça recebe um valor e cada jogador recebe uma pontuação dependendo das peças restantes. O jogador com a pontuação mais alta é considerado “vencedor” naquele estágio do jogo.
No entanto, os programadores de xadrez que inocentemente pedissem aos jogadores de Go uma função de avaliação seriam recebidos com incredulidade! Essa avaliação simples não existe. Como existe apenas um único tipo de peça, somente o número que cada jogador tem no tabuleiro poderia ser usado para uma simples heurística material, e não há quase nenhuma correlação discernível entre o número de pedras no tabuleiro e qual será o resultado final do jogo.
A análise de um problema tão difícil, com a força bruta completamente fora de cogitação, é coloquialmente chamada de “IA”, embora esse termo seja um pouco exagerado para mim. Prefiro pensar nisso como a criação de sistemas que podem aprender com a experiência, também conhecido como aprendizado de máquina. Aqui está uma palestra que aborda o aprendizado da DeepMind para jogar videogames clássicos do Atari 2600. (Vá até a marca de 10 minutos para ver o que quero dizer).
Por mais impressionante que isso seja – e realmente é -, lembre-se de que jogos tão simples como o Pac-Man ainda estão muito além do alcance do Deep Mind. Mas o que acontece quando o senhor aponta um sistema como esse para o jogo de Go?
A DeepMind criou um sistema, AlphaGo, projetado para ver até onde poderia chegar com essas abordagens no jogo de Go. O AlphaGo enfrentou recentemente um dos melhores jogadores de Go do mundo, Lee Sedol, e o o derrotou em uma impressionante exibição de 4-1. Como otimista que sou, imaginei que o DeepMind venceria um ou dois jogos, mas uma goleada quase total como essa? É incrível. Em um espaço de apenas 20 anos, os computadores passaram de quase não vencerem os melhores humanos no xadrez, com um espaço de problema de 1050, para vencer definitivamente os melhores humanos em Go, com um espaço de problemas de 10170. Como isso aconteceu?
Bem, algumas coisas aconteceram, mas um herói desconhecido nessa transformação é a humilde placa de vídeo, ou GPU.
Considere este detalhamento de o custo das operações de ponto flutuante ao longo do tempo, medido em dólares por gigaflop:
| 1961 | $8,300,000,000 | |
| 1984 | $42,780,000 | |
| 1997 | $42,000 | |
| 2000 | $1,300 | |
| 2003 | $100 | |
| 2007 | $52 | |
| 2011 | $1.80 | |
| 2012 | $0.73 | |
| 2013 | $0.22 | |
| 2015 | $0.08 |
O que não está claro nessa tabela é que depois de 2007, todos os grandes avanços em FLOPS vieram das placas de vídeo para jogos projetadas para renderização 3D em tempo real de alta velocidade e, como um efeito colateral incrivelmente benéfico, elas também são loucamente rápidos em tarefas de aprendizado de máquina.
O projeto Google Brain tinha acabado de obter resultados surpreendentes – aprendeu a reconhecer gatos e pessoas assistindo a filmes no YouTube. Mas foram necessárias 2.000 CPUs em servidores alimentados e resfriados em um dos gigantescos data centers do Google. Poucos têm computadores dessa escala. A NVIDIA e a GPU entraram em cena. Bryan Catanzaro, da NVIDIA Research, juntou-se à equipe de Andrew Ng, em Stanford, para usar GPUs para aprendizagem profunda. Como se viu, 12 GPUs NVIDIA poderiam oferecer o desempenho de aprendizagem profunda de 2.000 CPUs.
Vamos considerar um caso relacionado de computação altamente paralela. Quanto mais rápida é uma GPU em hashing de senhas?
| Radeon 7970 | 8213,6 M c/s |
| CPU AMD de 6 núcleos | 52,9 M c/s |
Somente 155 vezes mais rápido logo de cara. Não é nada demais. Além disso, o desempenho da CPU ficou praticamente estagnado na última década. Embora cada vez mais núcleos sejam colocados em cada matriz, o que é ótimo quando os problemas são paralelizáveis – como definitivamente são neste caso – a melhoria real do desempenho de qualquer núcleo individual nos últimos 5 a 10 anos é bastante modesta.
Mas as GPUs ainda estão dobrando de desempenho a cada poucos anos. Considere a quebra de hash de senha expressa na taxa de hashes por segundo:
| GTX 295 | 2009 | 25k |
| GTX 690 | 2012 | 54k |
| GTX 780 Ti | 2013 | 100k |
| GTX 980 Ti | 2015 | 240k |
Essa última placa de vídeo é a que está em minha máquina no momento. É provável que a próxima grande revisão da Nvidia, prevista para o final deste ano, seja dobre essas taxas novamente.
(Já que estou falando disso, gostaria de enfatizar o quanto é ruim ter uma senha de 8 caracteres no mundo de hoje. Se sua senha tiver apenas 8 caracteres, isso é perigosamente próximo de não ter senha alguma. É também por isso que o senhor sua senha é (provavelmente) muito curta. Na verdade, acabamos de aumentar a mínimo de permitido de comprimento de senha em Discurso a 10 caracteres, porque regras irritantes de complexidade de senha são muito menos eficazes na realidade do que simplesmente exigir senhas mais longas.)
AlphaGo distribuído usou 1202 CPUs e 176 GPUs. Embora isso não pareça muito, considere que, como vimos, cada GPU pode ser até 150 vezes mais rápida no processamento desses tipos de conjuntos de dados altamente paralelos – portanto, essas 176 GPUs foram o equivalente a adicionar ~26.400 CPUs à tarefa. Ou mais!
Mesmo que o senhor não se importe com videogames, eles têm um profundo impacto acidental nos aprimoramentos do aprendizado de máquina. Toda vez que o senhor vir o lançamento de uma nova placa de vídeo, não pense em “jogos um pouco mais bonitos”, pense em “uau, o hash cracking e a IA ficaram 2 vezes mais rápidos… de novo!”
Certamente não estou cometendo o mesmo erro que cometi ao analisar o xadrez em 2006. (E, em minha defesa, eu não vi a era das GPUs como um auxílio essencial para o aprendizado de máquina, embora eu seja um jogador). Se o AlphaGo era intimidador hoje, tendo derrotado o melhor jogador humano de Go do mundo, ele não será contestado depois de mais alguns anos em que as GPUs dobrarem e redobrarem suas velocidades novamente.
O AlphaGo, em termos gerais, é o ponto culminante de duas tendências muito importantes na computação:
-
Enormes aumentos no poder de processamento paralelo impulsionados por GPUs de consumo e videogames, que começaram em 2007. Portanto, se o senhor é um jogador, parabéns! O senhor faz parte da solução do problema.
-
Estamos começando a criar abordagens algorítmicas sofisticadas (e combinadas) para espaços de problemas totalmente novos que são vastos demais para serem resolvidos apenas por métodos de força bruta. E essas abordagens claramente funcionam, na medida em que eles dominaram um dos jogos mais difíceis do mundo, um jogo no qual muitos pensavam que os seres humanos jamais seriam derrotados.
Excelente. Outro jogo arruinado para sempre pelos computadores. Idiotas.
Com base em nossa experiência com o xadrez e agora com o Go, sabemos que os computadores continuarão a nos derrotar em praticamente todos os jogos que jogamos, da mesma forma que os golfinhos sempre nadarão mais rápido do que nós. Mas e se essa mesma mente humana fosse capaz não apenas de construir o golfinho, mas de refiná-lo continuamente até chegar ao o peixe-anão mais rápido do mundo? Enquanto o Deep Blue foi o resultado final mais ou menos inevitável da computação de força bruta, o AlphaGo é o início de uma era totalmente nova de solução sofisticada de problemas contra problemas muito maiores. A vitória do AlphaGo não é uma derrota da mente humana, mas seu maior triunfo.
(Se quiser saber mais sobre a poderosa interseção de algoritmos sofisticados de aprendizado de máquina e sua GPU, leia este excelente resumo do AlphaGo e depois faça o download do aluno do DeepMind Atari e experimente o senhor mesmo).