Como É Que o AlphaZero Joga Xadrez?
Por esta altura já ouviste falar do novo miúdo entre os computadores de xadrez, AlphaZero, e a sua esmagadora vitória no confronto vs Stockfish, o programa livre de xadrez mais forte.
As reacções da comunidade xadrezista a este confronto variaram de admiração a completa incredulidade.
Mas como é que AlphaZero realmente funciona?
Como é que este difere de outros programas e porque é tão superior? Neste artigo de duas-partes eu vou tentar explicar um pouco do que se passa no interior de AlphaZero.
Primeiro, vamos reflectir no que aconteceu. O AlphaZero foi desenvolvido por DeepMind (uma companhia que pertence à Google) para se especializar em aprender como jogar jogos de dois-jogadores, e de lances alternados. Neste programa foram introduzidas as regras de xadrez, e mais nada.
Este começou então a aprender xadrez ao jogar partidas contra si mesmo. Partida um teria consistido totalmente de lances aleatórios. No fim desta partida, AlphaZero tinha aprendido que o lado perdedor tinha feito coisas que não tinham sido nada espertas, e de que o lado vencedor tinha jogado melhor. AlphaZero tinha ensinado a si mesmo a sua primeira lição. A qualidade do xadrez na partida dois foi ligeiramente melhor do que na primeira.
Nove horas e 44 milhões mais tarde de partidas de xadrez de dupla personalidade, o AlphaZero tinha (muito possivelmente) ensinado a si mesmo o suficiente para se tornar o maior jogador de xadrez, de sílica ou baseado em carbono (humano), de todos os tempos.
Como é possível que este o tenha feito?
A sede da Google em Londres vista do interior, com a secção do DeepMind no oitavo andar. | Foto: Maria Emelianova/Chess.com.
Este não calculou um número maior de variantes do que o Stockfish.
Bastante o oposto de facto: o Stockfish examinou 70 milhões de posições por segundo enquanto o AlphaZero se contentou com cerca de 99,89 porcento menos posições: 80.000 por segundo. Isto faz-nos pensar num comentário feito por Jonathan Rowson depois de Michael Adams o ter esmagado num confronto em 1998: "Eu fiquei admirado com a pequena quantidade de coisas para que ele olhou."
Jogadores fortes têm tendência a calcular menos variantes do que os mais fracos. Em vez disso a sua intuição altamente apurada guia-os a focar os seus cálculos nas linhas mais relevantes. Isso é exatamente o que AlphaZero fez. Ensinou-se a si mesmo a jogar xadrez duma forma bastante humana, desenvolvendo uma "intuição' como nenhuma outra máquina de jogar xadrez alguma vez tinha feito, e combinou isto com uma quantidade de cálculo frio.
Vejamos como é que este fez isso.
O IM Danny Rensch explica o confronto do AlphaZero numa série de vídeos no Twitch.
A Árvore de Análise
Programas de xadrez utilizam uma estrutura em forma de árvore para calcular variantes, e usam uma função de avaliação para atribuir à posição no fim da variante um valor como +1.5 (a vantagem das Brancas vale um peão e meio) ou -9.0 (a vantagem das Pretas vale uma dama). A abordagem do AlphaZero tanto para calcular variantes como para avaliar posições é radicalmente diferente daquela que outros programas fazem.
Todos os programas populares de xadrez são baseados no algoritmo minimax, um nome elegante que significa apenas que tu escolhes o lance que te dá a maior vantagem independentemente do que o teu oponente joga. Minimax é invariavelmente melhorada com uma selecção alpha-beta, que é usada para reduzir o tamanho da árvore de variantes a ser examinada. Aqui está um exemplo extremo de como esta selecção funciona: Digamos que um programa está a considerar um lance e vê que o seu oponente tem 20 respostas possíveis. Uma dessas respostas conduz a um xeque-mate forçado. Então o programa pode abandonar (ou "cortar") o lance que estava a considerar, independentemente de como este se desempenhar depois de qualquer outra das 19 respostas.
Outra questão é de que se um programa corta lances que somente parecem ser maus, e.g. aqueles que perdem material, pode falhar de considerar qualquer tipo de sacrifício, que é em parte a razão porque os primeiros programas eram tão materialistas. Nos programas correntes como Stockfish, a selecção alpha-beta é combinada com uma variedade de outros melhoramentos que são específicos para o xadrez tais como a heurística de lance-mortífero (um lance forte noutra variante semelhante é provável que seja aqui também forte), heurística de contra-lance (alguns lances têm respostas naturais independentemente da posição — eu aposto que tu respondeste frequentemente axb5 com axb5, certo?) e muitos outros.
O AlphaZero, em contraste, usa uma Pesquisa de Árvore Monte Carlo (Monte Carlo Tree Search), ou MCTS abreviada. Monte Carlo é famoso pelos seus casinos, portanto quando tu vês este termo num contexto de computação este significa que algo aleatório está a ter lugar. Um programa que utiliza um MCTS puro avaliaria uma posição gerando um número de sequências de lances (chamadas "playouts") aleatoriamente a partir daquela posição, e fazendo uma média das pontuações finais (vitória/empate/derrota) que estas produzem. Esta abordagem pode parecer completamente simplista, mas se pensares sobre o assunto tu irás perceber que de facto esta é uma forma bastante plausível de avaliar uma posição.
O Casino de Monte Carlo.
O AlphaZero cria 800 'playouts' em cada lance. Este expande também o MCTS puro ao preferir lances que ainda não tentou (muito), que parecem prováveis e que parecem conduzir a "boas" posições, onde "boas" quer dizer que a função de avaliação (mais sobre isto no próximo artigo) lhes dá um valor alto. Está na realidade a criar 'playouts' semi-aleatórios, linhas que parecem apropriadas à sua função de avaliação em constante aperfeiçoamento. Não é esta bastante a forma como tu calculas? Num foco nas linhas de jogo razoáveis?
Repara que até agora não há absolutamente nada que seja específico ao xadrez naquilo que o AlphaZero faz. No meu próximo artigo, quando nós olhamos para como o AlphaZero aprende a avaliar posições de xadrez, nós veremos que ali não existe também absolutamente nada que seja específico ao xadrez!
Como um bebe recém-nascido, o AlphaZero veio ao mundo com pouco conhecimentos, mas está massivamente orientado para aprender. Uma fraqueza do MCTS é de que uma vez que é baseado na criação de 'playouts' semi-aleatórios, este pode errar completamente em posições tensas onde existe exatamente uma linha de jogo ideal. Se não seleciona aleatoriamente esta linha, é provável que cometa uma asneira. Esta cegueira foi provavelmente o que causou ao predecessor de jogar Go do AlphaZero, AlphaGo, de perder uma partida para o 18-vezes campeão do mundo de Go Lee Sedol. No entanto, isso não parece ter sido um problema no confronto com Stockfish.
MCTS tinha sido previamente utilizado para jogo de dois-jogadores, mas tinha-se descoberto que tinha um desempenho muito pior do que a abordagem bem estabelecida do minimax combinado com alpha-beta. No AlphaZero, o MCTS é bem combinado com a empregada função de avaliação de rede-neural.
No meu próximo artigo, eu explicarei mais sobre esta rede neural e especialmente sobre a forma fascinante como este aprende, por si mesmo, a como avaliar posições de xadrez. Eu irei também descrever o 'hardware' que o AlphaZero utiliza, e fazer algumas previsões sobre o impacto que tudo isto irá ter no xadrez como nós o conhecemos.
O que pensas sobre como o AlphaZero joga xadrez? Diz-nos nos comentários.
Gostarias de receber mais conteúdo de xadrez em Português? Segue estes canais!
 |
/chesscom.pt |  |
/chesscom_pt |  |
/chesscomPT |  |
/chesscom_xadrez |
