ch07PositionEvaluationFunction.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "653089c9",
   "metadata": {},
   "source": [
    "# Chapter 7: Position Evaluation in MiniMax\n",
    "\n",
    "\n",
    "\n",
    "***\n",
    "*“Part of the improvement between ‘96 and ‘97 is we detected more patterns in a chess position and could put values on them and therefore evaluate chess positions more accurately.”*\n",
    "\n",
    "-- Murray Campbell, who programmed Deep Blue's evaluation function\n",
    "***\n",
    "\n",
    "\n",
    "\n",
    "What you'll learn in this chapter:\n",
    "\n",
    "* What is a position evaluation function\n",
    "* Designing a game strategy using an evaluation function in Connect Four\n",
    "* Adding a position evaluation function to MiniMax with depth pruning\n",
    "* Assessing the effectiveness of MiniMax augmented by an evaluation function\n",
    "\n",
    "The IBM Chess engine Deep Blue had two matches with then-world\n",
    "Chess champion Garry Kasparov. In the first match, which was held\n",
    "in Philadelphia in 1996, Deep Blue lost to Kasparov. In the second match in New\n",
    "York City in 1997, Deep Blue defeated Kasparov. What changed, you may wonder?\n",
    "According to Murray Campbell, the team member who programmed Deep Blue’s\n",
    "evaluation function, the Chess engine had a more accurate evaluation function in\n",
    "1997 compared to 1996.\n",
    "\n",
    "With depth pruning and alpha-beta pruning to reduce the time it needs to make\n",
    "a move, the MiniMax algorithm can produce fairly powerful agents with advancements\n",
    "in computing hardware. For example, “the 1997 version of Deep Blue searched\n",
    "between 100 million and 200 million positions per second, depending on the type of\n",
    "position. The system could search to a depth of between six and eight pairs of moves—\n",
    "one white, one black—to a maximum of 20 or even more pairs in some situations.”\n",
    "According to an article in Scientific America by Larry Greenemeier in 2017.\n",
    "\n",
    "What made Deep Blue even more powerful was the position evaluation function it\n",
    "used. In Chapter 6, we assume that the game is tied when the number of depth is\n",
    "reached and the game is not over. In many real-world games, however, even when the\n",
    "game is not over, we usually have a good estimate of the outcome of the game based\n",
    "on heuristics. For example, in Chess, we can count the value of each game piece.\n",
    "Whichever side has a higher value of pieces tends to win.\n",
    "\n",
    "In this chapter, we introduce the concept of the position evaluation function and\n",
    "apply it to the Connect Four game. We show that our evaluation function makes\n",
    "the MiniMax agent much stronger. Specifically, you’ll use an evaluation function that\n",
    "we’ll develop in Chapter 15: the function takes a game board as the input, and returns\n",
    "an evaluation between −1 and 1. An evaluation of −1 means that the current player\n",
    "will lose for sure, while an evaluation of 1 means that the current player will win for\n",
    "sure. An evaluation of 0 means the game is most likely to be tied.\n",
    "\n",
    "You’ll first use the evaluation function to design a game strategy: an agent armed with\n",
    "this evaluation function will make hypothetical moves and evaluate each future game\n",
    "state. The agent will then select the next move that leads to the highest evaluation\n",
    "of the future game state. We show that the agent beats random moves 97 percent\n",
    "of the time. We then augment the MiniMax algorithm with the position evaluation\n",
    "function. We’ll use the evaluation function to evaluate the future game state when\n",
    "the number of depth is reached and the game is not over. The evaluation function\n",
    "provides a more accurate assessment of the game state, hence allowing the MiniMax\n",
    "agent to make more intelligent moves. We show that the augmented MiniMax agent\n",
    "beats the earlier version of the MiniMax agent without position evaluation in seven\n",
    "out of ten games.\n",
    "\n",
    "We’ll also use the concept of position evaluation extensively in later chapters of this\n",
    "book. For example, AlphaGo trained two deep neural networks when designing its\n",
    "game strategies: a policy network and a value network. The value network was used\n",
    "to assess the strength of each next board position, and this, in turn, helps AlphaGo\n",
    "select the best next move.   "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "282ad876",
   "metadata": {},
   "source": [
    "# 1. What Are Position Evaluation Functions?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4db31da9",
   "metadata": {},
   "source": [
    "## 1.1. A Model to Predict Outcome in Connect Four"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "089ca5fb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: tensorflow in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (2.12.0)\n",
      "Requirement already satisfied: tensorflow-intel==2.12.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow) (2.12.0)\n",
      "Requirement already satisfied: setuptools in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (67.8.0)\n",
      "Requirement already satisfied: typing-extensions>=3.6.6 in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (4.5.0)\n",
      "Requirement already satisfied: tensorflow-estimator<2.13,>=2.12.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (2.12.0)\n",
      "Requirement already satisfied: keras<2.13,>=2.12.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (2.12.0)\n",
      "Requirement already satisfied: protobuf!=4.21.0,!=4.21.1,!=4.21.2,!=4.21.3,!=4.21.4,!=4.21.5,<5.0.0dev,>=3.20.3 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (4.23.2)\n",
      "Requirement already satisfied: libclang>=13.0.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (16.0.0)\n",
      "Requirement already satisfied: numpy<1.24,>=1.22 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (1.23.5)\n",
      "Requirement already satisfied: grpcio<2.0,>=1.24.3 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (1.54.2)\n",
      "Requirement already satisfied: astunparse>=1.6.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (1.6.3)\n",
      "Requirement already satisfied: wrapt<1.15,>=1.11.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (1.14.1)\n",
      "Requirement already satisfied: six>=1.12.0 in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (1.16.0)\n",
      "Requirement already satisfied: google-pasta>=0.1.1 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (0.2.0)\n",
      "Requirement already satisfied: gast<=0.4.0,>=0.2.1 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (0.4.0)\n",
      "Requirement already satisfied: packaging in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (23.0)\n",
      "Requirement already satisfied: opt-einsum>=2.3.2 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (3.3.0)\n",
      "Requirement already satisfied: h5py>=2.9.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (3.8.0)\n",
      "Requirement already satisfied: absl-py>=1.0.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (1.4.0)\n",
      "Requirement already satisfied: termcolor>=1.1.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (2.3.0)\n",
      "Requirement already satisfied: jax>=0.3.15 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (0.4.12)\n",
      "Requirement already satisfied: flatbuffers>=2.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (23.5.26)\n",
      "Requirement already satisfied: tensorflow-io-gcs-filesystem>=0.23.1 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (0.31.0)\n",
      "Requirement already satisfied: tensorboard<2.13,>=2.12 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorflow-intel==2.12.0->tensorflow) (2.12.3)\n",
      "Requirement already satisfied: wheel<1.0,>=0.23.0 in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from astunparse>=1.6.0->tensorflow-intel==2.12.0->tensorflow) (0.38.4)\n",
      "Requirement already satisfied: scipy>=1.7 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from jax>=0.3.15->tensorflow-intel==2.12.0->tensorflow) (1.10.1)\n",
      "Requirement already satisfied: importlib-metadata>=4.6 in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from jax>=0.3.15->tensorflow-intel==2.12.0->tensorflow) (6.0.0)\n",
      "Requirement already satisfied: ml-dtypes>=0.1.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from jax>=0.3.15->tensorflow-intel==2.12.0->tensorflow) (0.2.0)\n",
      "Requirement already satisfied: werkzeug>=1.0.1 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (2.3.6)\n",
      "Requirement already satisfied: tensorboard-data-server<0.8.0,>=0.7.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (0.7.0)\n",
      "Requirement already satisfied: markdown>=2.6.8 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (3.4.3)\n",
      "Requirement already satisfied: google-auth<3,>=1.6.3 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (2.19.1)\n",
      "Requirement already satisfied: requests<3,>=2.21.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (2.31.0)\n",
      "Requirement already satisfied: google-auth-oauthlib<1.1,>=0.5 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (1.0.0)\n",
      "Requirement already satisfied: urllib3<2.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from google-auth<3,>=1.6.3->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (1.26.16)\n",
      "Requirement already satisfied: cachetools<6.0,>=2.0.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from google-auth<3,>=1.6.3->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (5.3.1)\n",
      "Requirement already satisfied: rsa<5,>=3.1.4 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from google-auth<3,>=1.6.3->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (4.9)\n",
      "Requirement already satisfied: pyasn1-modules>=0.2.1 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from google-auth<3,>=1.6.3->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (0.3.0)\n",
      "Requirement already satisfied: requests-oauthlib>=0.7.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from google-auth-oauthlib<1.1,>=0.5->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (1.3.1)\n",
      "Requirement already satisfied: zipp>=0.5 in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from importlib-metadata>=4.6->jax>=0.3.15->tensorflow-intel==2.12.0->tensorflow) (3.11.0)\n",
      "Requirement already satisfied: certifi>=2017.4.17 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from requests<3,>=2.21.0->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (2023.5.7)\n",
      "Requirement already satisfied: idna<4,>=2.5 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from requests<3,>=2.21.0->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (3.4)\n",
      "Requirement already satisfied: charset-normalizer<4,>=2 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from requests<3,>=2.21.0->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (3.1.0)\n",
      "Requirement already satisfied: MarkupSafe>=2.1.1 in c:\\users\\hlliu2\\anaconda3\\envs\\mla\\lib\\site-packages (from werkzeug>=1.0.1->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (2.1.1)\n",
      "Requirement already satisfied: pyasn1<0.6.0,>=0.4.6 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from pyasn1-modules>=0.2.1->google-auth<3,>=1.6.3->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (0.5.0)\n",
      "Requirement already satisfied: oauthlib>=3.0.0 in c:\\users\\hlliu2\\appdata\\roaming\\python\\python39\\site-packages (from requests-oauthlib>=0.7.0->google-auth-oauthlib<1.1,>=0.5->tensorboard<2.13,>=2.12->tensorflow-intel==2.12.0->tensorflow) (3.2.2)\n"
     ]
    }
   ],
   "source": [
    "!pip install tensorflow"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "c1337aea",
   "metadata": {},
   "outputs": [],
   "source": [
    "import tensorflow as tf\n",
    "\n",
    "model=tf.keras.models.load_model('files/value_conn.h5')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c28f0581",
   "metadata": {},
   "source": [
    "Dowload the file *ch07util.py* from the book's GitHub repository and place it in the folder /Desktop/ai/utils/ on your computer. In it, we have defined a *prediction_eval()* function to generate an evaluation of the game state: "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c36194d7",
   "metadata": {},
   "source": [
    "```python\n",
    "def position_eval(env,model):\n",
    "    # obtain the current state, reshape it      \n",
    "    state=env.state.reshape(-1,7,6,1)\n",
    "    pred=model.predict(state,verbose=0)\n",
    "    # prob(current player wins)-prob(opponent wins)\n",
    "    evaluation=pred[0][1]-pred[0][2]\n",
    "    return evaluation \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eee28a4e",
   "metadata": {},
   "source": [
    "## 1.2. Play A Game with the Position Evaluations\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "cbac434b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "from utils.ch07util import position_eval\n",
    "\n",
    "def eval_move(env,model):\n",
    "    # create a dictionary to hold all values\n",
    "    values={}\n",
    "    # iteratre through all possible next moves\n",
    "    for m in env.validinputs:\n",
    "        # make a hypothetical move\n",
    "        env_copy=deepcopy(env)\n",
    "        s,r,d,_=env_copy.step(m)\n",
    "        # evaluate the hypothetical game state\n",
    "        value=position_eval(env_copy,model)\n",
    "        # add value to the dictionary\n",
    "        if env.turn==\"red\":\n",
    "            values[m]=round(value,5)\n",
    "        # multiply value by -1 for yellow\n",
    "        else:\n",
    "            values[m]=round(-value,5)\n",
    "    # choose the move with the highest evaluation    \n",
    "    action = max(values,key=values.get)        \n",
    "    return action, values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d54069ab",
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the current state is \n",
      "[[0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]]\n",
      "evaluations of future moves are\n",
      "{1: 0.57383, 2: 0.58247, 3: 0.52876, 4: 0.86937, 5: 0.7459, 6: 0.12794, 7: 0.09338}\n",
      "the red player chose column 4\n",
      "what's your move?4\n",
      "the yellow player chose column 4\n",
      "the current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0  1  0  0  0]]\n",
      "evaluations of future moves are\n",
      "{1: 0.92464, 2: 0.96153, 3: 0.97883, 4: 0.94346, 5: 0.98155, 6: 0.96366, 7: 0.94616}\n",
      "the red player chose column 5\n",
      "what's your move?4\n",
      "the yellow player chose column 4\n",
      "the current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0  1  1  0  0]]\n",
      "evaluations of future moves are\n",
      "{1: 0.91422, 2: 0.9949, 3: 0.99994, 4: 0.95631, 5: 0.97798, 6: 0.99123, 7: 0.97749}\n",
      "the red player chose column 3\n",
      "what's your move?2\n",
      "the yellow player chose column 2\n",
      "the current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0 -1  1  1  1  0  0]]\n",
      "evaluations of future moves are\n",
      "{1: 0.99909, 2: 0.99899, 3: 0.99689, 4: 0.99205, 5: 0.99792, 6: 1.0, 7: 0.99976}\n",
      "the red player chose column 6\n",
      "the current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0 -1  1  1  1  1  0]]\n",
      "the red player won\n"
     ]
    }
   ],
   "source": [
    "from utils.conn_simple_env import conn\n",
    "\n",
    "env=conn()\n",
    "state=env.reset()  \n",
    "print(f\"the current state is \\n{state.T[::-1]}\") \n",
    "while True:\n",
    "    action, values=eval_move(env,model)\n",
    "    print(f\"evaluations of future moves are\\n{values}\")   \n",
    "    print(f\"the red player chose column {action}\")\n",
    "    state, reward, done, info=env.step(action)\n",
    "    if done: \n",
    "        print(f\"the current state is \\n{state.T[::-1]}\")\n",
    "        print(\"the red player won\")\n",
    "        break    \n",
    "    # the opponent chooses random moves   \n",
    "    action=int(input(\"what's your move?\"))\n",
    "    print(f\"the yellow player chose column {action}\")\n",
    "    state, reward, done, info=env.step(action)\n",
    "    print(f\"the current state is \\n{state.T[::-1]}\")\n",
    "    if done: \n",
    "        if reward==-1:\n",
    "            print(\"the yellow player won\")\n",
    "        else:\n",
    "            print(\"game over, it's a tie\")\n",
    "        break "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f7ff3c0",
   "metadata": {},
   "source": [
    "## 1.3. The Position Evaluation Function vs Random Moves\n",
    "To have a better understanding of how intelligent the position evaluation function is, we simulate 100 games. The opponent chooses random moves, as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "45be0572",
   "metadata": {},
   "outputs": [],
   "source": [
    "results=[]\n",
    "for i in range(100):\n",
    "    env=conn()\n",
    "    state=env.reset() \n",
    "    if i%2==0:\n",
    "        action=env.sample()\n",
    "        state, reward, done, info=env.step(action)\n",
    "    while True:\n",
    "        action, values=eval_move(env,model)\n",
    "        state, reward, done, info=env.step(action)\n",
    "        if done: \n",
    "            results.append(abs(reward))\n",
    "            break     \n",
    "        action=env.sample()\n",
    "        state, reward, done, info=env.step(action)        \n",
    "        if done: \n",
    "            results.append(-abs(reward))\n",
    "            break  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6f1bf179",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the evaluation agent won 97 games\n",
      "the evaluation agent lost 3 games\n",
      "the game was tied 0 times\n"
     ]
    }
   ],
   "source": [
    "# count how many times the evaluation agent won\n",
    "wins=results.count(1)\n",
    "print(f\"the evaluation agent won {wins} games\")\n",
    "# count how many times the evaluation agent lost\n",
    "losses=results.count(-1)\n",
    "print(f\"the evaluation agent 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": "5cbe6000",
   "metadata": {},
   "source": [
    "# 2. MINIMAX WITH POSITION EVALUATION IN CONNECT FOUR"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7710c0ce",
   "metadata": {},
   "source": [
    "## 2.1. The eval_payoff_conn() Function\n",
    "\n",
    "The *eval_payoff_conn()* function is defined as follows. It's saved in the file *h07util.py* that you just downloaded. "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b2c5975",
   "metadata": {},
   "source": [
    "```python\n",
    "def eval_payoff_conn(env,model,reward,done,depth,alpha,beta):\n",
    "    # if the game has ended after the previous player's move\n",
    "    if done:\n",
    "        # if it's not a tie\n",
    "        if reward!=0:\n",
    "            return -1\n",
    "        else:\n",
    "            return 0\n",
    "    # If the maximum depth is reached, assume tie game\n",
    "    if depth==0:\n",
    "        if env.turn==\"red\":\n",
    "            return position_eval(env,model) \n",
    "        else:\n",
    "            return -position_eval(env,model)    \n",
    "    if alpha==None:\n",
    "        alpha=-2\n",
    "    if beta==None:\n",
    "        beta=-2\n",
    "    if env.turn==\"red\":\n",
    "        best_payoff = alpha\n",
    "    if env.turn==\"yellow\":\n",
    "        best_payoff = beta         \n",
    "    # iterate through all possible moves\n",
    "    for m in env.validinputs:\n",
    "        env_copy=deepcopy(env)\n",
    "        state,reward,done,info=env_copy.step(m)  \n",
    "        # If I make this move, what's the opponent's response?\n",
    "        opponent_payoff=eval_payoff_conn(env_copy,model,\\\n",
    "                             reward,done,depth-1,alpha,beta)\n",
    "        # Opponent's payoff is the opposite of your payoff\n",
    "        my_payoff=-opponent_payoff \n",
    "        if my_payoff > best_payoff:        \n",
    "            best_payoff = my_payoff\n",
    "            if env.turn==\"red\":\n",
    "                alpha=best_payoff\n",
    "            if env.turn==\"yellow\":\n",
    "                beta=best_payoff       \n",
    "        if alpha>=-beta:\n",
    "            break        \n",
    "    return best_payoff \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "db6cead4",
   "metadata": {},
   "source": [
    "## 2.2. The MiniMax_conn_eval() Function\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b402953",
   "metadata": {},
   "source": [
    "```python\n",
    "def MiniMax_conn_eval(env,model,depth=3):\n",
    "    values={} \n",
    "    # iterate through all possible next moves\n",
    "    for m in env.validinputs:\n",
    "        # make a hypothetical move and see what happens\n",
    "        env_copy=deepcopy(env)\n",
    "        state,reward,done,info=env_copy.step(m) \n",
    "        # If current player wins with m, take it.\n",
    "        if done and reward!=0:\n",
    "            return m \n",
    "        # See what's the best response from the opponent\n",
    "        opponent_payoff=eval_payoff_conn(env_copy,\\\n",
    "                             model,reward,done,depth,-2,-2)  \n",
    "        # Opponent's payoff is the opposite of your payoff\n",
    "        my_payoff=-opponent_payoff \n",
    "        values[m]=my_payoff\n",
    "    # pick the move with the highest value       \n",
    "    best_move=max(values,key=values.get)\n",
    "    return best_move  \n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0838d4e3",
   "metadata": {},
   "source": [
    "## 3. Test Minimax with Position Evaluations in Connect Four\n",
    "\n",
    "\n",
    "## 3.1 Play Aganist the Evaluation-Augmented MiniMax \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "20703e88",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Current state is \n",
      "[[0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 0 0 0 0]\n",
      " [0 0 0 1 0 0 0]]\n",
      "What's your move, player yellow?4\n",
      "Player yellow chose column 4\n",
      "Current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0  1  0  0  0]]\n",
      "Current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  1  1  0  0  0]]\n",
      "What's your move, player yellow?4\n",
      "Player yellow chose column 4\n",
      "Current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  1  1  0  0  0]]\n",
      "Current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  1  1  1  0  0  0]]\n",
      "What's your move, player yellow?5\n",
      "Player yellow chose column 5\n",
      "Current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  1  1  1 -1  0  0]]\n",
      "Current state is \n",
      "[[ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0  0  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 0  0  0 -1  0  0  0]\n",
      " [ 1  1  1  1 -1  0  0]]\n",
      "Player red won!\n"
     ]
    }
   ],
   "source": [
    "from utils.ch07util import MiniMax_conn_eval\n",
    "\n",
    "# Initiate the game environment\n",
    "env=conn()\n",
    "state=env.reset()   \n",
    "# Play a full game manually\n",
    "while True:\n",
    "    action = MiniMax_conn_eval(env,model)   \n",
    "    state, reward, done, info = env.step(action)\n",
    "    print(f\"Current state is \\n{state.T[::-1]}\")\n",
    "    if done: \n",
    "        print(\"Player red won!\")\n",
    "        break    \n",
    "    action = int(input(\"What's your move, player yellow?\")) \n",
    "    print(f\"Player yellow chose column {action}\")\n",
    "    state, reward, done, info = env.step(action)\n",
    "    print(f\"Current state is \\n{state.T[::-1]}\")\n",
    "    if done: \n",
    "        if reward==-1:\n",
    "            print(\"Player yellow won!\")\n",
    "        else:\n",
    "            print(\"Game over, it's a tie!\")\n",
    "        break     "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "58df6cd7",
   "metadata": {},
   "source": [
    "## 3.2 Effectiveness of Position Evaluations\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0c3d78a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "from utils.ch06util import MiniMax_conn\n",
    "\n",
    "results=[]\n",
    "for i in range(10):\n",
    "    state=env.reset() \n",
    "    if i%2==0:\n",
    "        action=MiniMax_conn(env,depth=3)    \n",
    "        state,reward,done,_=env.step(action)\n",
    "    while True:\n",
    "        action=MiniMax_conn_eval(env,model,depth=3) \n",
    "        state,reward,done,_=env.step(action)\n",
    "        if done: \n",
    "            results.append(abs(reward))\n",
    "            break \n",
    "        action=MiniMax_conn(env,depth=3) \n",
    "        state,reward,done,_=env.step(action)\n",
    "        if done: \n",
    "            results.append(-abs(reward))\n",
    "            break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "787481ac",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "MiniMax with evaluation won 7 games\n",
      "MiniMax with evaluation lost 2 games\n",
      "the game is tied 1 times\n"
     ]
    }
   ],
   "source": [
    "# count how many times MiniMax with evaluation won\n",
    "wins=results.count(1)\n",
    "print(f\"MiniMax with evaluation won {wins} games\")\n",
    "# count how many times MiniMax with evaluation lost\n",
    "losses=results.count(-1)\n",
    "print(f\"MiniMax with evaluation lost {losses} games\")\n",
    "# count tie games\n",
    "ties=results.count(0)\n",
    "print(f\"the game is 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
}