ch02TicTacToe.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "653089c9",
   "metadata": {},
   "source": [
    "# Chapter 2: Look-Ahead Search in Tic Tac Toe\n",
    "\n",
    "\n",
    "\n",
    "***\n",
    "*“Saying Deep Blue doesn't really think about chess is like saying an airplane doesn't really\n",
    "fly because it doesn't flap its wings.”*\n",
    "\n",
    "-- Drew McDermott\n",
    "***\n",
    "\n",
    "\n",
    "\n",
    "What you'll learn in this chapter:\n",
    "\n",
    "* Learning the rules of Tic Tac Toe\n",
    "* Playing Tic Tac Toe in the local game environment\n",
    "* Creating agents that can think one, two, or three steps ahead\n",
    "* Testing the effectiveness of AI agents in Tic Tac Toe\n",
    "\n",
    "\n",
    "In this chapter, you'll learn to play the Tic Tac Toe game in a local game environment. You'll hard code in various rules to make the AI player think up to three\n",
    "steps ahead. You'll then deploy the strategies against a random player and each other\n",
    "and see how effective they are. Coding in rule-based AI in Tic Tac Toe\n",
    "in this chapter serves at least four purposes. First, you'll learn how to\n",
    "build an AI agent that can think up to three steps ahead and generalize\n",
    "the logic to other games or real-world situations. Second, it introduces\n",
    "you to the game environment of Tic Tac Toe, as we'll use this game to\n",
    "study other AI algorithms later in this book, such as MiniMax, Monte\n",
    "Carlo Tree Search, Actor-Critic, and so on. Third, in deep reinforcement\n",
    "learning, an agent learns from playing against intelligent opponents, and\n",
    "we'll use the AI players created in this chapter as opponents when we\n",
    "design deep reinforcement learning game strategies. Fourth, later in\n",
    "this book, we'll use rule-based AI to test how effective a certain game\n",
    "strategy is; that is, we'll use rule-based AI as our benchmark when\n",
    "testing the effectiveness of various game strategies.\n",
    "\n",
    "To build an AI player who can think one step ahead, we iterate through\n",
    "all possible next moves and check if any one of them leads to winning\n",
    "the game right away. If yes, the AI player will take the move. Thinking\n",
    "two steps ahead means that the AI player tries to prevent the opponent\n",
    "from winning the next turn. The program iterates through all\n",
    "combinations of the next two moves and checks if there is a combination that\n",
    "leads to a win for the opponent. If yes, the AI player blocks the\n",
    "opponent's move. By thinking three steps ahead, the AI player follows\n",
    "the path that most likely leads to a victory after three moves. In many\n",
    "scenarios, thinking three steps ahead can guarantee a win for the AI\n",
    "player in three steps."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "282ad876",
   "metadata": {},
   "source": [
    "# 1. The Tic Tac Toe Game Environment"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79c437e8",
   "metadata": {},
   "source": [
    "## 1.1. Methods and Attributes in Tic Tac Toe\n",
    "\n",
    "First, download the file *coin_env.py* from the book's GitHub repository https://github.com/markhliu/AlphaGoSimplified and  place it in the folder /Desktop/ags/utils/ on your computer. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "de2d7767",
   "metadata": {},
   "source": [
    "## 1.2. Familirize Yourself with the Tic Tac Toe Game Environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a847d4fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils.ttt_env import ttt\n",
    "\n",
    "env = ttt()\n",
    "env.reset()                    \n",
    "env.render()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06e6bd0a",
   "metadata": {},
   "source": [
    "We import the *ttt* class from the local *ttt_env* module and set it as our game environment. Since we called the *render()* method in the above code cell, you should see a separate turtle window, with a game board as shown below: \n",
    "<img src=\"https://gattonweb.uky.edu/faculty/lium/ml/ttt_start.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0977029b",
   "metadata": {},
   "source": [
    "The nine cells on the game board are marked 1 through nine. After each move, the corresponding cell will be marked with an X or an O. \n",
    "\n",
    "If you want to close the game board window, use the *close()* method, like so:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "439f093e",
   "metadata": {},
   "outputs": [],
   "source": [
    "env.close()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "15b9c0d7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the number of possible actions is 9\n",
      "the following are ten sample actions\n",
      "2\n",
      "7\n",
      "9\n",
      "9\n",
      "6\n",
      "8\n",
      "4\n",
      "2\n",
      "5\n",
      "9\n",
      "the shape of the observation space is (9,)\n"
     ]
    }
   ],
   "source": [
    "env=ttt()\n",
    "# check the action space\n",
    "number_actions=env.action_space.n\n",
    "print(\"the number of possible actions is\", number_actions)\n",
    "# sample the action space ten times\n",
    "print(\"the following are ten sample actions\")\n",
    "for i in range(10):\n",
    "   print(env.sample())\n",
    "# check the shape of the observation space\n",
    "print(\"the shape of the observation space is\",\\\n",
    "      env.observation_space.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe6f879a",
   "metadata": {},
   "source": [
    "## 1.3. Play Games in the Tic Tac Toe Environment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f44d0601",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the current state is \n",
      "[[0 0 0]\n",
      " [0 0 0]\n",
      " [0 0 0]]\n",
      "Player X has chosen action=2\n",
      "the current state is \n",
      "[[0 0 0]\n",
      " [0 0 0]\n",
      " [0 1 0]]\n",
      "Player O has chosen action=1\n",
      "the current state is \n",
      "[[ 0  0  0]\n",
      " [ 0  0  0]\n",
      " [-1  1  0]]\n",
      "Player X has chosen action=9\n",
      "the current state is \n",
      "[[ 0  0  1]\n",
      " [ 0  0  0]\n",
      " [-1  1  0]]\n",
      "Player O has chosen action=4\n",
      "the current state is \n",
      "[[ 0  0  1]\n",
      " [-1  0  0]\n",
      " [-1  1  0]]\n",
      "Player X has chosen action=8\n",
      "the current state is \n",
      "[[ 0  1  1]\n",
      " [-1  0  0]\n",
      " [-1  1  0]]\n",
      "Player O has chosen action=7\n",
      "game state is \n",
      "[[-1  1  1]\n",
      " [-1  0  0]\n",
      " [-1  1  0]]\n",
      "Player O has won!\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "# Initiate the game environment\n",
    "env=ttt()\n",
    "state=env.reset()   \n",
    "env.render()\n",
    "# Play a full game \n",
    "while True:\n",
    "    print(f\"the current state is \\n{state.reshape(3,3)[::-1]}\")    \n",
    "    action = env.sample()\n",
    "    time.sleep(1)\n",
    "    print(f\"Player X has chosen action={action}\")    \n",
    "    state, reward, done, info = env.step(action)\n",
    "    env.render()\n",
    "    if done:\n",
    "        print(f\"game state is \\n{state.reshape(3,3)[::-1]}\")\n",
    "        if reward==1:\n",
    "            print(\"Player X has won!\") \n",
    "        else:\n",
    "            print(\"It's a tie!\") \n",
    "        break\n",
    "    print(f\"the current state is \\n{state.reshape(3,3)[::-1]}\")    \n",
    "    action = env.sample()\n",
    "    time.sleep(1)\n",
    "    print(f\"Player O has chosen action={action}\")    \n",
    "    state, reward, done, info = env.step(action)\n",
    "    env.render()\n",
    "    if done:\n",
    "        print(f\"game state is \\n{state.reshape(3,3)[::-1]}\")\n",
    "        print(\"Player O has won!\") \n",
    "        break  \n",
    "env.close()    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "aac17214",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter a number between 1 and 9 as your move:\n",
      "game state is \n",
      "[[0 0 0]\n",
      " [0 0 0]\n",
      " [0 0 0]]\n",
      "Player X, what's your move?\n",
      "5\n",
      "Player X has chosen action=5\n",
      "game state is \n",
      "[[0 0 0]\n",
      " [0 1 0]\n",
      " [0 0 0]]\n",
      "Player O, what's your move?\n",
      "1\n",
      "Player O has chosen action=1\n",
      "game state is \n",
      "[[ 0  0  0]\n",
      " [ 0  1  0]\n",
      " [-1  0  0]]\n",
      "Player X, what's your move?\n",
      "3\n",
      "Player X has chosen action=3\n",
      "game state is \n",
      "[[ 0  0  0]\n",
      " [ 0  1  0]\n",
      " [-1  0  1]]\n",
      "Player O, what's your move?\n",
      "7\n",
      "Player O has chosen action=7\n",
      "game state is \n",
      "[[-1  0  0]\n",
      " [ 0  1  0]\n",
      " [-1  0  1]]\n",
      "Player X, what's your move?\n",
      "4\n",
      "Player X has chosen action=4\n",
      "game state is \n",
      "[[-1  0  0]\n",
      " [ 1  1  0]\n",
      " [-1  0  1]]\n",
      "Player O, what's your move?\n",
      "6\n",
      "Player O has chosen action=6\n",
      "game state is \n",
      "[[-1  0  0]\n",
      " [ 1  1 -1]\n",
      " [-1  0  1]]\n",
      "Player X, what's your move?\n",
      "2\n",
      "Player X has chosen action=2\n",
      "game state is \n",
      "[[-1  0  0]\n",
      " [ 1  1 -1]\n",
      " [-1  1  1]]\n",
      "Player O, what's your move?\n",
      "8\n",
      "Player O has chosen action=8\n",
      "game state is \n",
      "[[-1 -1  0]\n",
      " [ 1  1 -1]\n",
      " [-1  1  1]]\n",
      "Player X, what's your move?\n",
      "9\n",
      "Player X has chosen action=9\n",
      "game state is \n",
      "[[-1 -1  1]\n",
      " [ 1  1 -1]\n",
      " [-1  1  1]]\n",
      "It's a tie!\n"
     ]
    }
   ],
   "source": [
    "state=env.reset() \n",
    "env.render()  \n",
    "print(\"enter a number between 1 and 9 as your move:\")\n",
    "# Play a full game manually\n",
    "while True:\n",
    "    print(f\"game state is \\n{state.reshape(3,3)[::-1]}\")   \n",
    "    m=int(input(f\"Player {env.turn}, what's your move?\\n\"))\n",
    "    print(f\"Player {env.turn} has chosen action={m}\")    \n",
    "    state, reward, done, info = env.step(m)\n",
    "    env.render() \n",
    "    if done:\n",
    "        print(f\"game state is \\n{state.reshape(3,3)[::-1]}\")\n",
    "        if reward!=0:\n",
    "            print(f\"Player {env.turn} has won!\") \n",
    "        else:\n",
    "            print(\"It's a tie!\") \n",
    "        break \n",
    "env.close()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9bcbdf00",
   "metadata": {},
   "source": [
    "# 2. Think One Step Ahead in Tic Tac Toe"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e18df585",
   "metadata": {},
   "source": [
    "## 2.1. Create an AI Player Who Thinks One Step Ahead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "3557ff1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "\n",
    "def ttt_think1(env):\n",
    "    # iterate through all possible next moves\n",
    "    for m in env.validinputs:\n",
    "        # make a hypothetical move\n",
    "        env_copy=deepcopy(env)\n",
    "        state,reward,done,_=env_copy.step(m) \n",
    "        # if reward is 1 or -1, current player wins\n",
    "        if done and abs(reward)==1:\n",
    "            # take the winning move\n",
    "            return m                  \n",
    "    # otherwise, randomly select a move\n",
    "    return env.sample()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "71c3e8e9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ttt_random(env):\n",
    "    move = env.sample()\n",
    "    return move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "b0cb728f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ttt_manual(env):\n",
    "    print(f\"game state is \\n{env.state.reshape(3,3)[::-1]}\") \n",
    "    while True:\n",
    "        move = input(f\"Player {env.turn}, what's your move?\")\n",
    "        try: \n",
    "            move = int(move)\n",
    "        except:\n",
    "            print(\"the move must be a number\")\n",
    "        if move in env.validinputs:\n",
    "            return move\n",
    "        else:\n",
    "            print(\"please enter a valid move\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "fc2f8827",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define the one_ttt_game() function\n",
    "def one_ttt_game(player1, player2):\n",
    "    env = ttt()\n",
    "    env.reset()     \n",
    "    while True:    \n",
    "        action = player1(env)  \n",
    "        state, reward, done, _ = env.step(action)\n",
    "        if done:\n",
    "            break\n",
    "        action = player2(env)  \n",
    "        state, reward, done, _ = env.step(action)\n",
    "        if done:\n",
    "            break            \n",
    "    return reward      "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2ebaaecd",
   "metadata": {},
   "source": [
    "## 2.2. Test the Think-One-Step-Ahead AI in Tic Tac Toe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "e9d23acb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "game state is \n",
      "[[0 0 0]\n",
      " [0 1 0]\n",
      " [0 0 0]]\n",
      "Player O, what's your move?1\n",
      "game state is \n",
      "[[ 0  0  1]\n",
      " [ 0  1  0]\n",
      " [-1  0  0]]\n",
      "Player O, what's your move?2\n",
      "game state is \n",
      "[[ 0  0  1]\n",
      " [ 0  1  1]\n",
      " [-1 -1  0]]\n",
      "Player O, what's your move?4\n",
      "the game outcome is 1\n"
     ]
    }
   ],
   "source": [
    "from utils.ch02util import one_ttt_game, ttt_think1, ttt_manual\n",
    "\n",
    "reward=one_ttt_game(ttt_think1, ttt_manual)\n",
    "print(f\"the game outcome is {reward}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "176c2b71",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils.ch02util import ttt_random\n",
    "\n",
    "results=[]\n",
    "for i in range(1000):\n",
    "    # AI moves first if i is an even number\n",
    "    if i%2==0:\n",
    "        result=one_ttt_game(ttt_think1,ttt_random)\n",
    "        # record game outcome\n",
    "        results.append(result)\n",
    "    # AI moves second if i is an odd number\n",
    "    else:\n",
    "        result=one_ttt_game(ttt_random,ttt_think1)\n",
    "        # record negative of the game outcome\n",
    "        results.append(-result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "d1e19a63",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the AI player has won 653 games\n",
      "the AI player has lost 272 games\n",
      "the game was tied 75 times\n"
     ]
    }
   ],
   "source": [
    "# count how many times AI player has won\n",
    "wins=results.count(1)\n",
    "print(f\"the AI player has won {wins} games\")\n",
    "# count how many times AI player has lost\n",
    "losses=results.count(-1)\n",
    "print(f\"the AI player has lost {losses} games\")\n",
    "# count tie games\n",
    "ties=results.count(0)\n",
    "print(f\"the game was tied {ties} times\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7373bfa",
   "metadata": {},
   "source": [
    "# 3. Think Two Steps Ahead in Tic Tac Toe\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bd5e7d9",
   "metadata": {},
   "source": [
    "## 3.1. A Tic Tac Toe Agent Who Thinks Two Steps Ahead\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d0f0dc85",
   "metadata": {},
   "outputs": [],
   "source": [
    "def ttt_think2(env):\n",
    "    # iterate through all possible next moves\n",
    "    for m in env.validinputs:\n",
    "        # make a hypothetical move\n",
    "        env_copy=deepcopy(env)\n",
    "        state,reward,done,_=env_copy.step(m) \n",
    "        # if reward is 1 or -1, current player wins\n",
    "        if done and abs(reward)==1:\n",
    "            # take the winning move\n",
    "            return m  \n",
    "    # otherwise, look two moves ahead\n",
    "    for m1 in env.validinputs:\n",
    "        for m2 in env.validinputs:\n",
    "            if m1!=m2:\n",
    "                env_copy=deepcopy(env)\n",
    "                s,r,done,_=env_copy.step(m1) \n",
    "                s,r,done,_=env_copy.step(m2)                     \n",
    "                # block opponent's winning move\n",
    "                if done and r!=0:\n",
    "                    return m2 \n",
    "    # otherwise, return a random move               \n",
    "    return env.sample()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6997e023",
   "metadata": {},
   "source": [
    "## 3.2. Test the Think-Two-Steps-Ahead AI in Tic Tac Toe "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "f34930dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "game state is \n",
      "[[0 1 0]\n",
      " [0 0 0]\n",
      " [0 0 0]]\n",
      "Player O, what's your move?5\n",
      "game state is \n",
      "[[ 0  1  0]\n",
      " [ 0 -1  0]\n",
      " [ 1  0  0]]\n",
      "Player O, what's your move?3\n",
      "game state is \n",
      "[[ 1  1  0]\n",
      " [ 0 -1  0]\n",
      " [ 1  0 -1]]\n",
      "Player O, what's your move?2\n",
      "the game outcome is 1\n"
     ]
    }
   ],
   "source": [
    "from utils.ch02util import ttt_think2\n",
    "\n",
    "reward=one_ttt_game(ttt_think2, ttt_manual)\n",
    "print(f\"the game outcome is {reward}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "63d36b68",
   "metadata": {},
   "outputs": [],
   "source": [
    "results=[]\n",
    "for i in range(1000):\n",
    "    # think-two-steps-ahead AI moves first at even i\n",
    "    if i%2==0:\n",
    "        result=one_ttt_game(ttt_think2, ttt_think1)\n",
    "        # record game outcome\n",
    "        results.append(result)\n",
    "    # think-two-steps-ahead AI moves second at odd i\n",
    "    else:\n",
    "        result=one_ttt_game(ttt_think1, ttt_think2)\n",
    "        # record negative of game outcome\n",
    "        results.append(-result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "d07476eb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "think-two-steps-ahead AI won 778 games\n",
      "think-two-steps-ahead AI lost 77 games\n",
      "the game was tied 145 times\n"
     ]
    }
   ],
   "source": [
    "# count how many times think-two-steps-ahead AI won\n",
    "wins=results.count(1)\n",
    "print(f\"think-two-steps-ahead AI won {wins} games\")\n",
    "# count how many times it lost\n",
    "losses=results.count(-1)\n",
    "print(f\"think-two-steps-ahead AI lost {losses} games\")\n",
    "# count tie games\n",
    "ties=results.count(0)\n",
    "print(f\"the game was tied {ties} times\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "21150dcc",
   "metadata": {},
   "source": [
    "# 4. Think Three Steps Ahead\n"
   ]
  },
  {
   "attachments": {
    "think3.png": {
     "image/png": "iVBORw0KGgoAAAANSUhEUgAAAnoAAAKaCAYAAACp7vSOAAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAADEBSURBVHhe7d1tjF3nQeDxZ8YdnA42SZtCU0EbCp7QBicFoYrWTuiLdgV2xSoSELHLitKy8vBhWVtCRZRGaLXqqit1AVt82LWlhXQ/oDq8KF9iUwloA7FbqFjaxHWrzJQ2TYvT1zix69qaju/e58w5M9fjuTNz38/znN9PuvK9d8bje8+Lz/8+52WmLl++3GoL8RZV99c/t5XtfE/qmvAeAaDupqamynv52s57rL4n/tl5u+G5S5cutfvlxrirbtH6P7vZ6us5aMJ7pF4sczBc1UaQtDVhPm71Hquvd/654e3FF19sXb9+vdigVLdr166Fb33rW+HKlSvh29/+dlheXrbBGYBpBwDDEwOm6eI0mJmZCbOzs8XtZS97WbjllltWv7Z6u3jxYrtD1iLv61//erhw4UK44447wq5du8L3fu/3Fj8IAID6WFpaKgbkLl++HJ577rmi3X7gB37gxtB7/vnnV0PvmWeeCXF0784771ytQgAA6u3q1avhS1/6UtFxr33ta8P09HQRetOdI3nxzx/7sR8TeQAACYntdtdddxVx97WvfW11T20RerEC4+7a17zmNeW3AwCQmrhX9qtf/WrRdquhF0+8iPt1jeQBAKQrtlxsuueff34l9OK+3Hh2bTzpAgCAtMWmiydpxMYrRvTi2RrDCL2PfOQj4T/+6q+G9/zO+8pnAAAYp9h0cRCvGNGLT8Tr5H3P93xP8cV+xOHB3/zN3wy//4cfDP/ut/9vOPfp/1d+BQCAcYpNFy+9EhUjeoN673vfG+6f/6Pwn/7nX4cPf+y5cNttt5VfAQBgEmLjTV24cKH16U9/Ouzfv798uje/8Ru/Ed7+n/93cf/YHz0cXnnPz4Vd//jb4Q/+4A/CK17xiuJ5AIBh+MQnPhE+97nPFRGzkXh5kde97nXhTW96U/lMPfz5n/952H/ffeFVd9xRPnOjC889F8488UT4xV/8xfKZwZw5cya84Q1vGCz0vvOd74QHHvj58Ou//9fhv/32kXDXwd8Jy5/6X+Hly18Kf/Inf1J+1+YeffTR4qzf9Q4cOBAef/zx8IM/+IPh/vvvL5/dXJzxZ8+eLR+tiT/jZ3/2Z8tHvfvwhz9c7Ote793vfnd5rz9///d/H77yla+EX/7lXy6f2Vy8BM7p06fLR2te/vKXt+fDA+Wj3sWfG6f1dl9Hp/Xzb25ubtvzazv++I//eMPp/MlPfjI89dRTA88DANLy8MMPF9u8+Gu/NhJ/jetf/MVfhF/7tV8rn6mHGHKPf+xj4S1vfetNsbfZ1/o1lNA7dOhQ+Df/5URx/9ffvDv82w8shG888mD4y7/8y55H8+KGOwbDIEHWKcbZW97ylvCqV72qfGZwMcyiYYZMv2JgxU8s8daPzunTb+jFCLvnnnvCG9/4xvKZlRNyhjUPo26hB0AzxYGkX/mVX9n03IL4Pe9617vKR/WxUdCNIvKiKvSKkzH68YUvfCF85jPnivtV5EU/8iM/YpdtA8SgWx950TAjDwByEkMuBl0Muxh4o4q8Tn2P6L3vfe8Lb/j3/724X4XepY//frh9+dlitKhXG43orR+16tyFulFkdOocsap281X27du3+jPjKN3CwkqkbrULdP2I3vpdxZ2vaf1u1rgrev3oYud7rn523JUb32Mckt5shG39tImvJd6q19/5uLofxStlR9V0jO/5p3/6p28Y0eucXt1ex1YjbdV7i2dkx4s3xn+jc3pUu3ir0cS4e72aD527f6tRw+r1VNO48/1FG83HzucG3X0PQD2kPKJXqQIvGlXkDTyiF39xblRFXuv69bD0lU+GP/3TPy2eH7YYbj/6oz9axEW8bRZ568Xvrf5ejLwqemIIfPOb31z92maRt14MlBh5MeCqvx9jpPrZMWqq5+P3/MM//EPx/GZilMQ4jX8nxlGMpWGJ0RWjMEZbvMWAi69r/XuOrz/GZvXa4zSvIrRT57ERcVrEIIu3GKCV+HPi+4n/Rozc6mfGWxVgURWd8fn4muLX4s+sxNcevxbn3ec///ny2TUbzcf49zvfh8gDuFkMou3cSFffobdjx47y3oqLZ/4wvO1tbwvT033/yK6qjf76uIshVAXGVqOI8evx+zpH4GIcVCNinaqfGW9VuK335S9/uRgl6hyliyNRX//611f/TvUzYvTFWNlK/PvVz7v99ttXR9+GIY5ybfRe14uvP77W6rXHeI3Tab3Ok1OqiIsh1mn99Im7e6uf2ylGYzWCF78//r04fStVpMXX3/nvVjaaj9W/2xmeANwojnpt58bwdO6u7dyNOyp9X0cvht6737SrfBTCS771qfB7v/d75aPx6Byp22w3Z4y8n/iJn9gwRjZS/cx4204cdap+X3AMq86fE2+piMHZ+bo3GumM76+XEccYeTHotjstdu/eXd7rX1wm4vyLYRn/fQCYpPXH5K0/Zm/YVn8zRj+eeeaZ8B/etbLB/sf/8cbwgQ98oLh2zShUozOD7Mq89dZbiz/j667EUbNuI3Zb+aEf+qFi12DnLsa4yzE+H+Mijor1+7P7Ed9f56hh5/vcSAzSF154oXy05vu///tv2K3aTXyPnbuqt6OK4PXzMY7SVT8n/hmnay+Bvdl8jD8n7g6OxwoCkL7YGvESKt3EbcqoemQQ6yOvMurY2/Fbv/Vb//WrX/1qeM1rXlM+tT0/9VM/Ff7P8ePha1/7Wvjd331v+IVf+IXyK/3513/91+K6fHv27CmfWdnoxzN4423v3r3FqMw///M/F7fvfve7xS6+bs6dOxd++Id/uBgZihv5eIxc/Hvf933fV/zdGAB33nlnEUR/93d/V3wt3t8sMKrjEuPfiz/3pS99afjoRz+6+priaOFrX/va4nvi1+Ju4uprcTp1vreo8z13/uxo/eP1OqdNFF9P/Deq99L5Pr/xjW8Ut873FnfRxpNw4nuOcRr/jNM4/rz4u4//5m/+ZvW1bzSt4/fd0V44O9//s88+G37yJ3+y+Nr6+Rl/xj/90z8V3zczMxMuXbpUfG/8t+L3Xrx4sZhe8WfE6Vi9r/j98fsq1ePO97TRfIzh+2d/9mfF48XFxWL0t/qZAKQrHtYUj82O/79/6lOfuul2/vz5YtsQt2118pG/+qtw/8/8zIYnXuzetSvc3t5GxQsm33333eWzg4nb01e+8pVhqr2RbT355JN9XUfvxRdfLAIgbrShH3FEtN+LNQMAG4tn3d57773977qNdu7cWd4DAKBuBg699WdQAgBQDwNfC+WXfumXynvQu3iijd22ADAaw7/oHQAAtSD0AAAyJfQAADIl9AAAMiX0AAAyJfQAADIl9AAAMrX6K9De9KY3lU8BAJCyT3ziEyu/Aq3VapVPAQCQi9h4dt0CAGRq6itf+UrrqaeeumHX7cMnT5b3AACou5/7+Z8Pd8zOlo9Wdt3ec8893UPvyPx8+QgAgLq62GqF5y5c6D304l8EAKDeuoWeY/QAADIl9AAAMiX0AAAyJfQAADIl9AAAMiX0AAAyJfQAADIl9AAAMiX0AAAyJfQAADJV/Aq0J598Mrz5zW8un+r/V6DdNlXeAQBg6C52SbP1vwLt4x//eLj33nuHN6In8gAARqvX3rLrFgAgU0IPACBTQg8AIFNDOxljo33G3Q4YhKaxfkB31g/obrvrx8hPxgAAoF6EHgBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmpls9/PYLAADSEBvPiB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKamvvzlL7eeeuqp8OY3v7l8KoSHT54MR+bnw8UerrF321R5p8NFl+iDgvUDurN+jN+z586V9wb36r17y3uMwnbXj+cuXAh3zM6Wj0L4+Mc/Hu655x6hB+Ng/YDurB/DN8yQG5QQHMygoWfXLQBkIMZddauTur6uphB6AJCo1CIqtdebA6EHAAnJJZZyeR91J/QAoOZyj6Lc398kCT0AqKGmxk9T3/eoCD0AqBGRs8a0GJzQA4CaEDUbM136J/QAYMKMXG3NNOqP0AOACREvvTPNeiP0AGDMxMrgTMPtEXoAMCbiZPhM080JPQAYAzEyWqbvxoQeAIyQEafxMa1vJvQAYEREx2SY7muEHgCMgNiYLNN/hdADgCETGfVgPgg9ABiaGBbiol6aPk+EHgAMgcCrt6bOH6EHAAMSeWlo4nwSegAwAJGXlqbNL6EHAH0SeWlq0nwTegDQB5GXtqbMP6EHAD0SeXlownwUegDQA5GXl9znp9ADgG0SeXnKeb4KPQDYBpGXt1znr9ADgC2IvGbIcT4LPQCATAk9ANiE0bxmyW1+Cz0A6ELkNVNO813oAcAGRF6z5TL/hR4ArCPyiHJYDoQeAECmhB4AdDCaR6fUlwehBwAlkcdGUl4upq9fvx7iDQCAPFR9Z0QPANqM5rGZVJcPoQcAkCmhB0DjGc1jO1JcToQeAECmhB4AjWY0j16ktrwIPQCATAk9ABrLaB79SGm5EXoANJLIYxCpLD9CDwAgU0IPgMYxmscwpLAcCT0AgEwJPQCATAk9ABrFbluGqe7Lk9ADAMiU0AMAyJTQA6Ax7LZlFOq8XAk9AIBMCT0AgEwJPQAawW5bRqmuy5fQAwDIlNADAMiU0AMge3bbMg51XM6EHgBApoQeAECmhB4AWbPblnGq2/Im9AAAMiX0AAAyJfQAADIl9AAAMiX0AAAyJfQAADIl9AAAMiX0AMiWa+gxCXVa7oQeAECmhB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKamW61WeRcAgFzExjOiBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhB0C2Xr13b3kPxqdOy53QAwDIlNADAMiU0AMAyJTQAwDIlNADAMiU0AMAyJTQAwDIlNADIGuupcc41W15E3oAAJkSegAAmRJ6AGTP7lvGoY7LmdADAMiU0AMAyJTQA6AR7L5llOq6fAk9AIBMCT0AgEwJPQAaw+5bRqHOy5XQAwDIlNADAMiU0AOgUey+ZZjqvjwJPQCATAk9AIBMCT0AGsfuW4YhheVI6AEAZEroAdBIRvUYRCrLj9ADoLHEHv1IabkRegAAmRJ6ADSaUT16kdryIvQAADIl9ABoPKN6bEeKy4nQAwDIlNADgDajemwm1eVD6AEAZEroAUDJqB4bSXm5EHoA0EHs0Sn15UHoAQBkSugBwDpG9YhyWA6EHgBsQOw1Wy7zX+gBQBdir5lymu9CDwA2IfaaJbf5LfQAADIl9ABgC0b1miHH+Sz0AGAbxF7ecp2/tQ+9mfmpcOtUD7f50+XfhGaZPn0szO7ff8P6sGv/fJhZXCy/A5prZf3o2FZM7Q+72tuLXjeCYi9POc9XI3qQgZn5/WH3wSNh5uzZ8pkVO86eCLNzc2HXMbFHUy0WAwYr60f5VOFs2HHiYNjdDr6dPa4eYi8vuc/P2ofe0vFWeKG1+e3KofKbw6Fw5fiB8j40xOn5MHtiZQu2fOhUuFStGwunwtV9xdNhx5G5MGuwmwaamW8v+yfKB/uOhisL1bZjob3tiCvI2XDLnNhrqibMx/RH9IqN3MrdpVPHw9LKXWiIxbDz/eUK0I68y+0POtdXHoWw50C4dmZhNfZm3n/MED7Nsngs7Kwir71+vHDmcFjaUz4Oe8LS8TPh0tEy9j7Y+ychsZe2psy/xP/fPx1mD65t5K4YzKNxFsKOcnfU0gMbrQDtjdmDZemdPR92rNyDRph+7JFymd8Xrr5n4w3E9cMPrQwQnHh/z6N6kdhLU5PmW9KhNzN/MMwU97qvxNAU0087Dg867Thffgra92DHSN56c2G5+Cx0NuxYKJ7omdhLS9PmV7qh1zEkv3z0Q+Fa15UYclZtpNobtUce22CFXgwzj5Qbu0MPOLSBZtp719ohDTfZE66X2/1BPiyJvTQ0cT4lG3ozHzxSDskfCtcOqzyaak+49tChsBzvnj0SZjsvF7G4GHbOz4Vbis4z6g0bWwzT51bu7Tjf55BeSezVW1PnT6KhdzrMrB5ga5SChjtwPFxeOBqW9rU3VMXlIsrrhM21Iy+uJ/sOhSsLZ4x60zjLd5fD3SceLQ/z2cjaca7DEGNC8NVL0+dJEXqtVqt4kIrpY+93bB50mH7sfJjutrE6ey7MLDh+j+a5/o4HV0a7w4mws8u1JNe2J8Ml9uqhyfOharsER/Q6jjna9ABbaIbiYrBHThSHMiwf7biOXsd1wmYOumgyDbTncLhWXmc1Xkvyxt+EES+kvL+97gxxOG8dsTdZpv+K9EJv8bHVq5svPXR4kwNsoQE6riO5fHQhXD7ccR29G64TFjd07+zr8hGQsqXja9eSvOHQhql4IeWzxXqzdtH94RMbk2G6r0ku9Naui3QoLNlrS8PNPLp6sGrXk5JWrxMWR/YeU3o0zZ7iwuFXjpYnLZWWi2NXW+0PR+3tSnkyxvLdcyt3hixGh/AYD9P6ZomFXudu27tvWGmh0TY9KanjEiwDnlUIadoTlg4fD5dXD2toB96Z4+WhP8M9GWMzAmS0TN+NJRZ6ayvk8oPvsNsWgMEsPl1uCPeFpXeM/qBvI07DZ5puLq3QW10hQ7h+l7MwoNfLR4xq1xTU0un58ni8/V2PT107HGhvuD7GzYo4GZxpuD1phd5C9bs694Vl2yvo8fIR4xmxgNqYqw7x6XJ86uKxMFuedbt89D0TuSarWOmdadabpEJv+unyiNkxf/KC2url8hGHHnLRZJrlhvXjnWH29FrsTZ8+FnbNlb9had/RcGXCv2FJvGzNNOpPUqG39guqnYgBla0uHxEtHzoVLh13mjrNs3T8VPFbY6rrSa6sG1Nh98Eq8g6FK2fqc6kuIbMx06V/ae26rWz6C6qhaeLlI1rh0qn4a9DK4ivFS0hcPbUQLrcjzzpDMx1oh1x5eZXO1aO9rizFC4zHs2/Lp+rCyNUa02JwU88880zrqaeeCvfdd1/5VAgPnzwZjszPh4ut7f9qtNumyjsdLqb1m9VgZKwf0J31Y2vPnqsOXcqfsLvRdteP5y5cCHfMzpaPQnjiiSfCPffck+iIHgA0SDWylWsE5f7+JknoAUBCcomiXN5H3U23etg9CwDUR2qxlNrrTV1sPCN6AJCBukZUXV9XU0x98YtfbJ07d87JGDBC1g/ozvoxfsM8uUPAjdYgJ2Psbc8boQdjYP2A7qwf0N2goWfXLQBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmhB4AQKaEHgBApoQeAECmpr74xS+2zp07F+67777yqRAePnkyHJmfDxdbrfKZrd02Vd4BAGBkLm6QZ89duBDumJ0tH4XwxBNPhL179xrRAwDIldADAMiU0AMAyJTQAwDI1EhPxtjoYEFoIusHdGf9gO62u344GQMAoGGEHgBApoQeAECmpls9HIcHAEAaYuMZ0QMAyJTQAwDIlNADAMiU0AMAyJTQAwDIlNADAMiU0AMAyJTQAwDIlNADAMiU0AMAyJTQAwDIlNADAMiU0AMAyNTUF77whdZnPvOZcN9995VPhfDwyZPhyPx8uNhqlc9s7bap8k6Hi9v/6/Th2XPnynuDe/XeveU9RsH6Ad1ZP6C77a4fz124EO6YnS0fhfDEE0+EH//xH18JvXPtYLj//vvLLwm9uhhmyA1KCA7G+gHdWT+gu0FDz67bmolxV93qpK6vCwDoTujVQGoRldrrBYCmEnoTkkss5fI+ACBHQm+Mco+i3N8fAKRG6I1YU+Onqe8bAOpE6I2IyFljWgDAZAi9ERA1GzNdAGC8hN4QGbnammkEAOMj9IZAvPTONAOA0RN6AxArgzMNAWB0hF4fxMnwmaYAMHxCr0diZLRMXwAYHqG3TUacxse0BoDhEHrbIDomw3QHgMFMt1qt8i4bERuTZfoDQO+qvjOitwmRUQ/mw3jE6VzdyI/5C80k9DbgP8P6MU9Ga/20Na3zYv5Ccwm9dfwHWG/mz/iY1nkwH6HZhF4H/yGmwXwaH9M6beYfIPRK/kNMi/k1XK/eu7e8dzPTOk2bzbfN5jeQF6HXZkOWJvNtuMRePkQeUGl86NmApc38Gy6xlz6RB3RqdOjZcOXBfBwusZcukQes19jQs8HKi/k5XGIvPSIP2EgjQ8+GKk/m63CJvXSIPKCbxoWeDVTezN/hEnv1J/KAzTQq9GyYmsF8Hi6xV18iD9hKo0/GALZH7NWPyAO2ozGhZ2PULOb38Im9+hB5wHY1IvRshJrJfB8+sTd5Ig/YrlarlX/o2fg0m/k/fGJvckQe0KusQ89Gh8hyMHxib/xEHtAPJ2MAfRF74yPygH5lG3o2NHSyPIyG2Bs9kQcMIsvQs4FhI5aL0RB7oyPygEHZdQsMTOwNn8gDhiG70LNRYTOWj9ERe8Mj8oBhMaIHDI3YG5zIA4Ypq9CzIWE7LCejJfb6J/KAYTOiBwyd2OudyANGIZvQs/GgF5aX0RN72yfygFExogeMjNjbmsgDRimL0LPBoB+Wm/EQe92JPGDUkg89G2sGYfkZD7F3M5EHjEMReq1Wq3gAMCpib43IA0atarukR/SMxjAMlqPxEXsiDxgvJ2MAY9Xk2BN5wLgJPWDsmhh7Ig+YhGRDL/dP/oyX5Wn8mhR7Ig+YFCN6wMQ0IfZEHjBJQg+YqJxjT+QBk5Zk6OXySZ96sVxNTo6xJ/KAOjCiB9RCTrEn8oC6EHpAbeQQeyIPqJPkQi+1T/akxfI1eSnHnsgD6saIHlA7KcaeyAPqSOgBtZRS7Ik8oK6SCr26fpInL5az+kgh9kQeUGdG9IBaq3PsiTyg7qZbrVZ5F6Ce6hh7Ig+ou9h4yYzoTfqTO81ieaufOsWeyANSYdctkIw6xJ7IA1Ii9ICkTDL2RB6QGqEHJGcSsSfygBQJPSBJ44w9kQekSugByRpH7Ik8IGVCD0jaKGNP5AGpE3pA8kYReyIPyEESoTfop3Loh+UuLcOMPZEH5MKIHpCNYcSeyANyIvSArAwSeyIPyI3QA7LTT+yJPCBHQg/IUi+xJ/KAXAk9IFvbiT2RB+RM6AFZ62Vkr5PIA3Ig9IDs9RptIg/IhdADGmG78SbygJwIPaAxtoo4kQfkRugBjbHZMXnRVl8HSI3QAxphuxEn9oCcCD0ge73Gm9gDciH0gKxtFm2bHZMn9oAcCD0gW9uJPLEH5EzoAVnqZSRP7AG5EnpAdnqJvIrYA3Ik9ICs9BN5FbEH5EboAdkYJPIqYg/ISRKht93/oGGYLHdpGUbkVcQekAsjekDyhhl5FbEH5GC61WqVdwHSM4rIq4g9IGWx8YzoAckaZeRVxB6QMqEHJGkckVcRe0CqhB6QnHFGXkXsASkSekBSJhF5FbEHpEboAcmYZORVxB6QkmRCb1z/iUNkeaufOkReRewBqTCiB9RenSKvIvaAFAg9oNbqGHkVsQfUXVKhN+n/1GkGy1l91DnyKmIPqDMjekAtpRB5FbEH1JXQA2onpciriD2gjpILvbr+J08eLF+Tl2LkVcQeUDdG9IDaSDnyKmIPqBOhB9RCDpFXEXtAXRSh12q1igepSO0/fdJguZqcnCKvIvaASarazogeMFE5Rl5F7AGTJvSAick58ipiD5ikZEMvl40A9WB5Gr8mRF5F7AGTYkQPGLsmRV5F7AGTIPSAsWpi5FXEHjBuSYde7hsFxsNyND5NjryK2APGyYgeMBYib43YA8Yl+dAzGsMgLD/jIfJuJvaAcchiRM/Gmn5YbsZD5HUn9oBRs+sWGBmRtzWxB4xSNqFno0EvLC+jJ/K2T+wBo2JEDxg6kdc7sQeMQlahZwPCdlhORkvk9U/sAcNmRA8YGpE3OLEHDNN0q9Uq7+bBxoTNWD5GR+QNj9gDhiE2nhE9YGAib/jEHjAMWYaeDQsbsVyMhsgbHbEHDCrbET0bGDpZHkZD5I2e2AMGYdct0BeRNz5iD+hX1qFnY0NkORg+kTd+Yg/oR/YjejY6zWb+D5/ImxyxB/SqEbtubXyayXwfPpE3eWIP6EVjjtGzEWoW83v4RF59iD1gu5yMAWxJ5NWP2AO2o1GhZ4PUDObzcIm8+hJ7wFYaN6Jnw5Q383e4RF79iT1gM2mH3uKxsGtqKtw6tT/sXCyf2wYbqDw1eb5OH9vfXg/iurDJbf50+d3bI/LSIfa2YfF02Dm/v9xmlLf9+8Ps6UXHMJG1hJfvxbDznUfCjvJRr2yo8tL0+bnj/Nny3nCIvPSIve6mT8+HXXMHwy0nzt64zTh7NswcnAu79x8Te2Qr2WV7+tg7wy0DbttssPJgPp4OMyfin/vC1YVWeKHV5Xb8QPHdWxF56RJ7G2hH3u6DJ1YCb9+hcGV1HVkIV47uK74lnD0Sdvc44g2pSDP0Fo+F2SPDGcGw4Uqb+de2+PTKirzvwbC0p3imbyIvfWKv02LY+f7iU1B7/TgaLp053rGO7AlLh8+ES1XsnXg0zKzcg6wkGHpru2yXDh1aeWpANmBpMt9KC+dXRiv23hWuF0/0R+TlQ+yVTn+w3POzL1z90OEN14/r73gwLBf3ToQZg3pkKLnQW91le+hUuPLAynPDYEOWFvNrzfTTKxvupQe2t2t2IyIvP2IvhJlHq9G8TUa79xwOl8vDG670vwpBbaUVequ7bA+FK9s83qgXNmhpMJ9utHIixqGwPHfzWYW79s+HmcUeTklfx7ROW7Pn32KYLnt2+cF3DDTaDSlLKPQ6dtmeOh6WVp4cOhu2ejN/1qtOxDgRbtngrMIdZ0+E2bm5sOtY77FnWuehufNxob38r9y7flcczmuHXzz7dv/Nl1eBnCUTejfssh3x8Hr8j9FGrl7Mky6qEzEK+8LS0VPhUnWW7cJCuHJo5UDzHUc2j73109a0zksj5+8N68Zi2Ll/buXs2zL+CuXlVW51eRUylsayPeJdtt3Y2NWD+bCJ6kSMtqVTZ8KVwwfWdlHt2ROWjrefK89Z2nHkg5ueVRinc3UjP02evzHm4kDB8qGOD0Lx8irlByGXVyFnCYTeeHbZdmOjN1mm/xYOHC83Wt0PJF86fqpcb06EnX3swoUcLB9dCJePd3wQipdXaX8QWru8yvt7+g1LkIrah944d9l2IzYmw3QflrmwXG7LdpxfWLkDTbLvaLhyeOPTbq8ffqj8IHQ2zDym9MhPvUNvQrtsNxKjQ3iMh2k9bHvCdZOTJtv0GpM+CJG3Wofe9GOPlMcfnQizHZeMWL0dLK+R1P4kdstc+dyIj7MQIKNl+gJDsWct7pbvnivvbcQHIfKWxskYNWPEafhM01HquJ7Yphs8yMl2R+rW1g/IUa1D7/rhM6sHmm94O1X9CrSOX+Y+5rNyxclgTMPBzMyXI9mbXR5i8bEwU15SYuV6YtAEe8LSg9WJFpv9Htu16+35IESOjOgNgVjpnWk2HEsPlB92zj4SZjY8jnztrPV4QPrVyR7qCmPV+XtsZ7sc1jMzf7CMwEPhWpcTNiBlQm+IxMvWTKMhO/CecLUYtIjHqa67yv/i6TC7f+X6YdHSQxv/UnfI1p7D4crq5VMOhl3zx8L06iqy2I689jpTHuq9fPQ9Y798F4zDdKvVKu8yLEJmY6bLKOwJ1z50KiyVsVdc5b86WWnuYLnLdl9YOrXgF7bTSPEQoNXfEHPiSNhdnbg3NdeOvJVPQfFCypeN5pEpI3ojYuRqjWkxYnsOhCtn2iF39NDqwecr9rU3YEfDlYX2hu6AjRjNVVwYeSF+ILphBWmvL4fC1faHoHghZcjV1NNPP9367Gc/G97ylreUT4Xw8MmT4cj8fLjYw2jfbVPlnQ4XDRbe4NlzzTm1S9jdyPoB3Vk/oLvtrh/PXbgQ7pidLR+F8Pjjj4e7777biN44VSNbuUZQ7u8PAFIj9CYklyjK5X0AQI6EXg2kFkupvV4AaCqhVzN1jai6vi4AoDsnYyRsmCd3CLjRsn5Ad9YP6G7QkzGEHoyB9QO6s35Ad4OGnl23AACZEnoAAJkSegAAmRJ6AACZEnoAAJkSegAAmSpCr9XDZVQAAKi/2HdG9AAAMiX0AAAyJfQAADIl9AAAMiX0AAAyJfQAADIl9AAAMiX0AAAyJfQAADIl9AAAMjX19NNPt86fPx/e+ta3lk+F8PDJk+HI/Hy42MOvRrttqrwDAMDIXNwgz567cCHcMTtbPgrh8ccfD69//euN6AEA5EroAQBkSugBAGSmVR5+J/QAADI10pMxNjpYEJrI+gHdWT+gu+2uH+tPxvjYxz4W7r77biN6AAC5EnoAAJkSegAAmRJ6AACZEnoAAJkSegAAmRJ6AACZEnoAAJkSegAAmRJ6AACZEnoAAJkSegAAmZputfzmaACA3MTGM6IHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkKki9FqtVvEAAID0VW1nRA8AIFNCDwAgU0IPACBTQg8AIFNCDwAgU0IPACBTjQq9Z8+dW72RH/MXAG7UmNBbv/EXA3kxfwHgZo3edSsG8mA+AsDGGn+MnkhIm/kHAN01JvRevXdvee9mYiFNm823zeY3ADRFo0b0xF4+RB4AbK1xu27FXvpEHgBsTyOP0RN76RJ5ALB9061Wq7zbLGIvPSIPAHrT6LNuxV46RB4A9K7RoReJvfoTeQDQn8aHXiT26kvkAUD/hF5J7NWPyAOAwQi9DmKvPkQeAAxO6K0j9iZP5AHAcAi9DYi9yRF5ADA8Qq8LsTd+Ig8AhkvobULsjY/IA4DhE3pbEHujJ/IAYDSE3jaIvdEReQAwOkJvm8Te8Ik8ABgtodcDsTc8Ig8ARk/o9UjsDU7kAcB4CL0+iL3+iTwAGI9WqyX0+iX2eifyAGC8hN4AxN72iTwAGD+hNyCxtzWRBwCTIfSGQOx1J/IAYHKE3pCIvZuJPACYLKE3RGJvjcgDgMkTekMm9kQeANSF0BuBJseeyAOA+hB6I9LE2BN5AFAvQm+EmhR7Ig8A6kfojVgTYk/kAUA9Cb0xyDn2RB4A1JfQG5McY0/kAUC9Cb0xyin2RB4A1J/QG7McYk/kAUAahN4EpBx7Ig8A0iH0JiTF2BN5AJAWoTdBKcWeyAOA9Ai9CUsh9kQeAKRJ6NVAnWNP5AFAuoReTdQx9kQeAKRN6NVInWJP5AFA+oRezdQh9kQeAORB6NXQJGNP5AFAPoReTU0i9kQeAORF6NXYOGNP5AFAfoRezY0j9kQeAORJ6CVglLEn8gAgX0IvEaOIPZEHAHmbbrVa5V3qbpixJ/IAIG+x8YzoJWYYsSfyAKAZhF6CBok9kQcAzSH0EtVP7Ik8AGgWoZewXmJP5AFA8wi9xG0n9kQeADST0MtALyN7nUQeAORN6GWi12gTeQCQP6GXke3Gm8gDgGYQepnZKuJEHgA0h9DLzGbH5EVbfR0AyIfQy8h2I07sAUAzCL1M9BpvYg8A8if0MrBZtG12TJ7YA4C8Cb3EbSfyxB4ANFMReq1Wq3hAWnoZyRN7ANA8RvQS1UvkVcQeADSL0EtQP5FXEXsA0BxCLzGDRF5F7AFAMwi9hAwj8ipiDwDyJ/QSMczIq4g9AMib0EvAKCKvIvYAIF9Cr+ZGGXkVsQcAeRJ6NTaOyKuIPQDIj9CrqXFGXkXsAUBehF4NTSLyKmIPAPIh9GpmkpFXEXsAkAehVyN1iLyK2AOA9Am9mqhT5FXEHgCkTejVQB0jryL2ACBdQm/C6hx5FbEHAGlptVrFn0JvglKIvIrYA4D0CL0JSSnyKmIPANIi9CYgxciriD0ASIfQG7OUI68i9gAgDUJvjHKIvIrYA4D6E3pjklPkVcQeANSb0BuDHCOvIvYAoL6E3ojlHHkVsQcA9ST0RqgJkVcRewBQP0JvRJoUeRWxBwD1IvRGoImRVxF7AFAfQm/Imhx5FbEHAPUg9IZI5K0RewAweUJvSETezcQeAEzWdKvVKu/SL5HXndgDgMkxojcgkbc1sQcAkyH0BiDytk/sAcD4Cb0+ibzeiT0AGC+h1weR1z+xBwDjI/R6JPIGJ/YAYDyEXg9E3vCIPQAYPaG3TSJv+MQeAIyW0NsGkTc6Yg8ARkfobUHkjZ7YA4DREHqbEHnjI/YAYPiEXhcib/zEHgAMl9DbgMibHLEHAMMj9NYReZMn9gBgOIReB5FXH2IPAAYn9Eoir37EHgD0r9VqCb1I5NWX2AOA/jU+9ERe/Yk9AOhPwqG3GHbunwq3Ts2HmfKZXom8dIi9LSwuhplj82FXsU6s3Xbtb68fi+X3QINNn16/fuwPu+ZPh2nrB5lLNvSmj70z3HK2fNAHkZcesddF3IDNzYXZIyfCjnXrxI6zJ8LsXDv4jtma0VQrgwK7D65fP86GHScOht1z+8NOqwcZSzL0po/tD7uP9F95Ii9dYm+dxWNhV9yAxfv7DoUrCwvhhVZr5bZwKlzdV3xX2HGkHYKnV+5Dk8zMz5WDAvvC0qkb14+lYv04G26Z63/PENRdYqG32F5pRV7Tib010489shJ5oR15Z46HpT17ikeFPQfCtTMLq7E38/5jDsqlWdofhHaeWLm7dOpMuHLgxvXjypl27BUPToSdRr3JVDL/70+fPhZm98+F2RMrkbe8r9x69UDk5UPsRe0PPo+UH3oOPVBusNbbE649dGjl7tlHHK9Ho3R+EFo6UNxZ50BYKlePHecXVu5AZhIJvdPhloNHwkzH8Pvlh3oLM5GXH7HXjrgz5W6o4xtuxVbM3R2Wy7vQJNcPnyl31R7v8kEI8pfUnpzlQ6fCpda64fcBiby0mX/bsHC+HNUAbtC5a/eBTT4sQcISCb0D4epCK1w+fiBcL58ZBpGQB/NxczOPlluysDdcH95nJEhaPBxo19yR8kSmo+GqziNTyYzoDbqBWh8D4iAv5m8XHSMW3Y/jg6aorr8aL7eyEnnLR0+FS2cOD3UQAeokqV23g4ob/+pGfszf9dobtXeWIxbxrNzNjuODRlgIO87uK07mq45b3XHkYJidd0Y6+bJsQ5biyEV1/bB4aQkHo0M8DOhK60y4fKZ9a7XCpVNHi+DbceJI2L1f7JEnyzVk58bIWz66EK4YzIObXD9wOFw+VV1+6Ei4xUXFydD01NRUeRdI382Rd/mwMzCgqwPvWbuo+KNKj7zExjOiB9k4XVxUfG13rciDre0J1x3WS8aEHuRgsR15Uwc7LireGur1JiFfi2G6Wb85kYYRepC8duTNtSOvuL8vXF2IFxUvHkCjzcyvXErl1k1PtIhn4q7cW757buUOZEToQdLiMXk3Rt41A3lQWHpg6xMtZubX1p+ld1h5yI/Qg4RNH3tnxzF5Ig9u0HmixcH9Yfb04tpGb7H9IWm+/Vx5QfHlox+y/pAloQfJOh1uOVJWXtvMwXI31Sa3XccWy++GJtgTrp05FZaK2DvbXkfmwu5qfZibC7ecWFl/nJ1OzoQepGrxaSswbOlAuHJmIVw6dSgsl6N7K/aF5UNHw5X4e9RFHhlLdztx4Hh4odVq31zxn4bac7i4uv/KerC9mw0azbQnXG9vMy6f6VwfzoTLxw+HJasEmTMgAACQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkCmhBwCQKaEHAJApoQcAkKnpVqtV3gUAICdG9AAAMjV1/vz51uc+97nw9re/vXwqhIdPngxH5ufDxR5G+26bKu8AADAyFzfIs+cuXAh3zM6Wj0L427/92/D617/eiB4AQK6EHgBApoQeAECmhhZ6G+0vBgBgeHrtranPfvazxckYb3vb28qn+jsZAwCAyVh/MsZHP/rR8LrXvW5lRM+19AAA8lG13fTU1FR4yUteEq5du1Y8AQBAumLTzczMhNh4xYjezp07w6VLl4ovAgCQrhdffLFou6gY0XvpS19aPNnJ8XkAAOmJg3ex7WLjTT399NOtK1euhGeeeSa88Y1vDLOzs+G59mMAANIRT8aITffJT34y3HnnnUXTFaF3/fr18M1vfjMsLy+He++9t/x2AABS8uSTT4bp6enwile8ovizOEYvDu297GUvC9/5znfCpz/96aIGAQBIQ2y32HDf/va3i6YrdtvG28LCQiueghtH8+Lt+eefL0b3Xv3qV4fdu3eHW2+9dfWAPgAA6iGeXRvPsYi3Z599Ntx+++1F5O3YsaO4xRG9qcXFxSL04u7bGHrxz6tXrxZ/KY7wxfvf/e53ix9YXZNlmAb5maN4PZsZ9783CNOGcTL/RyN+Gid9qczHlJa3cb/WQf69UbzW+DPjLV5CJQ7GxWPx4uBcvB/jroq8IvQ+//nPt/+PvjH04i2q7nc+7qbf/+gnsYEY92tN6T32axLvcdy8R1Ix7o1gSiYxbVKZHylNmxgwqej3PW7296r3X8VcEXTt74+3zsgrnv+Xf/mX4mSM+B98Z9jFx53PRdWfG+l3AzHIhmUS/2Y/xv3vRU14j/1K6bX2qwnvke763bA0wSSmTSrzownTpt9/b5DXOYp/MwZc9WcRc+3v7fxz7TYd/j9rDTNSDszKJAAAAABJRU5ErkJggg=="
    }
   },
   "cell_type": "markdown",
   "id": "d84715aa",
   "metadata": {},
   "source": [
    "## 4.1. Think-Three-Steps-Ahead AI in Tic Tac Toe\n",
    "Consider the example as illustrated in the figure below. It's Player X's turn to move, and if it chooses cell 2 as its next move, it can create a double attack and gurantee a win in three steps: Player X can win by placing a piece in cell 3 or cell 8 in three steps and win the game. Player O can either block cell 3 or cell 8, but not both. \n",
    "\n",
    "![think3.png](attachment:think3.png) "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb8383c8",
   "metadata": {},
   "source": [
    "We define a function *ttt_think3()* in the local module *ch02util*. The function checks if there is a move that wins the game for the AI player right away or if the opponent has a winning move two steps ahead. If not, the funnction looks three steps ahead and chooses the move that most likely leads to a win for the current player.  \n",
    "\n",
    "Take a look at the function *ttt_think3()* in the file *ch02util.py*. In particular, the following lines of code allows the agent to look three steps ahead:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6f8a7eff",
   "metadata": {},
   "source": [
    "```Python\n",
    "def ttt_think3(env):\n",
    "    ...\n",
    "    # look three steps ahead\n",
    "    w3=[]\n",
    "    for m1 in env.validinputs:\n",
    "        for m2 in env.validinputs:\n",
    "            for m3 in env.validinputs:\n",
    "                if m1!=m2 and m1!=m3 and m2!=m3:\n",
    "                    env_copy=deepcopy(env)\n",
    "                    s,r,done,_=env_copy.step(m1) \n",
    "                    s,r,done,_=env_copy.step(m2)   \n",
    "                    s,r,done,_=env_copy.step(m3)                    \n",
    "                    if done and r!=0:\n",
    "                        w3.append(m1) \n",
    "    # Choose the most frequent winner\n",
    "    if len(w3)>0:\n",
    "        return max(w3,key=w3.count)                \n",
    "    # Return random move otherwise\n",
    "    return env.sample()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f207d6d",
   "metadata": {},
   "source": [
    "## 4.2. Test the Think-Three-Steps-Ahead AI in Tic Tac Toe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "26a3bd78",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "game state is \n",
      "[[0 0 0]\n",
      " [0 1 0]\n",
      " [0 0 0]]\n",
      "Player O, what's your move?4\n",
      "game state is \n",
      "[[ 0  0  0]\n",
      " [-1  1  0]\n",
      " [ 1  0  0]]\n",
      "Player O, what's your move?9\n",
      "game state is \n",
      "[[ 0  0 -1]\n",
      " [-1  1  0]\n",
      " [ 1  1  0]]\n",
      "Player O, what's your move?3\n",
      "the game outcome is 1\n"
     ]
    }
   ],
   "source": [
    "from utils.ch02util import ttt_think3\n",
    "\n",
    "reward=one_ttt_game(ttt_think3, ttt_manual)\n",
    "print(f\"the game outcome is {reward}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "bdb68745",
   "metadata": {},
   "outputs": [],
   "source": [
    "results=[]\n",
    "for i in range(1000):\n",
    "    # think-three-steps-ahead AI moves first at even i\n",
    "    if i%2==0:\n",
    "        result=one_ttt_game(ttt_think3, ttt_think2)\n",
    "        # record game outcome\n",
    "        results.append(result)\n",
    "    # think-three-steps-ahead AI moves second otherwise\n",
    "    else:\n",
    "        result=one_ttt_game(ttt_think2, ttt_think3)\n",
    "        # record negative game outcome\n",
    "        results.append(-result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "0be4d7ec",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "think-three-steps-ahead AI won 270 games\n",
      "think-three-steps-ahead AI lost 179 games\n",
      "the game was tied 551 times\n"
     ]
    }
   ],
   "source": [
    "# count how many times think-three-steps-ahead AI won\n",
    "wins=results.count(1)\n",
    "print(f\"think-three-steps-ahead AI won {wins} games\")\n",
    "# count how many times it lost\n",
    "losses=results.count(-1)\n",
    "print(f\"think-three-steps-ahead AI lost {losses} games\")\n",
    "# count tie games\n",
    "ties=results.count(0)\n",
    "print(f\"the game was tied {ties} times\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}