isolation game code -- occlusions found via numpy functions

isolation_game_state.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 307,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The blackcellmagic extension is already loaded. To reload it, use:\n",
      "  %reload_ext blackcellmagic\n"
     ]
    }
   ],
   "source": [
    "%load_ext blackcellmagic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 484,
   "metadata": {},
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "import numpy as np\n",
    "\n",
    "xlim, ylim = 3, 2  # Board dims are x = [0, xlim) and y = [0, ylim)\n",
    "\n",
    "\n",
    "class GameState:\n",
    "    \"\"\"\n",
    "    Attributes\n",
    "    ----------\n",
    "    TODO: Copy in your implementation from the previous quiz\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self):\n",
    "        self.player_id = 0  # 0 or 1, in this two player game\n",
    "        self.board = np.zeros([ylim, xlim]).astype(\"int\")\n",
    "        self.board[-1, -1] = 1  # block the lower right corner\n",
    "        self.locs = {0: None, 1: None}\n",
    "\n",
    "        # helper precomputation\n",
    "\n",
    "        # get index values of each board element\n",
    "        self.x_idxes = np.array([list(range(xlim))]).repeat(ylim, axis=0)\n",
    "        self.x_idxes_rev = np.flip(self.x_idxes, axis=1)\n",
    "        self.y_idxes = np.array([list(range(ylim))]).transpose().repeat(xlim, axis=1)\n",
    "\n",
    "        # identify diagonals\n",
    "        self.left_to_right_diagonals = self.x_idxes + self.y_idxes\n",
    "        self.right_to_left_diagonals = self.x_idxes_rev + self.y_idxes\n",
    "\n",
    "    def actions(self):\n",
    "        \"\"\" Return a list of legal actions for the active player \n",
    "        \n",
    "        You are free to choose any convention to represent actions,\n",
    "        but one option is to represent actions by the (row, column)\n",
    "        of the endpoint for the token. For example, if your token is\n",
    "        in (0, 0), and your opponent is in (1, 0) then the legal\n",
    "        actions could be encoded as (0, 1) and (0, 2).\n",
    "        \"\"\"\n",
    "        loc = self.locs[self.player()]\n",
    "        return self.liberties(loc)\n",
    "\n",
    "    def player(self):\n",
    "        \"\"\" Return the id of the active player \n",
    "        \n",
    "        Hint: return 0 for the first player, and 1 for the second player\n",
    "        \"\"\"\n",
    "        return self.player_id\n",
    "\n",
    "    def result(self, action):\n",
    "        \"\"\" Return a new state that results from applying the given\n",
    "        action in the current state\n",
    "        \n",
    "        Hint: Check out the deepcopy module--do NOT modify the\n",
    "        objects internal state in place\n",
    "        \"\"\"\n",
    "        # An action is an (x,y) tuple that shows where a piece will land\n",
    "        assert action in self.actions(), \"Attempted forecast of illegal move\"\n",
    "        x, y = action\n",
    "        new_state = deepcopy(self)\n",
    "        new_state.locs[new_state.player()] = (x, y)\n",
    "        new_state.board[y, x] = 1\n",
    "        new_state.player_id ^= 1\n",
    "\n",
    "        return new_state\n",
    "\n",
    "    def terminal_test(self):\n",
    "        \"\"\" return True if the current state is terminal,\n",
    "        and False otherwise\n",
    "        \n",
    "        Hint: an Isolation state is terminal if _either_\n",
    "        player has no remaining liberties (even if the\n",
    "        player is not active in the current state)\n",
    "        \"\"\"\n",
    "        liberties_0, liberties_1 = self.liberties(self.locs[0]), self.liberties(self.locs[1])\n",
    "        return len(liberties_0) == 0 or len(liberties_1) == 0\n",
    "\n",
    "    def starburst(self, loc):\n",
    "        \"\"\"\n",
    "        Create masks in the shape of a star burst, centered at a loc.\n",
    "        These represent the spaces a player at a loc could move into,\n",
    "        given no obstructions.\n",
    "        \n",
    "        The starburst is broken into a '+' shaped crossbar, \n",
    "        a left-to-right diagonal '/', and a right-to-left diagonal '\\'\n",
    "        \"\"\"\n",
    "\n",
    "        x, y = loc\n",
    "\n",
    "        # A starburst is made of a vertical/horizontal crossbar and two diagonals.\n",
    "        # The crossbar is simple, just get all elems in the same row or column:\n",
    "        crossbar = np.logical_or(self.x_idxes == x, self.y_idxes == y).astype('int')\n",
    "\n",
    "        # To get the diagonals, find the left-to-right and right-to-left\n",
    "        # diagonals centered at our loc\n",
    "        left_to_right = (self.left_to_right_diagonals == x + y).astype('int')\n",
    "        diagonal_offset = self.left_to_right_diagonals[y, x] - self.right_to_left_diagonals[y, x]\n",
    "        right_to_left = (self.right_to_left_diagonals == x + (y - diagonal_offset)).astype('int')\n",
    "        \n",
    "        assert (right_to_left + left_to_right)[y, x] == 2 # make sure the diagonals intersect as expected\n",
    "\n",
    "        # return the starburst\n",
    "        return crossbar, left_to_right, right_to_left\n",
    "\n",
    "    def liberties(self, loc):\n",
    "        \"\"\" Return a list of all open cells in the\n",
    "        neighborhood of the specified location.  The list \n",
    "        should include all open spaces in a straight line\n",
    "        along any row, column or diagonal from the current\n",
    "        position. (Tokens CANNOT move through obstacles\n",
    "        or blocked squares in queens Isolation.)\n",
    "        \n",
    "        Note: if loc is None, then return all empty cells\n",
    "        on the board\n",
    "        \"\"\"\n",
    "\n",
    "        if loc is None:\n",
    "            return self.mask_to_idxes(self.board != 1)  # return empty cells\n",
    "        x, y = loc\n",
    "        assert x < xlim and y < ylim\n",
    "\n",
    "        # If loc is real then find unobstructed nodes on rays from that loc\n",
    "\n",
    "        # First get a starburst centered at a location,\n",
    "        # representing the free nodes.\n",
    "        crossbar, left_to_right, right_to_left = self.starburst(loc)\n",
    "\n",
    "        # Find rays that are occluded by taking the board state and seeing\n",
    "        # what's in the path of the rays.\n",
    "        board_copy = deepcopy(self.board)\n",
    "\n",
    "        occlusions_left_to_right = board_copy + left_to_right == 2\n",
    "        occlusions_right_to_left = board_copy + right_to_left == 2\n",
    "        occlusions_crossbar = board_copy + crossbar == 2\n",
    "\n",
    "        # We cannot go beyond the closest occlusions (in either direction)\n",
    "        # for either the crossbar or the diagonals\n",
    "\n",
    "        crossbar_occlusions_x_idxes = self.x_idxes[occlusions_crossbar]\n",
    "        crossbar_occlusions_y_idxes = self.y_idxes[occlusions_crossbar]\n",
    "\n",
    "        crossbar_occlusions_x_distances = crossbar_occlusions_x_idxes - x\n",
    "        crossbar_occlusions_y_distances = crossbar_occlusions_y_idxes - y\n",
    "\n",
    "        truncated_crossbar = self.get_truncated_crossbar(\n",
    "            loc, crossbar, crossbar_occlusions_x_distances, crossbar_occlusions_y_distances\n",
    "        )\n",
    "\n",
    "        # Get diagonal occlusions and truncate the diagonals\n",
    "\n",
    "        left_to_right_occlusions_x_idxes = self.x_idxes[occlusions_left_to_right]\n",
    "        right_to_left_occlusions_x_idxes = self.x_idxes[occlusions_right_to_left]\n",
    "\n",
    "        left_to_right_occlusions_x_distances = self.x_idxes[occlusions_left_to_right] - x\n",
    "        right_to_left_occlusions_x_distances = self.x_idxes[occlusions_right_to_left] - x\n",
    "\n",
    "        truncated_diagonals = self.get_truncated_diagonals(\n",
    "            loc,\n",
    "            left_to_right,\n",
    "            right_to_left,\n",
    "            left_to_right_occlusions_x_distances,\n",
    "            right_to_left_occlusions_x_distances,\n",
    "        )\n",
    "\n",
    "        # liberties are the indices of what's left on the starburst, after\n",
    "        # we block rays with whatever occlusions are on the board\n",
    "\n",
    "        occluded_starburst = np.logical_or(truncated_crossbar, truncated_diagonals)\n",
    "        occluded_starburst[y, x] = 0  # We also must eliminate where we already are!\n",
    "\n",
    "        return self.mask_to_idxes(occluded_starburst)\n",
    "\n",
    "    def mask_to_idxes(self, mask):\n",
    "        free_x_idxes = self.x_idxes[mask]\n",
    "        free_y_idxes = self.y_idxes[mask]\n",
    "\n",
    "        return list(zip(free_x_idxes, free_y_idxes))\n",
    "\n",
    "    def get_truncated_diagonals(\n",
    "        self,\n",
    "        loc,\n",
    "        left_to_right,\n",
    "        right_to_left,\n",
    "        left_to_right_occlusions_x_distances,\n",
    "        right_to_left_occlusions_x_distances,\n",
    "    ):\n",
    "        x, y = loc\n",
    "\n",
    "        # Take advantage of the fact that an occlusion on a diagonal will have\n",
    "        # an x-distance from us equal to a y_distance\n",
    "        ltr_left_distance, ltr_right_distance = self.get_distance_limits(\n",
    "            left_to_right_occlusions_x_distances\n",
    "        )\n",
    "        ltr_mask = self.make_square_mask(\n",
    "            ltr_left_distance + x, ltr_right_distance + x, -np.inf, np.inf\n",
    "        )\n",
    "        truncated_left_to_right = np.logical_and(ltr_mask, left_to_right)\n",
    "\n",
    "        # The same for rtl diagonal\n",
    "        rtl_left_distance, rtl_right_distance = self.get_distance_limits(\n",
    "            right_to_left_occlusions_x_distances\n",
    "        )\n",
    "        rtl_mask = self.make_square_mask(\n",
    "            rtl_left_distance + x, rtl_right_distance + x, -np.inf, np.inf\n",
    "        )\n",
    "        truncated_right_to_left = np.logical_and(rtl_mask, right_to_left)\n",
    "\n",
    "        return np.logical_or(truncated_left_to_right, truncated_right_to_left)\n",
    "\n",
    "    def get_truncated_crossbar(\n",
    "        self, loc, crossbar, crossbar_occlusions_x_distances, crossbar_occlusions_y_distances\n",
    "    ):\n",
    "        x, y = loc\n",
    "\n",
    "        # Get the closest occlusions in the negative and positive x directions\n",
    "        left_distance, right_distance = self.get_distance_limits(crossbar_occlusions_x_distances)\n",
    "\n",
    "        # Get the closest occlusions in the negative and positive y directions\n",
    "        up_distance, down_distance = self.get_distance_limits(crossbar_occlusions_y_distances)\n",
    "\n",
    "        mask = self.make_square_mask(\n",
    "            left_distance + x, right_distance + x, up_distance + y, down_distance + y\n",
    "        )\n",
    "\n",
    "        return np.logical_and(crossbar, mask)\n",
    "\n",
    "    def make_square_mask(self, xmin, xmax, ymin, ymax):\n",
    "        x_mask = np.logical_and(self.x_idxes > xmin, self.x_idxes < xmax)\n",
    "        y_mask = np.logical_and(self.y_idxes > ymin, self.y_idxes < ymax)\n",
    "\n",
    "        return np.logical_and(x_mask, y_mask)\n",
    "\n",
    "    def get_distance_limits(self, occlusion_distances):\n",
    "\n",
    "        negatives = occlusion_distances[occlusion_distances < 0]\n",
    "        minimum = None\n",
    "        if len(negatives) != 0:\n",
    "            minimum = np.max(negatives)\n",
    "        else:\n",
    "            minimum = -np.inf  # Consider the farthest bound your minimum, INCLUSIVE\n",
    "\n",
    "        positives = occlusion_distances[occlusion_distances > 0]\n",
    "        maximum = None\n",
    "        if len(positives) != 0:\n",
    "            maximum = np.min(positives)\n",
    "        else:\n",
    "            maximum = np.inf  # Consider the farthest bound your minimum\n",
    "\n",
    "        return minimum, maximum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 485,
   "metadata": {},
   "outputs": [],
   "source": [
    "gs = GameState()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 486,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1)]"
      ]
     },
     "execution_count": 486,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs.actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 487,
   "metadata": {},
   "outputs": [],
   "source": [
    "gs_1 = gs.result(gs.actions()[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 488,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 0), (2, 0), (0, 1), (1, 1)]"
      ]
     },
     "execution_count": 488,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_1.actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 489,
   "metadata": {},
   "outputs": [],
   "source": [
    "gs_2 = gs_1.result(gs_1.actions()[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 490,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 1, 0],\n",
       "       [0, 0, 1]])"
      ]
     },
     "execution_count": 490,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_2.board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 491,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 1), (1, 1)]"
      ]
     },
     "execution_count": 491,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_2.actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 492,
   "metadata": {},
   "outputs": [],
   "source": [
    "gs_3 = gs_2.result(gs_2.actions()[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 493,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 1, 0],\n",
       "       [1, 0, 1]])"
      ]
     },
     "execution_count": 493,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_3.board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 494,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 0), (1, 1)]"
      ]
     },
     "execution_count": 494,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_3.actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 495,
   "metadata": {},
   "outputs": [],
   "source": [
    "gs_4 = gs_3.result(gs_3.actions()[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 496,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 1)]"
      ]
     },
     "execution_count": 496,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_4.actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 497,
   "metadata": {},
   "outputs": [],
   "source": [
    "gs_5 = gs_4.result(gs_4.actions()[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 498,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 1, 1],\n",
       "       [1, 1, 1]])"
      ]
     },
     "execution_count": 498,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_5.board"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 499,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 499,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs_5.actions()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 500,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 2],\n",
       "       [1, 2, 3]])"
      ]
     },
     "execution_count": 500,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs.left_to_right_diagonals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 501,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2, 1, 0],\n",
       "       [3, 2, 1]])"
      ]
     },
     "execution_count": 501,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs.right_to_left_diagonals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 502,
   "metadata": {},
   "outputs": [],
   "source": [
    "xlim, ylim = 3, 2\n",
    "\n",
    "m = GameState()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 503,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 2],\n",
       "       [1, 2, 3]])"
      ]
     },
     "execution_count": 503,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m.left_to_right_diagonals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 504,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[2, 1, 0],\n",
       "       [3, 2, 1]])"
      ]
     },
     "execution_count": 504,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gs.right_to_left_diagonals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}