ipynb/Konane.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\" align=\"right\"><i>Peter Norvig, 1 Dec 2021</i></div>\n",
    "\n",
    "# Mel's Konane Board\n",
    "\n",
    "My friend and former NASA colleague [Mel Montemerlo](https://www.linkedin.com/in/mel-montemerlo-a2040b205/) made this beautiful Konane set for me:\n",
    "\n",
    "![Wooden Konane Board](konane.jpg)\n",
    "\n",
    "I don't have the woodworking skills to make anything nearly as nice as that, so instead I thought I'd use my coding skills to make a nice program to solve the game. It's the least I can do to return the favor to Mel. \n",
    "\n",
    "# Konane Rules\n",
    "\n",
    "Konane (or Kōnane) is a two-player board game from Hawaii.  To set up the game, fill each space with a marble, alternating between black and white marbles in a checkerboard pattern.  To complete the set-up, remove two adjacent marbles (one black, one white) from the board. \n",
    "\n",
    "From there on, the players take turns, with black moving first. A move consists of jumping a marble of your color over an adjacent opponent marble, removing that marble, and landing on the empty space beyond it.  If there is another opponent marble followed by another empty space in the same direction, the player may optionally make a double (or more) jump. Jumps may not be diagonal, and a multiple jump may not change directions.\n",
    "\n",
    "When one player is unable to jump, that player loses.\n",
    "\n",
    "(Some rules say the removed marbles must be either in a corner or in the very center; others say the two can be anywhere on the board. If you accept that they must be in a corner or the center, then there are only two distinct starting positions; the others ten are equivalent under rotation and reflection.)\n",
    "\n",
    "# Approach to Solving  Konane\n",
    "\n",
    "A game is said to be **solved** if, for any state of the game that occurs during play, you can instantly say whether the player to move can force a win from that state. \n",
    "\n",
    "The first thing to consider is whether a 6 by 6 board is small enough that we can solve the game by exhaustive search of the graph of possible states of the game. By **state** I mean an indication of everything that matters: whose turn it is to play, and what marbles are in what spaces. The player to move is either black or white, and each of the 36 spaces can either hold a marble or not, so an upper bound is  2<sup>37</sup> ≈ 137 billion game states. However, the rules for jumping constrain the possible states of the game; most of those theoretical states are unreachable from the start state.  As a wild guess, I estimate that maybe 100 million to a billion states are rechable. That's few enough that I should be able to solve the game with exhaustive search. I'm lucky that Mel chose 6 by 6; even a 7 by 7 board would be far too large for exhaustive search.\n",
    "\n",
    "\n",
    "I will define a function `winner(state)` that will return the player who can force a win from that state, regardless of what the other player does. (There must be one such player, because ties are not allowed and there is no randomness.) Once I have cached the values of `winner`,  the optimal strategy is easy: \n",
    "\n",
    "- Play a move that leads to a game state where you are the winner.\n",
    "- If there is no such move, then you're doomed (against an optimal player); play anything."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation of Basic Types\n",
    "\n",
    "\n",
    "The number of states for the 6 by 6 board puts us right on the edge: small enough that I'm confident I can get the program to work; big enough to require some judicious implementation choices to save time and space. For example, a straightforward way to implement a game state would be a structure with two fields, player and board, where the board is a 6 by 6 array where each element is either black, white, or empty. But a billion of those structures would consume a lot of memory. A more efficient encoding is to represent the board as a bit string: a binary integer where bit *s* is a 1 if there is a marble in space *s*, according to the following numbering scheme:\n",
    "\n",
    "\n",
    "     0  1  2  3  4  5\n",
    "     6  7  8  9 10 11\n",
    "    12 13 14 15 16 17\n",
    "    18 19 20 21 22 23\n",
    "    24 25 26 27 28 29\n",
    "    30 31 32 33 34 35\n",
    "    \n",
    "The bit representation for a board doesn't have to say whether a marble is black or white; black marbles can only be in spaces numbered 0, 2, 4, 7, 9, 11, ... (spaces where the x coordinates plus y coordinate is even) and white only in spaces 1, 3, 5, 6, 8, 10, ... (spaces where the x coordinate plus y coordinate is odd).\n",
    "\n",
    "The representation of a state can also be a single `int`, with the low-order bit being 1 for black, 0 for white, and the other bits being a board shifted left a bit.\n",
    "    \n",
    "Given this, the implementation choices are as follows:\n",
    "- **N**: the size of the board: a global variable, defined as 6.\n",
    "- **Board**: a bit string (`int`) indicating which spaces hold marbles.\n",
    "  - The function `get(board space)` returns the player on that space, or `empty`.\n",
    "  - The function `remove(board, spaces)` returns a new board with the marbles on `spaces` removed.\n",
    "- **State**: a bit string (`int`) indicating both the board and the player whose turn it is.\n",
    "  - The function `start_state(removed)` returns a state with a full board except for `removed` spaces.\n",
    "  - The functions `encode_state` and `decode_state` join and split a board/player pair.\n",
    "- **Space**: an integer from 0 to 35 (or in general, 0 to N<sup>2</sup> - 1). \n",
    "  - The function `space(x, y)` returns an integer representing the space with given `x` and `y` coordinates. \n",
    "  - The functions `x_(space)` and `y_(space)` invert that.\n",
    "- **Player**: a one-character string, `'*'` for black and `'o'` for white.\n",
    "  - The function `other(player)` gives the opponent player.\n",
    "- **Direction**: a direction of movement is an integer giving the difference between adjacent spaces.\n",
    "  - This is +1 for right; -1 for left; -6 for up (or in general, -N); +6 for down (or in general, +N).\n",
    "  - The function `go(space, direction, k)` gives the space that is `k` steps in `direction` from `space`.\n",
    "\n",
    "\n",
    "Here is the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing      import *\n",
    "from dataclasses import dataclass\n",
    "from functools   import lru_cache\n",
    "from collections import Counter, defaultdict\n",
    "from itertools   import takewhile\n",
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "################ Types\n",
    "\n",
    "Board  = int # A board is a bit string with a 1 bit for each space with a marble\n",
    "State  = int # A state is a board shifted left, with a bit indicated whose turn it is\n",
    "Space  = int # A space is an integer from 0 to N**2 - 1\n",
    "Player = str # A character, '*' or 'o'\n",
    "Direction = int # Direction of movement (left, right, up, down)\n",
    "\n",
    "################ Constants\n",
    "\n",
    "N      = 6\n",
    "black  = '*'\n",
    "white  = 'o'\n",
    "empty  = '·'\n",
    "\n",
    "################ Boards\n",
    "\n",
    "def get(board, space) -> str:\n",
    "    \"\"\"Get the contents of space on board: black, white, or empty.\"\"\"\n",
    "    return (empty if board & (1 << space) == 0 else\n",
    "            black if (x_(space) + y_(space)) % 2 == 0 else\n",
    "            white)\n",
    "\n",
    "def remove(board, spaces) -> Board: \n",
    "    \"\"\"Return a new board with the marbles on spaces removed.\"\"\"\n",
    "    return board - sum(1 << s for s in spaces)\n",
    "\n",
    "################ States\n",
    "\n",
    "def start_state(removed=(0, 1)) -> State:\n",
    "    \"\"\"A new NxN board with a marble in all spaces, except `removed`,\n",
    "    which should be a tuple of two spaces (default upper-left corner).\"\"\"\n",
    "    full = sum(1 << s for s in range(N * N))\n",
    "    return encode_state(remove(full, removed), black)\n",
    "\n",
    "def encode_state(board, player) -> State:\n",
    "    \"\"\"Combine the board and the player into a single int.\"\"\"\n",
    "    return board * 2 + (player == black)\n",
    "\n",
    "def decode_state(state) -> Tuple[Board, Player]:\n",
    "    \"\"\"Split the state into board and player components.\"\"\"\n",
    "    return state // 2, (black if state & 1 else white)\n",
    "\n",
    "################ Spaces\n",
    "\n",
    "def space(x, y) -> int: return N * y + x\n",
    "def x_(space) -> int:   return space % N\n",
    "def y_(space) -> int:   return space // N\n",
    "\n",
    "def center() -> Tuple[Space, Space]:\n",
    "    \"\"\"Two spaces in the center of the board.\"\"\"\n",
    "    m = N // 2\n",
    "    return space(m, m), space(m - 1, m)\n",
    "\n",
    "################ Players\n",
    "\n",
    "def other(player) -> Player: return white if player == black else black\n",
    "\n",
    "################ Directions\n",
    "\n",
    "L, R, U, D = directions = (-1, +1, -N, +N)\n",
    "\n",
    "def go(space, direction, steps=1) -> Optional[Space]:\n",
    "    \"\"\"The space that is `steps` in `direction` from `space`,\n",
    "    or `None` if going in that direction ends up off the board.\"\"\"\n",
    "    x, y = x_(space), y_(space)\n",
    "    return (space + steps * direction \n",
    "            if (direction == L and steps <= x)\n",
    "            or (direction == R and steps < N - x)\n",
    "            or (direction == U and steps <= y)\n",
    "            or (direction == D and steps < N - y)\n",
    "            else None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Displaying Game States\n",
    "\n",
    "The representation of a state is not very informative to look at, neither in decimal nor binary notation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "137438953465"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "start_state()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'0b1111111111111111111111111111111111001'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(_)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll define a function, `state_str`, to create better-looking output for a state:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def state_str(state) -> str:\n",
    "    \"\"\"A string depicting the given state of the game.\"\"\"\n",
    "    board, player = decode_state(state)\n",
    "    def row(y): return f'{y + 1} | {\" \".join(get(board, space(x, y)) for x in range(N))}'\n",
    "    return (f'    {\" \".join(columns[:N])} ({player} to move)\\n  +{\"--\" * N}\\n' +\n",
    "            '\\n'.join(row(y) for y in range(N)))\n",
    "\n",
    "columns = 'abcdefghijklmnopqrstuvwxyz'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | · · * o * o\n",
      "2 | o * o * o *\n",
      "3 | * o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n"
     ]
    }
   ],
   "source": [
    "print(state_str(start_state()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o * o * o\n",
      "2 | o * o * o *\n",
      "3 | * o * o * o\n",
      "4 | o * · · o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n"
     ]
    }
   ],
   "source": [
    "print(state_str(start_state(removed=center())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Making Moves\n",
    "\n",
    "The next step is to define `legal_moves(state)` which returns a list of the available legal moves from a state, and `make_move(state, move)` which returns a new state that is the result of the chosen move. \n",
    "\n",
    "A move is a structure with fields for the starting space, the ending space, and the space(s) of the opponent marble(s) that were jumped. I'll divide the task of finding legal moves into two phases: first define all the `potential_moves` that start at a given square and go in a given direction. In that direction there can be a single jump, a double jump, etc.; as long as the jump doesn't go off the edge of the board. The jumps are processed in that order, so when we get to, say, a triple jump, we know that the single- and double-jumps were legal; that makes checking each jump for legality easier. The function `potential_moves` doesn't consider what marbles are on the board; the function `legal_moves` does. \n",
    "\n",
    "I have these two separate functions and put a `@lru_cache` on `potential_moves` so that `Move` objects are created only once (for each of the 36 spaces and 4 directions), not millions of times for each state. Because `Move`s are not created millions of times, I'm not worried about trying to make them be efficient bit strings."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "@dataclass\n",
    "class Move:\n",
    "    \"\"\"A jumping move.\"\"\"\n",
    "    start:  Space\n",
    "    jumped: List[Space]\n",
    "    end:    Space\n",
    "        \n",
    "    def __str__(self):\n",
    "        start, end, *jumped = [f'{columns[x_(s)]}{y_(s) + 1}'\n",
    "                               for s in (self.start, self.end, *self.jumped)]\n",
    "        return f'{start} → {end} jumping {\" and \".join(jumped)}'\n",
    "\n",
    "def legal_moves(state) -> List[Move]:\n",
    "    \"\"\"All possible moves for player from this state.\"\"\"\n",
    "    board, player = decode_state(state)\n",
    "    opponent = other(player)\n",
    "    def legal(move) -> bool:\n",
    "        return get(board, move.jumped[-1]) == opponent and get(board, move.end) == empty\n",
    "    return [move for start in range(N * N) if get(board, start) == player\n",
    "                 for d in directions\n",
    "                 for move in takewhile(legal, potential_moves(start, d))]\n",
    "        \n",
    "@lru_cache(None)\n",
    "def potential_moves(start: Space, d: Direction) -> List[Move]:\n",
    "    \"\"\"All potential moves starting from space and going in direction, shortest first.\"\"\"\n",
    "    moves = []\n",
    "    for steps in range(2, N, 2):\n",
    "        end = go(start, d, steps)\n",
    "        if end is not None:\n",
    "            moves.append(Move(start, list(range(start + d, end, 2 * d)), end))\n",
    "    return moves\n",
    "        \n",
    "def make_move(state, move) -> State:\n",
    "    \"\"\"Make a move from this state to yield a new state.\"\"\"\n",
    "    board, player = decode_state(state)\n",
    "    board2 = remove(board | 1 << move.end, [move.start, *move.jumped])\n",
    "    return encode_state(board2, other(player))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are some examples of how these functions work:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "state1 = start_state()\n",
    "state2 = make_move(state1, Move(start=12, jumped=[6], end=0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | · · * o * o\n",
      "2 | o * o * o *\n",
      "3 | * o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'a3 → a1 jumping a2': Move(start=12, jumped=[6], end=0)}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(state_str(state1))\n",
    "{str(m): m for m in legal_moves(state1)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · * o * o\n",
      "2 | · * o * o *\n",
      "3 | · o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'d1 → b1 jumping c1': Move(start=3, jumped=[2], end=1),\n",
       " 'c2 → a2 jumping b2': Move(start=8, jumped=[7], end=6),\n",
       " 'b3 → b1 jumping b2': Move(start=13, jumped=[7], end=1)}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(state_str(state2))\n",
    "{str(m): m for m in legal_moves(state2)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Move(start=0, jumped=[6], end=12), Move(start=0, jumped=[6, 18], end=24)]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "potential_moves(space(0, 0), D)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Strategies and Playing Games\n",
    "\n",
    "We're now ready to play a game. The function `play_game` takes as input a dictionary with two keys, black and white, each mapped to a strategy for that player. A **strategy** is a function that takes a state as input and returns a move."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "Strategy = Callable[[State], Move]\n",
    "\n",
    "def play_game(strategies: Dict[Player, Strategy], start=None, verbose=True) -> Player:\n",
    "    \"\"\"Play a game between black and white, using their respective strategies.\n",
    "    Return the player that wins the game.\"\"\"\n",
    "    state = start or start_state()\n",
    "    while True:\n",
    "        board, player = decode_state(state)\n",
    "        if verbose: print(state_str(state))\n",
    "        moves = legal_moves(state)\n",
    "        if not moves:\n",
    "            if verbose: print(f'\\n{player} has no moves and loses')\n",
    "            return other(player)\n",
    "        else:\n",
    "            move = strategies[player](state)\n",
    "            if verbose: print(f'\\n{player} moves {move}\\n')\n",
    "            assert move in moves\n",
    "            state = make_move(state, move)\n",
    "            \n",
    "def play_games(strategies, k, start=None) -> Counter:\n",
    "    \"\"\"Play k games silently; return a count of winning players.\"\"\"\n",
    "    return Counter(play_game(strategies, start, False) for _ in range(k))\n",
    "            \n",
    "def random_strategy(state) -> Move:\n",
    "    \"\"\"Pick a random legal move.\"\"\"\n",
    "    return random.choice(legal_moves(state))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below black and white each play randomly:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | · · * o * o\n",
      "2 | o * o * o *\n",
      "3 | * o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves a3 → a1 jumping a2\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · * o * o\n",
      "2 | · * o * o *\n",
      "3 | · o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves d1 → b1 jumping c1\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · · * o\n",
      "2 | · * o * o *\n",
      "3 | · o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves c3 → c1 jumping c2\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o * · * o\n",
      "2 | · * · * o *\n",
      "3 | · o · o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves e2 → a2 jumping d2 and b2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o * · * o\n",
      "2 | o · · · · *\n",
      "3 | · o · o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves a5 → a3 jumping a4\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o * · * o\n",
      "2 | o · · · · *\n",
      "3 | * o · o * o\n",
      "4 | · * o * o *\n",
      "5 | · o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves e4 → e2 jumping e3\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o * · * o\n",
      "2 | o · · · o *\n",
      "3 | * o · o · o\n",
      "4 | · * o * · *\n",
      "5 | · o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves b4 → b2 jumping b3\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o * · * o\n",
      "2 | o * · · o *\n",
      "3 | * · · o · o\n",
      "4 | · · o * · *\n",
      "5 | · o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves c4 → e4 jumping d4\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o * · * o\n",
      "2 | o * · · o *\n",
      "3 | * · · o · o\n",
      "4 | · · · · o *\n",
      "5 | · o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves b6 → b4 jumping b5\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o * · * o\n",
      "2 | o * · · o *\n",
      "3 | * · · o · o\n",
      "4 | · * · · o *\n",
      "5 | · · * o * o\n",
      "6 | o · o * o *\n",
      "\n",
      "o moves b1 → b3 jumping b2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * · * · * o\n",
      "2 | o · · · o *\n",
      "3 | * o · o · o\n",
      "4 | · * · · o *\n",
      "5 | · · * o * o\n",
      "6 | o · o * o *\n",
      "\n",
      "* moves b4 → b2 jumping b3\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · * · * o\n",
      "2 | o * · · o *\n",
      "3 | * · · o · o\n",
      "4 | · · · · o *\n",
      "5 | · · * o * o\n",
      "6 | o · o * o *\n",
      "\n",
      "o moves d5 → b5 jumping c5\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * · * · * o\n",
      "2 | o * · · o *\n",
      "3 | * · · o · o\n",
      "4 | · · · · o *\n",
      "5 | · o · · * o\n",
      "6 | o · o * o *\n",
      "\n",
      "* moves f2 → d2 jumping e2\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · * · * o\n",
      "2 | o * · * · ·\n",
      "3 | * · · o · o\n",
      "4 | · · · · o *\n",
      "5 | · o · · * o\n",
      "6 | o · o * o *\n",
      "\n",
      "o moves f1 → b1 jumping e1 and c1\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · · · ·\n",
      "2 | o * · * · ·\n",
      "3 | * · · o · o\n",
      "4 | · · · · o *\n",
      "5 | · o · · * o\n",
      "6 | o · o * o *\n",
      "\n",
      "* moves e5 → e3 jumping e4\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · · · ·\n",
      "2 | o * · * · ·\n",
      "3 | * · · o * o\n",
      "4 | · · · · · *\n",
      "5 | · o · · · o\n",
      "6 | o · o * o *\n",
      "\n",
      "o moves b1 → b3 jumping b2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * · · · · ·\n",
      "2 | o · · * · ·\n",
      "3 | * o · o * o\n",
      "4 | · · · · · *\n",
      "5 | · o · · · o\n",
      "6 | o · o * o *\n",
      "\n",
      "* moves d6 → b6 jumping c6\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · · · · ·\n",
      "2 | o · · * · ·\n",
      "3 | * o · o * o\n",
      "4 | · · · · · *\n",
      "5 | · o · · · o\n",
      "6 | o * · · o *\n",
      "\n",
      "o moves a2 → a4 jumping a3\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * · · · · ·\n",
      "2 | · · · * · ·\n",
      "3 | · o · o * o\n",
      "4 | o · · · · *\n",
      "5 | · o · · · o\n",
      "6 | o * · · o *\n",
      "\n",
      "* moves b6 → b4 jumping b5\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · · · · ·\n",
      "2 | · · · * · ·\n",
      "3 | · o · o * o\n",
      "4 | o * · · · *\n",
      "5 | · · · · · o\n",
      "6 | o · · · o *\n",
      "\n",
      "o moves d3 → d1 jumping d2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * · · o · ·\n",
      "2 | · · · · · ·\n",
      "3 | · o · · * o\n",
      "4 | o * · · · *\n",
      "5 | · · · · · o\n",
      "6 | o · · · o *\n",
      "\n",
      "* moves b4 → b2 jumping b3\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · · o · ·\n",
      "2 | · * · · · ·\n",
      "3 | · · · · * o\n",
      "4 | o · · · · *\n",
      "5 | · · · · · o\n",
      "6 | o · · · o *\n",
      "\n",
      "o moves f3 → d3 jumping e3\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * · · o · ·\n",
      "2 | · * · · · ·\n",
      "3 | · · · o · ·\n",
      "4 | o · · · · *\n",
      "5 | · · · · · o\n",
      "6 | o · · · o *\n",
      "\n",
      "* moves f6 → d6 jumping e6\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · · o · ·\n",
      "2 | · * · · · ·\n",
      "3 | · · · o · ·\n",
      "4 | o · · · · *\n",
      "5 | · · · · · o\n",
      "6 | o · · * · ·\n",
      "\n",
      "o moves f5 → f3 jumping f4\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * · · o · ·\n",
      "2 | · * · · · ·\n",
      "3 | · · · o · o\n",
      "4 | o · · · · ·\n",
      "5 | · · · · · ·\n",
      "6 | o · · * · ·\n",
      "\n",
      "* has no moves and loses\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'o'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "randomly = {black: random_strategy, white: random_strategy}\n",
    "\n",
    "play_game(randomly)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can play 1000 random games and see who has an advantage:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'o': 512, '*': 488})"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play_games(randomly, 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It looks like white has a slight advantage if both players play randomly. But what if they are more clever?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Playing Optimally\n",
    "\n",
    "As promised, here I define:\n",
    "- `winner` to determine which player can force a win from a given state.\n",
    "- `optimal_strategy` to play perfectly, taking advantage of the knowledge cached in `winner`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def winner(state) -> Player:\n",
    "    \"\"\"The player that can force a win from this state.\"\"\"\n",
    "    _, player = decode_state(state)\n",
    "    return (player if any(winner(make_move(state, move)) == player \n",
    "                          for move in legal_moves(state))\n",
    "            else other(player))\n",
    "\n",
    "def optimal_strategy(state) -> Move:\n",
    "    \"\"\"Make a winning move if there is one.\"\"\"\n",
    "    _, player = decode_state(state)\n",
    "    for move in legal_moves(state):\n",
    "        if winner(make_move(state, move)) == player:\n",
    "            return move\n",
    "    return move"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving a Smaller Board: 4 by 4\n",
    "\n",
    "Before starting a time-consuming computation of the winner for a 6 by 6 board, I'd like to quickly validate the program on a smaller board; let's say 4 by 4. But I can't simply execute the statement `N = 4`, because other parts of the program depend on the value of `N`: the \"up\" and \"down\" directions `U` and `D`, as well as the caches for `potential_moves` and `winner`. So I'll introduce the function `set_N`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def set_N(n):\n",
    "    \"\"\"Use an n x n board; set global variables accordingly.\"\"\"\n",
    "    global N, R, L, U, D, directions\n",
    "    if n != N:\n",
    "        N = n\n",
    "        L, R, U, D = directions = (-1, +1, -N, +N)\n",
    "        potential_moves.cache_clear()\n",
    "        winner.cache_clear()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can solve 4 by 4 Konane:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('o', 'o')"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_N(4)\n",
    "\n",
    "winner(start_state()), winner(start_state(removed=center()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That says that **white is the winner on a 4 by 4 board, from either starting position**.\n",
    "\n",
    "Here's an optimally-played 4 by 4 game:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    a b c d (* to move)\n",
      "  +--------\n",
      "1 | · · * o\n",
      "2 | o * o *\n",
      "3 | * o * o\n",
      "4 | o * o *\n",
      "\n",
      "* moves a3 → a1 jumping a2\n",
      "\n",
      "    a b c d (o to move)\n",
      "  +--------\n",
      "1 | * · * o\n",
      "2 | · * o *\n",
      "3 | · o * o\n",
      "4 | o * o *\n",
      "\n",
      "o moves d1 → b1 jumping c1\n",
      "\n",
      "    a b c d (* to move)\n",
      "  +--------\n",
      "1 | * o · ·\n",
      "2 | · * o *\n",
      "3 | · o * o\n",
      "4 | o * o *\n",
      "\n",
      "* moves c3 → c1 jumping c2\n",
      "\n",
      "    a b c d (o to move)\n",
      "  +--------\n",
      "1 | * o * ·\n",
      "2 | · * · *\n",
      "3 | · o · o\n",
      "4 | o * o *\n",
      "\n",
      "o moves b1 → d1 jumping c1\n",
      "\n",
      "    a b c d (* to move)\n",
      "  +--------\n",
      "1 | * · · o\n",
      "2 | · * · *\n",
      "3 | · o · o\n",
      "4 | o * o *\n",
      "\n",
      "* has no moves and loses\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'o'"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "optimally = {black: optimal_strategy, white: optimal_strategy}\n",
    "\n",
    "play_game(optimally)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, white wins.\n",
    "\n",
    "Although white will win every game with optimal play, if white plays randomly, an optimal black player can win a majority of games:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({'*': 541, 'o': 459})"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play_games({black: optimal_strategy, white: random_strategy}, 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving a 5 by 5 Board\n",
    "\n",
    "We can repeat the exercise on a 5 by 5 board. This time I will check how long it takes to solve:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 668 ms, sys: 3.7 ms, total: 671 ms\n",
      "Wall time: 671 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "('*', '*')"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_N(5)\n",
    "\n",
    "%time winner(start_state()), winner(start_state(removed=center()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With a **5 by 5 board, black wins from either starting position**. The computation takes about 2/3 of a second."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving Mel's 6 by 6 Board\n",
    "\n",
    "Finally we are ready to solve the 6 by 6 board.  A 6 by 6 board has 2<sup>11</sup> = 2048 times more states than a 5 by 5 board, and each state is bigger and thus will take more time to process. So I estimate it will take about a half hour to fill the `winner` cache for a 6 by 6 board.  Let's find out (one starting position at a time):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 3min 55s, sys: 439 ms, total: 3min 55s\n",
      "Wall time: 3min 58s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'o'"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "set_N(6)\n",
    "\n",
    "%time winner(start_state())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So **white wins a 6 by 6 game** when we start with corner marbles removed. And the computation was a **lot faster** than I guessed! \n",
    "\n",
    "How many states were explored? The `cache_info` method will tell us:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "CacheInfo(hits=8397349, misses=10071659, maxsize=None, currsize=10071659)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "winner.cache_info()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `currsize` field is the number of states in the cache; about 10 million. \n",
    "\n",
    "Now let's see who wins if we start with the center marbles removed:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 1h 10min 59s, sys: 7.85 s, total: 1h 11min 7s\n",
      "Wall time: 1h 13min 34s\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'o'"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%time winner(start_state(removed=center()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**White wins there too**, but my celebration over the speed of the program was a bit premature–that took a full hour, double my estimate. We can count the total number of states from both starting positions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "CacheInfo(hits=188641148, misses=145177949, maxsize=None, currsize=145177949)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "winner.cache_info()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That's 145 million states. I guess it makes sense that there would be more reachable states starting from a position with the center pieces removed, because we can spread to any corner. It also makes sense that the corner-removed board leads to a search space that is more tree-like (the ratio of hits/misses–that is, the ratio of paths that lead to a state a second time to total states–is 0.8) and the center-removed board leads to a search space that is more graph-like (the ratio is 1.3).\n",
    "\n",
    "Here's an optimally-played game (which we expect white to win):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | · · * o * o\n",
      "2 | o * o * o *\n",
      "3 | * o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves a3 → a1 jumping a2\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * · * o * o\n",
      "2 | · * o * o *\n",
      "3 | · o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves d1 → b1 jumping c1\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · · * o\n",
      "2 | · * o * o *\n",
      "3 | · o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves a5 → a3 jumping a4\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · · * o\n",
      "2 | · * o * o *\n",
      "3 | * o * o * o\n",
      "4 | · * o * o *\n",
      "5 | · o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves f1 → d1 jumping e1\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | · * o * o *\n",
      "3 | * o * o * o\n",
      "4 | · * o * o *\n",
      "5 | · o * o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves c5 → a5 jumping b5\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | · * o * o *\n",
      "3 | * o * o * o\n",
      "4 | · * o * o *\n",
      "5 | * · · o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves c2 → a2 jumping b2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | o · · * o *\n",
      "3 | * o * o * o\n",
      "4 | · * o * o *\n",
      "5 | * · · o * o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves e5 → c5 jumping d5\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | o · · * o *\n",
      "3 | * o * o * o\n",
      "4 | · * o * o *\n",
      "5 | * · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves a2 → a4 jumping a3\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | · · · * o *\n",
      "3 | · o * o * o\n",
      "4 | o * o * o *\n",
      "5 | * · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves a5 → a3 jumping a4\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | · · · * o *\n",
      "3 | * o * o * o\n",
      "4 | · * o * o *\n",
      "5 | · · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves e2 → c2 jumping d2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | · · o · · *\n",
      "3 | * o * o * o\n",
      "4 | · * o * o *\n",
      "5 | · · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves d4 → d2 jumping d3\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · ·\n",
      "2 | · · o * · *\n",
      "3 | * o * · * o\n",
      "4 | · * o · o *\n",
      "5 | · · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves f3 → f1 jumping f2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · o * · ·\n",
      "3 | * o * · * ·\n",
      "4 | · * o · o *\n",
      "5 | · · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves f4 → d4 jumping e4\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · o * · ·\n",
      "3 | * o * · * ·\n",
      "4 | · * o * · ·\n",
      "5 | · · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "o moves c4 → a4 jumping b4\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · o * · ·\n",
      "3 | * o * · * ·\n",
      "4 | o · · * · ·\n",
      "5 | · · * · · o\n",
      "6 | o * o * o *\n",
      "\n",
      "* moves f6 → f4 jumping f5\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · o * · ·\n",
      "3 | * o * · * ·\n",
      "4 | o · · * · *\n",
      "5 | · · * · · ·\n",
      "6 | o * o * o ·\n",
      "\n",
      "o moves c2 → e2 jumping d2\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · · · o ·\n",
      "3 | * o * · * ·\n",
      "4 | o · · * · *\n",
      "5 | · · * · · ·\n",
      "6 | o * o * o ·\n",
      "\n",
      "* moves d6 → f6 jumping e6\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · · · o ·\n",
      "3 | * o * · * ·\n",
      "4 | o · · * · *\n",
      "5 | · · * · · ·\n",
      "6 | o * o · · *\n",
      "\n",
      "o moves e2 → e4 jumping e3\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · · · · ·\n",
      "3 | * o * · · ·\n",
      "4 | o · · * o *\n",
      "5 | · · * · · ·\n",
      "6 | o * o · · *\n",
      "\n",
      "* moves b6 → d6 jumping c6\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · · · · ·\n",
      "3 | * o * · · ·\n",
      "4 | o · · * o *\n",
      "5 | · · * · · ·\n",
      "6 | o · · * · *\n",
      "\n",
      "o moves a4 → a2 jumping a3\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | o · · · · ·\n",
      "3 | · o * · · ·\n",
      "4 | · · · * o *\n",
      "5 | · · * · · ·\n",
      "6 | o · · * · *\n",
      "\n",
      "* moves c3 → a3 jumping b3\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | o · · · · ·\n",
      "3 | * · · · · ·\n",
      "4 | · · · * o *\n",
      "5 | · · * · · ·\n",
      "6 | o · · * · *\n",
      "\n",
      "o moves a2 → a4 jumping a3\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | * o · o · o\n",
      "2 | · · · · · ·\n",
      "3 | · · · · · ·\n",
      "4 | o · · * o *\n",
      "5 | · · * · · ·\n",
      "6 | o · · * · *\n",
      "\n",
      "* moves a1 → e1 jumping b1 and d1\n",
      "\n",
      "    a b c d e f (o to move)\n",
      "  +------------\n",
      "1 | · · · · * o\n",
      "2 | · · · · · ·\n",
      "3 | · · · · · ·\n",
      "4 | o · · * o *\n",
      "5 | · · * · · ·\n",
      "6 | o · · * · *\n",
      "\n",
      "o moves f1 → d1 jumping e1\n",
      "\n",
      "    a b c d e f (* to move)\n",
      "  +------------\n",
      "1 | · · · o · ·\n",
      "2 | · · · · · ·\n",
      "3 | · · · · · ·\n",
      "4 | o · · * o *\n",
      "5 | · · * · · ·\n",
      "6 | o · · * · *\n",
      "\n",
      "* has no moves and loses\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'o'"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "play_game(optimally)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "Here's a chart of who has a forced win for various values of **N**, in the cases where the two marbles are removed from the corner and from the center:\n",
    "\n",
    "|N|Corner|Center|\n",
    "|-|------|------|\n",
    "|4|white|white|\n",
    "|5|black|black|\n",
    "|6|white|white|\n",
    "|7+|?????|?????|\n",
    "\n",
    "# Further Work\n",
    "\n",
    "I'll stop here, but here are some things that you could look into if you are interested:\n",
    "\n",
    "- **Make it prettier**: Use graphics for the output, e.g. ⚪️ and ⚫️ instead of 'o' and '*'.\n",
    "- **Make it interactive**: allow players to click on the board to make moves and set up positions. An interactive web page would be great, but loading 145 million positions into it would take a while. But you could trim that down: the 145 million states include the exploration of multiple paths for the optimal player, until a winning path is found. You could eliminate all branches of the tree except for one winning choice at each choice point for the optimal player (and all responses for the opponent).\n",
    "- **Use a faster language**: Statically-typed languages like Java or C++ or Go can typically execute faster than Python. Of particular interest for this program, in Python 3 the `int` returned by `start_state()` uses 32 bytes of memory. There is overhead to store the reference count, the type of the object, etc. Other languages can represent a state in just 8 bytes, as a 64-bit integer.\n",
    "- **Use concurrency**: Python is not a convenient language for taking advantage of multiple CPUs, so I didn't try to parallelize the search. But you could.\n",
    "- **Find heuristics for good but non-optimal play**: No matter how clever we get, there will be some value of **N** beyond which solving the game is impractical. But we could still achieve good play by doing alpha-beta search to a certain cut-off level and using an evaluation function to rank the resulting game states.  The evaluation function could be hand-crafted from features or learned with machine learning. Alternatively, Monte Carlo tree search could be used; this does not require an evaluation function.\n",
    "- **Explore the computational complexity**: My friend Bob Hearn has a nice [paper](https://www.semanticscholar.org/paper/Amazons%2C-Konane%2C-and-Cross-Purposes-are-Hearn/89f291d89c09de98a14bb265e996cd008ddd4e92) proving that Konane is PSPACE-complete. What else can be said?\n",
    "- **Apply combinatorial game theory**: A [paper](https://www.cs.cmu.edu/~sleator/papers/Sprouts.htm) by several authors including my friend Danny Sleator shows how to use combinatorial game theory to break a game state into components that can be analyzed separately and then combined. Using these techniques allowed them to solve the game of Sprouts for much larger sizes than had been done before; I suspect the same approach would work for Konane. Whether combinatorial game theory would work for Konane or not, it is a fascinating piece of mathematics to know about. As Bob Hearn said in [a review](http://webdocs.cs.ualberta.ca/~hayward/cgt/asn/hearn-WW.pdf) of the classic [Winning Ways for Your Mathematical Plays](https://www.amazon.com/Elwyn-R-Berlekamp/e/B001HQ1K5A/ref=dp_byline_cont_pop_book_1), \"The theory hinges on an amazing discovery of [John] Conway. In a nutshell, the natural unification of Cantor’s construction of the ordinals with Dedekind’s construction of the reals yields, in one stroke, not only the fabulous number system that Donald Knuth dubbed the surreal numbers, but also a natural framework for combinatorial games. It’s as if the the mathematics we all know, that underpins all of science, were suddenly revealed to be a just special case of games: the universe is telling us that ultimately, it’s all about play.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Appendix: Tests\n",
    "\n",
    "Some simple tests of the low-level functions:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def test():\n",
    "    set_N(6)\n",
    "    state = start_state()\n",
    "    board, player = decode_state(state)\n",
    "    assert state == encode_state(board, player)\n",
    "    assert player == black\n",
    "    assert get(board, 0) == empty and get(board, 2) == black and get(board, 3) == white\n",
    "    \n",
    "    board2 = remove(board, [3, 4])\n",
    "    assert get(board2, 3) == empty\n",
    "    \n",
    "    s = space(0, 0)\n",
    "    assert (go(s, R), go(s, L), go(s, U), go(s, D)) == (1, None, None, 6)\n",
    "    \n",
    "    s = space(2, 1)\n",
    "    assert s == 8 and x_(s) == 2 and y_(s) == 1\n",
    "    assert go(s, R) == space(3, 1)\n",
    "    assert go(s, L) == space(1, 1)\n",
    "    assert go(s, U) == space(2, 0)\n",
    "    assert go(s, D) == space(2, 2)\n",
    "    assert go(s, L, 2) == space(0, 1)\n",
    "    assert go(s, L, 3) == None\n",
    "    \n",
    "    assert other(black) == white and other(white) == black\n",
    "    \n",
    "    assert potential_moves(0, R) == [Move(start=0, jumped=[1], end=2), \n",
    "                                     Move(start=0, jumped=[1, 3], end=4)]\n",
    "    return True\n",
    "\n",
    "test()"
   ]
  }
 ],
 "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.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}