Criando uma IA que aprende a jogar Pong
Como usar RL e Q-Learning para criar um excelente jogador
Texto escrito por Pedro Sacramento e Ariel Guerreiro.
Bem vindos a mais uma edição do Turing Talks! Nesse texto veremos como criar um jogador do famoso jogo Pong, usando o versátil algoritmo de RL Q-Learning.
Introdução
No filme Groundhog day (“O feitiço do tempo”, 1993), o egocêntrico jornalista Phil Connors é obrigado a reviver o mesmo dia várias e várias vezes. Quanto mais vezes o personagem de Bill Murray vive o Dia da Marmota, mais ele aproveita os detalhes a seu favor, deixando de ser egoísta e alcançando no final seu objetivo de conquistar Rita.
A maneira em que Phil aprendeu sobre seu ambiente se assemelha a mecanismos de Q-Learning, algoritmo de Reinforcement Learning (RL), onde o agente (Phil) repete o ambiente (Dia da Marmota), testando possibilidades de ações para cada estado e recebendo seu retorno, até encontrar o conjunto de ações que maximiza seu ganho.
Neste texto, será apresentado um algoritmo de Q-learning tabular, aplicado ao clássico jogo Pong.
Se você quiser uma introdução ao Aprendizado por Reforço, recomendamos ler nossa série de textos sobre RL.
O Algoritmo
Antes de partirmos para a aplicação no jogo, uma explicação mais teórica. Q-Learning é um algoritmo de RL off-policy e com temporal difference. Temporal difference se refere à capacidade do algoritmo de aprender durante os episódios e não somente quando eles acabam. Já off-policy indica que a política usada para gerar o comportamento do agente não está relacionada com a política que estima a recompensa (a que será melhorada). Também é um algoritmo model-free, pois não depende da criação do modelo do ambiente que está sendo aplicado.
Q-learning, como Phil Connors, trabalha geralmente dentro de dois loops. O externo é aquele que mantém o agente interagindo com o ambiente repetidas vezes, tal como Phil revive o mesmo dia (chamados em RL de episódios). O interno é aquele que mantém o agente interagindo com o ambiente durante o episódio, assim como Phil vive os acontecimentos da cidade de Punxsutawney que acontecem cada dia. Assim como as experiências de Bill permitem que ele amadureça, nosso modelo aprende e amadurece conforme os episódios passam.
O Q (de Qualidade), mede o quão bom é tomar uma ação em um determinado estado. Como pode se ver pela fórmula acima, é calculado como a recompensa recebida logo após tomar a ação, somada à qualidade da próxima ação a ser tomada multiplicada por um fator de desconto gama.
O aprendizado ocorre graças à Equação de Bellman, já mencionada em outros Turing Talks, mas que pode ser conferida na imagem abaixo:
Nessa equação, existem, além da recompensa e o Q, dois parâmetros que podem ser ajustados para refinar o desempenho do agente: o alpha (
α), learning rate, corresponde a quanto os valores são atualizados para cada iteração, e o gama (γ), discount factor, às vezes chamado informalmente de “fator de miopia”. Quando muito baixo, o agente desconsidera as recompensas futuras e, quando muito alto, considera tanto as recompensas atuais quanto as futuras.
O método funciona buscando estimar um valor Q(s,a) para o valor verdadeiro de cada par ação-estado encontrado pelo agente. Faz-se isso a partir de atualizações sucessivas dos Q-values segundo a equação de Bellman. Na aplicação tabular do algoritmo, abordada nesse texto, utiliza-se a “Q-table”, uma tabela que guarda os Q-values. Inicialmente, as estimativas para os valores de cada estado-ação estão longe de serem corretas, contudo, após diversas iterações, o algoritmo melhora suas estimativas.
Para cada iteração, os Q-values são atualizados, incrementados pela recompensa da ação escolhida nesse estado e por uma parte do quão melhor é avaliada a melhor ação do próximo estado em relação àquela tomada.
Aplicando para o Pong
Agora, podemos aplicar o algoritmo para o jogo em si. O ambiente utilizado não será o Gym, mas sim uma versão construída em cima da biblioteca Pygame. O código para a implementação do jogo e do algoritmo pode ser conferida no link. Porém, a aplicação é baseada no Gym, uma vez criado o ambiente, seu funcionamento é quase igual.
Não será utilizado o Pong do Gym porque a forma que os estados são fornecidos são inviáveis para a aplicação do Q-Learning tabular. Se fosse utilizado o “Pong-ram-v0”, que é idêntico à versão do Atari, o número de estados possíveis tornaria essa aplicação impossível.
Nessa implementação, o nosso agente possui como estado a distância vertical e horizontal da bola. Como ações, existem 3 disponíveis: não fazer nada, ir para cima ou ir para baixo.
No vídeo acima, está o nosso agente (do lado esquerdo) antes de seu treinamento. Nosso agente não sabe como o jogo funciona ou o que deve fazer. O agente se comporta de forma aleatória, rebatendo às vezes a bola por sorte.
A seguir, veremos como será o treinamento do modelo e seu resultado:
Inicialmente, importamos as bibliotecas necessárias. Pickle é uma biblioteca para exportar objetos python, que será utilizada para salvar a q-table. “objects” é o arquivo que contém o ambiente criado.
Iniciamos as variáveis de learning rate, epsilon (e seu valor minimo e decaimento) e o gama. Definimos também o número de episódios e iniciamos um dicionário “Q” e a lista “times”, que grava a duração de casa episódio. Também está presente o código para salvar a q-table no pickle.
Definimos então uma função que é a estratégia epsilon-greedy, onde o agente tem uma chance epsilon de tomar uma ação aleatória. Conforme as estimativas vão sendo otimizadas e vão se passando os episódios, o valor de epsilon decai. Para cada step, o valor decai uma certa quantidade até atingir o valor mínimo.
A função discretize tem como papel reduzir a possibilidade de estados, para facilitar o treinamento. Por exemplo, estados como [280, 163] e [283, 158] são extremamente próximos e, se forem tratados como iguais, reduzem muito o tamanho da q-table. Com a divisão de cada distância por 10, reduzimos em 100 vezes o tamanho da tabela.
Em seguida, definimos uma função de treino, onde os estados ainda não explorados são adicionados a q-table e iniciando seus q-values para as 3 ações possíveis como 0. Também se atualiza os q-values segundo a equação de Bellman.
Acima, vemos que o ambiente é criado. Em cada episódio (um dia na vida de Phil Connors), o ambiente é reiniciado e algumas variáveis são atribuídas. Enquanto o episódio não acabar, uma ação vai ser tomada, serão obtidas a recompensa e o próximo estado, levando à atualização da q-table. Um episódio termina quando o agente toma 5 pontos ou chega ao final de 1000000 de passos (cada interação do “while not done”).
Ao final do treinamento, temos a q-table final. A seguir, podemos ver o comportamento do modelo treinado:
Podemos ver o que o nosso agente (esquerda) aprendeu muito bem como se movimentar, sendo capaz de aprender a rebater a bolinha somente por meio da recompensa negativa ao tomar um ponto e a recompensa positiva de sobreviver por mais tempo. Abaixo, temos um gráfico mostrando a média de recompensa (considerando as 50 anteriores) que o modelo obteve. O modelo só teve um bom desempenho depois de 700 episódios e atingindo a recompensa máxima possível.
Conclusão
Q-Learning é um algoritmo de aprendizado extremamente versátil e eficaz, já que não depende de uma modelagem do ambiente, somente de recompensa, para aprender o que deve ser feito.
Porém, o Q-Learning tabular, utilizado nesse texto, possui uma grande limitação: à medida que as possibilidades de estados possíveis aumentam, o tamanho da tabela que armazena os estados e recompensas cresce exponencialmente. Para problemas mais complexos, essa implementação se torna inviável. Uma alternativa a uma tabela é a utilização de redes neurais para cálculo da recompensa esperada, chamada Deep Q-Learning, que será apresentada em um texto futuro.
Caso queira ver o código utilizado neste texto, veja o repositório no Github. Não deixe de conferir o nossas redes sociais: Facebook, Instagram, LinkedIn, além do próprio Medium.
Até a próxima!
