TD-Gammon000-Backgammon.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Backgammon\n",
    "\n",
    "Quelle: https://github.com/awni/backgammon\n",
    "\n",
    "Erweitert um das Extrahieren von 192 Features für TD-Gammon"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import time\n",
    "import numpy as np\n",
    "\n",
    "class Game:\n",
    "\n",
    "    LAYOUT = \"0-2-o,5-5-x,7-3-x,11-5-o,12-5-x,16-3-o,18-5-o,23-2-x\"\n",
    "    NUMCOLS = 24\n",
    "    QUAD = 6\n",
    "    OFF = 'off'\n",
    "    ON = 'on'\n",
    "    TOKENS = ['x', 'o']\n",
    "\n",
    "    def __init__(self, layout=LAYOUT, grid=None, off_pieces=None, bar_pieces=None, num_pieces=None, players=None):\n",
    "        \"\"\"\n",
    "        Define a new game object\n",
    "        \"\"\"\n",
    "        self.die = Game.QUAD\n",
    "        self.layout = layout\n",
    "        if grid:\n",
    "            self.grid = copy.deepcopy(grid)\n",
    "            self.off_pieces = copy.deepcopy(off_pieces)\n",
    "            self.bar_pieces = copy.deepcopy(bar_pieces)\n",
    "            self.num_pieces = copy.deepcopy(num_pieces)\n",
    "            self.players = players\n",
    "            return\n",
    "        self.players = Game.TOKENS\n",
    "        self.grid = [[] for _ in range(Game.NUMCOLS)]\n",
    "        self.off_pieces = {}\n",
    "        self.bar_pieces = {}\n",
    "        self.num_pieces = {}\n",
    "        for t in self.players:\n",
    "            self.bar_pieces[t] = []\n",
    "            self.off_pieces[t] = []\n",
    "            self.num_pieces[t] = 0\n",
    "\n",
    "    @staticmethod\n",
    "    def new():\n",
    "        game = Game()\n",
    "        game.reset()\n",
    "        return game\n",
    "\n",
    "    # Methode die exakt die 198 Features liefert die in TD-Gammon 0.0 benutzt wurden\n",
    "    # Nach \"Reinforcement Learning: An Introduction\", Sutton & Barto, 2017\n",
    "    def extractFeatures(self, player):\n",
    "        features = []\n",
    "        # 196 Features kodieren den Zustand der Spielfelder, 98 für jeden Spieler\n",
    "        for p in self.players:\n",
    "            # 24 mögliche Brettpositionen\n",
    "            for col in self.grid:\n",
    "                # 4 Features kodieren eine Stelle auf dem Spielbrett\n",
    "                feats = [0.] * 4\n",
    "                if len(col) > 0 and col[0] == p:\n",
    "                    # 0,1,2,3,4,5 Steine werden kodiert als\n",
    "                    # 0000, 1000, 1100, 1110, 1110.5, 1111\n",
    "                    # (4. Bit = (n-3)/2)\n",
    "                    for i in range(len(col)):\n",
    "                        if i < 3:\n",
    "                            feats[i] += 1\n",
    "                        else:\n",
    "                            feats[3] = (len(col)-3)/2.0\n",
    "                            break\n",
    "                features += feats\n",
    "            # Anzahl der Steine auf der \"Bar\", n/2\n",
    "            features.append(float(len(self.bar_pieces[p])) / 2.)\n",
    "            # Anzahl der Steine die bereits aus dem Spiel sind, n/15\n",
    "            features.append(float(len(self.off_pieces[p])) / 15.)\n",
    "        # Zwei Features für den derzeitigen Spieler\n",
    "        if player == self.players[0]:\n",
    "            features += [1., 0.]\n",
    "        else:\n",
    "            features += [0., 1.]\n",
    "        return np.array(features).reshape(1, -1)\n",
    "\n",
    "    def roll_dice(self):\n",
    "        return (random.randint(1, self.die), random.randint(1, self.die))\n",
    "\n",
    "    def play(self, players, draw=False):\n",
    "        player_num = random.randint(0, 1)\n",
    "        while not self.is_over():\n",
    "            self.next_step(players[player_num], player_num, draw=draw)\n",
    "            player_num = (player_num + 1) % 2\n",
    "        return self.winner()\n",
    "\n",
    "    def next_step(self, player, player_num, draw=False):\n",
    "        roll = self.roll_dice()\n",
    "\n",
    "        if draw:\n",
    "            self.draw()\n",
    "\n",
    "        self.take_turn(player, roll, draw=draw)\n",
    "\n",
    "    def take_turn(self, player, roll, draw=False):\n",
    "        if draw:\n",
    "            print(\"Player %s rolled <%d, %d>.\" % (player.player, roll[0], roll[1]))\n",
    "            time.sleep(1)\n",
    "\n",
    "        moves = self.get_actions(roll, player.player, nodups=True)\n",
    "        move = player.get_action(moves, self) if moves else None\n",
    "\n",
    "        if move:\n",
    "            self.take_action(move, player.player)\n",
    "\n",
    "    def clone(self):\n",
    "        \"\"\"\n",
    "        Return an exact copy of the game. Changes can be made\n",
    "        to the cloned version without affecting the original.\n",
    "        \"\"\"\n",
    "        return Game(None, self.grid, self.off_pieces,\n",
    "                    self.bar_pieces, self.num_pieces, self.players)\n",
    "\n",
    "    def take_action(self, action, token):\n",
    "        \"\"\"\n",
    "        Makes given move for player, assumes move is valid,\n",
    "        will remove pieces from play\n",
    "        \"\"\"\n",
    "        ateList = [0] * 4\n",
    "        for i, (s, e) in enumerate(action):\n",
    "            if s == Game.ON:\n",
    "                piece = self.bar_pieces[token].pop()\n",
    "            else:\n",
    "                piece = self.grid[s].pop()\n",
    "            if e == Game.OFF:\n",
    "                self.off_pieces[token].append(piece)\n",
    "                continue\n",
    "            if len(self.grid[e]) > 0 and self.grid[e][0] != token:\n",
    "                bar_piece = self.grid[e].pop()\n",
    "                self.bar_pieces[bar_piece].append(bar_piece)\n",
    "                ateList[i] = 1\n",
    "            self.grid[e].append(piece)\n",
    "        return ateList\n",
    "\n",
    "    def undo_action(self, action, player, ateList):\n",
    "        \"\"\"\n",
    "        Reverses given move for player, assumes move is valid,\n",
    "        will remove pieces from play\n",
    "        \"\"\"\n",
    "        for i, (s, e) in enumerate(reversed(action)):\n",
    "            if e == Game.OFF:\n",
    "                piece = self.off_pieces[player].pop()\n",
    "            else:\n",
    "                piece = self.grid[e].pop()\n",
    "                if ateList[len(action) - 1 - i]:\n",
    "                    bar_piece = self.bar_pieces[self.opponent(player)].pop()\n",
    "                    self.grid[e].append(bar_piece)\n",
    "            if s == Game.ON:\n",
    "                self.bar_pieces[player].append(piece)\n",
    "            else:\n",
    "                self.grid[s].append(piece)\n",
    "\n",
    "\n",
    "    def get_actions(self, roll, player, nodups=False):\n",
    "        \"\"\"\n",
    "        Get set of all possible move tuples\n",
    "        \"\"\"\n",
    "        moves = set()\n",
    "        if nodups:\n",
    "            start = 0\n",
    "        else:\n",
    "            start = None\n",
    "\n",
    "        r1, r2 = roll\n",
    "        if r1 == r2: # doubles\n",
    "            i = 4\n",
    "            # keep trying until we find some moves\n",
    "            while not moves and i > 0:\n",
    "                self.find_moves(tuple([r1]*i), player, (), moves, start)\n",
    "                i -= 1\n",
    "        else:\n",
    "            self.find_moves(roll, player, (), moves, start)\n",
    "            self.find_moves((r2, r1), player, (), moves, start)\n",
    "            # has no moves, try moving only one piece\n",
    "            if not moves:\n",
    "                for r in roll:\n",
    "                    self.find_moves((r, ), player, (), moves, start)\n",
    "\n",
    "        return moves\n",
    "\n",
    "    def find_moves(self, rs, player, move, moves, start=None):\n",
    "        if len(rs)==0:\n",
    "            moves.add(move)\n",
    "            return\n",
    "        r, rs = rs[0], rs[1:]\n",
    "        # see if we can remove a piece from the bar\n",
    "        if self.bar_pieces[player]:\n",
    "            if self.can_onboard(player, r):\n",
    "                piece = self.bar_pieces[player].pop()\n",
    "                bar_piece = None\n",
    "                if len(self.grid[r - 1]) == 1 and self.grid[r - 1][-1]!=player:\n",
    "                    bar_piece = self.grid[r - 1].pop()\n",
    "\n",
    "                self.grid[r - 1].append(piece)\n",
    "\n",
    "                self.find_moves(rs, player, move+((Game.ON, r - 1), ), moves, start)\n",
    "                self.grid[r - 1].pop()\n",
    "                self.bar_pieces[player].append(piece)\n",
    "                if bar_piece:\n",
    "                    self.grid[r - 1].append(bar_piece)\n",
    "            return\n",
    "\n",
    "        # otherwise check each grid location for valid move using r\n",
    "        offboarding = self.can_offboard(player)\n",
    "\n",
    "        for i in range(len(self.grid)):\n",
    "            if start is not None:\n",
    "                start = i\n",
    "            if self.is_valid_move(i, i + r, player):\n",
    "\n",
    "                piece = self.grid[i].pop()\n",
    "                bar_piece = None\n",
    "                if len(self.grid[i+r]) == 1 and self.grid[i+r][-1] != player:\n",
    "                    bar_piece = self.grid[i + r].pop()\n",
    "                self.grid[i + r].append(piece)\n",
    "                self.find_moves(rs, player, move + ((i, i + r), ), moves, start)\n",
    "                self.grid[i + r].pop()\n",
    "                self.grid[i].append(piece)\n",
    "                if bar_piece:\n",
    "                    self.grid[i + r].append(bar_piece)\n",
    "\n",
    "            # If we can't move on the board can we take the piece off?\n",
    "            if offboarding and self.remove_piece(player, i, r):\n",
    "                piece = self.grid[i].pop()\n",
    "                self.off_pieces[player].append(piece)\n",
    "                self.find_moves(rs, player, move + ((i, Game.OFF), ), moves, start)\n",
    "                self.off_pieces[player].pop()\n",
    "                self.grid[i].append(piece)\n",
    "\n",
    "    def opponent(self, token):\n",
    "        \"\"\"\n",
    "        Retrieve opponent players token for a given players token.\n",
    "        \"\"\"\n",
    "        for t in self.players:\n",
    "            if t != token:\n",
    "                return t\n",
    "\n",
    "    def is_won(self, player):\n",
    "        \"\"\"\n",
    "        If game is over and player won, return True, else return False\n",
    "        \"\"\"\n",
    "        return self.is_over() and player == self.players[self.winner()]\n",
    "\n",
    "    def is_lost(self, player):\n",
    "        \"\"\"\n",
    "        If game is over and player lost, return True, else return False\n",
    "        \"\"\"\n",
    "        return self.is_over() and player != self.players[self.winner()]\n",
    "\n",
    "    def reverse(self):\n",
    "        \"\"\"\n",
    "        Reverses a game allowing it to be seen by the opponent\n",
    "        from the same perspective\n",
    "        \"\"\"\n",
    "        self.grid.reverse()\n",
    "        self.players.reverse()\n",
    "\n",
    "    def reset(self):\n",
    "        \"\"\"\n",
    "        Resets game to original layout.\n",
    "        \"\"\"\n",
    "        for col in self.layout.split(','):\n",
    "            loc, num, token = col.split('-')\n",
    "            self.grid[int(loc)] = [token for _ in range(int(num))]\n",
    "        for col in self.grid:\n",
    "            for piece in col:\n",
    "                self.num_pieces[piece] += 1\n",
    "\n",
    "    def winner(self):\n",
    "        \"\"\"\n",
    "        Get winner.\n",
    "        \"\"\"\n",
    "        return 0 if len(self.off_pieces[self.players[0]]) == self.num_pieces[self.players[0]] else 1\n",
    "\n",
    "    def is_over(self):\n",
    "        \"\"\"\n",
    "        Checks if the game is over.\n",
    "        \"\"\"\n",
    "        for t in self.players:\n",
    "            if len(self.off_pieces[t]) == self.num_pieces[t]:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def can_offboard(self, player):\n",
    "        count = 0\n",
    "        for i in range(Game.NUMCOLS - self.die, Game.NUMCOLS):\n",
    "            if len(self.grid[i]) > 0 and self.grid[i][0] == player:\n",
    "                count += len(self.grid[i])\n",
    "        if count+len(self.off_pieces[player]) == self.num_pieces[player]:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def can_onboard(self, player, r):\n",
    "        \"\"\"\n",
    "        Can we take a players piece on the bar to a position\n",
    "        on the grid given by roll-1?\n",
    "        \"\"\"\n",
    "        if len(self.grid[r - 1]) <= 1 or self.grid[r - 1][0] == player:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "    def remove_piece(self, player, start, r):\n",
    "        \"\"\"\n",
    "        Can we remove a piece from location start with roll r ?\n",
    "        In this function we assume we are cool to offboard,\n",
    "        i.e. no pieces on the bar and all are in the home quadrant.\n",
    "        \"\"\"\n",
    "        if start < Game.NUMCOLS - self.die:\n",
    "            return False\n",
    "        if len(self.grid[start]) == 0 or self.grid[start][0] != player:\n",
    "            return False\n",
    "        if start + r == Game.NUMCOLS:\n",
    "            return True\n",
    "        if start + r > Game.NUMCOLS:\n",
    "            for i in range(start - 1, Game.NUMCOLS - self.die - 1, -1):\n",
    "                if len(self.grid[i]) != 0 and self.grid[i][0] == self.players[0]:\n",
    "                    return False\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "    def is_valid_move(self, start, end, token):\n",
    "        if len(self.grid[start]) > 0 and self.grid[start][0] == token:\n",
    "            if end < 0 or end >= len(self.grid):\n",
    "                return False\n",
    "            if len(self.grid[end]) <= 1:\n",
    "                return True\n",
    "            if len(self.grid[end]) > 1 and self.grid[end][-1] == token:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def draw_col(self,i,col):\n",
    "        print(\"|\", end = '')\n",
    "        if i==-2:\n",
    "            if col<10:\n",
    "                print(\" \", end = '')\n",
    "            print(str(col), end = '')\n",
    "        elif i==-1:\n",
    "            print(\"--\", end = '')\n",
    "        elif len(self.grid[col])>i:\n",
    "            print(\" \"+self.grid[col][i], end = '')\n",
    "        else:\n",
    "            print(\"  \", end = '')\n",
    "\n",
    "    def draw(self):\n",
    "        largest = max([len(self.grid[i]) for i in range(int(len(self.grid)/2),len(self.grid))])\n",
    "        for i in range(-2,largest):\n",
    "            for col in range(int(len(self.grid)/2),len(self.grid)):\n",
    "                self.draw_col(i,col)\n",
    "            print(\"|\")\n",
    "        print()\n",
    "        print()\n",
    "        largest = max([len(self.grid[i]) for i in range(int(len(self.grid)/2))])\n",
    "        for i in range(largest-1,-3,-1):\n",
    "            for col in range(int(len(self.grid)/2)-1,-1,-1):\n",
    "                self.draw_col(i,col)\n",
    "            print(\"|\")\n",
    "        for t in self.players:\n",
    "            print(\"<Player %s>  Off Board : \"%(t), end = '')\n",
    "            for piece in self.off_pieces[t]:\n",
    "                print(t+'', end = '')\n",
    "            print(\"   Bar : \", end = '')\n",
    "            for piece in self.bar_pieces[t]:\n",
    "                print(t+'', end = '')\n",
    "            print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Wie sieht das Spielfeld und die extrahierten Features aus?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Spielfeld:\n",
      "|12|13|14|15|16|17|18|19|20|21|22|23|\n",
      "|--|--|--|--|--|--|--|--|--|--|--|--|\n",
      "| x|  |  |  | o|  | o|  |  |  |  | x|\n",
      "| x|  |  |  | o|  | o|  |  |  |  | x|\n",
      "| x|  |  |  | o|  | o|  |  |  |  |  |\n",
      "| x|  |  |  |  |  | o|  |  |  |  |  |\n",
      "| x|  |  |  |  |  | o|  |  |  |  |  |\n",
      "\n",
      "\n",
      "| o|  |  |  |  |  | x|  |  |  |  |  |\n",
      "| o|  |  |  |  |  | x|  |  |  |  |  |\n",
      "| o|  |  |  | x|  | x|  |  |  |  |  |\n",
      "| o|  |  |  | x|  | x|  |  |  |  | o|\n",
      "| o|  |  |  | x|  | x|  |  |  |  | o|\n",
      "|--|--|--|--|--|--|--|--|--|--|--|--|\n",
      "|11|10| 9| 8| 7| 6| 5| 4| 3| 2| 1| 0|\n",
      "<Player x>  Off Board :    Bar : \n",
      "<Player o>  Off Board :    Bar : \n",
      "\n",
      "Features aus der Sicht von x:\n",
      "[[0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1.\n",
      "  0. 0. 0. 0. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  1. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 0. 0.\n",
      "  0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1.\n",
      "  1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 0. 0. 0.\n",
      "  0. 0. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.\n",
      "  0. 0. 0. 0. 1. 0.]]\n",
      "\n",
      "Form von den Features: (1, 198)\n"
     ]
    }
   ],
   "source": [
    "game = Game.new()\n",
    "print(\"Spielfeld:\")\n",
    "game.draw()\n",
    "x = game.extractFeatures(Game.TOKENS[0])\n",
    "print()\n",
    "print(\"Features aus der Sicht von x:\")\n",
    "print(x)\n",
    "print()\n",
    "print(\"Form von den Features:\", x.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Wer spielt das Spiel?\n",
    "-> Bisher gibt es keine Spieler"
   ]
  },
  {
   "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.5.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}