Um pouco de história e tendências

Origens

• Claude Shannon. Programming a Computer for Playing Chess. Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950. Uma proposta de uso do algoritmo Min Max no jogo de Xadrez.

• Claude Shannon cita neste artigo o livro publicado por John von Neumann e Oskar Morgenstern: Theory of Games and Economic Behavior publicado em 1944.

• John von Neumann cita no seu livro as origens da ideia de Min Max: Waldegrave (1713) Minmax solution of a 2-person, zero-sum game, reported in a letter from P. de Montmort to N. Bernouilli, transl, and with comments by H. W. Kuhin in W. J. Baurnol and Goldfeld (eds.), Precusors of Mathenatical Economics.

Deep Blue versus Garry Kasparov

• O DeepBlue fazia uso do algoritmo MinMax com poda alpha-beta.
• A solução tinha 256 processadores dedicados para a tarefa.
• Examinava em torno de 30 bilhões de movimentos por minuto.
• A profundidade geralmente era de 13. No entanto, em determinadas situações podia chegar até 30.

• Para fazer a poda da árvore ou alongar o caminho de busca, a solução fazia uso de uma base de jogos históricos de Xadrez. Com isto era possível determinar o valor de um estado sem continuar a busca.

• Game over: Kasparov and The Machine, 2003

• Deep Blue - Down the Rabbit Hole: um vídeo um tanto quanto interessante sobre o assunto com vários detalhes que são difíceis de encontrar em outras fontes.

O que mudou de Shannon até o Deep Blue?

• Imagem retirada do artigo When will computer hardware match the human brain? de Hans Moravec de 1997.

O avanço no jogo de xadrez parou depois do Deep Blue?

• Imagem retirada do texto Chess’s New Best Player Is A Fearless, Swashbuckling Algorithm publicado em 2018.

• Elo é um ranking utilizado para medir o desempenho de jogadores em qualquer jogo de soma zero, incluindo o xadrez.

AlphaZero

• Imagem retirada do artigo D. Silver et al., “Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm”, CoRR, vol. abs/1712.01815, 2017, [Online]. Disponível em: http://arxiv.org/abs/1712.01815

• Uma segunda versão do artigo foi publicada em D. Silver et al., “A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play”, Science, vol. 362, nº 6419, p. 1140–1144, 2018.

Impactos

• M. Sadler, N. Regan, e G. Kasparov, Game Changer: AlphaZero’s Groundbreaking Chess Strategies and the Promise of AI. New in Chess, 2019.

• N. Tomasev, U. Paquet, D. Hassabis, e V. Kramnik, “Assessing Game Balance with AlphaZero: Exploring Alternative Rule Sets in Chess”, CoRR, vol. abs/2009.04374, 2020, [Online]. Disponível em: https://arxiv.org/abs/2009.04374

Próximas atividades

Se você quiser, é possível baixar todo o código na sua máquina, configurar o ambiente e executar o jogo e os jogadores na sua máquina local. Se esta for a sua intenção então você pode ir para o arquivo de configuração.

Material adicional

Existe uma variante do algoritmo MinMax chamado MinMax com alpha-beta. A descrição de como esta variante funciona pode ser acessada aqui.