Enfim chegamos a era onde os computadores jogam xadrez melhor que eles mesmos!

Gerson Cortês
03/01/2018

Em 1950 o matemático Claude E. Shannon publicou um artigo sobre como “ensinar” um computador a jogar xadrez [2].  Ciente de que essa tarefa poderia parecer de pouca importância prática para alguns, Shannon lista, ainda na introdução, algumas tarefas de grande relevância (muitas delas já realizadas por máquinas hoje em dia) que poderiam ser implementadas utilizando essa “máquina de xadrez” como paradigma. O sonho por essa entidade não-humana capaz de jogar o nobre jogo é muita antiga, como o próprio Claude Shannon relata em seu artigo. Uma das mais famosas “máquinas” foi concebida no século XVIII pelo húngaro Wolfgang Von Kempelen, batizada de “The Maelzel’s Chess Automaton” (O autômato de xadrez de Maelzel) e popularmente conhecida como “The Turk” (O Turco) [ver imagem acima]. Suas apresentações geraram muita agitação e polêmica nos Estados Unidos no começo do século XIX, chamando a atenção de ninguém mais ninguém menos que o escritor e poeta Edgar Allan Poe, que escreveu um ensaio intitulado “Maelzel’s Chess Player” [3]. As décadas após o trabalho de Claude Shannon foram de grandes avanços para a criação de uma máquina de xadrez eficiente, o que começou a despertar o seguinte questionamento: Seria possível construir uma máquina capaz de bater o campeão mundial de xadrez?

A resposta definitiva para essa questão foi dada em 1997, quando o então campeão mundial de Xadrez Garry Kasparov foi derrotado pelo Deep Blue (IBM) [4] (ver imagem abaixo) em um match de seis partidas, vencendo uma partida e perdendo duas, além de três empates. O que era por muitos enxadristas de alto nível impossível de acontecer, aconteceu. Uma máquina derrotara nosso melhor jogador! Com uma altura de 1,95m e pesando 1,4 toneladas a máquina da IBM era formada de 32 microprocessadores PSSC de 120MHz, capaz de analisar 200 milhões de posições por segundo.  A fórmula implementada pela equipe da IBM e até hoje utilizada pelos maiores desenvolvedores de máquinas de xadrez envolve dois grandes pilares: grande esforço computacional, com processadores cada vez mais potentes capazes de avaliar mais posições em menos tempo; um gigantesco banco de dados, que vai de centenas de milhares de partidas analisadas de grandes mestres a um extenso e detalhado livro de aberturas e tabelas de finais de jogo. Esse banco de dados, criado com praticamente 600 anos de material produzido pela mente humana, ajuda o computador a “economizar” esforços tanto na abertura como no final de jogo, além de ajuda-lo a aperfeiçoar sua função de avaliação de posições do meio-jogo. Para aliar de forma harmônica o poder de processamento e as informações contidas no banco de dados, faz-se necessário um eficiente algoritmo de busca chamado de alpha-beta [6]. Esse algoritmo vem sendo utilizado exaustivamente nas atuais máquinas de xadrez para selecionar as melhores linhas de continuação do jogo e “podar” linhas fracas. Esse trabalho é de fato muito complexo e a própria construção da função de avaliação da posição [2] é meio manual (ajudada por grandes mestres para aperfeiçoar o entendimento da máquina de certas posições críticas), meio automática, onde o próprio programa aperfeiçoa seus parâmetros através de sua prática.

Ironicamente 20 anos após a fantástica vitória contra Kasparov, foi a vez das máquinas de sofrer uma contundente derrota. Mas quem seria capaz de derrotar uma máquina? Simples, outra máquina! Desenvolvida pela Google e a empresa de inteligência artificial DeepMind [7], batizada de AlphaZero, essa nova máquina com apenas 9 horas de treinamento jogando 44 milhões de jogos (com apenas 40 ms de tempo para executar um lance) consigo mesma foi capaz de atingir tal nível de compreensão do jogo que a permitiu desafiar a então campeão dos torneio de máquinas de 2016 (TCEC 2016) Stockfish para um match de 100 jogos. O resultado foi impressionante. AlphaZero impôs uma convincente derrota à Stockfish, ganhando 28 jogos e empatando os demais 72. Nenhuma derrota! Alguns detalhes dessa extraordinária performance são contados pelos próprios desenvolvedores em um artigo científico publicado na plataforma arXiv.org em  5 de dezembro de 2017 [8].

O segredo do sucesso de AlphaZero (que além de xadrez também joga Go e Shogi) está na maneira como o programa aprende o jogo, uma abordagem mais “humana”, por assim dizer. Enquanto as máquinas anteriores eram baseadas na equação “Força Bruta”(esforço computacional) mais “enorme banco de dados”, a abordagem do pessoal da DeepMind é menos “Força Bruta”, mais reforço da aprendizagem baseado em auto-treinamento [9] e zero banco de dados prévio. Inicialmente, os programadores implementam apenas as regras básicas e objetivo do jogo, logo após o computador começa uma seção de treinamento com ele mesmo.  Uma abordagem tipo “papel em branco” conhecido comumente como tabula rasa. Ao invés de utilizar uma função de avaliação “manufaturada” (meio humana, meio máquina), Alphazero utiliza uma abordagem via redes neurais com parâmetros ajustáveis [10]. Essa rede neural recebe uma determinada posição no tabuleiro como input e devolve um vetor cujas componentes são as probabilidades atribuídas para cada ação (próximo lance), além de um número que estima o resultado do jogo (vitória, empate ou derrota das peças brancas). Essas probabilidades e valor estimado são utilizados para guiar sua procura pelo melhor continuação do jogo.

O método de busca do AlphaZero também é bem diferente dos utilizados pelas máquinas atuais. Enquanto Stockfish, por exemplo, utiliza o algoritmo Alpha-Beta para excluir linhas fracas, AlphaZero utiliza um algoritmo similar a que os físicos, químicos e engenheiros utilizam há muito tempo: O Método de Monte Carlo [11]. O algoritmo de busca conhecido como Monte Carlo Tree Search (MCTS), permite que a máquina, dado uma posição inicial, escolha o melhor lance, aquele de maior probabilidade de vitória de acordo com os parâmetros atuais da rede neural. Os parâmetros da rede neural são “treinados” a se aperfeiçoarem através da estratégia de auto-treinamento, começando de valores escolhidos aleatoriamente.  A cada jogo os lances de ambos os jogadores são escolhidos através do algoritmo MCTS e ao final do jogo é guardado o resultado da partida. Os parâmetros da rede neural são atualizados para que a previsão do resultado da partida se aproxime o máximo do resultado final da mesma, além de maximizar a similaridade entre as probabilidades calculadas pela rede neural e as obtidas pelo algoritmo de busca.

O treinamento do AlphaZero foi realizado em 700.000 passos (aproximadamente 9 horas), utilizando 5.000 TPU’s [12] de primeira geração para gerar os jogos e 64 TPU’s de segunda geração para treinar a rede neural. Em apenas 4 horas de treinamento (ver gráficos na figura abaixo), AlphaZero foi capaz de superar o rating [Elo] de Stockfish quando a mesma foi campeã do TCEC 2016. O match  de 100 partidas entre as duas foi realizado seguindo regras de torneios oficiais, com um tempo de reflexão de um minuto por lance. Para esse torneio, AlphaZero utilizou uma única máquina com 4 TPU’s, enquanto Stockfish utilizou uma CPU de 44 núcleos Intel Xeon E5 2699 2.8Ghz, com 128Gb de memória RAM DDR4. O resultado como já comentamos não poderia ser mais contundente, não é?

Com uma abordagem mais “humana”, pode-se dizer que AlphaZero é um passo importante para a concretização das ideias visionadas por Shannon na década de 1950. Enquanto as máquinas baseadas no algoritmo Alpha-Beta de busca analisam da ordem de centena de milhões de posições por segundos, AlphaZero analisa “apenas” 80 mil posições, compensando esse baixo número com sua rede neural capaz de selecionar apenas as mais promissoras variantes. Agora imagine essa nova tecnologia empregada nos mais diversos ramos do conhecimento. Imagine essas máquinas desenvolvendo novos softwares, dirigindo carros,  controlando tráfego em grandes cidades, estudando e propondo novas drogas para combater doenças, controlando estações espaciais etc. Apenas aprendendo por si só. Definitivamente podemos afirmar que vivemos em uma nova era. Uma era onde os computadores superaram eles mesmos!

[1] Crédito da imagem: Karl Gottlieb von Windisch (Public domain) / Wikimedia Commons. https://commons.wikimedia.org/wiki/File%3ATuerkischer_schachspieler_windisch4.jpg.

[2] CE Shannon. XXII Programming a Computer for Playing Chess. Philosophical Magazine 41, 256 (1950).

[3] EA Poe. Maelzel’s Chess Player. Southern Literary Messenger 2, 318 (1836). O artigo pode ser encontrado na página: https://www.eapoe.org/works/essays/maelzel.htm.

[4] M Campbell et al. Deep Blue. https://web.archive.org/web/20050520043104/http://sjeng.org/ftp/deepblue.pdf (2001).

[5] Crédito da imagem: Jim Gardner (Flickr) / Creative Commons (CC BY 2.0). https://www.flickr.com/photos/22453761@N00/592436598/.

[6] Mais informações sobre o algoritmo de busca AlphaBeta: Wikipedia.  Alpha–beta pruning. https://en.wikipedia.org/wiki/Alpha–beta_pruning. Acesso: 02 de janeiro (2018).

[7] Mais informações: DeepMind. https://deepmind.com/. A DeepMind já sacudiu o mundo dos jogos de tabuleiro quando lançou o AlphaGo, máquina de jogar Go, primeira máquina capaz de derrotar o campeão europeu de Go. Os principais avanços obtidos pela DeepMind no uso de redes neurais para construir máquinas de jogos de tabuleiro foram publicados em uma série de artigos na conceituada Nature: D Silver et al. Mastering the game of Go with deep neural networks and tree search. Nature 529, 484 (2016); Mastering the game of Go without human knowledge. Nature 550, 354 (2017).

[8] D Silver et al. Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. arXiv:1712.01815. https://arxiv.org/abs/1712.01815. Publicado em  5 de dezembro (2017).

[9] Uma tradução livre do conceito de machine learning (aprendizagem por máquinas ) “Reinforcement Learning by Self-Play”.

[10] H Macedo. Go machine, go! Saense. http://www.saense.com.br/2017/11/go-machine-go/. Publicado em 03 de novembro (2017).

[11] Wikipédia. Método de Monte Carlo. https://pt.wikipedia.org/wiki/M%C3%A9todo_de_Monte_Carlo. Acesso: 02 de janeiro (2018).

[12] A siga TPU vem do termo em inglês “Tensor processing unit” e é o circuito integrado desenvolvido pela Google especificamente para aplicação em redes neurais.  

Como citar este artigo: Gerson Cortês. Enfim chegamos a era onde os computadores jogam xadrez melhor que eles mesmos! Saense. http://www.saense.com.br/2018/01/enfim-chegamos-a-era-onde-os-computadores-jogam-xadrez-melhor-que-eles-mesmos/. Publicado em 03 de janeiro (2018).

Artigos de Gerson Cortês     Home