ipynb/Cant-Stop.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Can't Stop board](https://upload.wikimedia.org/wikipedia/en/thumb/0/04/CantStop-sm.png/250px-CantStop-sm.png)\n",
    "\n",
    "# Can't Stop Game\n",
    "\n",
    "**[Can't Stop](https://en.wikipedia.org/wiki/Can%27t_Stop_(board_game&#41;)** is a board game with [these rules](https://www.yucata.de/en/Rules/CantStop). In this notebook I will explore rational plays in the game. (Note: I use a term that is not in the rule book: what they call a \"marker\" or \"neutral marker,\" I call a \"sherpa\": a guide for leading you to the top.)\n",
    "\n",
    "\n",
    "# Representing Dice Rolls\n",
    "\n",
    "The first thing I'll want to model is rolls of the dice. A player rolls four dice, and let's say gets 2-3-5-6.\n",
    "The player must arrange the four dice into two pairs. In this case there are three ways to do it:\n",
    "\n",
    "# ⚁ ⚂, ⚄ ⚅ = 5, 11<br>⚁ ⚄, ⚅ ⚂ = 7, 9<br>⚁ ⚅, ⚄ ⚂ = 8, 8\n",
    "\n",
    "I'll define the function `Roll` to return a set of all possible ways of pairing up four dice. (I'll make it a *hashable* set, because I'll need that later.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from itertools   import combinations, product\n",
    "from functools   import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def Roll(a, b, c, d): \n",
    "    \"A set of all the pairs of numbers that can be made with these 4 dice.\"\n",
    "    return Set((Pair(a+b, c+d), Pair(a+c, b+d), Pair(a+d, b+c)))\n",
    "\n",
    "def Pair(a, b): return (a, b) if a < b else (b, a)\n",
    "\n",
    "class Set(set):\n",
    "    \"A hashable set. Caveat mutator!\"\n",
    "    def __hash__(self): return sum(map(hash, self))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(5, 11), (7, 9), (8, 8)}"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Roll(2, 3, 5, 6) # You get 3 choices with 4 distinct numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(5, 9), (6, 8)}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Roll(2, 3, 3, 6) # You get 2 choices with 3 distinct numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(4, 8)}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Roll(2, 2, 2, 6) # You get 1 choice with 1 or 2 distinct numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now I want to consider all possible dice rolls. In this game, the roll 2-3-5-6 is the same as 6-5-3-2; there are 24 permutations of 4 numbers. So rather than a `list` of rolls, I'll make a `Counter`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Counter({{(2, 2)}: 1,\n",
       "         {(2, 3)}: 4,\n",
       "         {(2, 4)}: 4,\n",
       "         {(2, 5)}: 4,\n",
       "         {(2, 6)}: 4,\n",
       "         {(2, 7)}: 4,\n",
       "         {(2, 4), (3, 3)}: 6,\n",
       "         {(2, 5), (3, 4)}: 12,\n",
       "         {(2, 6), (3, 5)}: 12,\n",
       "         {(2, 7), (3, 6)}: 12,\n",
       "         {(2, 8), (3, 7)}: 12,\n",
       "         {(2, 6), (4, 4)}: 6,\n",
       "         {(2, 7), (4, 5)}: 12,\n",
       "         {(2, 8), (4, 6)}: 12,\n",
       "         {(2, 9), (4, 7)}: 12,\n",
       "         {(2, 8), (5, 5)}: 6,\n",
       "         {(2, 9), (5, 6)}: 12,\n",
       "         {(2, 10), (5, 7)}: 12,\n",
       "         {(2, 10), (6, 6)}: 6,\n",
       "         {(2, 11), (6, 7)}: 12,\n",
       "         {(2, 12), (7, 7)}: 6,\n",
       "         {(3, 4)}: 4,\n",
       "         {(3, 5), (4, 4)}: 12,\n",
       "         {(3, 6), (4, 5)}: 24,\n",
       "         {(4, 6)}: 8,\n",
       "         {(3, 7), (4, 6)}: 12,\n",
       "         {(3, 8), (4, 7)}: 12,\n",
       "         {(3, 7), (4, 6), (5, 5)}: 24,\n",
       "         {(3, 8), (4, 7), (5, 6)}: 24,\n",
       "         {(4, 8), (5, 7)}: 24,\n",
       "         {(3, 9), (4, 8), (5, 7)}: 24,\n",
       "         {(3, 8), (5, 6)}: 12,\n",
       "         {(3, 9), (5, 7), (6, 6)}: 24,\n",
       "         {(3, 10), (6, 7)}: 12,\n",
       "         {(5, 8)}: 4,\n",
       "         {(3, 10), (5, 8), (6, 7)}: 24,\n",
       "         {(3, 11), (6, 8), (7, 7)}: 24,\n",
       "         {(3, 12), (7, 8)}: 12,\n",
       "         {(4, 7), (5, 6)}: 24,\n",
       "         {(4, 8), (6, 6)}: 18,\n",
       "         {(4, 9), (6, 7)}: 24,\n",
       "         {(4, 9), (5, 8), (6, 7)}: 24,\n",
       "         {(4, 10), (5, 9), (7, 7)}: 24,\n",
       "         {(4, 10), (6, 8)}: 24,\n",
       "         {(4, 11), (6, 9), (7, 8)}: 24,\n",
       "         {(4, 12), (7, 9)}: 12,\n",
       "         {(5, 9), (6, 8)}: 24,\n",
       "         {(5, 10), (7, 8)}: 24,\n",
       "         {(5, 10), (6, 9)}: 12,\n",
       "         {(5, 11), (6, 10), (7, 9)}: 24,\n",
       "         {(5, 12), (7, 10)}: 12,\n",
       "         {(6, 10)}: 4,\n",
       "         {(6, 11), (7, 10)}: 12,\n",
       "         {(6, 12), (7, 11)}: 12,\n",
       "         {(7, 12)}: 4,\n",
       "         {(4, 4)}: 1,\n",
       "         {(4, 5)}: 4,\n",
       "         {(4, 7)}: 4,\n",
       "         {(4, 8)}: 4,\n",
       "         {(4, 6), (5, 5)}: 6,\n",
       "         {(4, 9), (5, 8)}: 12,\n",
       "         {(4, 10), (7, 7)}: 6,\n",
       "         {(4, 11), (7, 8)}: 12,\n",
       "         {(4, 12), (8, 8)}: 6,\n",
       "         {(5, 6)}: 4,\n",
       "         {(5, 7), (6, 6)}: 12,\n",
       "         {(5, 8), (6, 7)}: 24,\n",
       "         {(5, 9), (6, 8), (7, 7)}: 24,\n",
       "         {(5, 10), (6, 9), (7, 8)}: 24,\n",
       "         {(5, 11), (7, 9), (8, 8)}: 24,\n",
       "         {(5, 12), (8, 9)}: 12,\n",
       "         {(6, 8)}: 8,\n",
       "         {(6, 9), (7, 8)}: 24,\n",
       "         {(6, 10), (8, 8)}: 18,\n",
       "         {(6, 10), (7, 9)}: 24,\n",
       "         {(6, 11), (7, 10), (8, 9)}: 24,\n",
       "         {(6, 12), (8, 10)}: 12,\n",
       "         {(7, 10)}: 4,\n",
       "         {(7, 11), (8, 10)}: 12,\n",
       "         {(7, 12), (8, 11)}: 12,\n",
       "         {(8, 12)}: 4,\n",
       "         {(6, 6)}: 1,\n",
       "         {(6, 7)}: 4,\n",
       "         {(6, 9)}: 4,\n",
       "         {(6, 8), (7, 7)}: 6,\n",
       "         {(6, 11), (8, 9)}: 12,\n",
       "         {(6, 12), (9, 9)}: 6,\n",
       "         {(7, 8)}: 4,\n",
       "         {(7, 9), (8, 8)}: 12,\n",
       "         {(7, 10), (8, 9)}: 24,\n",
       "         {(7, 11), (8, 10), (9, 9)}: 24,\n",
       "         {(7, 12), (9, 10)}: 12,\n",
       "         {(8, 10)}: 8,\n",
       "         {(8, 11), (9, 10)}: 24,\n",
       "         {(8, 12), (9, 11)}: 12,\n",
       "         {(9, 12)}: 4,\n",
       "         {(8, 8)}: 1,\n",
       "         {(8, 9)}: 4,\n",
       "         {(8, 10), (9, 9)}: 6,\n",
       "         {(8, 12), (10, 10)}: 6,\n",
       "         {(9, 10)}: 4,\n",
       "         {(9, 11), (10, 10)}: 12,\n",
       "         {(9, 12), (10, 11)}: 12,\n",
       "         {(10, 12)}: 4,\n",
       "         {(10, 10)}: 1,\n",
       "         {(10, 11)}: 4,\n",
       "         {(10, 12), (11, 11)}: 6,\n",
       "         {(11, 12)}: 4,\n",
       "         {(12, 12)}: 1})"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "die = (1, 2, 3, 4, 5, 6)\n",
    "all_rolls = Counter(Roll(*dice) for dice in product(die, repeat=4))\n",
    "all_rolls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(109, 1296)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The number of different rolls, and the total number of rolls\n",
    "len(all_rolls), sum(all_rolls.values()) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What Columns Can a Roll Make?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I'll define the function `best_pairing` to return the maximum *worth* that a roll can make,  given the columns we are trying to make, and a function, `worth`, that says how much it is worth to advance a space in a column. (The default is that each space advanced is worth one point, regardless of column.) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def one(col): \"One space advanced is worth 1 point.\"; return 1\n",
    "\n",
    "def best_pairing(columns, roll, worth=one):\n",
    "    \"The maximum total worth of a roll, considering all ways of pairing up the roll.\"\n",
    "    return max((a in columns) * worth(a) + (b in columns) * worth(b) \n",
    "               for (a, b) in roll)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, consider again the  roll `(2, 3, 5, 6)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(5, 11), (7, 9), (8, 8)}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "roll = Roll(2, 3, 5, 6)\n",
    "roll"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What can we do with that roll?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_pairing([7], roll) # We can get 1 point for making 7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_pairing([6, 10, 12], roll) # We can't get any of 6-10-12; we've \"blown it\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_pairing([5, 7, 12], roll) # We can get 5, or we can get 7, but we can't get both at once"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_pairing([5, 7, 11], roll) # We can get 5 and 11 (which is more than just getting 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_pairing([8], roll) # We can get 8 twice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "# Probabilities and Expectations\n",
    "\n",
    "The function `best_pairing` gives us an answer for one roll, but what about over all possible rolls? \n",
    "\n",
    "The function `E(columns, worth)` gives the expectation (that is, the mean value), of the total `worth` averaged over all possible rolls. \n",
    "\n",
    "The function `P(columns)` gives the probability of advancing in at least one of the columns (that is, the probability of not blowing it)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@lru_cache(None)\n",
    "def E(columns, worth):\n",
    "    \"The expected value over all rolls of the pairing that maximizes the sum of `worth(col)`.\"\n",
    "    return sum(best_pairing(columns, roll, worth) * all_rolls[roll] \n",
    "               for roll in all_rolls) / sum(all_rolls.values())\n",
    "\n",
    "@lru_cache(None)\n",
    "def P(columns):\n",
    "    \"The probability of not blowing it, given these columns.\"\n",
    "    return sum(bool(best_pairing(columns, roll)) * all_rolls[roll] \n",
    "               for roll in all_rolls) / sum(all_rolls.values())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that because I use `lru_cache`, from now on I'll represent a collection of columns as a tuple, not a list. \n",
    "\n",
    "First, let's ask what's the probability of being able to make at least one 7? And whats the expected value of the number of 7s we can make?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6435185185185185"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P((7,))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7129629629629629"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E((7,), one)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How about column 2?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.13194444444444445"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P((2,))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.13271604938271606"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E((2,), one)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Column Progress\n",
    "\n",
    "Another important concept is **progress** towards claiming a column. While we have seen that it is easier to make a 7 than a 2, advancing a space in the 2 column is more valuable in the sense that it gets you 1/3 of the way to claiming the column, while advancing in the 7 column gets you only 1/13 of the way. We will implement `progress`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "col_length = [0, 0, 3, 5, 7, 9, 11, 13, 11, 9, 7, 5, 3]\n",
    "\n",
    "def progress(col):\n",
    "    \"The amount of progress as a fraction of the column's length.\"\n",
    "    return 1 / col_length[col] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.05484330484330481"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E((7,), progress)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.04423868312757201"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "E((2,), progress)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How Easy or Difficult is Each Column?\n",
    "\n",
    "Now, let's create a table that, for each column, answers these questions:\n",
    "- What column number is it?\n",
    "- What's the probability of being able to make that column's number?\n",
    "- What's the expected number of spaces we can advance in that column in one roll?\n",
    "- What's the expected progress in that column for one roll?\n",
    "- What is the length of the column on the game board?\n",
    "- What is the expected number of rolls it would take to claim the column? (The reciprocal of `progress`.)\n",
    "- What is the expected number of *remaining* rolls it would take to claim the column: if we choose to\n",
    "advance in the column in this roll, how many additional rolls would it take, on average, to claim the column?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  c  P(c) E(c) progr len rolls remaining\n",
      " ==  ==== ==== ===== === ===== ====\n",
      "  2  13%  0.13 0.044   3  22.6 15.1\n",
      "  3  23%  0.24 0.048   5  21.0 16.8\n",
      "  4  36%  0.37 0.053   7  18.9 16.2\n",
      "  5  45%  0.48 0.053   9  18.9 16.8\n",
      "  6  56%  0.61 0.055  11  18.1 16.4\n",
      "  7  64%  0.71 0.055  13  18.2 16.8\n",
      "  8  56%  0.61 0.055  11  18.1 16.4\n",
      "  9  45%  0.48 0.053   9  18.9 16.8\n",
      " 10  36%  0.37 0.053   7  18.9 16.2\n",
      " 11  23%  0.24 0.048   5  21.0 16.8\n",
      " 12  13%  0.13 0.044   3  22.6 15.1\n"
     ]
    }
   ],
   "source": [
    "print('  c  P(c) E(c) progr len rolls remaining')\n",
    "print(' ==  ==== ==== ===== === ===== ====')\n",
    "for c in range(2, 13):\n",
    "    Ec, Ep = E((c,), one), E((c,), progress)\n",
    "    print(' {:2}  {:2.0%}  {:4.2f} {:5.3f}  {:2}  {:4.1f} {:4.1f}'\n",
    "          .format(c, P((c,)), Ec, Ep, col_length[c],  col_length[c] / Ec, (col_length[c] - 1) / Ec))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, while 7 is the easiest column to make (at 64%), 6 and 8 are the easiest columns to claim (taking 18.1 rolls to claim, on average; this means that 6 and 8 give you the highest expected progress per roll). Columns 2 and 12 are the hardest to claim.\n",
    "\n",
    "But, if you happen to roll a combination that can make a 2 or a 12, it may be a good idea to take it, because then you only need an expected 15.1 more rolls to claim the column, which is better than any of the other columns.\n",
    "\n",
    "Overall, this tells me that [Sid Sackson](https://en.wikipedia.org/wiki/Sid_Sackson) did an amazingly good job of making the game balanced!  \n",
    "\n",
    "# How Good is Each Combination of 3 Sherpas?\n",
    "\n",
    "Intuitively, you are unlikely to blow it with sherpas on 6, 7, and 8, and more likely with, say, 2, 11, and 12. Let's quantify that intuition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9197530864197531"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P((6, 7, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4382716049382716"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P((2, 11, 12))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So there's a 91.97% chance of not blowing it if you have 6-7-8, but only  43.8% if you have 2-11-12. \n",
    "\n",
    "Let's see which combinations of sherpas are best overall, under a variety of criteria:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# All possible combinations of three sherpas\n",
    "def top(n, fn, fmt='{:6.3f} {}'.format): \n",
    "    \"Print best n triples of sherpas, in order, along with their fn(sherpas) values.\"\n",
    "    C = Counter({sherpas: fn(sherpas) \n",
    "                 for sherpas in combinations(range(2, 13), 3)})\n",
    "    for (sherpas, val) in C.most_common(n):\n",
    "        print(fmt(val, sherpas))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0.920 (6, 7, 8)\n",
      " 0.914 (5, 7, 8)\n",
      " 0.914 (6, 7, 9)\n",
      " 0.911 (4, 6, 8)\n",
      " 0.911 (6, 8, 10)\n",
      " 0.903 (4, 7, 8)\n",
      " 0.903 (6, 7, 10)\n",
      " 0.895 (5, 6, 8)\n",
      " 0.895 (6, 8, 9)\n",
      " 0.893 (3, 7, 8)\n",
      " 0.893 (4, 7, 9)\n",
      " 0.893 (5, 7, 10)\n",
      " 0.893 (6, 7, 11)\n",
      " 0.890 (2, 7, 8)\n",
      " 0.890 (6, 7, 12)\n",
      " 0.887 (5, 6, 7)\n",
      " 0.887 (7, 8, 9)\n",
      " 0.886 (4, 6, 7)\n",
      " 0.886 (7, 8, 10)\n",
      " 0.883 (2, 6, 8)\n",
      " 0.883 (4, 6, 10)\n",
      " 0.883 (4, 8, 10)\n",
      " 0.883 (6, 8, 12)\n",
      " 0.877 (4, 7, 10)\n",
      " 0.867 (5, 6, 9)\n",
      " 0.867 (5, 8, 9)\n",
      " 0.865 (3, 6, 7)\n",
      " 0.865 (7, 8, 11)\n",
      " 0.864 (2, 6, 7)\n",
      " 0.864 (4, 6, 9)\n"
     ]
    }
   ],
   "source": [
    "# The combinations of sherpas that are best for not blowing it:\n",
    "top(30, P)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 1.318 (6, 7, 8)\n",
      " 1.296 (5, 7, 8)\n",
      " 1.296 (6, 7, 9)\n",
      " 1.242 (4, 7, 8)\n",
      " 1.242 (6, 7, 10)\n",
      " 1.231 (5, 6, 7)\n",
      " 1.231 (7, 8, 9)\n",
      " 1.228 (5, 6, 8)\n",
      " 1.228 (6, 8, 9)\n",
      " 1.219 (4, 6, 7)\n",
      " 1.219 (7, 8, 10)\n",
      " 1.193 (4, 6, 8)\n",
      " 1.193 (6, 8, 10)\n",
      " 1.184 (3, 7, 8)\n",
      " 1.184 (4, 7, 9)\n",
      " 1.184 (5, 7, 10)\n",
      " 1.184 (6, 7, 11)\n",
      " 1.151 (5, 6, 9)\n",
      " 1.151 (5, 8, 9)\n",
      " 1.148 (2, 7, 8)\n",
      " 1.148 (6, 7, 12)\n",
      " 1.147 (3, 6, 7)\n",
      " 1.147 (7, 8, 11)\n",
      " 1.145 (5, 7, 9)\n",
      " 1.123 (4, 5, 7)\n",
      " 1.123 (7, 9, 10)\n",
      " 1.116 (2, 6, 7)\n",
      " 1.116 (4, 6, 9)\n",
      " 1.116 (5, 8, 10)\n",
      " 1.116 (7, 8, 12)\n"
     ]
    }
   ],
   "source": [
    "# The combinations of sherpas that advance the most number of spaces in one roll:\n",
    "top(30, lambda s: E(s, one))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0.143 (2, 4, 10)\n",
      " 0.143 (4, 10, 12)\n",
      " 0.140 (2, 8, 12)\n",
      " 0.140 (2, 6, 12)\n",
      " 0.139 (2, 5, 11)\n",
      " 0.139 (3, 9, 12)\n",
      " 0.138 (2, 8, 10)\n",
      " 0.138 (4, 6, 12)\n",
      " 0.138 (2, 6, 10)\n",
      " 0.138 (4, 8, 12)\n",
      " 0.138 (2, 4, 11)\n",
      " 0.138 (3, 10, 12)\n",
      " 0.138 (4, 6, 10)\n",
      " 0.138 (4, 8, 10)\n",
      " 0.138 (4, 9, 12)\n",
      " 0.138 (2, 5, 10)\n",
      " 0.138 (3, 4, 10)\n",
      " 0.138 (4, 10, 11)\n",
      " 0.137 (2, 6, 11)\n",
      " 0.137 (3, 8, 12)\n",
      " 0.137 (2, 7, 12)\n",
      " 0.136 (4, 6, 11)\n",
      " 0.136 (3, 8, 10)\n",
      " 0.136 (2, 9, 12)\n",
      " 0.136 (2, 4, 9)\n",
      " 0.136 (2, 5, 12)\n",
      " 0.136 (5, 10, 12)\n",
      " 0.136 (2, 4, 8)\n",
      " 0.136 (6, 10, 12)\n",
      " 0.136 (2, 3, 10)\n"
     ]
    }
   ],
   "source": [
    "# The combinations of sherpas that give the most progress towards claiming columns in one roll:\n",
    "top(30, lambda s: E(s, progress))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Interesting. The results for `progress` are quite different from the others: either 2 or 12 shows up in *all* of the top dozen spots for `progress`, but *none* of the top dozen for the other two."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Odd versus Even\n",
    "\n",
    "You may have noticed that even numbers are more common at the top of these lists than odd numbers. That is in part because it is always possible to make some even column, no matter what roll you get, while rolls that do not contain an odd number (or that contain 4 odd numbers) cannot make odd columns: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P((2, 4, 6, 8, 10, 12))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.875"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P((3, 5, 7, 9, 11))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Should I stop or should I roll?\n",
    "\n",
    "Now we're ready for the key question: when should I roll and when should I stop? Clearly, if you have fewer than 3 sherpas on the board, and if no column has been claimed, then you should always roll, because you will always be able to make some column. But once you have three sherpas, at some point you will want to stop; every time you roll you risk losing the progress you have made so far. Let's figure out under what conditions you should stop. Here are the points I considered:\n",
    "\n",
    "- Ultimately, you want to optimize the chance of winning the game, but that is too hard a goal for right now. Instead we'll try to maximize total progress (which is a good proxy for winning, at least in the opening phases of the game).\n",
    "\n",
    "- We'll define `optimal(sherpas, worth)` to return the expected total worth of an entire turn, assuming optimal play in pairing the dice and in deciding when to stop.  \n",
    "\n",
    "- The function `optimal` calls the recursive function `optimal_1`, which has some additional parameters: `sofar` is the total worth accumlated on this turn; `maxrolls` is the maximum number of rolls in a turn (otherwise we would recurse forever); and `cache` is a cache of intermediate results. \n",
    "\n",
    "- Why did I arrange things that way? Because I know that this is a dynamic programming problem, where the cache will be important in making the function run faster. But `@lru_cache` won't do the job properly: if the correct move is to *stop* when you have accumulated a certain amount of worth `sofar`, then stopping should be the correct move regardless of what the `maxdepth` is. But `@lru_cache` would compute a separate result for each value of `maxdepth`; that would be doing more computation than necessary. So I manage my own cache, which (for a given set of sherpas and worth function) depends only on `sofar`, not on `maxdepth`.\n",
    "\n",
    "- The overall approach for `optimal` / `optimal_1` is to stop (and return the accumlated worth `sofar`) when `maxdepth` hits zero, and otherwise to consider the weighted mean of optimal play over all possible rolls, and compare that to the result you would get from stopping (namely, `sofar`). \n",
    "\n",
    "- It is unfortunate that the way I defined the expectation function, `E`, I can't reuse it here; I need to define a new function, `weighted_mean`.\n",
    "\n",
    "- I also define `decision` to return `'ROLL'` or `'STOP'`, whichever is optimal.\n",
    "\n",
    "- I also define `stopping_point` to say at what point (in terms of total worth) you should stop.\n",
    "\n",
    "- Why do I define `optimal_1` to have a `maxrolls` of 16? By empirical tests (not shown here), I determined that any larger value gives the same results (and just takes longer to compute), but any smaller value gives different (sub-optimal) results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "@lru_cache(1024)\n",
    "def optimal(sherpas, worth=progress):\n",
    "    \"The expected total worth, assuming optimal play.\"\n",
    "    return optimal_1(sherpas, worth, {})\n",
    "\n",
    "@lru_cache(1024)\n",
    "def stopping_point(sherpas, worth=progress):\n",
    "    \"At what total worth should you stop rather than roll?\"\n",
    "    cache = {}\n",
    "    optimal_1(sherpas, worth, cache)\n",
    "    return min(sofar for sofar in cache if sofar == cache[sofar])\n",
    "\n",
    "def optimal_1(sherpas, worth, cache, sofar=None, maxrolls=16):\n",
    "    \"The expected total worth, with a cache that depends only on `sofar`.\"\n",
    "    if sofar is None: \n",
    "        sofar = sum(map(worth, sherpas))\n",
    "    if sofar not in cache:\n",
    "        if maxrolls == 0:\n",
    "            cache[sofar] = sofar\n",
    "        else:\n",
    "            def roll_it(roll):\n",
    "                this_turn = best_pairing(sherpas, roll, worth)\n",
    "                return (0 if this_turn == 0 else\n",
    "                        optimal_1(sherpas, worth, cache, sofar + this_turn, maxrolls - 1))\n",
    "            cache[sofar] = max(sofar, weighted_mean(roll_it, all_rolls))\n",
    "    return cache[sofar]\n",
    "    \n",
    "def weighted_mean(func, counter):\n",
    "    \"The weighted mean of func(x), for each x is counter.\"\n",
    "    return sum(func(x) * counter[x] \n",
    "               for x in counter) / sum(counter.values())\n",
    "\n",
    "def decision(sherpas, worth=progress, sofar=None):\n",
    "    \"Return 'STOP' or 'ROLL', whichever gives a higher score.\"\n",
    "    if sofar is None: \n",
    "        sofar = sum(map(worth, sherpas))\n",
    "    return ('STOP' if optimal(sherpas, worth) == sofar else 'ROLL')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some examples. First consider sherpas on 2-3-12, using the `one` worth function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "optimal((2, 3, 12), one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'STOP'"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decision((2, 3, 12), one)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stopping_point((2, 3, 12), one)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's look at 6-7-8, using the (default) `progress` worth function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6579805166909175"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "optimal((6, 7, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ROLL'"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decision((6, 7, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.44055944055944"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stopping_point((6, 7, 8))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This might look like a contradiction: the expected value is 0.65798 (that is, total progress equivalent to about 2/3 towards claiming a column), but the stopping point is 1.44 (almost one and a half columns of progress, spread over the 3 columns). How can that be? The answer is that with optimal play, more than half the time you will blow it, but if you don't blow it, you're almost half way to winning the game. In other words, since there is a 92% chance of not blowing it on any one roll, the optimal decision is to keep rolling and rolling until you either blow it or accumulate 1.44 columns worth of progress.\n",
    "\n",
    "Here's one more example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6134923445225983"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "optimal((2, 7, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ROLL'"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "decision((2, 7, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8388278388278387"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stopping_point((2, 7, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{(2, 7, 10, 2): 0.8864468864468864,\n",
       " (2, 7, 10, 7, 7): 0.7069597069597069,\n",
       " (2, 7, 10, 10, 10): 0.8388278388278387}"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What do we need to reach the stopping point?\n",
    "\n",
    "{x: sum(map(progress, x)) \n",
    " for x in [(2, 7, 10, 2), (2, 7, 10, 10, 10), (2, 7, 10, 7, 7)]}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In other words, if you have sherpas that have advanced one space in each of the 2-7-10 column, you should roll again, and if you get another 2 you should immediately stop; if you get two 7s you should roll again; and if you get two 10s you should stop.\n",
    "\n",
    "Now let's see what triples of sherpas are most valuable under optimal play:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0.867 (2, 3, 12)\n",
      " 0.867 (2, 11, 12)\n",
      " 0.810 (2, 4, 12)\n",
      " 0.810 (2, 10, 12)\n",
      " 0.778 (2, 5, 12)\n",
      " 0.778 (2, 9, 12)\n",
      " 0.758 (2, 6, 12)\n",
      " 0.758 (2, 8, 12)\n",
      " 0.744 (2, 7, 12)\n",
      " 0.733 (2, 3, 11)\n",
      " 0.733 (3, 11, 12)\n",
      " 0.698 (6, 7, 12)\n",
      " 0.698 (2, 7, 8)\n",
      " 0.689 (2, 6, 8)\n",
      " 0.689 (6, 8, 12)\n",
      " 0.686 (6, 8, 10)\n",
      " 0.686 (4, 6, 8)\n",
      " 0.676 (2, 3, 4)\n",
      " 0.676 (2, 3, 10)\n",
      " 0.676 (2, 4, 11)\n",
      " 0.676 (2, 10, 11)\n",
      " 0.676 (3, 4, 12)\n",
      " 0.676 (3, 10, 12)\n",
      " 0.676 (4, 11, 12)\n",
      " 0.676 (10, 11, 12)\n",
      " 0.658 (6, 7, 8)\n",
      " 0.652 (6, 7, 9)\n",
      " 0.652 (5, 7, 8)\n",
      " 0.644 (2, 3, 5)\n",
      " 0.644 (2, 3, 9)\n",
      "CPU times: user 3min 8s, sys: 1.71 s, total: 3min 9s\n",
      "Wall time: 3min 23s\n"
     ]
    }
   ],
   "source": [
    "%time top(30, optimal)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here are the triples that will have you rolling the longest:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 1.441 (6, 7, 8)\n",
      " 1.429 (4, 6, 8)\n",
      " 1.429 (6, 8, 10)\n",
      " 1.395 (5, 7, 8)\n",
      " 1.395 (6, 7, 9)\n",
      " 1.267 (4, 7, 8)\n",
      " 1.267 (6, 7, 10)\n",
      " 1.195 (4, 6, 10)\n",
      " 1.195 (4, 8, 10)\n",
      " 1.186 (2, 7, 8)\n",
      " 1.186 (6, 7, 12)\n",
      " 1.183 (4, 7, 9)\n",
      " 1.183 (5, 7, 10)\n",
      " 1.172 (3, 7, 8)\n",
      " 1.172 (6, 7, 11)\n",
      " 1.152 (2, 6, 8)\n",
      " 1.152 (6, 8, 12)\n",
      " 1.141 (5, 6, 8)\n",
      " 1.141 (6, 8, 9)\n",
      " 1.088 (4, 7, 10)\n",
      " 1.050 (4, 6, 7)\n",
      " 1.050 (7, 8, 10)\n",
      " 1.002 (5, 6, 7)\n",
      " 1.002 (7, 8, 9)\n",
      " 0.942 (4, 6, 9)\n",
      " 0.942 (5, 8, 10)\n",
      " 0.931 (4, 8, 9)\n",
      " 0.931 (5, 6, 10)\n",
      " 0.928 (2, 6, 7)\n",
      " 0.928 (7, 8, 12)\n",
      "CPU times: user 3min 7s, sys: 1.79 s, total: 3min 9s\n",
      "Wall time: 3min 34s\n"
     ]
    }
   ],
   "source": [
    "%time top(30, stopping_point)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Strategy\n",
    "\n",
    "You can use the `stopping_point` or `decision` functions to decide how to maximize your progress in any given situation. But you can't quite use it to maximize your chances of winning the game. That would require some more work:\n",
    "\n",
    "- How should I pair up the four dice?\n",
    "  - When there are less than 3 sherpas out, it is usually best to minimize the number of sherpas (3-3-4-4 is usually better as (7, 7), not (6, 8)).\n",
    "  - Otherwise I should chose columns where I am likely to increase my chance of claiming the column, or deny an\n",
    "  opponent their chance of claiming the column.\n",
    "  - If I am way ahead in a column, I probably want to claim it as early as possible when I am winning, but may want to delay claiming it when I am losing.\n",
    "  \n",
    "  \n",
    "- Should I stop or should I roll?\n",
    "  - Where are the other player's pieces? If another player is very close to winning the game, you should take more risks to try to win, but if you are in the lead, you should be more conservative.\n",
    "  - If there are more than 2 players, can you get the others to fight each other and not you?\n",
    "  - Within each column, are you ahead or behind? How much would adding a space in a column change your chance (or an opponent's chance) of winning the column?\n",
    "  \n",
    "None of these are insurmountable, but we won't attempt to solve them here."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}