hw2/src/report.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 2: Nannon\n",
    "### By Ari Porad\n",
    "### For COSI 101A with Professor Jordan Pollack, April 12th 2021"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Discussion\n",
    "\n",
    "For this assignment, I built an implementation of the game Nannon and several different algorithms that could play it. Some high-level discussion of my approach follows in this section, then I'll walk through my implementation in more detail.\n",
    "\n",
    "### Representation\n",
    "\n",
    "I'm a big believer that if you choose your data structures right, the rest of your program writes itself. (That's a rough quote from someone, but I can't remember who.) To that end, I spent a substantial amount of time during this project iterating on my data structures. Originally, I stored the board as a list, where each item in the list represented a position on the board. Legal values were `0` (spot is empty), `1` (current player's checker), and `-1` (opponent's checker). Checkers in the home and goal zones were stored separately. That data structure was simple, which was nice. However, it was easy to get into an illegal state (wrong number of checkers), which I didn't like--a good data structure is one that can't represent an illegal state, after all. It was also hard to manipulate, with lots of loops looking for checkers. I ultimately decided to switch to a representation with an (unordered) list of `Checker`s, each of which has a `Player` (black or white) and a `Position`. Initially, I attempted to have each checker's position be relative _to that checker's home_, which meant that the representation was entirely perspective-independent. That ended up being too complicated to manage, so I settled on a perspective-dependent representation where all checker positions are measured relative to one player's (the perspective player's) home. I'm still not satisfied with this representation--it simultaneously feels a little too complicated, while also needing too much perspective swapping--but it's good enough.\n",
    "\n",
    "The list of checkers (which is always `2 * checkers_per_player` long) is encapsulated by a `Board`, which also tracks the perspective (if the perspective is Black, then lower indexes are closer to Black's home and vis versa) and `GameConfiguration` (the variant of Nannon, such as `{6,3,6}` or `{8,4,6}`). `Board` contains much of the game logic, including calculating open spots, legal `Move`s, and the winner. The `Move` class trackes a possible move, and is responsible for properly executing it and returning the resulting `Board`. Finally, a `Dicestream` class wraps various iterators that can provide a stream of dice rolls.\n",
    "\n",
    "### Knowledge-Based Player\n",
    "\n",
    "My knowledge-based Nannon player ended up somewhat similar to the score-based player, but with some key differences. It's built by assigning \"points\" to different aspects of each possible move. It picks the move with the highest total point value.\n",
    "\n",
    "The algorithm's guiding principles are:\n",
    "\n",
    "* Checkers closer to the goal are better\n",
    "* Knocking off an opponent's checker is valuable, especially if it's close to the goal\n",
    "* Using a roll of 6 to move a checker that's 1 away from the goal is a waste\n",
    "\n",
    "There were a couple of things that I expected to result in significant improvements, but in testing either had negligible or negative impacts, so aren't part of the final algorithm:\n",
    "* Favoring protected checkers\n",
    "* Trying to account for the risk of getting trapped\n",
    "* Valuing checkers closer to the goal non-linearly (ie. a checker right next to the goal is _way_ more valuable than one right next to home)\n",
    "* Optimizing for the number of legal moves\n",
    "\n",
    "### Sticking Points\n",
    "\n",
    "As mentioned above, picking (and iterating on) a set of datastructures was a big sticking point for this assignment. Building a knowledge-based player was also more difficult than anticipated--the strategies that I intuitively expected to work well weren't actually that effective, whereas the very simple score-based player was actually quite good (as, was somewhat surprisingly, the simple last-piece-first player). It's also quite possible that I'm just bad at Nannon--as any of my friends or family can attest, I'm not generally not one for playing games like these the old-fashion way. Additionally, I ran into some very very strange situations that I think are bugs in the Python interpreter, which are more thoroughly documented in `cli.py`--but basically, `Player.BLACK.long_str` would sometimes return `'White'`, but only in the PyCharm debugger and inconsistently. That was a fun one.\n",
    "\n",
    "### Performance\n",
    "\n",
    "I spent a substantial amount of time optimizing the performance of this solution. Running a profiler against a tournament led me to introduce significant memoization (using Python's [`functools.cache`/`functools.cached_property`][caching]) throught the system, and to optimize the equality checking and hashing of various classes. This ultimately resulted in a 2-3x performance increase over the initial version.\n",
    "\n",
    "[caching]: https://docs.python.org/3/library/functools.html\n",
    "\n",
    "## Running the Code\n",
    "\n",
    "I hope I've provided enough information in this report that--as requested--you won't need to run the code. If you do, however, there are a couple of ways to do so.\n",
    "\n",
    "First, much of the code, especially the game foundation, is unit tested through Python's [doctest][] module. Tests can be run from the command line:\n",
    "\n",
    "```bash\n",
    "# This prints nothing if the tests pass\n",
    "$ python3 -m doctest src/*.py\n",
    "```\n",
    "\n",
    "Additionally, I built a simple CLI for interacting with the game system:\n",
    "\n",
    "```bash\n",
    "$ python3 src/cli.py --help\n",
    "usage: cli.py [-h] [-n ROUNDS] [-b BOARD_SIZE] [-c CHECKERS] [-d DIE_SIZE] [-s SEED]\n",
    "              {g,game,t,tournament,r,roundrobin} {first,human,knowledge,last,random,score} [{first,human,knowledge,last,random,score} ...]\n",
    "\n",
    "positional arguments:\n",
    "  {g,game,t,tournament,r,roundrobin}\n",
    "                        game mode\n",
    "  {first,human,knowledge,last,random,score}\n",
    "                        player algorithms (2 for game our tournament, 2+ for round robin)\n",
    "\n",
    "optional arguments:\n",
    "  -h, --help            show this help message and exit\n",
    "  -n ROUNDS, --rounds ROUNDS\n",
    "                        number of matches to run\n",
    "  -b BOARD_SIZE, --board-size BOARD_SIZE\n",
    "                        board size\n",
    "  -c CHECKERS, --checkers CHECKERS\n",
    "                        checkers per player\n",
    "  -d DIE_SIZE, --die-size DIE_SIZE\n",
    "                        die size\n",
    "  -s SEED, --seed SEED  the seed for the random roll generator\n",
    "\n",
    "$ python3 src/cli.py game random human  # play against a random player\n",
    "<Output not shown because it requires humna input>\n",
    "\n",
    "$ python3 src/cli.py tournament random first last score -n 3000  # run a tournament and show the aggregate results\n",
    "Playing a Nannon{6,3,6} bulk tournament of 3000 games each between random, first, last, score. seed = 1618284126\n",
    "Played 6 tournaments of 3000 games each. Took 3s.\n",
    "Loser → | first   | last    | random  | score\n",
    "-----------------------------------------------\n",
    "random  | 53.5%   | 45.8%   | -       | 46.8%\n",
    "first   | -       | 44.9%   | 46.5%   | 43.0%\n",
    "last    | 55.1%   | -       | 54.2%   | 50.2%\n",
    "score   | 57.0%   | 49.8%   | 53.2%   | -\n",
    "\n",
    "$ python3 src/cli.py tournament last score first --seed 12345  # set the seed to any integer for consistent dice (doesn't affect the random player's decisions). We'll use the same seed as above\n",
    "Playing a Nannon{6,3,6} bulk tournament of 100 games each between last, score, first. seed = 12345\n",
    "Played 3 tournaments of 100 games each. Took 0s.\n",
    "Loser → | first   | last    | score\n",
    "-------------------------------------\n",
    "last    | 55.0%   | -       | 48.0%\n",
    "score   | 52.0%   | 52.0%   | -\n",
    "first   | -       | 45.0%   | 48.0%\n",
    "```\n",
    "\n",
    "[doctest]: https://docs.python.org/3/library/doctest.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Results\n",
    "\n",
    "First off, let's run a round-robin tournament and look at the results. We'll run a large number of matches to get more consistent results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Playing a Nannon{6,3,6} bulk tournament of 10000 games each between last, first, score, random, knowledge. seed = 1618293516\n",
      "Played 10 tournaments of 10000 games each. Took 21s.                                                                              \n",
      "Loser →   | first     | knowledge | last      | random    | score    \n",
      "---------------------------------------------------------------------\n",
      "last      | 62.0%     | 42.6%     | -         | 59.7%     | 48.2%    \n",
      "first     | -         | 30.0%     | 38.0%     | 46.8%     | 35.8%    \n",
      "score     | 64.2%     | 43.9%     | 51.8%     | 61.0%     | -        \n",
      "random    | 53.2%     | 33.3%     | 40.3%     | -         | 39.0%    \n",
      "knowledge | 70.0%     | -         | 57.4%     | 66.7%     | 56.1%    \n"
     ]
    }
   ],
   "source": [
    "from bulk_tournament import bulk_tournament\n",
    "from structs import *\n",
    "from Dicestream import *\n",
    "from Board import *\n",
    "from players import *\n",
    "\n",
    "results = bulk_tournament([\n",
    "    LastPlayerAlgorithm(),\n",
    "    FirstPlayerAlgorithm(),\n",
    "    ScorePlayerAlgorithm(),\n",
    "    RandomPlayerAlgorithm(),\n",
    "    KnowledgePlayerAlgorithm()\n",
    "], rounds=10000, config=GameConfiguration(6, 3, 6), seed=1618293516)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "That ran each a 10,000 game match between each of 5 players (for total of 100,000 matches), showing that (for example), the `last` algorithm triumphs over the `first` algorithm 62% of the time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## Walthrough\n",
    "\n",
    "Now, I'll walk you through each part of the assignment:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### Part 1: Basic Functions and Game Logic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Random Roll: 2\n",
      "Random Roll: 5\n",
      "Random Roll: 1\n",
      "This will be 1: 1\n",
      "This will be 2 (p1 rolls 5, p2 rolls 3): 2\n"
     ]
    }
   ],
   "source": [
    "# Dicestreams\n",
    "rand = Dicestream.random(die_size=6, seed=1)\n",
    "print(\"Random Roll:\", rand.roll())\n",
    "print(\"Random Roll:\", rand.roll())\n",
    "print(\"Random Roll:\", rand.roll())\n",
    "dicestream = Dicestream.fixed([1, 5, 3])\n",
    "print(\"This will be 1:\", dicestream.roll())\n",
    "print(\"This will be 2 (p1 rolls 5, p2 rolls 3):\", dicestream.first_roll())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Here's a starting board from Black's perspective:\n",
      "           ● Black →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |     ← Goal\n",
      "           |  ●  ●        ○  ○  |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |   ○ ← Home\n",
      "                        ← White ○\n",
      "Here's the same board, but swapped:\n",
      "           ○ White →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |     ← Goal\n",
      "           |  ○  ○        ●  ●  |\n",
      "Home → ○   |  ▲  ▲  ▲  ▲  ▲  ▲  |   ● ← Home\n",
      "                        ← Black ●\n",
      "Here's a board where Black won:\n",
      "Who Won?  Player.BLACK\n",
      "           ● Black →\n",
      "Goal → ○○  |  ▼  ▼  ▼  ▼  ▼  ▼  | ●●● ← Goal\n",
      "           |                 ○  |\n",
      "Home →     |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n"
     ]
    }
   ],
   "source": [
    "# Board Representation and Swapping\n",
    "print(\"Here's a starting board from Black's perspective:\")\n",
    "print(Board.create_starting_board(perspective=Player.BLACK).draw())\n",
    "print(\"Here's the same board, but swapped:\")\n",
    "print(Board.create_starting_board(perspective=Player.BLACK).swapped.draw())\n",
    "print(\"Here's a board where Black won:\")\n",
    "black_won = Board(perspective=Player.BLACK, board=('', '-----W', 'BBBWW'))\n",
    "print(\"Who Won? \", black_won.whowon)  # Black\n",
    "print(black_won.draw())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Here's a board where white will move from spot 2 to spot 5 (zero-indexed):\n",
      "Move(W: 2 -> 5)\n",
      "           ○ White →\n",
      "Goal → ●●  |  ▼  ▼  ▼  ▼  ▼  ▼  |  ○○ ← Goal\n",
      "           |  ●     -        ○  |\n",
      "Home →     |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← Black ●\n"
     ]
    }
   ],
   "source": [
    "# Legal Move Generation (hyphen represents the checker's previous location)\n",
    "print(\"Here's a board where white will move from spot 2 to spot 5 (zero-indexed):\")\n",
    "move = Board(perspective=Player.WHITE, board=('', 'B-W---', 'BBWW')) \\\n",
    "    .legal_moves(3, player=Player.WHITE)[0]\n",
    "print(move)\n",
    "print(move.draw())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### Part 2: Generalize the Game\n",
    "\n",
    "How many possible boards are there in various permutations of Nannon?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 2529 possible configurations of Nannon{6, 3, 6}.\n",
      "There are 31102 possible configurations of Nannon{8, 4, 6}.\n",
      "There are 367241 possible configurations of Nannon{10, 5, 6}.\n"
     ]
    }
   ],
   "source": [
    "from explore import explore\n",
    "\n",
    "# explore() takes a while to run, so I've hard-coded the outputs (from a previous run) below for convenience\n",
    "num_boards_636 = 2529\n",
    "num_boards_846 = 31102\n",
    "num_boards_1056 = 367241\n",
    "recalculate = False\n",
    "\n",
    "if recalculate:\n",
    "    num_boards_636 = len(explore(GameConfiguration(6, 3, 6)))\n",
    "    num_boards_846 = len(explore(GameConfiguration(8, 4, 6)))\n",
    "    num_boards_1056 = len(explore(GameConfiguration(10, 5, 6)))\n",
    "\n",
    "print(f\"There are {num_boards_636} possible configurations of Nannon{{6, 3, 6}}.\")\n",
    "print(f\"There are {num_boards_846} possible configurations of Nannon{{8, 4, 6}}.\")\n",
    "print(f\"There are {num_boards_1056} possible configurations of Nannon{{10, 5, 6}}.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### ~~Part 3: Tournaments~~\n",
    "\n",
    "_This section involves a lot of output, so I've put it at the end so that you don't have to scroll through it all. I'll skip it for the time being._"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 4: Knowledge-Based Player\n",
    "\n",
    "This was already addressed in detail above (including with head-to-head results in the table), but I'll show a tournament here too:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Playing a Nannon{6,3,6} tournament of 5000 games, first vs knowledge. seed = 98765\n",
      "Played 5000 games first vs knowledge: first won 1459 (29.18%). Took 5s.                                                        \n"
     ]
    }
   ],
   "source": [
    "# There's a slightly different function for head-to-head tournaments for UI reasons\n",
    "from play_tournament import play_tournament\n",
    "\n",
    "win_ratio = play_tournament(FirstPlayerAlgorithm(), KnowledgePlayerAlgorithm(), rounds=5000, seed=98765, config=GameConfiguration(6, 3, 6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "### Part 3: Tournaments\n",
    "\n",
    "For ease of grading, I'll show two games now. That's a lot of output, so I've put it here at the end. You can also see and/or play these games interactively through the CLI."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Playing a Game of Nannon{6,3,6}! Black: first, White: last. Seed = 12345\n",
      "White (last) rolled 2 and played:\n",
      "           ● Black →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |     ← Goal\n",
      "           |  ●  ●     ○  ○  -  |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |   ○ ← Home\n",
      "                        ← White ○\n",
      "Black (first) rolled 1 and played:\n",
      "           ● Black →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |     ← Goal\n",
      "           |  ●  -  ●  ○  ○     |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |   ○ ← Home\n",
      "                        ← White ○\n",
      "White (last) rolled 3 and played:\n",
      "           ● Black →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |     ← Goal\n",
      "           |  ●  ○  ●  ○  -     |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |   ○ ← Home\n",
      "                        ← White ○\n",
      "Black (first) rolled 3 and played:\n",
      "           ● Black →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |     ← Goal\n",
      "           |  ●  ○  -  ○     ●  |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |   ○ ← Home\n",
      "                        ← White ○\n",
      "White (last) rolled 2 and played:\n",
      "           ● Black →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |     ← Goal\n",
      "           |  ●  ○     ○  ○  ●  |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |   - ← Home\n",
      "                        ← White ○\n",
      "Black (first) rolled 3 and played:\n",
      "           ● Black →\n",
      "Goal →     |  ▼  ▼  ▼  ▼  ▼  ▼  |   ● ← Goal\n",
      "           |  ●  ○     ○  ○  -  |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "           ● Black →\n",
      "Goal → ○   |  ▼  ▼  ▼  ▼  ▼  ▼  |   ● ← Goal\n",
      "           |  ●  ○     ○  -     |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "Black (first) rolled 4 and played:\n",
      "           ● Black →\n",
      "Goal → ○   |  ▼  ▼  ▼  ▼  ▼  ▼  |   ● ← Goal\n",
      "           |  -  ○     ○  ●     |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "White (last) rolled 2 and played:\n",
      "           ● Black →\n",
      "Goal → ○○  |  ▼  ▼  ▼  ▼  ▼  ▼  |   ● ← Goal\n",
      "           |     -     ○  ●     |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "Black (first) rolled 3 and played:\n",
      "           ● Black →\n",
      "Goal → ○○  |  ▼  ▼  ▼  ▼  ▼  ▼  |  ●● ← Goal\n",
      "           |           ○  -     |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "White (last) rolled 1 and played:\n",
      "           ● Black →\n",
      "Goal → ○○  |  ▼  ▼  ▼  ▼  ▼  ▼  |  ●● ← Goal\n",
      "           |        ○  -        |\n",
      "Home → ●   |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "Black (first) rolled 4 and played:\n",
      "           ● Black →\n",
      "Goal → ○○  |  ▼  ▼  ▼  ▼  ▼  ▼  |  ●● ← Goal\n",
      "           |        ○  ●        |\n",
      "Home → -   |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "White (last) rolled 3 and played:\n",
      "           ● Black →\n",
      "Goal → ○○○ |  ▼  ▼  ▼  ▼  ▼  ▼  |  ●● ← Goal\n",
      "           |        -  ●        |\n",
      "Home →     |  ▲  ▲  ▲  ▲  ▲  ▲  |     ← Home\n",
      "                        ← White ○\n",
      "Winner: White (last)! \n",
      "Playing a Game of Nannon{12,5,6}! Black: first, White: last. Seed = 56789\n",
      "Black (first) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●  ●  ●  -  ●           ○  ○  ○  ○  |\n",
      "Home → ●     |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |     ○ ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 6 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●  ●  ●     ●     ○     ○  ○  ○  ○  |\n",
      "Home → ●     |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |     - ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 4 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●  ●  -     ●     ●     ○  ○  ○  ○  |\n",
      "Home → ●     |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |     ○ ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●  ●        ●     ●  ○  ○  ○  ○  ○  |\n",
      "Home → ●     |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |     - ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 4 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●  -        ●  ●  ●  ○  ○  ○  ○  ○  |\n",
      "Home → ●     |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●        ○  ●  ●  ●  ○  -  ○  ○  ○  |\n",
      "Home → ●     |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 3 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●        ○  ●  -  ●  ○  ●  ○  ○  ○  |\n",
      "Home → ●     |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●        ○  ●     ○  ○  ●  ○  ○  -  |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 3 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●        ○  ●     ○  ○  -  ○  ○  ●  |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |       ← Goal\n",
      "             |  ●        ○  ●     ○  ○  ○  -  ○  ●  |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 4 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●        ○  ●     ○  ○  ○     ○  -  |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●        ○  ●     ○  ○  ○  ○  -     |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●        ○  -  ●  ○  ○  ○  ○        |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 2 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●        ○     ○  ○  -  ○  ○        |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 6, but couldn't make any moves! SKIPPED!\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●        ○  ○  ○  ○     ○  -        |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 6, but couldn't make any moves! SKIPPED!\n",
      "White (last) rolled 4 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●     ○  ○  ○  ○  -     ○           |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  -  ●  ○  ○  ○  ○        ○           |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |     ●  ○  ○  ○  ○     ○  -           |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal →       |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●  ●  ○  ○  ○  ○     ○              |\n",
      "Home → -●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●  ●  ○  ○  -  ○     ○              |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 3 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●  -  ○  ○  ●  ○     ○              |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●     ○  ○  ●  ○  ○  -              |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●     ○  ○  -  ○  ○        ●        |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●     ○  ○  ○  -  ○        ●        |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 2 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ●     ○  ○  ○     ○        -     ●  |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 4 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |     ● ← Goal\n",
      "             |  ○     ○  ○  -     ○              ●  |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 6 and played:\n",
      "             ● Black →\n",
      "Goal → ○     |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○     ○  ○        ○              -  |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 4 and played:\n",
      "             ● Black →\n",
      "Goal → ○○    |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○     ○  -        ○                 |\n",
      "Home → ●●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 4 and played:\n",
      "             ● Black →\n",
      "Goal → ○○    |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○     ○  ●        ○                 |\n",
      "Home → -●●   |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal → ○○    |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○  ○  ○  ●        -                 |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 2 and played:\n",
      "             ● Black →\n",
      "Goal → ○○    |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○  ○  ○  -     ●                    |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal → ○○○   |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○  ○  -        ●                    |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 1 and played:\n",
      "             ● Black →\n",
      "Goal → ○○○   |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○  ○           -  ●                 |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 5 and played:\n",
      "             ● Black →\n",
      "Goal → ○○○○  |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○  -              ●                 |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Black (first) rolled 3 and played:\n",
      "             ● Black →\n",
      "Goal → ○○○○  |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  ○                 -        ●        |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "White (last) rolled 3 and played:\n",
      "             ● Black →\n",
      "Goal → ○○○○○ |  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  ▼  |    ●● ← Goal\n",
      "             |  -                          ●        |\n",
      "Home → ●●    |  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  ▲  |       ← Home\n",
      "                                            ← White ○\n",
      "Winner: White (last)! \n"
     ]
    }
   ],
   "source": [
    "from play_game import play_game\n",
    "\n",
    "# Let's play just one game of Nannon{6,3,6}\n",
    "winner6 = play_game(\n",
    "    FirstPlayerAlgorithm(), LastPlayerAlgorithm(),\n",
    "    seed=12345, config=GameConfiguration(6, 3, 6))\n",
    "\n",
    "# It works for higher-order Nannon too, like Nannon{12,5,6}\n",
    "winner12 = play_game(\n",
    "    FirstPlayerAlgorithm(), LastPlayerAlgorithm(),\n",
    "    seed=56789, config=GameConfiguration(12, 5, 6))"
   ]
  }
 ],
 "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}