08_RL_Minimax_TicTacToe.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Minimax State"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "class State:\n",
    "    def __init__(self, pieces=None, enemy_pieces=None):\n",
    "        self.pieces = pieces if pieces != None else [0]*9\n",
    "        self.enemy_pieces = enemy_pieces if enemy_pieces != None else [0]*9\n",
    "        \n",
    "    def piece_count(self, pieces):\n",
    "        count = 0\n",
    "        for i in pieces:\n",
    "            if( i == 1 ):\n",
    "                count += 1\n",
    "                \n",
    "        return count\n",
    "    \n",
    "    def is_lose(self):\n",
    "        def is_comp(x, y, dx, dy):\n",
    "            for k in range(3):\n",
    "                if( (y<0) or (2<y) or (x<0) or (2<x) or (self.enemy_pieces[x+y*3] == 0) ):\n",
    "                    return False\n",
    "                x = x + dx\n",
    "                y = y + dy\n",
    "            return True\n",
    "        \n",
    "        if( is_comp(0, 0, 1, 1) or is_comp(0, 2, 1, -1) ):\n",
    "            return True\n",
    "        \n",
    "        for i in range(3):\n",
    "            if( is_comp(0, i, 1, 0) or is_comp(i, 0, 0, 1) ):\n",
    "                return True\n",
    "            \n",
    "        return False\n",
    "    \n",
    "    def is_draw(self):\n",
    "        return ( (self.piece_count(self.pieces) + self.piece_count(self.enemy_pieces)) == 9 )\n",
    "    \n",
    "    def is_done(self):\n",
    "        return self.is_lose() or self.is_draw()\n",
    "    \n",
    "    def next(self, action):\n",
    "        pieces = self.pieces.copy()\n",
    "        pieces[action] = 1\n",
    "        \n",
    "        return State(self.enemy_pieces, pieces)\n",
    "    \n",
    "    def legal_actions(self):\n",
    "        actions = []\n",
    "        for i in range(9):\n",
    "            if( (self.pieces[i] == 0) and (self.enemy_pieces[i] == 0) ):\n",
    "                actions.append(i)\n",
    "        \n",
    "        return actions\n",
    "    \n",
    "    def is_first_player(self):\n",
    "        return ( self.piece_count(self.pieces) == self.piece_count(self.enemy_pieces) )\n",
    "    \n",
    "    def __str__(self):\n",
    "        ox = ('o', 'x') if self.is_first_player() else ('x', 'o')\n",
    "        str = '   '\n",
    "        \n",
    "        for i in range(9):\n",
    "            if( self.pieces[i] == 1 ):\n",
    "                str += ox[0]\n",
    "            elif( self.enemy_pieces[i] == 1 ):\n",
    "                str += ox[1]\n",
    "            else:\n",
    "                str += '-'\n",
    "            if( i%3 == 2):\n",
    "                str += '\\n   '\n",
    "        \n",
    "        return str"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Starategy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def random_action(state):\n",
    "    legal_actions = state.legal_actions()\n",
    "    \n",
    "    return legal_actions[random.randint(0, len(legal_actions)-1)]\n",
    "\n",
    "def mini_max(state):\n",
    "    if( state.is_lose() ):\n",
    "        return -1\n",
    "    \n",
    "    if( state.is_draw() ):\n",
    "        return 0\n",
    "    \n",
    "    best_score = -1 * float('inf')\n",
    "    for action in state.legal_actions():\n",
    "        score = -mini_max(state.next(action))\n",
    "        if( score > best_score ):\n",
    "            best_score = score\n",
    "            \n",
    "    return best_score\n",
    "\n",
    "def mini_max_action(state):\n",
    "    best_action = 0\n",
    "    best_score = -1 * float('inf')\n",
    "    \n",
    "    str = ['', '']\n",
    "    for action in state.legal_actions():\n",
    "        score = -mini_max(state.next(action))\n",
    "        if( score > best_score ):\n",
    "            best_action = action\n",
    "            best_score = score\n",
    "        \n",
    "        str[0] = '{}{:2d},'.format(str[0], action)\n",
    "        str[1] = '{}{:2d},'.format(str[1], score)\n",
    "    \n",
    "    print('action: ', str[0], '\\nscore: ', str[1], '\\n')\n",
    "    \n",
    "    return best_action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Play Game"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "action:   0, 1, 2, 3, 4, 5, 6, 7, 8, \n",
      "score:   0, 0, 0, 0, 0, 0, 0, 0, 0, \n",
      "\n",
      "<Step: 01>\n",
      "   o--\n",
      "   ---\n",
      "   ---\n",
      "   \n",
      "==================================================\n",
      "\n",
      "<Step: 02>\n",
      "   ox-\n",
      "   ---\n",
      "   ---\n",
      "   \n",
      "==================================================\n",
      "\n",
      "action:   2, 3, 4, 5, 6, 7, 8, \n",
      "score:   0, 1, 1, 0, 1, 0, 0, \n",
      "\n",
      "<Step: 03>\n",
      "   ox-\n",
      "   o--\n",
      "   ---\n",
      "   \n",
      "==================================================\n",
      "\n",
      "<Step: 04>\n",
      "   oxx\n",
      "   o--\n",
      "   ---\n",
      "   \n",
      "==================================================\n",
      "\n",
      "action:   4, 5, 6, 7, 8, \n",
      "score:   1, 1, 1, 1, 1, \n",
      "\n",
      "<Step: 05>\n",
      "   oxx\n",
      "   oo-\n",
      "   ---\n",
      "   \n",
      "==================================================\n",
      "\n",
      "<Step: 06>\n",
      "   oxx\n",
      "   oox\n",
      "   ---\n",
      "   \n",
      "==================================================\n",
      "\n",
      "action:   6, 7, 8, \n",
      "score:   1,-1, 1, \n",
      "\n",
      "<Step: 07>\n",
      "   oxx\n",
      "   oox\n",
      "   o--\n",
      "   \n",
      "==================================================\n",
      "\n"
     ]
    }
   ],
   "source": [
    "state = State()\n",
    "\n",
    "step = 1\n",
    "while True:\n",
    "    if( state.is_done() ):\n",
    "        break\n",
    "        \n",
    "    if( state.is_first_player() ):\n",
    "        action = mini_max_action(state)\n",
    "    else:\n",
    "        action = random_action(state)\n",
    "        \n",
    "    state = state.next(action)\n",
    "    \n",
    "    print(\"<Step: {0:02d}>\".format(step))\n",
    "    print(state)\n",
    "    print(\"=\" * 50)\n",
    "    print(\"\")\n",
    "    step += 1"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "rl_practice",
   "language": "python",
   "name": "rl_practice"
  },
  "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}