TD-Gammon é um programa de computador para o jogo de gamão desenvolvido na década de 1990 por Gerald Tesauro no IBM Thomas J. Watson Research Center. Seu nome deriva do uso de uma rede neural artificial treinada por aprendizado por diferença temporal, especificamente TD-Lambda. Ele explorou estratégias que os humanos não haviam perseguido e levou a avanços na teoria do jogo de gamão correto. Em 1993, o TD-Gammon (versão 2.1) foi treinado com 1,5 milhão de jogos de autojogo e alcançou um nível de jogo ligeiramente abaixo do dos melhores jogadores humanos de gamão da época. Em 1998, durante uma série de 100 jogos, foi derrotado pelo campeão mundial por uma margem de apenas 8 pontos. Sua avaliação não convencional de algumas estratégias de abertura foi aceita e adotada por jogadores especialistas. TD-Gammon é comumente citado como um sucesso inicial do aprendizado por reforço e de redes neurais, e foi referenciado em artigos sobre aprendizado Q profundo e AlphaGo.
Algoritmo para Jogo e Aprendizado
Durante o jogo, o TD-Gammon examina em cada turno todos os movimentos legais possíveis e todas as suas respostas possíveis (busca com olhar à frente), alimenta cada posição resultante do tabuleiro em sua função de avaliação e escolhe o movimento que leva à posição do tabuleiro que obteve a maior pontuação. Nesse aspecto, o TD-Gammon não é diferente de quase qualquer outro programa de jogos de tabuleiro para computador. A inovação do TD-Gammon estava em como ele aprendia sua função de avaliação.
O algoritmo de aprendizado do TD-Gammon consiste em atualizar os pesos em sua rede neural após cada turno para reduzir a diferença entre sua avaliação das posições do tabuleiro de turnos anteriores e sua avaliação da posição do tabuleiro do turno atual - daí "aprendizado por diferença temporal". A pontuação de qualquer posição do tabuleiro é um conjunto de quatro números refletindo a estimativa do programa da probabilidade de cada resultado possível do jogo: Branco vence normalmente, Preto vence normalmente, Branco vence um gamão, Preto vence um gamão. Para a posição final do tabuleiro do jogo, o algoritmo compara com o resultado real do jogo em vez de sua própria avaliação da posição do tabuleiro.
O núcleo do TD-Gammon é uma rede neural com 3 camadas. A camada de entrada tem dois tipos de neurônios. Um tipo codifica a posição do tabuleiro: inteiros não negativos variando de 0 a 15, indicando o número de marcadores Brancos ou Pretos em cada localização do tabuleiro, com 99 neurônios de entrada para cada, totalizando 198 neurônios. Outro tipo codifica características feitas à mão anteriormente usadas no Neurogammon, codificando conceitos padrão usados por especialistas humanos, como "âncora avançada", "força de bloqueio", "força do tabuleiro de casa" e a probabilidade de um "blot" (marcador único) ser atingido. A camada oculta contém neurônios ocultos, com versões posteriores tendo mais. A camada de saída contém 4 neurônios, representando a estimativa da rede da probabilidade ("equidade") de que o tabuleiro atual levaria a: vitória normal de Branco, vitória de gamão de Branco, vitória normal de Preto, vitória de gamão de Preto. A vitória de gamão de Preto é tão rara que Tesauro optou por não representá-la.
Após cada turno, o algoritmo de aprendizado atualiza cada peso de acordo com a regra: w_{t+1} - w_t = alpha (Y_{t+1} - Y_t) sum_{k=1}^{t} lambda^{t-k} grad_w Y_k, onde alpha é a taxa de aprendizado, Y_t é a avaliação no turno t, e lambda é o parâmetro de decaimento. Foi descoberto que escolher um lambda pequeno oferecia desempenho aproximadamente igualmente bom, e um lambda grande degradava o desempenho. Por causa disso, após 1992, o TD-Gammon foi treinado com lambda = 0, degenerando em aprendizado TD padrão, o que economizou computação por um fator de 2.
Histórico de Desenvolvimento
A versão 1.0 usava busca simples de 1-ply: cada próximo movimento é pontuado pela rede neural, e o movimento com maior pontuação é selecionado. As versões 2.0 e 2.1 usavam busca de 2-ply: primeiro uma análise de 1-ply para remover movimentos improváveis ("poda direta"), depois uma análise minimax de 2-ply apenas para os movimentos prováveis, escolhendo o melhor movimento ponderado pela probabilidade de cada um dos 21 lançamentos de dados possíveis do oponente (ponderando não-duplos duas vezes mais que duplos). As versões 3.0 e 3.1 usavam busca de 3-ply, usando 21^2 = 441 lançamentos de dados possíveis em vez de 21. A última versão, 3.1, foi treinada especificamente para uma partida de exibição contra Malcolm Davis no AAAI Hall of Champions de 1998. Ela perdeu em -8 pontos, principalmente devido a um erro grave, onde o TD-Gammon optou por dobrar e sofreu um gamão em -32 pontos.
Experimentos e Estágios de Treinamento
Ao contrário de programas anteriores de gamão com redes neurais, como o Neurogammon (também escrito por Tesauro), onde um especialista treinava o programa fornecendo a avaliação "correta" de cada posição, o TD-Gammon foi inicialmente programado "sem conhecimento". Em experimentos iniciais, usando apenas uma codificação bruta do tabuleiro sem características projetadas por humanos, o TD-Gammon alcançou um nível de jogo comparável ao Neurogammon: o de um jogador humano de gamão de nível intermediário.
Embora o TD-Gammon tenha descoberto características perspicazes por conta própria, Tesauro se perguntou se seu jogo poderia ser melhorado usando características projetadas à mão como as do Neurogammon. De fato, o TD-Gammon autotreinado com características projetadas por especialistas logo superou todos os programas anteriores de gamão para computador. Ele parou de melhorar após cerca de 1.500.000 jogos (autojogo) usando uma rede neural de três camadas, com 198 unidades de entrada codificando características projetadas por especialistas, 80 unidades ocultas e uma unidade de saída representando a probabilidade prevista de vitória.
Avanços na Teoria do Gamão
O treinamento exclusivo do TD-Gammon através de autojogo (em vez de aprendizado por imitação) permitiu que ele explorasse estratégias que os humanos anteriormente não haviam considerado ou haviam descartado erroneamente. Seu sucesso com estratégias não ortodoxas teve um impacto significativo na comunidade do gamão. No final de 1991, Bill Robertie, Paul Magriel e Malcolm Davis foram convidados a jogar contra o TD-Gammon (versão 1.0). Um total de 51 jogos foram jogados, com o TD-Gammon perdendo em -0,25 ppg. Robertie considerou o TD-Gammon no nível de um jogador humano forte, e seus movimentos não convencionais foram posteriormente adotados por especialistas, mudando a compreensão da estratégia de abertura.
Legado e Influência
O TD-Gammon é amplamente reconhecido como um marco no aprendizado de máquina e na inteligência artificial, demonstrando que uma rede neural poderia aprender jogos estratégicos complexos através de autojogo e aprendizado por diferença temporal. Seu sucesso inspirou trabalhos posteriores em aprendizado por reforço, incluindo o desenvolvimento de redes Q profundas e AlphaGo. A capacidade do programa de descobrir estratégias novas que os humanos haviam perdido destacou o potencial das redes neurais para exceder a intuição humana em jogos, e ele permanece um exemplo clássico na história da pesquisa em IA.