week_8/marl_tictactoe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multi-agent Reinforcement Learning using PettingZoo: Tic-tac-toe example part I\n",
    "\n",
    "*Gertjan Verhoeven*\n",
    "\n",
    "*March 2021*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook, we will take our first steps into the exciting world of **multi-agent reinforcement learning**. The simplest approach to multi-agent learning is to have the agents learn independently from each other, without having knowledge of each other. From the perspective of the learning agent, the other agents are simply part of the environment. (Literature: Littman 1994, Busoniu 2010).\n",
    "\n",
    "The notebook uses [PettingZoo](https://www.pettingzoo.ml), a Python library for conducting research in multi-agent reinforcement learning. It's akin to a multi-agent version of OpenAI's Gym library. \n",
    "\n",
    "PettingZoo has a large collection of environments (games) available, including Tic-Tac-Toe. We already experimented with Tic-Tac-Toe as part of the introduction chapter of Sutton and Barto. Tic-Tac-Toe therefore seems a natural starting point to start with multi-agent learning.\n",
    "\n",
    "Before we can start with PettingZoo, we first need to learn about the concept behind the package, which is to model each game as **Agent Environment Cycle (AEC)** games.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Agent Environment Cycle (AEC) games\n",
    "\n",
    "From [the paper](https://arxiv.org/abs/2009.13051) by Justin Terry et al:\n",
    "\n",
    ">The  base  component  of  an  AEC  game  is  a  **changeable  list of agents**.  After the first agent in the list acts, the environment can “act” (allowing agents’ observations to be updated), or the next designated agent can act (skipping environment turns are how truly simultaneous games are depicted). This process continues indefinitely.  \n",
    "\n",
    ">As  for  reward,  after  every  agent  takes  a  turn  a  “partial” reward is emitted to every other agent. The reward associated with a single action performed by an agent is the total of all the partial rewards following that action and before the agent’s next turn (until this point, the reward is not fully defined).   \n",
    "\n",
    ">Different aspects of a game will be responsible for different portions of reward. As shown in [this paper], thinking about rewards in this atomized manner instead of lumping the reward process all together can be very helpful."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "## PettingZoo: interacting With Environments\n",
    "\n",
    "Environments can be interacted with using a similar interface to Gym:\n",
    "\n",
    "```{python}\n",
    "env.reset()\n",
    "for agent in env.agent_iter():\n",
    "    observation, reward, done, info = env.last()\n",
    "    action = policy(observation, agent)\n",
    "    env.step(action)\n",
    "```\n",
    "\n",
    "The commonly used methods are:\n",
    "\n",
    "`agent_iter(max_iter=2**63)` returns an **iterator** that yields the current agent of the environment. It terminates when all agents in the environment are done or when `max_iter` (steps have been executed).\n",
    "\n",
    "`last(observe=True)` returns `observation`, `reward`, `done`, and `info` for the agent currently able to act. The returned reward is the **cumulative reward** that the agent has received since it last acted. If observe is set to `False`, the observation will not be computed, and `None` will be returned in its place. Note that a single agent being done does not imply the environment is done.\n",
    "\n",
    "Code example:\n",
    "\n",
    "```{python}\n",
    "observation, reward, done, info = env.last()\n",
    "```\n",
    "\n",
    "`reset()` resets the environment and sets it up for use when called the first time. Only after calling this function do objects like `agents` become available.\n",
    "\n",
    "`step(action)` takes and executes the action of the agent in the environment, automatically switches control to the next agent.\n",
    "\n",
    "While developing code, several lower level methods I found useful.\n",
    "\n",
    "`agent_selection` displays the currently selected agent.\n",
    "\n",
    "`agents` list all available agents.\n",
    "\n",
    "The complete API including lower level functionality is at https://www.pettingzoo.ml/api\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Installing PettingZoo\n",
    "\n",
    "It is best to create a clean Python 3 virtual environment to run this notebook in. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "# create venv\n",
    "python3 -m venv marl-env\n",
    "# active venv\n",
    "source marl-env/bin/activate\n",
    "# upgrade really old pip version on my system\n",
    "pip install --upgrade pip\n",
    "# install packages\n",
    "pip install pettingzoo[classic]\n",
    "pip install spyder-notebook\n",
    "pip install dill\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This installs [Spyder](https://www.spyder-ide.org/), the IDE I currently use for Python development, with the Notebook plugin to work both with Python scripts and Jupyter notebooks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PettingZoo TicTacToe environment\n",
    "\n",
    "\n",
    "\n",
    "The TicTacToe environment AEC diagram is depicted below:\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://www.pettingzoo.ml/assets/img/aec/classic_tictactoe_aec.svg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We start with loading the required libraries:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "from collections import defaultdict\n",
    "import dill\n",
    "\n",
    "from pettingzoo.classic import tictactoe_v3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create an instance of a TicTacToe environment, call `reset()` to initialize the game and list the available agents (players):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = tictactoe_v3.env()\n",
    "\n",
    "env.reset()\n",
    "\n",
    "env.agents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It helps to understand exactly how the PettingZoo \"mechanics\" work.\n",
    "\n",
    "Below we use the `agent_selection` method to show exactly when the active agent switches between the players:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.reset()\n",
    "env.agent_selection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#env.step()\n",
    "# env acts by updating the observation and \n",
    "# switches to the next player\n",
    "env.agent_selection\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# now player 2 can act\n",
    "env.step(1)\n",
    "env.agent_selection"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, directly after an agent takes an action using `env.step()`, the game moves on to the environent which \"acts\" by updating the board position, and after that the other player can act."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using action masks to choose from available actions\n",
    "\n",
    "The TicTacToe PettingZoo environment uses so-called \"action masks\"  to filter out actions that are invalid or not available given the current state of the environment. The action mask is part of the `observation` output from `last()`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "observation, reward, done, info = env.last()\n",
    "\n",
    "observation['action_mask']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This mask tells us that for the current agent, actions `0` and `1` are not available.\n",
    "Our `policy()` function needs this information for action selection.\n",
    "\n",
    "If we choose an illegal action the environment throws an error message and terminates the current game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.reset()\n",
    "# player 1\n",
    "env.step(0)\n",
    "# player 2 attempts same move\n",
    "env.step(0)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If `done` is `True` , we can let the agent play action `None`. This allows the agents to keep on stepping until all rewards are received by all agents. \n",
    "\n",
    "For example this game where Player 1 plays the winning move:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.reset()\n",
    "env.step(0)\n",
    "env.step(3)\n",
    "env.step(1)\n",
    "env.step(4)\n",
    "env.step(2)\n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the player is Player 2, that receives its (negative) reward for losing the game. Note that it cannot play any legal moves anymore because the game has ended, but we need to call `step()` with action `None` to move back to Player 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "observation, reward, done, info = env.last()\n",
    "\n",
    "print(done)\n",
    "print(reward)\n",
    "\n",
    "env.step(None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Player 2 is removed from the list of available agents:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.agents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now player 1 can collect its reward for winning the game!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "observation, reward, done, info = env.last()\n",
    "\n",
    "print(done)\n",
    "print(reward)\n",
    "\n",
    "env.step(None)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# no active agents anymore, need to call env.reset() to start a new game\n",
    "env.agents\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise 1 Random play\n",
    "\n",
    "When two players who play completely randomly play Tic-Tac-Toe, the first player wins 58.49% of the time, the second player wins 28.81% of the time, and the game is a draw 12.70% of the time. \n",
    "\n",
    "Code up a function that has both players play a random policy for 10.000 games.\n",
    "Store the outcomes of the games (W/D/L) for both Players.\n",
    "Check your work by comparing with the percentages above.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# use this as starting point\n",
    "\n",
    "def policy(observation, agent):\n",
    "    action = random.choice(np.flatnonzero(observation['action_mask']))\n",
    "    return action\n",
    "\n",
    "env.reset()\n",
    "for agent in env.agent_iter():\n",
    "    observation, reward, done, info = env.last()\n",
    "    action = policy(observation, agent) if not done else None\n",
    "    env.step(action)\n",
    "    env.render() # this visualizes a single game\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hashing the board position to a key for use in a dictionary"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the TicTacToe environment, observations of agents consist of a complete description of the board position. An observation of the board is a 3D array and looks like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.reset()\n",
    "observation, reward, done, info = env.last()\n",
    "\n",
    "\n",
    "observation['observation']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare this to the properly rendered board position:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For Q-learning, we need the environment to store Q-values for each unique board position. A convenient way to create unique identifiers for all board positions is to use a **hash-function**.\n",
    "\n",
    "We encountered this concept at the beginning of the course:\n",
    "\n",
    ">*Hash functions* are used to transform a large amount of data (such as a complete board position aka game state) into a single number.\n",
    "The special thing about hash functions is that every board position is transformed into a unique number, i.e. there are no two board positions that are transformed to the same unique number.\n",
    "This allows us to use this to label / identify each board position, and use this as an identifier to store information about that board position.\n",
    "\n",
    "Example code (first convert observation to string, then hash):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "state = hash(str(observation['observation']))\n",
    "\n",
    "state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Update:** \n",
    "I discovered that in Python 3, the `hash()` function is, by design, not reproducible between python sessions! This makes it unsuitable for our purpose, since we want to learn an optimal policy for each state, and save that policy (the Q-table) to disk for later use. \n",
    "This later use will consist of things like testing the policy's performance, or as an AI player to play against ourselves.\n",
    "\n",
    "To have reproducible hashing we can use `hashlib`, a Python library containing various hashing algorithms. I chose the `MD5` algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib\n",
    "\n",
    "def encode_state(observation):\n",
    "    # encode observation as bytes           \n",
    "    obs_bytes = str(observation).encode('utf-8')\n",
    "    # create md5 hash\n",
    "    m = hashlib.md5(obs_bytes)\n",
    "    # return hash as hex digest\n",
    "    state = m.hexdigest()\n",
    "    return(state)\n",
    "\n",
    "encode_state(observation['observation'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make self-play (An single agent that plays against itself) easy to implement, in PettingZoo the observation contains information about which player is making the observation. This information is encoded in the observation by flipping the board position player index order (aka \"inverting the channels\").\n",
    "\n",
    "Take for example the observation of the board state after Player 1 made a first move:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = tictactoe_v3.env()\n",
    "env.reset()\n",
    "env.step(4)\n",
    "env.observe('player_1')['observation']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now compare this with how Player 2 observes the same board position:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.observe('player_2')['observation']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In practice, this is only an issue if both players see the same board position, which only occurs at the end of a game, when the players collect their rewards. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env = tictactoe_v3.env()\n",
    "env.reset()\n",
    "env.step(0)\n",
    "env.step(6)\n",
    "env.step(1)\n",
    "env.step(5)\n",
    "env.step(2)\n",
    "\n",
    "env.observe(\"player_1\")['observation']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "env.step(None)\n",
    "env.observe(\"player_2\")['observation']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To avoid double counting of end-game board positions, I used this trick:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "state = encode_state(env.render(mode = 'ansi'))\n",
    "\n",
    "state"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise 2 Hashing and dictionaries for the Q-table\n",
    "\n",
    "For this exercise, adapt your code from Exercise 1 to add a  `defaultdict` dictionary that contains the value `0` for each board position (identified using `encode_state()` ) the agents encounter. \n",
    "\n",
    "Run your code for 20.000 games with the agents playing a random policy to find out how many distinct states Tic-Tac-Toe contains. The dictionary should max out at 5478 different states.\n",
    "\n",
    "You can use the code provided below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "env.reset()\n",
    "\n",
    "Q = defaultdict(lambda: np.zeros(nA)) \n",
    "\n",
    "# reminder about how default dict works\n",
    "\n",
    "Q['32433'] = 0\n",
    "Q['-5323'] = 0\n",
    "Q['2397887'] = 0\n",
    "\n",
    "Q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## License\n",
    "\n",
    "The code in this notebook is copyrighted by Gertjan Verhoeven and licensed under the new BSD (3-clause) license:\n",
    "\n",
    "https://opensource.org/licenses/BSD-3-Clause\n",
    "\n",
    "The text and figures in this notebook (if any) are copyrighted by Gertjan Verhoeven and licensed under the CC BY-NC 4.0 license:\n",
    "\n",
    "https://creativecommons.org/licenses/by-nc/4.0/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (Spyder)",
   "language": "python3",
   "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}