Inteligência Artificial para Jogo da Velha

O uso de aprendizado por reforço para programar a inteligência artificial de jogos tem como destaque a criação nos anos 90 de um programa de conseguia jogar gamão a um nível profissional, por Gary Tesauro da IBM. A primeira tentativa foi construir um modelo dos diversos estados do jogo a partir de alguns exemplos e generalizar com aprendizado supervisionado. Além de ter sido um trabalho tedioso enumerar centenas de estados para depois poder generalizar, a performance do programa não foi satisfatória.

A segunda abordagem foi utilizar aprendizado por reforço e fazer duas versões do programa jogarem entre si. Ao final de cada partida, atribuía-se uma pontuação positiva para o vencedor e uma negativa para o perdedor. Após 200.000 jogos, o programa conseguia jogar como os melhores jogadores do mundo, sem precisar da experiência de jogadores profissionais ou descrever todos os mais de 1 trilhão de estados possíveis em uma partida.      

Com o objetivo de recriar o experimento para um jogo mais simples, propôs-se o desenvolvimento de um agente inteligente para o Jogo da Velha (tic-tac-toe em inglês), sem precisar escrever um algoritmo com as melhores estratégias ou enumerar todos os possíveis estados.

Analisando algumas partidas de Jogo da Velha, pode-se perceber algumas de suas propriedades:

• Um jogador pode vencer, perder ou empatar;
• Jogos entre dois jogadores que conhecem as melhores jogadas sempre  terminam empatados;
• Muitos dos estados são equivalentes - ao se girar o tabuleiro em 90o ou espelhá-lo, obtêm-se até oito estados equivalentes.

Sabendo da equivalência entre estados, pode-se facilitar sua classificação e reduzir o número de jogos necessários para que todos sejam visitados. Sem a equivalência, há nove quadrados que podem ser preenchidos de três modos diferentes (X, O ou vazio), o que, contando inclusive estados impossíveis de serem alcançados em uma partida (todos os espaços preenchidos por X, por exemplo), resultam em 39 = 19.683 possíveis estados. Considerando apenas os válidos e a equivalência entre estados, são necessários apenas 765 para cobrir o jogo todo.

Diante disso, foi feito com que duas versões de agentes para o Jogo da Velha jogassem entre si de maneira aleatória. De acordo com os resultados da partida, os estados alcançados após cada jogada de ambos os jogadores eram pontuados com base no resultado do jogo. Por exemplo, caso o primeiro a jogar começasse marcando o centro e viesse a ganhar, o estado com o tabuleiro preenchido pelo primeiro jogador no centro ganharia uma determinada pontuação. Do mesmo modo, se o segundo jogador marcasse uma das quinas e viesse a perder, o estado com a marcação do primeiro jogador no centro e do segundo em uma quina (quatro estados equivalentes nesse caso) seria penalizado. Era necessário então determinar uma função de pontuação para os estados.

Primeiramente, a pontuação deveria variar de acordo com o resultado da partida. Uma vitória deveria ser mais importante que um empate ou uma derrota e por sua vez um empate deveria ser melhor que uma derrota. 

Também deveriam ser atribuídos pesos diferentes para as primeiras e últimas jogadas, uma vez que a última jogada realizada é a que definiu o vencedor e o perdedor.

Por fim, deveria ser levada em consideração também o número de jogadas necessárias para se vencer a partida. Vencer na terceira rodada deveria ser mais importante do que vencer apenas na quinta.

A pontuação a ser atribuída a cada estado após a partida deveria ser então uma função do resultado (R), de a quantas rodadas para o fim o estado aconteceu (i) e quantas rodadas o jogador teve durante o jogo (d).
Após testar algumas combinações e variações do peso de cada variável, uma função encontrada que apresentou resultados satisfatórios foi:

onde R assume valor 7 para uma vitória, 2 para empate e -2 para derrota, i varia entre 0 e 4 e d varia entre 3 e 5.

Utilizando os resultados de 100.000 jogos na fase de treinamento, o agente agora teria capacidade de determinar qual a melhor jogada a se fazer para buscar a vitória ou no pior dos casos o empate. 
Para testar a eficiência do aprendizado, inicialmente foram realizados testes em partidas contra voluntários, que terminavam ou em empate ou em vitória do agente.

Para confirmar o funcionamento correto do programa, duas versões do mesmo foram novamente postas uma contra a outra, dessa vez com uma jogando aleatoriamente e a outra utilizando os conhecimentos adquiridos. Os resultados foram os esperados: em 50.000 jogos, o agente inteligente venceu cerca de 91% das vezes e empatou 9% delas sem perder nenhuma vez, uma média de dez vitórias a cada onze jogos.

Starting testing TicTacToe with 50000 games
done with 5000 games @ 14.980499 seconds: wins=>4533, ties=>467, losses=>0
done with 10000 games @ 29.581513 seconds: wins=>9081, ties=>919, losses=>0
done with 15000 games @ 45.025361 seconds: wins=>13639, ties=>1361, losses=>0
done with 20000 games @ 59.323242 seconds: wins=>18215, ties=>1785, losses=>0
done with 25000 games @ 73.78854 seconds: wins=>22771, ties=>2229, losses=>0
done with 30000 games @ 88.776816 seconds: wins=>27318, ties=>2682, losses=>0
done with 35000 games @ 109.011402 seconds: wins=>31877, ties=>3123, losses=>0
done with 40000 games @ 126.042564 seconds: wins=>36422, ties=>3578, losses=>0
done with 45000 games @ 141.150789 seconds: wins=>40951, ties=>4049, losses=>0
done with 50000 games @ 156.276316 seconds: wins=>45494, ties=>4506, losses=>0

Starting testing TicTacToe with 50000 games
done with 5000 games @ 17.896717 seconds: wins=>4553, ties=>447, losses=>0
done with 10000 games @ 35.501926 seconds: wins=>9087, ties=>913, losses=>0
done with 15000 games @ 52.823191 seconds: wins=>13648, ties=>1352, losses=>0
done with 20000 games @ 68.256094 seconds: wins=>18178, ties=>1822, losses=>0
done with 25000 games @ 83.470117 seconds: wins=>22733, ties=>2267, losses=>0
done with 30000 games @ 99.914703 seconds: wins=>27258, ties=>2742, losses=>0
done with 35000 games @ 117.766631 seconds: wins=>31788, ties=>3212, losses=>0
done with 40000 games @ 135.225512 seconds: wins=>36350, ties=>3650, losses=>0
done with 45000 games @ 156.867067 seconds: wins=>40899, ties=>4101, losses=>0
done with 50000 games @ 174.201975 seconds: wins=>45441, ties=>4559, losses=>0

Conclusão

Técnicas de aprendizado de máquina apresentam enorme versatilidade, sendo encontradas hoje em dia nas mais diversas áreas do conhecimento. Capazes de generalizar casos complexos ou de encontrar métodos para lidar com situações pouco conhecidas, espera-se que suas aplicações possibilitem promissores avanços não só na computação ou robótica, mas também em áreas como saúde e entretenimento.

Posted in: Tecnologia