Pong - Gabarito.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 🎮 Workshop de Introdução ao Aprendizado por Reforço\n",
    "⠀\n",
    "\n",
    "Bem vindes ao **Workshop de Introdução ao Aprendizado por Reforço**, organizado pelo Grupo Turing! \n",
    "\n",
    "O objetivo deste evento é ensinar o básico necessário da área de Aprendizado por Reforço utilizando um dos maiores clássicos da história dos video-games: ***Pong***.\n",
    "\n",
    "![Pong](https://media2.giphy.com/media/aTGwuEFyg6d8c/giphy.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instala os ambientes do Grupo Turing\n",
    "!pip install -U turing-envs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🏓 Sobre o Pong\n",
    "\n",
    "Começaremos falando sobre o problema, ou seja, sobre o jogo Pong. Este que foi o primeiro jogo de video-game lucrativo da história, publicado em 1972, constando 48 anos de legado.\n",
    "\n",
    "Pong simula uma partida de tênis, existem duas \"raquetes\" e uma bola, e o objetivo de cada uma das raquetes é não somente evitar que a bola passe por ela, como também fazer com que esta passe pela linha que a outra raquete protege, criando assim a premissa que sustenta o interesse pelo jogo. Queremos então desenvolver um algoritmo capaz de &mdash; sem nenhuma explicação adicional &mdash; maximizar as suas recompensas, sendo as ações, os estados e as recompensas, todas relativas ao jogo Pong. Teremos no final, portanto, um modelo treinado capaz de bom desempenho dentro do ambiente. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 💻 Programando..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Importando o Gym\n",
    "\n",
    "O **[Gym](https://gym.openai.com/)** é uma biblioteca desenvolvida pela OpenAI que contém várias implementações prontas de ambientes de Aprendizagem por Reforço. Ela é muito utilizada quando se quer testar um algoritmo de agente sem ter o trabalho de programar seu próprio ambiente.\n",
    "\n",
    "<img src=\"https://user-images.githubusercontent.com/10624937/42135602-b0335606-7d12-11e8-8689-dd1cf9fa11a9.gif\" alt=\"Exemplos de Ambientes do Gym\" class=\"inline\"/>\n",
    "<figcaption>Exemplo de Ambientes do Gym</figcaption>\n",
    "<br>\n",
    "\n",
    "Para se ter acesso a esses ambientes, basta importar o Gym da seguinte forma:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gym"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### O que é um Ambiente?\n",
    "\n",
    "Um **Ambiente** de Aprendizagem por Reforço é um espaço que representa o nosso problema, é o objeto com o qual o nosso agente deve interagir para cumprir sua função. Isso significa que o agente toma **ações** nesse ambiente, e recebe **recompensas** dele com base na qualidade de sua tomada de decisões.\n",
    "\n",
    "Todos os ambientes são dotados de um **espaço de observações**, que é a forma pela qual o agente recebe informações e deve se basear para a tomada de decisões, e um **espaço de ações**, que especifica as ações possíveis do agente. No xadrez, por exemplo, o espaço de observações seria o conjunto de todas as configurações diferentes do tabuleiro, e o espaço de ações seria o conjunto de todos os movimentos permitidos.\n",
    "\n",
    "<img src=\"https://www.raspberrypi.org/wp-content/uploads/2016/08/giphy-1-1.gif\" alt=\"Uma Ação do Xadrez\" class=\"inline\"/>\n",
    "\n",
    "### Como Funciona um Ambiente do Gym?\n",
    "\n",
    "Agora que você já sabe o que é um ambiente, é preciso entender como nosso agente interage efetivamente com ele. Todos os ambientes do Gym possuem alguns métodos simples para facilitar a comunicação com eles:\n",
    "\n",
    "<br>\n",
    "\n",
    "| Método         | Funcionalidade                                        |\n",
    "| :------------- |:----------------------------------------------------- |\n",
    "| `reset()`      | Inicializa o ambiente e recebe a observação inicial   |\n",
    "| `step(acao)`   | Executa uma ação e recebe a observação e a recompensa |\n",
    "| `render()`     | Renderiza o ambiente                                  |\n",
    "| `close()`      | Fecha o ambiente                                      |\n",
    "\n",
    "<br>\n",
    "\n",
    "Assim, o código para interagir com o ambiente costuma seguir o seguinte modelo:\n",
    "\n",
    "---\n",
    "\n",
    "```python\n",
    "env = gym.make(\"Nome do Ambiente\")                   # Cria o ambiente\n",
    "estado = env.reset()                                 # Inicializa o ambiente\n",
    "done = False                                         # Variável que diz se acabou\n",
    "\n",
    "while not done:\n",
    "    env.render()                                     # Renderiza o ambiente\n",
    "    acao = random()                                  # Define alguma ação\n",
    "    estado, recompensa, done, info = env.step(acao)  # Executa uma ação\n",
    "    \n",
    "env.close()                                          # Fecha o ambiente\n",
    "```\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Criando um Ambiente\n",
    "\n",
    "Para utilizar um dos ambientes do Gym, nós usamos a função ```gym.make()```, passando o nome do ambiente desejado como parâmetro e guardando o valor retornado em uma variável que chamaramos de ```env```. A lista com todos os ambientes do gym pode ser encontrada [aqui](https://gym.openai.com/envs/#classic_control). Nesse workshop, utilizaremos um ambiente de pong do Grupo Turing, que requer a instalação do [Turing Envs](https://github.com/GrupoTuring/turing-envs)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = gym.make(\"turing_envs:pong-easy-v0\")\n",
    "env.seed(0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nesse caso, nós vamos utilizar o ambiente ```turing_envs:pong-easy-v0```, um ambiente que reproduz o jogo _Pong_.\n",
    "\n",
    "<img src=\"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAYkAAAEkCAIAAABVPVraAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAEDklEQVR4Xu3csWkDQBBFwZNRCXf9F3hNOFKyYHBg5CeYCX8Bj432sfdeADFfcwAI0CagSJuAIm0CirQJKNImoEibgCJtAoq0CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoEibgCJtAoq0CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoEibgCJtAoqec3i5985prbXWOWdOAH/N3QQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRc85EHDvndOvnXPmBB/I3QQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJF/4UV+foO7CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoEibgCJtAoq0CSjyhwB4k3vvnNZaPzzecDcBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1A0XMOL+ecOQG8i7sJKNImoEibgCJtAoq0CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoEibgCJtAoq0CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoEibgCJtAoq0CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoEibgCJtAoq0CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoEibgCJtAoq0CSjSJqBIm4AibQKKtAko0iagSJuAIm0CirQJKNImoOix954bwH9zNwFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1CkTUCRNgFF2gQUaRNQpE1AkTYBRdoEFGkTUKRNQJE2AUXaBBRpE1D0DYCTDEdrWdtnAAAAAElFTkSuQmCC\" width=\"400px\" alt=\"Ambiente do turing_envs:pong-easy-v0\" class=\"inline\"/>\n",
    "\n",
    "#### Características do Pong\n",
    "\n",
    "Antes de treinar qualquer agente, primeiro é preciso entender melhor quais as características do nosso ambiente.\n",
    "\n",
    "O **Espaço de Observação** do pong (modo fácil) é definido por 2 informações:\n",
    "\n",
    "| Estado    | Informação                            |\n",
    "| :-------- | :------------------------------------ |\n",
    "| 0         | Distância _x_ entre a bola e o agente |\n",
    "| 1         | Distância _y_ entre a bola e o agente |\n",
    "\n",
    "Dessa forma, a cada instante recebemos uma lista da observação com o seguinte formato:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(env.observation_space.sample())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Já o **Espaço de Ação** é composto por três ações: mover o jogador para cima, baixo, ou deixá-lo parado:\n",
    "\n",
    "| Ação | Significado      |\n",
    "| :--- | :--------------- |\n",
    "| 0    | Ficar parado     |\n",
    "| 1    | Mover para baixo |\n",
    "| 2    | Mover para cima  |\n",
    "\n",
    "Por exemplo, para mover a barra para a cima, fazemos `env.step(2)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(env.action_space.sample())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por fim, cada vez que tomamos uma ação, recebemos do ambiente uma **recompensa**, conforme a tabela abaixo:\n",
    "\n",
    "| Ocorrência          | Recompensa |\n",
    "| :------------------ | ---------: |\n",
    "| Ponto do Agente     | $+500$     |\n",
    "| Ponto do Oponente   | $-500$     |\n",
    "| Vitória do Agente   | $+2000$    |\n",
    "| Vitória do Oponente | $-2000$    |\n",
    "\n",
    "O primeiro jogador a fazer quatro pontos ganha o jogo. Além disso, as recompensas são cumulativas. Isso significa que se o oponente fizer um ponto _e_ ganhar o jogo, a recompensa é de $-2500$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✍ Exercício de Gym\n",
    "\n",
    "Agora que você já entende como o Gym funciona, vamos tentar aplicar esse conhecimento criando uma função que roda um episódio de Pong tomando ações aleatórias!\n",
    "\n",
    "OBS: Lembrete das funções do Gym\n",
    "\n",
    "| Método                 | Funcionalidade                                          |\n",
    "| :--------------------- |:------------------------------------------------------- |\n",
    "| `reset()`              | Inicializa o ambiente e recebe a observação inicial     |\n",
    "| `step(acao)`           | Executa uma ação e recebe a observação e a recompensa   |\n",
    "| `render()`             | Renderiza o ambiente                                    |\n",
    "| `close()`              | Fecha o ambiente                                        |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Essa função deve rodar um episodio de Pong escolhendo ações aleatórias\n",
    "def rodar_ambiente():\n",
    "    # Criando o ambiente 'turing_envs:pong-easy-v0'\n",
    "    env = gym.make(\"turing_envs:pong-easy-v0\")\n",
    "\n",
    "    # Resete o ambiente e receba o primeiro estado\n",
    "    estado = env.reset()\n",
    "\n",
    "    # Inicializando done como false\n",
    "    done = False\n",
    "\n",
    "    # Loop de treino\n",
    "    while not done:\n",
    "        # Escolha uma acao aleatoria\n",
    "        acao = env.action_space.sample()\n",
    "\n",
    "        # Tome essa acao e receba as informacoes do estado seguinte\n",
    "        prox_estado, recompensa, done, info = env.step(acao)\n",
    "\n",
    "        # Renderize o ambiente\n",
    "        env.render()\n",
    "\n",
    "        # Atualizando o estado\n",
    "        estado = prox_estado\n",
    "\n",
    "    # Fechando o ambiente\n",
    "    env.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testando a função\n",
    "rodar_ambiente()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 👩‍💻 Algoritmo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Primeiramente, precisaremos utilizar uma biblioteca chamada ***NumPy*** para auxiliar nas computações. Esta é uma biblioteca do Python capaz de manusear diversas computações matemáticas com maestria e será importante futuramente para o nosso trabalho."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np # Importando a biblioteca NumPy\n",
    "import gym         # Importando a Biblioteca Gym\n",
    "\n",
    "# Criando o nosso Ambiente: Pong\n",
    "env = gym.make(\"turing_envs:pong-easy-v0\")\n",
    "\n",
    "# Número total de ações: 3\n",
    "# 0 = parado; 1 = baixo; 2 = cima\n",
    "n_acoes = env.action_space.n\n",
    "\n",
    "print('Número de ações:', n_acoes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔢 Discretizando o nosso Estado\n",
    "\n",
    "Como comentamos anteriormente, o estado que o nosso agente recebe consiste das distâncias horizontal e vertical da raquete controlada até a bola. Dessa forma, se a nossa tela possuir 800 unidades de largura e 600 unidades de altura, a quantidade total de diferentes estados possíveis seria aproximadamente $3 \\times 800 \\times 600 = 960000$.\n",
    "\n",
    "Como Q-Learning é um algoritmo que guarda em uma tabela as estimativas do Q de cada ação para cada estado, esse gigantesco número de estados exigiria não somente guardar como atualizar cada um desses Q. Não é uma situação ideal.\n",
    "\n",
    "Para simplificar (e agilizar) a situação, \"discretizar\" os nossos estados é razoável e esperado. Faremos com que estados similares o suficiente sejam considerados como iguais e comparilhem das mesmas estimativas, já que não faz sentido distinguir o estado (502,234) do estado (515,222)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def discretiza_estado(estado):\n",
    "    return tuple(round(x/10) for x in estado)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 🔀 Escolhendo Ações\n",
    "\n",
    "Para o processo de de escolha de ação, é necessário lembrar do dilema entre **Exploração** e **Explotação**. Nosso modelo precisa estabelecer um equilíbrio entre **explorar o ambiente**, escolhendo ações que ele não costuma tomar para encontrar alguma solução que ele não havia pensado antes, e **aproveitar** o conhecimento que já possui, tomando ações que ele acredita serem as melhores para maximizar as recompensas que receberá no episódio.\n",
    "\n",
    "De forma a assegurar que o agente busque tanto novas alternativas que podem gerar melhores resultados quanto seja capaz de utilizar o aprendizado obtido de forma a maximizar seu retorno, existem diversas estratégias para a escolha de exploração e explotação. Uma das mais utilizadas, que também vamos utilizar aqui, é a seleção de ações pela estratégia do **\"$\\epsilon$-greedy\"**.\n",
    "\n",
    "#### A Estratégia **$\\epsilon$-greedy**\n",
    "\n",
    "O algoritmo \"$\\epsilon$-greedy\" é definido da seguinte forma: é retirado um número aleatório, no intervalo entre 0 e 1. caso este número tenha valor inferior ao valor do epsilon, a escolha será de uma ação aleatória, o que configura exploração. Caso este número seja superior ao epsilon, a ação a ser tomada é a que gera a maior recompensa de acordo com os valores da tabela Q.\n",
    "\n",
    "Este valor de $\\epsilon$ não é constante ao longo do treinamento. Inicialmente, este valor é alto, incentivando a maior exploração do ambiente. A medida que o treinamento ocorre, mais informação sobre o ambiente é adquirida, conseguindo uma tabela Q mais representativa da realidade. Dessa forma, quanto mais avançado no treinamento, menor a necessidade de exploração e maior a necessidade de exploitar o conhecimento adquirido para maximizar a recompensa. Esta atualização do $\\epsilon$ é chamada **\"$\\epsilon$-decay\"** (decaimento do epsilon). Também é estabelecido um valor mínimo para o $\\epsilon$, para que o agente nunca pare completamente de explorar o ambiente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Constantes da Política Epsilon Greedy\n",
    "# Epsilon: probabilidade de experimentar uma ação aleatória\n",
    "EPSILON = 0.7        # Valor inicial do epsilon\n",
    "EPSILON_MIN = 0.01   # Valor mínimo de epsilon\n",
    "DECAIMENTO = 0.98    # Fator de decaímento do epsilon (por episódio)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def escolhe_acao(env, Q, estado, epsilon):\n",
    "    # Se não conhecermos ainda o estado, inicializamos o Q de cada ação como 0\n",
    "    if estado not in Q.keys(): Q[estado] = [0] * n_acoes\n",
    "\n",
    "    # Escolhemos um número aleatório com \"np.random.random()\"\n",
    "    # Se esse número for menor que epsilon, tomamos uma ação aleatória\n",
    "    if np.random.random() < epsilon:\n",
    "        # Escolhemos uma ação aleatória, com env.action_space.sample()\n",
    "        acao = env.action_space.sample()\n",
    "    else:\n",
    "        # Escolhemos a melhor ação para o estado atual, com np.argmax()\n",
    "        acao = np.argmax(Q[estado])\n",
    "    return acao"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para rodar uma partida, são necessárias algumas etapas. Inicialmente, o ambiente é reiniciado, de forma a inicar um novo episódio. Em seguida, é necessário discretizar o estado, pelos motivos já explicados acima. Esta discretização deve ocorrer toda vez em que estamos em um novo estado.\n",
    "\n",
    "Enquanto o ambiente não chega em seu estado terminal, indicado pela variável \"done\", será feito o processo de escolha de ações e, uma vez escolhida, deve-se receber do ambiente o próximo estado, a recompensa que a ação escolhida gerou, além do sinal se estamos no estado terminal. Todo o processo é repetido novamente para o próximo estado, até o final do episódio.\n",
    "\n",
    "Como explicado na seção sobre a biblioteca \"Gym\", \"env.render()\" tem como papel mostrar o ambiente (neste caso, a partida de Pong)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def roda_partida(env, Q, renderiza=True):\n",
    "    # Resetamos o ambiente\n",
    "    estado = env.reset()\n",
    "\n",
    "    # Discretizamos o estado\n",
    "    estado = discretiza_estado(estado)\n",
    "    \n",
    "    done = False\n",
    "    retorno = 0\n",
    "    \n",
    "    while not done:\n",
    "        # Escolhemos uma ação\n",
    "        acao = escolhe_acao(env, Q, estado, epsilon=0)\n",
    "\n",
    "        # Tomamos nossa ação escolhida e recebemos informações do próximo estado\n",
    "        prox_estado, recompensa, done, info = env.step(acao)\n",
    "\n",
    "        # Discretizamos o próximo estado\n",
    "        prox_estado = discretiza_estado(prox_estado)\n",
    "\n",
    "        # Renderizamos o ambiente\n",
    "        if renderiza:\n",
    "            env.render()\n",
    "\n",
    "        retorno += recompensa\n",
    "        estado = prox_estado\n",
    "\n",
    "    print(f'retorno {retorno:.1f},  '\n",
    "          f'placar {env.score[0]}x{env.score[1]}')\n",
    "    \n",
    "    env.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "# Rodamos uma partida de Pong\n",
    "Q = {}\n",
    "roda_partida(env, Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🏋️‍♀️ Treinamento\n",
    "\n",
    "Agora sim chegaremos no treinamento propriamente dito. Usando os conceitos vistos na apresentação e nas seções anteriores do notebook, podemos definir a função de treinamento que vai permitir que o agente aprenda a jogar PONG por meio de Q-Learning tabular."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "O algoritmo se baseia na atualização de estimativas dos valores Q para cada par estado-ação, de forma a chegar a uma tabela cada vez mais próxima da realidade do ambiente. Dessa forma, devemos atualizar cada entrada da tabela de acordo com a **equação do Q-Learning**:\n",
    "\n",
    "$$Q*(s,a) \\leftarrow Q*(s,a) + \\alpha \\cdot \\left[r + \\gamma \\cdot \\max_{a'} (Q(s',a')) - Q(s, a)\\right]$$\n",
    "\n",
    "Esta equação corrige o valor do Q(s,a) de acordo com os valores anteriores somados a uma parecela de correção, de forma a minimizar o erro. A recompensa é representada por r, enquanto os outros parâmetros estão explicados a seguir:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `ALFA` ($\\alpha$): algoritmos de aprendizado de máquina costumam precisar de uma forma de serem otimizados. Q-learning trabalha em cima de gradientes, uma entidade matemática que indica a direção para maximizar (ou minimizar) uma função. Dispondo dessa direção, precisamos informar qual deve ser o tamanho do passo a ser dado antes de atualizar a nova \"direção ideal\".\n",
    "\n",
    "* `GAMA` ($\\gamma$): denota o quanto desejamos que nosso algoritmo considere eventos futuros. Se \"$\\gamma = 1$\", nosso algoritmo avaliará que a situação futura ser melhor que a atual é tão importante quanto a recompensa da situação atual em si, por outro lado, se \"$\\gamma = 0$\", os eventos futuros não apresentam importância alguma para nosso algoritmo. \n",
    "\n",
    "* `Q` é um dicionário, ou seja, uma estrtura de dados capaz de buscar elementos de forma rápida. Nós o usaremos para guardar valores relativos às estimativas do algoritmo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Hiperparâmetros do Q-Learning\n",
    "ALFA = 0.05          # Learning rate\n",
    "GAMA = 0.9           # Fator de desconto\n",
    "\n",
    "# Dicionário dos valores de Q\n",
    "# Chaves: estados; valores: qualidade Q atribuida a cada ação\n",
    "Q = {}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def atualiza_q(Q, estado, acao, recompensa, prox_estado):\n",
    "    # para cada estado ainda não descoberto, iniciamos seu valor como nulo\n",
    "    if estado not in Q.keys(): Q[estado] = [0] * n_acoes\n",
    "    if prox_estado not in Q.keys(): Q[prox_estado] = [0] * n_acoes\n",
    "\n",
    "    # equação do Q-Learning\n",
    "    Q[estado][acao] = Q[estado][acao] + ALFA*(recompensa + GAMA*np.max(Q[prox_estado]) - Q[estado][acao])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pickle é uma maneira de salvar dados em um arquivo independente. Dessa forma, podemos gravar os valores da nossa tabela Q em um arquivo próprio, ficando disponível para ser acessada em outro momento. Assim, podemos efetivamente salvar o modelo treinado para ser utilizado posteriormente. Abaixo, já estão presentes as funções de salvar e de abrir as tabelas com pickle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "\n",
    "def salva_tabela(Q, nome = 'model.pickle'):\n",
    "    with open(nome, 'wb') as pickle_out:\n",
    "        pickle.dump(Q, pickle_out)\n",
    "\n",
    "def carrega_tabela(nome = 'model.pickle'):\n",
    "    with open(nome, 'rb') as pickle_out:\n",
    "        return pickle.load(pickle_out)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A função de treinamento tem estrutura semelhante à função roda_partida, conforme visto anteriormente. A cada episódio, o embiente deve ser reiniciado e discretizado, e deve indicar que o episódio ainda não chegou em sua condição terminal. Devemos também zerar o valor da recompensa, pois não devemos utilizar o retorno do episódio anterior.\n",
    "\n",
    "Enquanto o episódio não chega no final, o agente deve escolher uma ação e tomar a ação escolhida. Uma vez tomada a ação, o ambiente fornece o próximo estado, a recompensa recebida com a escolha, a indicação se o estado é terminal e informações sobre o ambiente.\n",
    "\n",
    "Em seguida, devemos discretizar o próximo estado e atualizar os valores de q, o retorno e o estado atual.\n",
    "\n",
    "Por fim, devemos atualizar o valor do epsilon, de acordo com o método $\\epsilon$-greedy, onde deve ocorrer o decaimento do epsilon, mas seu valor nunca deve ser inferior ao valor mínimo definido.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `N_EPISODIOS` dita quantas vezes o agente deverá \"reviver\" o ambiente (vitórias e derrotas) antes de acabar seu treinamento."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N_EPISODIOS = 250    # quantidade de episódios que treinaremos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def treina(env, Q):\n",
    "    retornos = []      # retorno de cada episódio\n",
    "    epsilon = EPSILON\n",
    "\n",
    "    for episodio in range(1, N_EPISODIOS+1):\n",
    "        # resetar o ambiente\n",
    "        estado = env.reset()\n",
    "        \n",
    "        # discretizar o estado inicial\n",
    "        estado = discretiza_estado(estado)\n",
    "        \n",
    "        done = False\n",
    "        retorno = 0\n",
    "        \n",
    "        while not done:\n",
    "            # politica\n",
    "            acao = escolhe_acao(env, Q, estado, epsilon)\n",
    "\n",
    "            # A ação é tomada e os valores novos são coletados\n",
    "            # O novo estado é salvo numa nova variavel\n",
    "            prox_estado, recompensa, done, info = env.step(acao)\n",
    "            prox_estado = discretiza_estado(prox_estado)\n",
    "\n",
    "            atualiza_q(Q, estado, acao, recompensa, prox_estado)\n",
    "\n",
    "            retorno += recompensa\n",
    "            estado = prox_estado\n",
    "\n",
    "        epsilon = max(DECAIMENTO*epsilon, EPSILON_MIN)\n",
    "        retornos.append(retorno)\n",
    "\n",
    "        if episodio % 10 == 0:\n",
    "            salva_tabela(Q)\n",
    "\n",
    "        print(f'episódio {episodio},  '\n",
    "              f'retorno {retorno:7.1f},  '\n",
    "              f'retorno médio (últimos 10 episódios) {np.mean(retornos[-10:]):7.1f},  '\n",
    "              f'placar {env.score[0]}x{env.score[1]},  '\n",
    "              f'epsilon: {epsilon:.3f}')\n",
    "        \n",
    "    env.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "treina(env, Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 🏓 Testando nosso Agente Treinado"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "roda_partida(env, Q)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}