ipynb/war.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div align=\"right\" style=\"text-align: right\"><i>Peter Norvig<br>Aug 2020</i></div>\n",
    "\n",
    "# War ([What is it Good For?](https://www.youtube.com/watch?v=bX7V6FAoTLc))\n",
    "\n",
    "The [538 Riddler Classic for 28 August 2020](https://fivethirtyeight.com/features/can-you-cover-the-globe/) asks about the chance of winning the children's [card game **War**](https://en.wikipedia.org/wiki/War_%28card_game%29) in a **sweep**: a game where player **A** wins 26 turns in a row against player **B**. (In **War**, players are dealt 26 cards each and on  each turn they flip the top card in their respective hands; higher rank card wins. Other rules are not relevant to this problem.)\n",
    "\n",
    "We'll analyze this problem and come up with a program to solve it. First let's get the imports out of the  way:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import collections\n",
    "from itertools  import permutations, combinations\n",
    "from statistics import mean"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here are the four approaches I considered:\n",
    "\n",
    "# Approach 1: Simple Arithmetic?\n",
    "\n",
    "There is no strategy in **War**, so on every turn, both players have an equal chance of winning the turn. If player **A** wins each turn with probability 1/2, than the probability of sweeping would be $(1/2)^{26}$ or about 15 in a billion. But that's **wrong** because there is also the possibility of a **tie**. After **A** picks a card, there are 51 cards remaining, and 3 have the same rank as **A**'s card, so the possible outcomes for the first turn are:    \n",
    "\n",
    "    tie:     3/51\n",
    "    A wins: 24/51\n",
    "    B wins: 24/51\n",
    "    \n",
    "If every subsequent turn were the same, the probability that **A** sweeps would be $(24/51)^{26}$ or about 3 in a billion. But that's not quite right because the outcome of each turn depends on the cards picked in the previous turns. So simple arithmetic isn't enough."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approach 2: Brute Force Enumeration?\n",
    "\n",
    "Brute force enumeration means:\n",
    "- Consider every possible permutation of the deck of cards.\n",
    "- For each permutation, deal out the cards and see whether or not **A** sweeps.\n",
    "- The probability that **A** sweeps is the number of sweeps divided by the number of permutations.\n",
    "\n",
    "Easy-peasy; here's the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "Probability = float # Type: Probability is a number between 0.0 and 1.0\n",
    "Deck = list         # Type: Deck is a list of card ranks\n",
    "\n",
    "def make_deck(ranks=13, suits=4) -> Deck: \n",
    "    \"\"\"A Deck is a list of ranks, each rank repeated `suits` times.\"\"\"\n",
    "    return [r + 1 for r in range(ranks) for _ in range(suits)] \n",
    "\n",
    "def sweep(deck) -> bool: \n",
    "    \"\"\"Upon dealing this deck, does player A win every turn?\"\"\"\n",
    "    return all(deck[i] > deck[i + 1] for i in range(0, len(deck), 2))\n",
    "\n",
    "def p_sweeps(decks) -> Probability:\n",
    "    \"\"\"The probability that A sweeps, averaged over the decks.\"\"\"\n",
    "    return mean(sweep(deck) for deck in decks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(*Implementation details:* in Python `False` is equivalent to `0` and `True` is equivalent to `1`, so the `mean` of an iterable of `bool` values is the same as the proportion (or probability) of `True` values. Also, it just felt wrong to have a card with rank `0`, thus I add 1 so that ranks start at `1`.)\n",
    "\n",
    "Here are two 8-card decks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_deck(8, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 2, 3, 3, 4, 4]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "make_deck(4, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And here are the probabilities of sweeping a game played with those decks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0625"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweeps(permutations(make_deck(8, 1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.03571428571428571"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweeps(permutations(make_deck(4, 2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What about the real deck, with 52 cards? Unfortunately, there are 52! permutations (more than $10^{67}$), and even if we were clever about the duplicated ranks and the ordering of the 26 turns, and\n",
    "even if we could process a billion deals a second, it would still take [millions of years](https://www.google.com/search?q=%2852%21+%2F+4%21%5E13+%2F+26%21%29+nanoseconds+in+years&oq=%2852%21+%2F+4%21%5E13+%2F+26%21%29+nanoseconds+in+years) to complete the brute force enumeration. And 538 Riddler wanted the answer by Monday.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approach 3: Simulation?\n",
    "\n",
    "It takes too long to look at **all** the permutations, but we can  **randomly sample** the permutations. We call that a **simulation**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample(deck, N) -> Deck: \n",
    "    \"\"\"Yield N randomly shuffled deals of deck.\"\"\"\n",
    "    for _ in range(N):\n",
    "        random.shuffle(deck)\n",
    "        yield deck"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweeps(sample(make_deck(), 10_000))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sampling 10,000 deals with the full 52-card deck we got zero sweeps. Approach 1 suggests the probability of a sweep is somewhere near 3 in a billion, which means we  would need to sample trillions of deals to get a reliable estimate of the probability. That would require roughly a day of run time: much better than millions of years, but still not good enough."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approach 4: Abstract Incremental Enumeration!\n",
    "\n",
    "\n",
    "\n",
    "As discussed in my [**How To Count Things**](How%20To%20Count%20Things.ipynb) notebook, in problems where brute force enumeration is not feasible it is often possible to consider every outcome if we use a representation that is:\n",
    "- **Abstract**: What matters is not the exact rank of every card in the deck, but rather whether **A**'s next card is higher, lower, or the same as **B**'s next card. The representation should tell us enough to compute the odds of those three outcomes, and no more.\n",
    "- **Incremental**: First we'll consider the possibilities for the two cards in the first turn, and only for the outcomes in which **A** wins will we then move on to consider possible cards for the next turn. For outcomes in which **A**  loses or ties, there is no need to consider the permutations of the remaining cards.\n",
    "\n",
    "For example, if there are two cards remaining then there are 52 × 51 possible concrete decks, but only two abstract cases: \n",
    "* The two cards are **the same** rank, in which case the probability of **A** winning is 0, because it will be a tie. <br>It doesn't matter whether the deck is `[5, 5]` or `[9, 9]`, or any other pair of cards. \n",
    "* The two cards are **different** ranks, in which case the probability of **A** winning is 1/2. <br>It doesn't matter whether the deck is `[10, 8]` or `[2, 5]` or any other two distinct ranks.\n",
    "     \n",
    "# Abstract Deck\n",
    "\n",
    "The representation I will use, which I call `AbDeck` for **abstract deck**, is as follows:\n",
    "- An `AbDeck` is a tuple of counts of the number of cards of each rank, without specifying the rank. \n",
    "- Ranks with counts of zero are dropped from the representation.\n",
    "- The counts are put in sorted order.\n",
    "- The tuple represents the deck without regard to the order of the cards (that is, not a specific permutation).\n",
    "- The tuple tells you just what you need (no more, no less) to compute the probability of a sweep.\n",
    "- The initial 52-card deck is 13 fours: `(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)`\n",
    "- The possible two-card decks are `(1, 1)` and `(2,)`.\n",
    "- The possible four-card decks are `(1, 1, 1, 1)`, `(1, 1, 2)`, `(1, 3)`, `(2, 2)`, and `(4,)`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "AbDeck = tuple # Type: An abstract deck\n",
    "\n",
    "def make_abdeck(ranks=13, suits=4) -> AbDeck: \n",
    "    \"\"\"Make an abstract deck.\"\"\"\n",
    "    return AbDeck([suits] * ranks)\n",
    "\n",
    "deck = make_abdeck(13, 4) # The initial 52-card abstract deck\n",
    "deck"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">***Note:***  I originally thought of *two* possible abstract representations for decks: `AbDeck` as described above, and an alternative in which: \n",
    "- A deck was a tuple where `deck[i]` gives the number of different ranks that have exactly `i` cards remaining in the deck.\n",
    "- The initial deck is represented as `(0, 0, 0, 0, 13)`: 13 ranks with 4-of-a-kind.\n",
    "- The two possible two-card decks are `(0, 2)` (two ranks with 1 card each) and `(0, 0, 1)` (one rank with two cards).\n",
    ">\n",
    ">That representation was more compact, and ran faster; I used it in the first version of this notebook. But the very nice  [implementation](https://laurentlessard.com/bookproofs/flawless-war/) shared by [Laurent Lessard](https://laurentlessard.com/) convinced me to switch to the `AbDeck` representation becausse it is simpler to code and understand.\n",
    "\n",
    "# Probability Distribution\n",
    "\n",
    "We want to keep track of the possible outcomes of each turn.  We'll do that with the help of a class called `PDist` (for **probability distribution**), a mapping of `{deck: p, ...}` where `deck` is an abstract deck that is the outcome after some number of turns, each of which **A** has won, and `p` is the probability of that outcome."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PDist(collections.Counter): \n",
    "    \"\"\"A probability distribution of {abstract_deck: probability}.\"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Abstract Incremental Enumeration Strategy\n",
    "\n",
    "The probability that **A** sweeps a game of **War** given an abstract deck, `p_sweep(deck)`, is computed as follows:\n",
    "\n",
    "- Start with `P` being a **probability distribution** of outcomes after 0 turns: `{deck: 1.0}`.\n",
    "- **for** each turn of the game (26 turns for a 52-card deck):\n",
    "  - Update `P` to be the probability distribution that results from playing a turn, `P = play_turn(P)`:\n",
    "    - **for** each `deck` in `P`:\n",
    "      - **for** each way of removing two cards of rank `i` and rank `j` from `deck` to yield a resulting deck:\n",
    "        - Increment the probability of the resulting deck by (probability of `deck` × probability of  `i` ×  probability of `j`).\n",
    "- **return** the sum of the probabilities of the winning decks in `P` from the final turn\n",
    "\n",
    "Note that (for example) `combinations(range(3), 2)` yields `(1, 2)`, but not `(1, 1)` nor `(2, 1)`. That's just what we want: if the two selected cards are `i, j = (1, 1)` then the result will be a tie, which we don't want to put in the probability distribution of decks where **A** sweeps. And out of the two possibilities `i, j = (1, 2)` and `i, j = (2, 1)`, exactly one will result in a win for **A**, so we only want to include one of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def p_sweep(deck: AbDeck) -> Probability:\n",
    "    \"\"\"The probability that player A sweeps a game of War.\"\"\"\n",
    "    P = PDist({deck: 1.0}) # The initial probability distribution\n",
    "    for turn in range(sum(deck) // 2):\n",
    "        P = play_turn(P)\n",
    "    return sum(P.values())\n",
    "\n",
    "def play_turn(P) -> PDist:\n",
    "    \"\"\"Play one turn with all possible card choices for players A and B; return\n",
    "    the probability distribution of outcomes where A still might sweep.\"\"\"\n",
    "    P1 = PDist() # The probability distribution of {deck: prob} after this turn\n",
    "    for deck in P:\n",
    "        n = sum(deck) # number of cards in deck\n",
    "        for i, j in combinations(range(len(deck)), 2):\n",
    "            P1[remove(deck, i, j)] += P[deck] * deck[i] / n * deck[j] / (n - 1)\n",
    "    return P1\n",
    "\n",
    "def remove(deck, *indexes) -> AbDeck:\n",
    "    \"\"\"Remove cards at indexes from deck.\"\"\"\n",
    "    counts = [c - indexes.count(i) for i, c in enumerate(deck)]\n",
    "    return AbDeck(sorted(c for c in counts if c > 0))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Answer!\n",
    "\n",
    "What's the probability that player **A** will win in a sweep?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.132436174322299e-09"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweep(deck)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A little over 3 in a billion. \n",
    "\n",
    "(By the way, this computation took about 0.2 seconds, a big improvement over millions of years.) \n",
    "\n",
    "That's the answer to *my* question about the probability of **A** sweeping, but 538 Riddler actually posed the question somewhat differently: \"*How many games of War would you expect to play until you had a game that lasted just 26 turns with no wars, like Duane’s friend’s granddaughter?*\" That is, they want to know the inverse of the probability, and they are allowing for either **A** or **B** to sweep. So that would be:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "159620171.70491105"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 / (2 * p_sweep(deck))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " We would expect a sweep about once every 160 million games. I have to say, I'm begining to doubt Duane’s friend’s granddaughter's claim. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Working through the algorithm\n",
    "\n",
    "Let's work through how `p_sweep` and `play_turn` work. We'll start with `P` being the initial probability distribution, and then play four turns, each time displaying how `P` is updated:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PDist({(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 1.0})"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = PDist({deck: 1.0})\n",
    "P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PDist({(3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.47058823529411703})"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = play_turn(P) # Turn 1\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That makes sense: the only result where **A** still has a chance to sweep is when the two players select different ranks, giving us two ranks with  three-of-a-kind remaining (and 11 with four-of-a-kind remaining). The probability of **A** sweeping one turn is 24/51 = 0.47058823529411703."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PDist({(2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.001728691476590634,\n",
       "       (2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.050708283313325254,\n",
       "       (3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.16902761104441777})"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = play_turn(P) # Turn 2\n",
    "P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PDist({(1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 3.065055809557862e-06,\n",
       "       (1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.00040458736686163773,\n",
       "       (2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.010114684171540949,\n",
       "       (1, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.0017981660749406122,\n",
       "       (2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.00020229368343081884,\n",
       "       (2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4): 0.04855048402339655,\n",
       "       (3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4): 0.043155985798574735})"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = play_turn(P) # Turn 3\n",
    "P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "PDist({(4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 1.4807032896414793e-09,\n",
       "       (1, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 5.212075579538007e-07,\n",
       "       (1, 1, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 3.648452905676605e-05,\n",
       "       (2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 5.863585026980257e-07,\n",
       "       (2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 1.563622673861402e-05,\n",
       "       (1, 1, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4): 2.3454340107921024e-06,\n",
       "       (1, 2, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4): 0.00018763472086336856,\n",
       "       (1, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4): 0.0016887124877703135,\n",
       "       (2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4): 4.397688770235195e-05,\n",
       "       (2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4): 0.0023923426910079496,\n",
       "       (2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4): 0.014635508227342713,\n",
       "       (3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4): 3.127245347722804e-05,\n",
       "       (1, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4): 0.002001437022542595,\n",
       "       (2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4): 0.02101508873669728,\n",
       "       (3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4): 0.007005029578899085})"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P = play_turn(P) # Turn 4\n",
    "P"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll leave it as an exercise for the reader to verify that these turns are correct."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Gaining Confidence in the Answer\n",
    "\n",
    "One way to gain confidence: The answer should be somewhere close to the arithmetic calculation of $(24/51)^{26}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0167508045532485"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_sweep(deck) / ((24/51) ** 26)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see that it is indeed close, differing by less than 2%.\n",
    "\n",
    "Another way to gain confidence: We can verify that there is no difference (∆ = 0) between the brute force `p_sweeps` and the abstract incremental `p_sweep` for small decks. This gives us some confidence that both are correct (or maybe both have similar errors). `p_sweeps` takes less than 50 milliseconds to solve decks of 8 cards or less, but takes about 4 seconds to do the 10! (almost 4 million) permutations of ten card decks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deck(2, 1):  p = 0.5000; ∆ = 0.000000000\n",
      "deck(4, 1):  p = 0.2500; ∆ = 0.000000000\n",
      "deck(2, 2):  p = 0.1667; ∆ = 0.000000000\n",
      "deck(6, 1):  p = 0.1250; ∆ = 0.000000000\n",
      "deck(3, 2):  p = 0.0667; ∆ = 0.000000000\n",
      "deck(2, 3):  p = 0.0500; ∆ = 0.000000000\n",
      "deck(8, 1):  p = 0.0625; ∆ = 0.000000000\n",
      "deck(4, 2):  p = 0.0357; ∆ = 0.000000000\n",
      "deck(2, 4):  p = 0.0143; ∆ = 0.000000000\n",
      "deck(5, 2):  p = 0.0180; ∆ = 0.000000000\n",
      "deck(2, 5):  p = 0.0040; ∆ = 0.000000000\n"
     ]
    }
   ],
   "source": [
    "for r, s in [(2, 1), \n",
    "             (4, 1), (2, 2), \n",
    "             (6, 1), (3, 2), (2, 3),\n",
    "             (8, 1), (4, 2), (2, 4), \n",
    "                     (5, 2), (2, 5)]:\n",
    "    p1 = p_sweeps(permutations(make_deck(r, s)))\n",
    "    p2 = p_sweep(make_abdeck(r, s))\n",
    "    print(f'deck({r}, {s}):  p = {p1:.4f}; ∆ = {abs(p1 - p2):.9f}')"
   ]
  }
 ],
 "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}