Como o IBM Deep Blue derrotou o lendário Garry Kasparov em 1997
Quando eu vi pela primeira vez o documentário do AlphaGo de 2015, eu achei muito interessante como esses sistemas alcançaram algo absurdamente difícil para qualquer ser humano, de ganhar de campeões mundiais em jogos complexos.
Tente jogar algumas partidas no Chess.com e você verá como é difícil manter mais que 1000 pontos de ranking. Iniciantes chegam no xadrez e acham que vai ser rápido o aprendizado, mas subir é bem mais complicado do que parece.
Os feitos da Inteligência artificial nesse meio foram tão grandes ao ponto de programas como AlphaZero e StockFish, se tornarem os melhores jogadores de Xadrez do mundo em um pódio que os maiores enxadristas não ousam tocar, embora possam tentar.
A primeira versão do Deep Blue, foi o Deep Thought e foi a primeira máquina a realmente ser bem sucedida em ganhar de jogadores de xadrez em nível professional.
Antes mesmo destes dois, ainda tinha o ChipTest (1986–1987), que foi a versão base criada por Feng-hsiung Hsu, Thomas Anantharaman e Murray Campbell.
Diferente do que talvez do que os documentários e a mídia passem sobre o tema, quando vemos a história do Deep Blue, vemos uma série de tentativas e erros que demoraram anos para serem resolvidas.
O aumento da capacidade computacional desde 1986 até 1997 com certeza ajudou nessa questão. O uso de computação paralela foi algo essencial para esse feito por permitir, mesmo que com o baixo nível de processamento da época, fossem criados supercomputadores, como o do Deep Blue na prática.
Mas como ela como funcionava, e qual era a extensão do seu poder?
Deep Thought e Deep Blue I e 2
O artigo acima de (Campbell, et.al 2002) mostra como era o funcionamento desse supercomputador da época. Além disso, mostra os principais algoritmos e processos usados para calcular as melhores jogadas.
O Deep Thought I tinha apenas um chip para o processamento das jogadas, ao todo ele podia calcular de 500,000 a 700,000 posições por segundo. A segunda versão do mesmo tinha algumas modificações importantes.
Ele teve seu programa de brute-force search totalmente refeito, adicionaram mais capacidade de memória e hardware além de adicionarem algo chamado Livro Extendido, que era um banco de dados de jogadas de xadrez.
Vale lembrar que os pesquisadores contavam com a ajuda de Grão Mestres renomados para avaliar o programa e jogar contra ele, e posteriormente criaram um banco de dados de jogadas e aberturas no xadrez enorme para o programa.
Entre as partidas jogadas pelo Deep Thought temos contra: , Rubens R. Reyns, David Lawson,Michael joseph Valvo ,Mikhail Zlotnikov, Igor Ivanov, Alexander Fishbein, respectivamente.
As aberturas mais usadas pelo programa eram: a Siciliana Alapin, Siciliana, abertura Inglesa, abertura Defesa Escandinava e a abertura Defesa Holandesa.
Deep Blue I
A primeira versão do sistema usava o IBM RS/6000®SPTM, que era um servidor bem potente para a época. Com 216 chips que eram focados em calcular as melhores jogadas durante cada momento da partida.
Cada um destes chips podia procurar de 1.6 até 2 milhões de posições por segundo. E a soma do processamento dela ia até 100 milhões de posições por segundo.
Esse programa duelou com grandes Grão mestres: derrotou Ilya Gurevich, empatou com Patrick Wolff, e perdeu para Joel Benjamin, que estão respectivamente acima.
Entretanto, perdeu para Garry Kasparov em 1996, algo que com certeza chocou os pesquisadores ao redor do grande espetáculo. A partida contra Kasparov foi feita na New Universty of Arts, e tinha uma mídia bem pesada nesse evento, algo similar ao que aconteceu com o AlphaGo.
Para eles obviamente a derrota contra Kasparov foi bem dura para a IBM, no documentário sobre essa partida é possível ver as reação quando deles quando o programa foi derrotado, com certeza foi um choque já que a confiança estava lá em cima.
Deep Blue II
Após o fiasco, o time de programadores começou a tentar melhorar o Sistema, a principal mudança é no hardware. Eles aumentaram a velocidade do sistema drasticamente, com algumas outras mudanças relevantes.
Com 38 unidades de processamento no servidor (ainda usando o IBM RS/6000 SP), 480 chips ao invés de 216 do anterior. Cada node com 1 GB de Ram e 4 GB de disco, tudo rodando o AIX®4.2, um sistema operacional para servidores da IBM, é usado ainda hoje, as versão mais recentes obviamente.
Cada chip usado para calcular jogadas agora tem uma velocidade de 2 até 2.5 milhões de posições por segundo. Dependendo da dificuldade das jogadas, esse monstro operava de 100 à 200 milhões de jogadas por segundo.
Além do algoritmo de brute force search que tentava dentro de cada momento da partida, encontrar a melhor jogada no tabuleiro. Eles também usavam o algoritmo de Duplo Crédito.
O Objetivo é assimilar as melhores jogadas possíveis e dar mais crédito a elas como se fossem pontos. O Deep Blue II deveria dentro de cada jogada usar esse algoritmo além do brute force search para entender qual era a mais adequada a aquele momento da partida.
É como uma peneira, ou um filtro que tira as impurezas das nossas escolhas para podermos ver com nitidez o que realmente é necessário para a vitória no longo prazo.
Além disso o programa contava com Hardware Search e Parallel Search, que são algoritmos do sistema calculando as melhores jogadas, mas a pesquisa paralela é aquela que merece mais atenção.
A computação paralela é algo essencial para supercomputadores. Ela permite usar milhares de nodes com unidades de processamento e memória para agirem juntas para resolver problemas.
Elas não calculam as coisas ao mesmo tempo sem parar, na verdade há um delay nessa questão (São milhares de nodes), mas isso aumenta a velocidade de forma brutal.
É como se em vez de pegar a pessoa mais forte do mundo para levantar um peso, você juntasse milhares de milhares de pessoas médias em força para juntas levantarem esse peso, é um exemplo simples, mas bem trivial.
O Deep Blue II também tinha uma função de evaluação das jogadas. Essa função é o agrupamento de todas as características do game. Isso inclui as jogadas possíveis do sistema e do adversário, é como uma manual interno de partidas do programa.
Ao todo são 8150 parâmetros que podem ser usados para o reconhecimento dos estados do jogo ao longo do tempo.
Livro de aberturas
O Deep Blue II tinha um banco de dados de aberturas, feito por Joel Benjamin (Principal), Nick De Firmian, John Fedorowicz e Miguel Illescas, todos Grão Mestres.
Isso também filtrava as melhores jogadas. O jogador de Xadrez também tem um banco de dados de partidas assim, mas na sua mente, e ele usa isso até de forma inconsciente.
Eles usaram esse mesmo princípio, nesse caso para aberturas, que são a forma que você começa o jogo, as primeiras jogadas. Elas podem decidir e muito o jogo mais para frente, embora Bobby Fischer já tenha feito uma piruetas no começo e conseguiu voltar para o game, o Deep Blue II não pode arriscar.
Livro Extendido
Esse banco de dados não estava presente no Deep Blue I (ou Deep Thought), ele consistia de 700 mil partidas que estavam disponíveis no Look Up Table do sistema.
Grão mestres também ajudaram a fazer esse livro extendido que foi absurdamente essencial para a vitória contra Kasparov.
A Vitória da Máquina
No fim, esse programa desenhado de forma muito inteligente derrotou Garry Kasparov em 1997.
A derrota parece o ter chocado muito ali, no momento, mas em podcasts (como o do Lex Fridman ) recentes ele mostra como o avanço da computação é beneficial à humanidade, e como foi bom talvez ele ter perdido.
Kasparov até escreveu um livro sobre essa partida e o conceito por trás dela. É óbvio que ele não só a superou mais aceitou a derrota com o tempo.
A verdade é que no momento não há nenhum jogador melhor que o StockFish e o AlphaZero que são os melhores programas atualmente em Xadrez.
Kasparov só foi o primeiro lendário jogador de xadrez que perdeu, e por isso na época a pancada foi maior, do que o Magnus Carlsen perder para o AlphaZero por exemplo, embora quem sabe ele ganhe…
Algo importante
Embora o artigo do Deep Blue tenha sido publicado em um Jornal Acadêmico de Inteligência Artificial, ele não usa IA em literalmente nada.
Ele não é um sistema de IA, ele não aprende, e constantemente era melhorado pelos programadores, alterando o seu hardware e software.
Já o Alpha Zero feito pela Deep Mind, é realmente um programa de IA usando Reinforcement Learning e Monte Carlo search para o sistema aprender a jogar Xadrez, e é o melhor atualmente.
Isso mostra como a Inteligência Artificial é o futuro e o presente para o desenvolvimento de jogos mais inteligentes e difíceis em que o jogador será rulado constantemente se não se atualizar sobre as novas jogadas criadas pelo sistema, tais que o programado nunca imaginou ou concebeu.
Referências:
- Campbell, M., Hoane, A.J., & Hsu, F. (2002). Deep Blue. Artif. Intell., 134, 57–83.
- Hsu, F. (1999). IBM’s Deep Blue Chess grandmaster chips. IEEE Micro, 19, 70–81.
