menace-nim.ipynb

   1 {
   2  "cells": [
   3   {
   4    "cell_type": "markdown",
   5    "metadata": {},
   6    "source": [
   7     "# Menace-like Nim player\n",
   8     "\n",
   9     "This is an implementation of a Menace-like player for one-stack Nim."
  10    ]
  11   },
  12   {
  13    "cell_type": "markdown",
  14    "metadata": {},
  15    "source": [
  16     "## Nim\n",
  17     "\n",
  18     "There are many version of Nim. This version uses a single stack of tokens (initially nine). Players take turns removing one, two, or three tokens from the stack. The player who takes the last token loses."
  19    ]
  20   },
  21   {
  22    "cell_type": "markdown",
  23    "metadata": {},
  24    "source": [
  25     "### Menace\n",
  26     "[Menace](http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/) was an early program that learnt how to play a perfect game of noughts and crosses. It was developed by [Donald Michie](https://en.wikipedia.org/wiki/Donald_Michie). As computers were rare in the 1950s, Michie implemented the machine as a set of matchboxes.\n",
  27     "\n",
  28     "There is one matchbox for each state of the game (330 for noughts and crosses, ignoring rotations and reflections; 9 for this version of Nim). Each box contains some beads, with each type of bead representing a different move. \n",
  29     "\n",
  30     "When playing the game, Menace makes its move by picking a random bead from the appropriate box. It plays randomly, but biased by the number of beads in each box.\n",
  31     "\n",
  32     "Learning takes place by [reinforcement learning](https://en.wikipedia.org/wiki/Reinforcement_learning) after the game. If Menace won, all the beads are replaced in their original boxes, and another bead of the same type is added to the box. In other words, one bead came out of the box, two beads of that type go back in. If Menace lost, the played beads are removed (with a minimum of one bead of each type remaining in each box)."
  33    ]
  34   },
  35   {
  36    "cell_type": "markdown",
  37    "metadata": {},
  38    "source": [
  39     "## Implementation\n",
  40     "We start with some imports and constant definitions."
  41    ]
  42   },
  43   {
  44    "cell_type": "code",
  45    "execution_count": 84,
  46    "metadata": {
  47     "collapsed": true
  48    },
  49    "outputs": [],
  50    "source": [
  51     "import collections\n",
  52     "import random\n",
  53     "from IPython.display import HTML, display"
  54    ]
  55   },
  56   {
  57    "cell_type": "code",
  58    "execution_count": 2,
  59    "metadata": {
  60     "collapsed": true
  61    },
  62    "outputs": [],
  63    "source": [
  64     "INITIAL_GAME_SIZE = 9\n",
  65     "MAX_TAKE = 3\n",
  66     "INITIAL_BEAD_COUNT = 3"
  67    ]
  68   },
  69   {
  70    "cell_type": "markdown",
  71    "metadata": {},
  72    "source": [
  73     "A **Menace** instance is just a collection of boxes, each box containing some beads. The bead types are just the number of tokens to remove on this move. \n",
  74     "\n",
  75     "I use a `collections.Counter` object to store counts of the number of beads. \n",
  76     "\n",
  77     "I use a `dict` of boxes, just to avoid off-by-one errors when comparing the number of tokens to the index of the box collection. \n",
  78     "\n",
  79     "Note that we ensure that only legal moves are represented in the Menace player."
  80    ]
  81   },
  82   {
  83    "cell_type": "code",
  84    "execution_count": 3,
  85    "metadata": {
  86     "collapsed": true
  87    },
  88    "outputs": [],
  89    "source": [
  90     "def new_menace():\n",
  91     "    boxes = {'human?': False}\n",
  92     "    for b in range(1, INITIAL_GAME_SIZE+1):\n",
  93     "        box = collections.Counter()\n",
  94     "        for i in range(1, MAX_TAKE+1):\n",
  95     "            if b >= i:\n",
  96     "                box[i] = INITIAL_BEAD_COUNT\n",
  97     "        boxes[b] = box\n",
  98     "    return boxes"
  99    ]
 100   },
 101   {
 102    "cell_type": "code",
 103    "execution_count": 4,
 104    "metadata": {},
 105    "outputs": [
 106     {
 107      "data": {
 108       "text/plain": [
 109        "{1: Counter({1: 3}),\n",
 110        " 2: Counter({1: 3, 2: 3}),\n",
 111        " 3: Counter({1: 3, 2: 3, 3: 3}),\n",
 112        " 4: Counter({1: 3, 2: 3, 3: 3}),\n",
 113        " 5: Counter({1: 3, 2: 3, 3: 3}),\n",
 114        " 6: Counter({1: 3, 2: 3, 3: 3}),\n",
 115        " 7: Counter({1: 3, 2: 3, 3: 3}),\n",
 116        " 8: Counter({1: 3, 2: 3, 3: 3}),\n",
 117        " 9: Counter({1: 3, 2: 3, 3: 3}),\n",
 118        " 'human?': False}"
 119       ]
 120      },
 121      "execution_count": 4,
 122      "metadata": {},
 123      "output_type": "execute_result"
 124     }
 125    ],
 126    "source": [
 127     "new_menace()"
 128    ]
 129   },
 130   {
 131    "cell_type": "markdown",
 132    "metadata": {},
 133    "source": [
 134     "Pick a random move by listing all the beads and picking one at random."
 135    ]
 136   },
 137   {
 138    "cell_type": "code",
 139    "execution_count": 5,
 140    "metadata": {
 141     "collapsed": true
 142    },
 143    "outputs": [],
 144    "source": [
 145     "def menace_move(box):\n",
 146     "    return random.choice(list(box.elements()))"
 147    ]
 148   },
 149   {
 150    "cell_type": "code",
 151    "execution_count": 6,
 152    "metadata": {},
 153    "outputs": [
 154     {
 155      "data": {
 156       "text/plain": [
 157        "2"
 158       ]
 159      },
 160      "execution_count": 6,
 161      "metadata": {},
 162      "output_type": "execute_result"
 163     }
 164    ],
 165    "source": [
 166     "menace_move(new_menace()[9])"
 167    ]
 168   },
 169   {
 170    "cell_type": "markdown",
 171    "metadata": {},
 172    "source": [
 173     "A **human** player has no state, apart from saying it's human. There's some complex logic to ensure that we only get valid moves from the human."
 174    ]
 175   },
 176   {
 177    "cell_type": "code",
 178    "execution_count": 7,
 179    "metadata": {
 180     "collapsed": true
 181    },
 182    "outputs": [],
 183    "source": [
 184     "def new_human():\n",
 185     "    return {'human?': True}"
 186    ]
 187   },
 188   {
 189    "cell_type": "code",
 190    "execution_count": 34,
 191    "metadata": {
 192     "collapsed": true
 193    },
 194    "outputs": [],
 195    "source": [
 196     "def human_move(game):\n",
 197     "    if game['history']:\n",
 198     "        print('Opponent took', game['history'][-1]['move'], 'pieces.')\n",
 199     "    else:\n",
 200     "        print('You play first.')\n",
 201     "    print('There are', game['tokens'], 'pieces left.')\n",
 202     "    \n",
 203     "    max_move = min(MAX_TAKE, game['tokens'])\n",
 204     "    valid_input = False\n",
 205     "    \n",
 206     "    while not valid_input:\n",
 207     "        user_input = input('Your move (1-{})? '.format(max_move))\n",
 208     "        if user_input.isnumeric():\n",
 209     "            move = int(user_input)\n",
 210     "            if move in range(1, max_move+1):\n",
 211     "                valid_input = True\n",
 212     "            else:\n",
 213     "                print('Number not a valid move.')\n",
 214     "        else:\n",
 215     "            print('Please enter a number.')\n",
 216     "    return move"
 217    ]
 218   },
 219   {
 220    "cell_type": "markdown",
 221    "metadata": {},
 222    "source": [
 223     "A **game** is the current state of the game (number of tokens, who's the current player), the two players, and a history of moves. We use the history for the reinforcement learning phase."
 224    ]
 225   },
 226   {
 227    "cell_type": "code",
 228    "execution_count": 9,
 229    "metadata": {},
 230    "outputs": [],
 231    "source": [
 232     "def new_game(player1, player2):\n",
 233     "    return {'tokens': INITIAL_GAME_SIZE,\n",
 234     "           'player1': player1,\n",
 235     "           'player2': player2,\n",
 236     "           'player1_active': True,\n",
 237     "           'history': []}"
 238    ]
 239   },
 240   {
 241    "cell_type": "code",
 242    "execution_count": 10,
 243    "metadata": {
 244     "collapsed": true
 245    },
 246    "outputs": [],
 247    "source": [
 248     "def game_finished(game):\n",
 249     "    return game['tokens'] == 0"
 250    ]
 251   },
 252   {
 253    "cell_type": "markdown",
 254    "metadata": {},
 255    "source": [
 256     "The last player to move in a game is the loser."
 257    ]
 258   },
 259   {
 260    "cell_type": "code",
 261    "execution_count": 11,
 262    "metadata": {
 263     "collapsed": true
 264    },
 265    "outputs": [],
 266    "source": [
 267     "def winner(game):\n",
 268     "    if game['history'][-1]['player1?']:\n",
 269     "        return game['player2']\n",
 270     "    else:\n",
 271     "        return game['player1']\n",
 272     "\n",
 273     "def loser(game):\n",
 274     "    if game['history'][-1]['player1?']:\n",
 275     "        return game['player1']\n",
 276     "    else:\n",
 277     "        return game['player2']          "
 278    ]
 279   },
 280   {
 281    "cell_type": "markdown",
 282    "metadata": {},
 283    "source": [
 284     "The **active player** makes a move, depending on whether it's a human or a menace. After the move is taken, update the game state and history. We store plenty in the history to make the learning phase easier."
 285    ]
 286   },
 287   {
 288    "cell_type": "code",
 289    "execution_count": 12,
 290    "metadata": {
 291     "collapsed": true
 292    },
 293    "outputs": [],
 294    "source": [
 295     "def make_move(game):\n",
 296     "    if game['player1_active']:\n",
 297     "        active = game['player1']\n",
 298     "    else:\n",
 299     "        active = game['player2']\n",
 300     "    if active['human?']:\n",
 301     "        move = human_move(game)\n",
 302     "    else:\n",
 303     "        move = menace_move(active[game['tokens']])\n",
 304     "    game['history'] += [{'player1?': game['player1_active'], 'move': move, 'tokens': game['tokens']}]\n",
 305     "    game['tokens'] -= move\n",
 306     "    game['player1_active'] = not game['player1_active'] "
 307    ]
 308   },
 309   {
 310    "cell_type": "markdown",
 311    "metadata": {},
 312    "source": [
 313     "A **game** is just move after move until the game is finished."
 314    ]
 315   },
 316   {
 317    "cell_type": "code",
 318    "execution_count": 15,
 319    "metadata": {
 320     "collapsed": true
 321    },
 322    "outputs": [],
 323    "source": [
 324     "def play_game(game):\n",
 325     "    while not game_finished(game):\n",
 326     "        make_move(game)"
 327    ]
 328   },
 329   {
 330    "cell_type": "markdown",
 331    "metadata": {},
 332    "source": [
 333     "### Test what we've got\n",
 334     "Let's test what we've got so far, by creating a game and making some moves with it."
 335    ]
 336   },
 337   {
 338    "cell_type": "code",
 339    "execution_count": 37,
 340    "metadata": {},
 341    "outputs": [
 342     {
 343      "data": {
 344       "text/plain": [
 345        "{'history': [],\n",
 346        " 'player1': {1: Counter({1: 3}),\n",
 347        "  2: Counter({1: 3, 2: 3}),\n",
 348        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 349        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 350        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 351        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 352        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 353        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 354        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 355        "  'human?': False},\n",
 356        " 'player1_active': True,\n",
 357        " 'player2': {1: Counter({1: 3}),\n",
 358        "  2: Counter({1: 3, 2: 3}),\n",
 359        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 360        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 361        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 362        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 363        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 364        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 365        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 366        "  'human?': False},\n",
 367        " 'tokens': 9}"
 368       ]
 369      },
 370      "execution_count": 37,
 371      "metadata": {},
 372      "output_type": "execute_result"
 373     }
 374    ],
 375    "source": [
 376     "p1 = new_menace()\n",
 377     "p2 = new_menace()\n",
 378     "g = new_game(p1, p2)\n",
 379     "g"
 380    ]
 381   },
 382   {
 383    "cell_type": "code",
 384    "execution_count": 38,
 385    "metadata": {},
 386    "outputs": [
 387     {
 388      "data": {
 389       "text/plain": [
 390        "{'history': [{'move': 3, 'player1?': True, 'tokens': 9}],\n",
 391        " 'player1': {1: Counter({1: 3}),\n",
 392        "  2: Counter({1: 3, 2: 3}),\n",
 393        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 394        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 395        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 396        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 397        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 398        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 399        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 400        "  'human?': False},\n",
 401        " 'player1_active': False,\n",
 402        " 'player2': {1: Counter({1: 3}),\n",
 403        "  2: Counter({1: 3, 2: 3}),\n",
 404        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 405        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 406        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 407        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 408        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 409        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 410        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 411        "  'human?': False},\n",
 412        " 'tokens': 6}"
 413       ]
 414      },
 415      "execution_count": 38,
 416      "metadata": {},
 417      "output_type": "execute_result"
 418     }
 419    ],
 420    "source": [
 421     "make_move(g)\n",
 422     "g"
 423    ]
 424   },
 425   {
 426    "cell_type": "code",
 427    "execution_count": 39,
 428    "metadata": {},
 429    "outputs": [
 430     {
 431      "data": {
 432       "text/plain": [
 433        "{'history': [{'move': 1, 'player1?': True, 'tokens': 9},\n",
 434        "  {'move': 2, 'player1?': False, 'tokens': 8},\n",
 435        "  {'move': 3, 'player1?': True, 'tokens': 6},\n",
 436        "  {'move': 2, 'player1?': False, 'tokens': 3},\n",
 437        "  {'move': 1, 'player1?': True, 'tokens': 1}],\n",
 438        " 'player1': {1: Counter({1: 3}),\n",
 439        "  2: Counter({1: 3, 2: 3}),\n",
 440        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 441        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 442        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 443        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 444        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 445        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 446        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 447        "  'human?': False},\n",
 448        " 'player1_active': False,\n",
 449        " 'player2': {1: Counter({1: 3}),\n",
 450        "  2: Counter({1: 3, 2: 3}),\n",
 451        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 452        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 453        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 454        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 455        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 456        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 457        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 458        "  'human?': False},\n",
 459        " 'tokens': 0}"
 460       ]
 461      },
 462      "execution_count": 39,
 463      "metadata": {},
 464      "output_type": "execute_result"
 465     }
 466    ],
 467    "source": [
 468     "p1 = new_menace()\n",
 469     "p2 = new_menace()\n",
 470     "g = new_game(p1, p2)\n",
 471     "play_game(g)\n",
 472     "g"
 473    ]
 474   },
 475   {
 476    "cell_type": "code",
 477    "execution_count": 40,
 478    "metadata": {},
 479    "outputs": [
 480     {
 481      "name": "stdout",
 482      "output_type": "stream",
 483      "text": [
 484       "Opponent took 1 pieces.\n",
 485       "There are 8 pieces left.\n",
 486       "Your move (1-3)? 2\n",
 487       "Opponent took 2 pieces.\n",
 488       "There are 4 pieces left.\n",
 489       "Your move (1-3)? 3\n",
 490       "You won\n"
 491      ]
 492     }
 493    ],
 494    "source": [
 495     "p1 = new_menace()\n",
 496     "ph = new_human()\n",
 497     "if random.choice([True, False]):\n",
 498     "    g = new_game(p1, ph)\n",
 499     "else:\n",
 500     "    g = new_game(ph, p1)\n",
 501     "play_game(g)\n",
 502     "if winner(g) == ph:\n",
 503     "    print('You won')\n",
 504     "else:\n",
 505     "    print('You lost')"
 506    ]
 507   },
 508   {
 509    "cell_type": "code",
 510    "execution_count": 41,
 511    "metadata": {},
 512    "outputs": [
 513     {
 514      "data": {
 515       "text/plain": [
 516        "{'human?': True}"
 517       ]
 518      },
 519      "execution_count": 41,
 520      "metadata": {},
 521      "output_type": "execute_result"
 522     }
 523    ],
 524    "source": [
 525     "winner(g)"
 526    ]
 527   },
 528   {
 529    "cell_type": "code",
 530    "execution_count": 42,
 531    "metadata": {},
 532    "outputs": [
 533     {
 534      "data": {
 535       "text/plain": [
 536        "{1: Counter({1: 3}),\n",
 537        " 2: Counter({1: 3, 2: 3}),\n",
 538        " 3: Counter({1: 3, 2: 3, 3: 3}),\n",
 539        " 4: Counter({1: 3, 2: 3, 3: 3}),\n",
 540        " 5: Counter({1: 3, 2: 3, 3: 3}),\n",
 541        " 6: Counter({1: 3, 2: 3, 3: 3}),\n",
 542        " 7: Counter({1: 3, 2: 3, 3: 3}),\n",
 543        " 8: Counter({1: 3, 2: 3, 3: 3}),\n",
 544        " 9: Counter({1: 3, 2: 3, 3: 3}),\n",
 545        " 'human?': False}"
 546       ]
 547      },
 548      "execution_count": 42,
 549      "metadata": {},
 550      "output_type": "execute_result"
 551     }
 552    ],
 553    "source": [
 554     "loser(g)"
 555    ]
 556   },
 557   {
 558    "cell_type": "markdown",
 559    "metadata": {},
 560    "source": [
 561     "## Learning\n",
 562     "Now we can play a game, it's time to start the learning. We need to extract the winning and losing moves from a game, and use them to update the counts of beads in the player."
 563    ]
 564   },
 565   {
 566    "cell_type": "code",
 567    "execution_count": 20,
 568    "metadata": {
 569     "collapsed": true
 570    },
 571    "outputs": [],
 572    "source": [
 573     "def winning_moves(game):\n",
 574     "    return [h for h in game['history'] \n",
 575     "            if h['player1?'] != game['history'][-1]['player1?']]\n",
 576     "\n",
 577     "def losing_moves(game):\n",
 578     "      return [h for h in game['history'] \n",
 579     "            if h['player1?'] == game['history'][-1]['player1?']]  "
 580    ]
 581   },
 582   {
 583    "cell_type": "code",
 584    "execution_count": 21,
 585    "metadata": {},
 586    "outputs": [
 587     {
 588      "data": {
 589       "text/plain": [
 590        "[{'move': 2, 'player1?': True, 'tokens': 9},\n",
 591        " {'move': 1, 'player1?': True, 'tokens': 4},\n",
 592        " {'move': 1, 'player1?': True, 'tokens': 2}]"
 593       ]
 594      },
 595      "execution_count": 21,
 596      "metadata": {},
 597      "output_type": "execute_result"
 598     }
 599    ],
 600    "source": [
 601     "winning_moves(g)"
 602    ]
 603   },
 604   {
 605    "cell_type": "code",
 606    "execution_count": 22,
 607    "metadata": {},
 608    "outputs": [
 609     {
 610      "data": {
 611       "text/plain": [
 612        "[{'move': 3, 'player1?': False, 'tokens': 7},\n",
 613        " {'move': 1, 'player1?': False, 'tokens': 3},\n",
 614        " {'move': 1, 'player1?': False, 'tokens': 1}]"
 615       ]
 616      },
 617      "execution_count": 22,
 618      "metadata": {},
 619      "output_type": "execute_result"
 620     }
 621    ],
 622    "source": [
 623     "losing_moves(g)"
 624    ]
 625   },
 626   {
 627    "cell_type": "markdown",
 628    "metadata": {},
 629    "source": [
 630     "**Updating the winner** is easy: just find the correct box for each move, and update the number of winning beads in that box."
 631    ]
 632   },
 633   {
 634    "cell_type": "code",
 635    "execution_count": 23,
 636    "metadata": {
 637     "collapsed": true
 638    },
 639    "outputs": [],
 640    "source": [
 641     "def update_winner(game):\n",
 642     "    player = winner(game)\n",
 643     "    moves = winning_moves(game)\n",
 644     "    for m in moves:\n",
 645     "        player[m['tokens']][m['move']] += 1"
 646    ]
 647   },
 648   {
 649    "cell_type": "markdown",
 650    "metadata": {},
 651    "source": [
 652     "**Updating the loser** is a bit tricker. The idea is the same as updating the winner, but we have to deal with excepttions. We don't update the bead count in three cases:\n",
 653     "1. There are no beads of that type in the box to start with (though this shouldn't happen in practice).\n",
 654     "2. There's only one instance of this type of bead in the box (unless we override that behaviour with the `allow_drop_move` flag).\n",
 655     "3. In any case, we never take the last bead from a box."
 656    ]
 657   },
 658   {
 659    "cell_type": "code",
 660    "execution_count": 183,
 661    "metadata": {
 662     "collapsed": true
 663    },
 664    "outputs": [],
 665    "source": [
 666     "def update_loser_0(game):\n",
 667     "    player = loser(game)\n",
 668     "    moves = losing_moves(game)\n",
 669     "    for m in moves:\n",
 670     "        if player[m['tokens']][m['move']] > 1:\n",
 671     "            player[m['tokens']][m['move']] -= 1"
 672    ]
 673   },
 674   {
 675    "cell_type": "code",
 676    "execution_count": 184,
 677    "metadata": {
 678     "collapsed": true
 679    },
 680    "outputs": [],
 681    "source": [
 682     "def update_loser(game, allow_drop_move=False):\n",
 683     "    player = loser(game)\n",
 684     "    moves = losing_moves(game)\n",
 685     "    for m in moves:\n",
 686     "        if allow_drop_move:\n",
 687     "            if len(list(player[m['tokens']].elements())) > 1:\n",
 688     "                player[m['tokens']][m['move']] -= 1\n",
 689     "        else:\n",
 690     "            if player[m['tokens']][m['move']] > 1:\n",
 691     "                player[m['tokens']][m['move']] -= 1"
 692    ]
 693   },
 694   {
 695    "cell_type": "markdown",
 696    "metadata": {},
 697    "source": [
 698     "### Testing\n",
 699     "We test the learning by playing a game and updating the players."
 700    ]
 701   },
 702   {
 703    "cell_type": "code",
 704    "execution_count": 52,
 705    "metadata": {},
 706    "outputs": [
 707     {
 708      "data": {
 709       "text/plain": [
 710        "{'history': [{'move': 1, 'player1?': True, 'tokens': 9},\n",
 711        "  {'move': 1, 'player1?': False, 'tokens': 8},\n",
 712        "  {'move': 2, 'player1?': True, 'tokens': 7},\n",
 713        "  {'move': 1, 'player1?': False, 'tokens': 5},\n",
 714        "  {'move': 3, 'player1?': True, 'tokens': 4},\n",
 715        "  {'move': 1, 'player1?': False, 'tokens': 1}],\n",
 716        " 'player1': {1: Counter({1: 3}),\n",
 717        "  2: Counter({1: 3, 2: 3}),\n",
 718        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 719        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 720        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 721        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 722        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 723        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 724        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 725        "  'human?': False},\n",
 726        " 'player1_active': True,\n",
 727        " 'player2': {1: Counter({1: 3}),\n",
 728        "  2: Counter({1: 3, 2: 3}),\n",
 729        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 730        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 731        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 732        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 733        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 734        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 735        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 736        "  'human?': False},\n",
 737        " 'tokens': 0}"
 738       ]
 739      },
 740      "execution_count": 52,
 741      "metadata": {},
 742      "output_type": "execute_result"
 743     }
 744    ],
 745    "source": [
 746     "p1 = new_menace()\n",
 747     "p2 = new_menace()\n",
 748     "g = new_game(p1, p2)\n",
 749     "play_game(g)\n",
 750     "g"
 751    ]
 752   },
 753   {
 754    "cell_type": "code",
 755    "execution_count": 53,
 756    "metadata": {},
 757    "outputs": [
 758     {
 759      "data": {
 760       "text/plain": [
 761        "{'history': [{'move': 1, 'player1?': True, 'tokens': 9},\n",
 762        "  {'move': 1, 'player1?': False, 'tokens': 8},\n",
 763        "  {'move': 2, 'player1?': True, 'tokens': 7},\n",
 764        "  {'move': 1, 'player1?': False, 'tokens': 5},\n",
 765        "  {'move': 3, 'player1?': True, 'tokens': 4},\n",
 766        "  {'move': 1, 'player1?': False, 'tokens': 1}],\n",
 767        " 'player1': {1: Counter({1: 3}),\n",
 768        "  2: Counter({1: 3, 2: 3}),\n",
 769        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 770        "  4: Counter({1: 3, 2: 3, 3: 4}),\n",
 771        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 772        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 773        "  7: Counter({1: 3, 2: 4, 3: 3}),\n",
 774        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 775        "  9: Counter({1: 4, 2: 3, 3: 3}),\n",
 776        "  'human?': False},\n",
 777        " 'player1_active': True,\n",
 778        " 'player2': {1: Counter({1: 2}),\n",
 779        "  2: Counter({1: 3, 2: 3}),\n",
 780        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 781        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 782        "  5: Counter({1: 2, 2: 3, 3: 3}),\n",
 783        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 784        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 785        "  8: Counter({1: 2, 2: 3, 3: 3}),\n",
 786        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 787        "  'human?': False},\n",
 788        " 'tokens': 0}"
 789       ]
 790      },
 791      "execution_count": 53,
 792      "metadata": {},
 793      "output_type": "execute_result"
 794     }
 795    ],
 796    "source": [
 797     "update_winner(g)\n",
 798     "update_loser(g)\n",
 799     "g"
 800    ]
 801   },
 802   {
 803    "cell_type": "markdown",
 804    "metadata": {},
 805    "source": [
 806     "This shows the winner's counts being increased and the losers decreased.\n",
 807     "\n",
 808     "What happens when the push the updates? Does the number of beads stay at the minum value of 1?"
 809    ]
 810   },
 811   {
 812    "cell_type": "code",
 813    "execution_count": 54,
 814    "metadata": {},
 815    "outputs": [
 816     {
 817      "data": {
 818       "text/plain": [
 819        "{'history': [{'move': 1, 'player1?': True, 'tokens': 9},\n",
 820        "  {'move': 1, 'player1?': False, 'tokens': 8},\n",
 821        "  {'move': 2, 'player1?': True, 'tokens': 7},\n",
 822        "  {'move': 1, 'player1?': False, 'tokens': 5},\n",
 823        "  {'move': 3, 'player1?': True, 'tokens': 4},\n",
 824        "  {'move': 1, 'player1?': False, 'tokens': 1}],\n",
 825        " 'player1': {1: Counter({1: 3}),\n",
 826        "  2: Counter({1: 3, 2: 3}),\n",
 827        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 828        "  4: Counter({1: 3, 2: 3, 3: 8}),\n",
 829        "  5: Counter({1: 3, 2: 3, 3: 3}),\n",
 830        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 831        "  7: Counter({1: 3, 2: 8, 3: 3}),\n",
 832        "  8: Counter({1: 3, 2: 3, 3: 3}),\n",
 833        "  9: Counter({1: 8, 2: 3, 3: 3}),\n",
 834        "  'human?': False},\n",
 835        " 'player1_active': True,\n",
 836        " 'player2': {1: Counter({1: 1}),\n",
 837        "  2: Counter({1: 3, 2: 3}),\n",
 838        "  3: Counter({1: 3, 2: 3, 3: 3}),\n",
 839        "  4: Counter({1: 3, 2: 3, 3: 3}),\n",
 840        "  5: Counter({1: 1, 2: 3, 3: 3}),\n",
 841        "  6: Counter({1: 3, 2: 3, 3: 3}),\n",
 842        "  7: Counter({1: 3, 2: 3, 3: 3}),\n",
 843        "  8: Counter({1: 1, 2: 3, 3: 3}),\n",
 844        "  9: Counter({1: 3, 2: 3, 3: 3}),\n",
 845        "  'human?': False},\n",
 846        " 'tokens': 0}"
 847       ]
 848      },
 849      "execution_count": 54,
 850      "metadata": {},
 851      "output_type": "execute_result"
 852     }
 853    ],
 854    "source": [
 855     "for _ in range(4):\n",
 856     "    update_winner(g)\n",
 857     "    update_loser(g)\n",
 858     "g"
 859    ]
 860   },
 861   {
 862    "cell_type": "markdown",
 863    "metadata": {},
 864    "source": [
 865     "Now try it again, but allow moves to be dropped. Does the bead count go to zero?"
 866    ]
 867   },
 868   {
 869    "cell_type": "code",
 870    "execution_count": 55,
 871    "metadata": {},
 872    "outputs": [
 873     {
 874      "data": {
 875       "text/plain": [
 876        "{1: Counter({1: 1}),\n",
 877        " 2: Counter({1: 3, 2: 3}),\n",
 878        " 3: Counter({1: 3, 2: 3, 3: 3}),\n",
 879        " 4: Counter({1: 3, 2: 3, 3: 3}),\n",
 880        " 5: Counter({1: 0, 2: 3, 3: 3}),\n",
 881        " 6: Counter({1: 3, 2: 3, 3: 3}),\n",
 882        " 7: Counter({1: 3, 2: 3, 3: 3}),\n",
 883        " 8: Counter({1: 0, 2: 3, 3: 3}),\n",
 884        " 9: Counter({1: 3, 2: 3, 3: 3}),\n",
 885        " 'human?': False}"
 886       ]
 887      },
 888      "execution_count": 55,
 889      "metadata": {},
 890      "output_type": "execute_result"
 891     }
 892    ],
 893    "source": [
 894     "update_loser(g, allow_drop_move=True)\n",
 895     "loser(g)"
 896    ]
 897   },
 898   {
 899    "cell_type": "markdown",
 900    "metadata": {},
 901    "source": [
 902     "Yes, that move is now forgotten."
 903    ]
 904   },
 905   {
 906    "cell_type": "code",
 907    "execution_count": 56,
 908    "metadata": {},
 909    "outputs": [
 910     {
 911      "data": {
 912       "text/plain": [
 913        "[2, 2, 2, 3, 3, 3]"
 914       ]
 915      },
 916      "execution_count": 56,
 917      "metadata": {},
 918      "output_type": "execute_result"
 919     }
 920    ],
 921    "source": [
 922     "list(g['player2'][8].elements())"
 923    ]
 924   },
 925   {
 926    "cell_type": "markdown",
 927    "metadata": {},
 928    "source": [
 929     "## Making clever players\n",
 930     "Now we can play games and have players learn, let's train some players. \n",
 931     "\n",
 932     "We'll create two players and get them to play a large number of games against each other. To avoid any first-player advantage, we'll randomly swap which player goes first."
 933    ]
 934   },
 935   {
 936    "cell_type": "code",
 937    "execution_count": 185,
 938    "metadata": {},
 939    "outputs": [
 940     {
 941      "data": {
 942       "text/plain": [
 943        "({1: Counter({1: 1}),\n",
 944        "  2: Counter({1: 1683, 2: 1}),\n",
 945        "  3: Counter({1: 1, 2: 1678, 3: 1}),\n",
 946        "  4: Counter({1: 1, 2: 1, 3: 1647}),\n",
 947        "  5: Counter({1: 1, 2: 1, 3: 1}),\n",
 948        "  6: Counter({1: 1634, 2: 1, 3: 1}),\n",
 949        "  7: Counter({1: 1, 2: 1714, 3: 1}),\n",
 950        "  8: Counter({1: 1, 2: 1, 3: 1573}),\n",
 951        "  9: Counter({1: 1, 2: 1, 3: 1}),\n",
 952        "  'human?': False},\n",
 953        " {1: Counter({1: 1}),\n",
 954        "  2: Counter({1: 1642, 2: 1}),\n",
 955        "  3: Counter({1: 1, 2: 1681, 3: 1}),\n",
 956        "  4: Counter({1: 1, 2: 1, 3: 1656}),\n",
 957        "  5: Counter({1: 1, 2: 1, 3: 1}),\n",
 958        "  6: Counter({1: 1694, 2: 1, 3: 1}),\n",
 959        "  7: Counter({1: 1, 2: 1603, 3: 1}),\n",
 960        "  8: Counter({1: 1, 2: 1, 3: 1599}),\n",
 961        "  9: Counter({1: 1, 2: 1, 3: 1}),\n",
 962        "  'human?': False})"
 963       ]
 964      },
 965      "execution_count": 185,
 966      "metadata": {},
 967      "output_type": "execute_result"
 968     }
 969    ],
 970    "source": [
 971     "p1 = new_menace()\n",
 972     "p2 = new_menace()\n",
 973     "for i in range(10000):\n",
 974     "    if random.choice([True, False]):\n",
 975     "        g = new_game(p1, p2)\n",
 976     "    else:\n",
 977     "        g = new_game(p2, p1)\n",
 978     "    play_game(g)\n",
 979     "    update_winner(g)\n",
 980     "    update_loser(g)\n",
 981     "p1, p2"
 982    ]
 983   },
 984   {
 985    "cell_type": "markdown",
 986    "metadata": {},
 987    "source": [
 988     "This shows there's clearly one correct move in each situation, and the first player loses.\n",
 989     "\n",
 990     "What if we allow the elimination of moves?"
 991    ]
 992   },
 993   {
 994    "cell_type": "code",
 995    "execution_count": 182,
 996    "metadata": {},
 997    "outputs": [
 998     {
 999      "data": {
1000       "text/plain": [
1001        "({1: Counter({1: 1}),\n",
1002        "  2: Counter({1: 14, 2: 1}),\n",
1003        "  3: Counter({1: 0, 2: 16, 3: 1}),\n",
1004        "  4: Counter({1: 0, 2: 0, 3: 26}),\n",
1005        "  5: Counter({1: 0, 2: 1, 3: 0}),\n",
1006        "  6: Counter({1: 14, 2: 2, 3: 0}),\n",
1007        "  7: Counter({1: 0, 2: 0, 3: 1}),\n",
1008        "  8: Counter({1: 0, 2: 0, 3: 12}),\n",
1009        "  9: Counter({1: 0, 2: 1, 3: 0}),\n",
1010        "  'human?': False},\n",
1011        " {1: Counter({1: 1}),\n",
1012        "  2: Counter({1: 14, 2: 1}),\n",
1013        "  3: Counter({1: 0, 2: 4974, 3: 0}),\n",
1014        "  4: Counter({1: 0, 2: 0, 3: 4965}),\n",
1015        "  5: Counter({1: 1, 2: 0, 3: 0}),\n",
1016        "  6: Counter({1: 17, 2: 0, 3: 1}),\n",
1017        "  7: Counter({1: 0, 2: 4948, 3: 0}),\n",
1018        "  8: Counter({1: 1, 2: 2, 3: 9}),\n",
1019        "  9: Counter({1: 0, 2: 4963, 3: 0}),\n",
1020        "  'human?': False})"
1021       ]
1022      },
1023      "execution_count": 182,
1024      "metadata": {},
1025      "output_type": "execute_result"
1026     }
1027    ],
1028    "source": [
1029     "p1 = new_menace()\n",
1030     "p2 = new_menace()\n",
1031     "for _ in range(10000):\n",
1032     "    if random.choice([True, False]):\n",
1033     "        g = new_game(p1, p2)\n",
1034     "    else:\n",
1035     "        g = new_game(p2, p1)\n",
1036     "    play_game(g)\n",
1037     "    update_winner(g)\n",
1038     "    update_loser2(g, allow_drop_move=True)\n",
1039     "p1, p2"
1040    ]
1041   },
1042   {
1043    "cell_type": "markdown",
1044    "metadata": {},
1045    "source": [
1046     "Much lower counts for some moves. These are the obviously losing moves, which seem to be taken rarely in the game. This isn't so good for playing against a human, as the **Menace** player needs to play well after non-optimal play by the human."
1047    ]
1048   },
1049   {
1050    "cell_type": "markdown",
1051    "metadata": {},
1052    "source": [
1053     "## Playing Menace\n",
1054     "Let's retrain, then try playing it!"
1055    ]
1056   },
1057   {
1058    "cell_type": "code",
1059    "execution_count": 58,
1060    "metadata": {
1061     "collapsed": true
1062    },
1063    "outputs": [],
1064    "source": [
1065     "p1 = new_menace()\n",
1066     "p2 = new_menace()\n",
1067     "for i in range(10000):\n",
1068     "    if random.choice([True, False]):\n",
1069     "        g = new_game(p1, p2)\n",
1070     "    else:\n",
1071     "        g = new_game(p2, p1)\n",
1072     "    play_game(g)\n",
1073     "    update_winner(g)\n",
1074     "    update_loser(g)"
1075    ]
1076   },
1077   {
1078    "cell_type": "code",
1079    "execution_count": 61,
1080    "metadata": {},
1081    "outputs": [
1082     {
1083      "name": "stdout",
1084      "output_type": "stream",
1085      "text": [
1086       "You play first.\n",
1087       "There are 9 pieces left.\n",
1088       "Your move (1-3)? 2\n",
1089       "Opponent took 2 pieces.\n",
1090       "There are 5 pieces left.\n",
1091       "Your move (1-3)? 1\n",
1092       "Opponent took 3 pieces.\n",
1093       "There are 1 pieces left.\n",
1094       "Your move (1-1)? 1\n",
1095       "You lost\n"
1096      ]
1097     }
1098    ],
1099    "source": [
1100     "ph = new_human()\n",
1101     "if random.choice([True, False]):\n",
1102     "    g = new_game(p1, ph)\n",
1103     "else:\n",
1104     "    g = new_game(ph, p1)\n",
1105     "play_game(g)\n",
1106     "if winner(g) == ph:\n",
1107     "    print('You won')\n",
1108     "else:\n",
1109     "    print('You lost')"
1110    ]
1111   },
1112   {
1113    "cell_type": "code",
1114    "execution_count": 62,
1115    "metadata": {},
1116    "outputs": [
1117     {
1118      "data": {
1119       "text/plain": [
1120        "{'history': [{'move': 2, 'player1?': True, 'tokens': 9},\n",
1121        "  {'move': 2, 'player1?': False, 'tokens': 7},\n",
1122        "  {'move': 1, 'player1?': True, 'tokens': 5},\n",
1123        "  {'move': 3, 'player1?': False, 'tokens': 4},\n",
1124        "  {'move': 1, 'player1?': True, 'tokens': 1}],\n",
1125        " 'player1': {'human?': True},\n",
1126        " 'player1_active': False,\n",
1127        " 'player2': {1: Counter({1: 1}),\n",
1128        "  2: Counter({1: 1676, 2: 1}),\n",
1129        "  3: Counter({1: 1, 2: 1695, 3: 1}),\n",
1130        "  4: Counter({1: 1, 2: 1, 3: 1653}),\n",
1131        "  5: Counter({1: 1, 2: 1, 3: 1}),\n",
1132        "  6: Counter({1: 1648, 2: 1, 3: 1}),\n",
1133        "  7: Counter({1: 2, 2: 1646, 3: 1}),\n",
1134        "  8: Counter({1: 1, 2: 1, 3: 1639}),\n",
1135        "  9: Counter({1: 1, 2: 1, 3: 1}),\n",
1136        "  'human?': False},\n",
1137        " 'tokens': 0}"
1138       ]
1139      },
1140      "execution_count": 62,
1141      "metadata": {},
1142      "output_type": "execute_result"
1143     }
1144    ],
1145    "source": [
1146     "g"
1147    ]
1148   },
1149   {
1150    "cell_type": "markdown",
1151    "metadata": {},
1152    "source": [
1153     "## How strong are these players?\n",
1154     "Let's generate some players by different methods, and get them playing each other. We'll also introduce a partially-trained player, a \"newbie\" untrained player (essentially random play), and a hand-crafted ideal player."
1155    ]
1156   },
1157   {
1158    "cell_type": "code",
1159    "execution_count": 149,
1160    "metadata": {},
1161    "outputs": [
1162     {
1163      "name": "stdout",
1164      "output_type": "stream",
1165      "text": [
1166       "Wins 23 games out of 10000 , or  0.23 %\n"
1167      ]
1168     }
1169    ],
1170    "source": [
1171     "p1 = new_menace()\n",
1172     "p2 = new_menace()\n",
1173     "for _ in range(10000):\n",
1174     "    if random.choice([True, False]):\n",
1175     "        g = new_game(p1, p2)\n",
1176     "    else:\n",
1177     "        g = new_game(p2, p1)\n",
1178     "    play_game(g)\n",
1179     "    update_winner(g)\n",
1180     "    update_loser(g)\n",
1181     "\n",
1182     "wins = 0\n",
1183     "plays = 10000\n",
1184     "for _ in range(plays):\n",
1185     "    g = new_game(p1, p2)\n",
1186     "    play_game(g)\n",
1187     "    if winner(g) == p1: \n",
1188     "        wins += 1\n",
1189     "print(\"Wins\", wins, \"games out of\", plays, \", or \", (100.0 * wins) / plays, \"%\")\n",
1190     "\n",
1191     "p_floor1 = p1"
1192    ]
1193   },
1194   {
1195    "cell_type": "code",
1196    "execution_count": 150,
1197    "metadata": {},
1198    "outputs": [],
1199    "source": [
1200     "p1 = new_menace()\n",
1201     "p2 = new_menace()\n",
1202     "for _ in range(100):\n",
1203     "    if random.choice([True, False]):\n",
1204     "        g = new_game(p1, p2)\n",
1205     "    else:\n",
1206     "        g = new_game(p2, p1)\n",
1207     "    play_game(g)\n",
1208     "    update_winner(g)\n",
1209     "    update_loser(g)\n",
1210     "\n",
1211     "p_parttrained = p1"
1212    ]
1213   },
1214   {
1215    "cell_type": "code",
1216    "execution_count": 170,
1217    "metadata": {},
1218    "outputs": [
1219     {
1220      "name": "stdout",
1221      "output_type": "stream",
1222      "text": [
1223       "Wins 0 games out of 10000 , or  0.0 %\n"
1224      ]
1225     }
1226    ],
1227    "source": [
1228     "p1 = new_menace()\n",
1229     "p2 = new_menace()\n",
1230     "for _ in range(10000):\n",
1231     "    if random.choice([True, False]):\n",
1232     "        g = new_game(p1, p2)\n",
1233     "    else:\n",
1234     "        g = new_game(p2, p1)\n",
1235     "    play_game(g)\n",
1236     "    update_winner(g)\n",
1237     "    update_loser(g, allow_drop_move=True)\n",
1238     "\n",
1239     "wins = 0\n",
1240     "plays = 10000\n",
1241     "for _ in range(plays):\n",
1242     "    g = new_game(p1, p2)\n",
1243     "    play_game(g)\n",
1244     "    if winner(g) == p1: \n",
1245     "        wins += 1\n",
1246     "print(\"Wins\", wins, \"games out of\", plays, \", or \", (100.0 * wins) / plays, \"%\")\n",
1247     "    \n",
1248     "p_floor0 = p2"
1249    ]
1250   },
1251   {
1252    "cell_type": "markdown",
1253    "metadata": {},
1254    "source": [
1255     "Let's try building a stable of players with the `allow_drop_move` and see if that's better."
1256    ]
1257   },
1258   {
1259    "cell_type": "code",
1260    "execution_count": 171,
1261    "metadata": {},
1262    "outputs": [
1263     {
1264      "name": "stdout",
1265      "output_type": "stream",
1266      "text": [
1267       "Wins 1068 games out of 10000 , or  10.68 %\n"
1268      ]
1269     }
1270    ],
1271    "source": [
1272     "players = [new_menace() for _ in range(10)]\n",
1273     "\n",
1274     "for _ in range(100000):\n",
1275     "    p1, p2 = random.sample(players, 2)\n",
1276     "    g = new_game(p1, p2)\n",
1277     "    play_game(g)\n",
1278     "    update_winner(g)\n",
1279     "    update_loser(g, allow_drop_move=True)\n",
1280     "\n",
1281     "wins = 0\n",
1282     "plays = 10000\n",
1283     "p1 = players[0]\n",
1284     "for _ in range(plays):\n",
1285     "    p2 = random.choice(players[1:])\n",
1286     "    g = new_game(p1, p2)\n",
1287     "    play_game(g)\n",
1288     "    if winner(g) == p1: \n",
1289     "        wins += 1\n",
1290     "print(\"Wins\", wins, \"games out of\", plays, \", or \", (100.0 * wins) / plays, \"%\")\n",
1291     "    \n",
1292     "p_floor0_stable = p1"
1293    ]
1294   },
1295   {
1296    "cell_type": "code",
1297    "execution_count": 172,
1298    "metadata": {},
1299    "outputs": [
1300     {
1301      "data": {
1302       "text/plain": [
1303        "{1: Counter({1: 1}),\n",
1304        " 2: Counter({1: 3323, 2: 0}),\n",
1305        " 3: Counter({1: 2, 2: 24, 3: 2}),\n",
1306        " 4: Counter({1: 0, 2: 0, 3: 7682}),\n",
1307        " 5: Counter({1: 0, 2: 1, 3: 0}),\n",
1308        " 6: Counter({1: 3288, 2: 0, 3: 0}),\n",
1309        " 7: Counter({1: 0, 2: 3302, 3: 0}),\n",
1310        " 8: Counter({1: 0, 2: 0, 3: 3290}),\n",
1311        " 9: Counter({1: 0, 2: 0, 3: 1}),\n",
1312        " 'human?': False}"
1313       ]
1314      },
1315      "execution_count": 172,
1316      "metadata": {},
1317      "output_type": "execute_result"
1318     }
1319    ],
1320    "source": [
1321     "p_floor0_stable"
1322    ]
1323   },
1324   {
1325    "cell_type": "code",
1326    "execution_count": 152,
1327    "metadata": {},
1328    "outputs": [
1329     {
1330      "data": {
1331       "text/plain": [
1332        "{1: Counter({1: 1}),\n",
1333        " 2: Counter({1: 1}),\n",
1334        " 3: Counter({2: 1}),\n",
1335        " 4: Counter({3: 1}),\n",
1336        " 5: Counter({1: 1}),\n",
1337        " 6: Counter({1: 1}),\n",
1338        " 7: Counter({2: 1}),\n",
1339        " 8: Counter({3: 1}),\n",
1340        " 9: Counter({1: 1}),\n",
1341        " 'human?': False}"
1342       ]
1343      },
1344      "execution_count": 152,
1345      "metadata": {},
1346      "output_type": "execute_result"
1347     }
1348    ],
1349    "source": [
1350     "newbie = new_menace()\n",
1351     "ideal = {'human?': False,\n",
1352     "         1: collections.Counter([1]),\n",
1353     "         2: collections.Counter([1]),\n",
1354     "         3: collections.Counter([2]),\n",
1355     "         4: collections.Counter([3]),\n",
1356     "         5: collections.Counter([1]),\n",
1357     "         6: collections.Counter([1]),\n",
1358     "         7: collections.Counter([2]),\n",
1359     "         8: collections.Counter([3]),\n",
1360     "         9: collections.Counter([1])}\n",
1361     "ideal"
1362    ]
1363   },
1364   {
1365    "cell_type": "code",
1366    "execution_count": 153,
1367    "metadata": {},
1368    "outputs": [],
1369    "source": [
1370     "def count_wins(p1, p2, plays=10000):\n",
1371     "    wins = 0\n",
1372     "    p2d = p2.copy()\n",
1373     "    for _ in range(plays):\n",
1374     "        g = new_game(p1, p2d)\n",
1375     "        play_game(g)\n",
1376     "        if not g['history'][-1]['player1?']:\n",
1377     "            wins += 1\n",
1378     "    return wins"
1379    ]
1380   },
1381   {
1382    "cell_type": "code",
1383    "execution_count": 173,
1384    "metadata": {
1385     "collapsed": true
1386    },
1387    "outputs": [],
1388    "source": [
1389     "players = [p_floor1, p_floor0, p_floor0_stable, newbie, p_parttrained, ideal]\n",
1390     "player_names = ['Floor 1', 'Floor 0', 'Floor 0 stable', 'Newbie', 'Part trained', 'Ideal']"
1391    ]
1392   },
1393   {
1394    "cell_type": "code",
1395    "execution_count": 174,
1396    "metadata": {
1397     "scrolled": true
1398    },
1399    "outputs": [
1400     {
1401      "data": {
1402       "text/plain": [
1403        "{(0, 0): 22,\n",
1404        " (0, 1): 1265,\n",
1405        " (0, 2): 511,\n",
1406        " (0, 3): 8646,\n",
1407        " (0, 4): 4449,\n",
1408        " (0, 5): 0,\n",
1409        " (1, 0): 12,\n",
1410        " (1, 1): 1575,\n",
1411        " (1, 2): 0,\n",
1412        " (1, 3): 7684,\n",
1413        " (1, 4): 6222,\n",
1414        " (1, 5): 0,\n",
1415        " (2, 0): 24,\n",
1416        " (2, 1): 2281,\n",
1417        " (2, 2): 1444,\n",
1418        " (2, 3): 8532,\n",
1419        " (2, 4): 3239,\n",
1420        " (2, 5): 0,\n",
1421        " (3, 0): 7,\n",
1422        " (3, 1): 783,\n",
1423        " (3, 2): 375,\n",
1424        " (3, 3): 5153,\n",
1425        " (3, 4): 1286,\n",
1426        " (3, 5): 0,\n",
1427        " (4, 0): 21,\n",
1428        " (4, 1): 781,\n",
1429        " (4, 2): 462,\n",
1430        " (4, 3): 7901,\n",
1431        " (4, 4): 3720,\n",
1432        " (4, 5): 0,\n",
1433        " (5, 0): 26,\n",
1434        " (5, 1): 0,\n",
1435        " (5, 2): 0,\n",
1436        " (5, 3): 8837,\n",
1437        " (5, 4): 7529,\n",
1438        " (5, 5): 0}"
1439       ]
1440      },
1441      "execution_count": 174,
1442      "metadata": {},
1443      "output_type": "execute_result"
1444     }
1445    ],
1446    "source": [
1447     "results = {}\n",
1448     "\n",
1449     "for i, p1 in enumerate(players):\n",
1450     "    for j, p2 in enumerate(players):\n",
1451     "        results[i, j] = count_wins(p1, p2)\n",
1452     "results"
1453    ]
1454   },
1455   {
1456    "cell_type": "code",
1457    "execution_count": 175,
1458    "metadata": {},
1459    "outputs": [
1460     {
1461      "data": {
1462       "text/html": [
1463        "<table border=1>\n",
1464        "<tr><td>&nbsp;</td><td>&nbsp;</td><th colspan=6>Player 1</th></tr>\n",
1465        "<tr><td>&nbsp;</td><td>&nbsp;</td><td>Floor 1</td><td>Floor 0</td><td>Floor 0 stable</td><td>Newbie</td><td>Part trained</td><td>Ideal</td></tr>\n",
1466        "<tr>\n",
1467        "<th rowspan=6>Player 2</th>\n",
1468        "<td>Floor 1</td>  <td>22</td>\n",
1469        "  <td>12</td>\n",
1470        "  <td>24</td>\n",
1471        "  <td>7</td>\n",
1472        "  <td>21</td>\n",
1473        "  <td>26</td>\n",
1474        "</tr>\n",
1475        "<tr>\n",
1476        "<td>Floor 0</td>  <td>1265</td>\n",
1477        "  <td>1575</td>\n",
1478        "  <td>2281</td>\n",
1479        "  <td>783</td>\n",
1480        "  <td>781</td>\n",
1481        "  <td>0</td>\n",
1482        "</tr>\n",
1483        "<tr>\n",
1484        "<td>Floor 0 stable</td>  <td>511</td>\n",
1485        "  <td>0</td>\n",
1486        "  <td>1444</td>\n",
1487        "  <td>375</td>\n",
1488        "  <td>462</td>\n",
1489        "  <td>0</td>\n",
1490        "</tr>\n",
1491        "<tr>\n",
1492        "<td>Newbie</td>  <td>8646</td>\n",
1493        "  <td>7684</td>\n",
1494        "  <td>8532</td>\n",
1495        "  <td>5153</td>\n",
1496        "  <td>7901</td>\n",
1497        "  <td>8837</td>\n",
1498        "</tr>\n",
1499        "<tr>\n",
1500        "<td>Part trained</td>  <td>4449</td>\n",
1501        "  <td>6222</td>\n",
1502        "  <td>3239</td>\n",
1503        "  <td>1286</td>\n",
1504        "  <td>3720</td>\n",
1505        "  <td>7529</td>\n",
1506        "</tr>\n",
1507        "<tr>\n",
1508        "<td>Ideal</td>  <td>0</td>\n",
1509        "  <td>0</td>\n",
1510        "  <td>0</td>\n",
1511        "  <td>0</td>\n",
1512        "  <td>0</td>\n",
1513        "  <td>0</td>\n",
1514        "</tr>\n",
1515        "</table>"
1516       ],
1517       "text/plain": [
1518        "<IPython.core.display.HTML object>"
1519       ]
1520      },
1521      "metadata": {},
1522      "output_type": "display_data"
1523     }
1524    ],
1525    "source": [
1526     "result_table = '<table border=1>\\n'\n",
1527     "result_table += '<tr><td>&nbsp;</td><td>&nbsp;</td><th colspan={}>Player 1</th></tr>\\n'.format(len(players))\n",
1528     "result_table += '<tr><td>&nbsp;</td><td>&nbsp;</td>'\n",
1529     "for i in range(len(players)):\n",
1530     "    result_table += '<td>{}</td>'.format(player_names[i])\n",
1531     "result_table += '</tr>\\n'\n",
1532     "\n",
1533     "for i in range(len(players)):\n",
1534     "    result_table += '<tr>\\n'\n",
1535     "    if i == 0:\n",
1536     "        result_table += '<th rowspan={}>Player 2</th>\\n'.format(len(players))\n",
1537     "    result_table += '<td>{}</td>'.format(player_names[i])\n",
1538     "    for j in range(len(players)):\n",
1539     "        result_table += '  <td>{}</td>\\n'.format(results[j, i])\n",
1540     "    result_table += '</tr>\\n'\n",
1541     "result_table += \"</table>\"\n",
1542     "# print(result_table)\n",
1543     "display(HTML(result_table))"
1544    ]
1545   },
1546   {
1547    "cell_type": "markdown",
1548    "metadata": {},
1549    "source": [
1550     "What do these numbers tell us? First, against a trained opponent, the first player is in a very bad position. Indeed, with optimal play (the \"ideal\" player against itself), the first player never wins. However, the disadvantage of first player is almost eliminated with random play.\n",
1551     "\n",
1552     "We can also see that the non-optimal play can throw off the \"floor 0\" player, while the \"floor 1\" player is more able to cope with non-ideal opponents. \"Floor 0\" ends up only knowing what to do in a few of the game positions. If it ends up outside on of those, it loses badly. This suggest that this player is overtrained, reliant on its opponent doing the right thing. \n",
1553     "\n",
1554     "All this goes to show that the non-perfect play from \"floor 1\" is an advantage, as it avoids overtraining, keeping the final player more flexible."
1555    ]
1556   },
1557   {
1558    "cell_type": "code",
1559    "execution_count": null,
1560    "metadata": {
1561     "collapsed": true
1562    },
1563    "outputs": [],
1564    "source": []
1565   }
1566  ],
1567  "metadata": {
1568   "kernelspec": {
1569    "display_name": "Python 3",
1570    "language": "python",
1571    "name": "python3"
1572   },
1573   "language_info": {
1574    "codemirror_mode": {
1575     "name": "ipython",
1576     "version": 3
1577    },
1578    "file_extension": ".py",
1579    "mimetype": "text/x-python",
1580    "name": "python",
1581    "nbconvert_exporter": "python",
1582    "pygments_lexer": "ipython3",
1583    "version": "3.5.2+"
1584   }
1585  },
1586  "nbformat": 4,
1587  "nbformat_minor": 2
1588 }