beating-shannon-m3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e090adff",
   "metadata": {},
   "source": [
    "# Minimal Example where Shannon’s Analog Heuristic Fails (M = 3)\n",
    "\n",
    "From [\"Bridg-It – Beating Shannon’s Analog Heuristic\"](https://www.minet.uni-jena.de//math-net/reports/sources/2009/09-07report.pdf) by Thomas Fisher\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6fdf074d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from birdcage import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b5fea4d",
   "metadata": {},
   "source": [
    "First let's create a birdcage board, and display it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ace1ab34",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    ● = ● = ●   \n",
       "5   |   |   |   \n",
       "4   ● - ● - ●   \n",
       "3   |   |   |   \n",
       "2   ● - ● - ●   \n",
       "1   |   |   |   \n",
       "    ● = ● = ●   \n",
       "    A B C D E   \n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bc = BirdCage()\n",
    "bc"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "455f40f0",
   "metadata": {},
   "source": [
    "By default we have an `M`=3 sized board.\n",
    "\n",
    "We can use the `Shannon` player to look at the voltage differences across the equivalent resistor network. We set `use_extra_resistors` to `False` so we don't use the pull-up resistors that are needed in the general case, since they change the voltage differences slightly.\n",
    "\n",
    "This corresponds to Figure 2a in the paper (note they are voltage differences, not voltages)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "93b6f2d5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    ●   ●   ●   \n",
      "5   1   1   1   \n",
      "4   ● 0 ● 0 ●   \n",
      "3   1   1   1   \n",
      "2   ● 0 ● 0 ●   \n",
      "1   1   1   1   \n",
      "    ●   ●   ●   \n",
      "\n"
     ]
    }
   ],
   "source": [
    "shannon = Shannon(use_extra_resistors=False)\n",
    "print(shannon.voltage_diffs_str(bc))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "78f4cba7",
   "metadata": {},
   "source": [
    "Play two moves (white/CUT then black/SHORT), and look at the voltage differences. Figure 2b."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "ffcdc126",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    ● = ● = ●   \n",
       "5       ‖   |   \n",
       "4   ● - ● - ●   \n",
       "3   |   |   |   \n",
       "2   ● - ● - ●   \n",
       "1   |   |   |   \n",
       "    ● = ● = ●   \n",
       "    A B C D E   \n",
       "A5, c5"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bc.move(\"A5\")\n",
    "bc.move(\"c5\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1a1c3ace",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     ●    ●    ●    \n",
      "5             25   \n",
      "4    ● 40 ● 25 ●    \n",
      "3   40   71   50   \n",
      "2    ●  9 ●  4 ●    \n",
      "1   49   58   54   \n",
      "     ●    ●    ●    \n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(shannon.voltage_diffs_str(bc))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "edaadc1c",
   "metadata": {},
   "source": [
    "This shows that the Shannon heuristic would choose C3, since it has the largest voltage difference: 71 (not 61 as mentioned in Figure 2b)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "924524de",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    ● = ● = ●   \n",
       "5       ‖   |   \n",
       "4   ● - ● - ●   \n",
       "3   |       |   \n",
       "2   ● - ● - ●   \n",
       "1   ‖   |   |   \n",
       "    ● = ● = ●   \n",
       "    A B C D E   \n",
       "A5, c5, C3, a1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bc.move(\"C3\")\n",
    "bc.move(\"a1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "838115e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     ●    ●    ●    \n",
      "5             10   \n",
      "4    ● 21 ● 10 ●    \n",
      "3   21        20   \n",
      "2    ●  4 ●  8 ●    \n",
      "1         4   12   \n",
      "     ●    ●    ●    \n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(shannon.voltage_diffs_str(bc))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dcf3100",
   "metadata": {},
   "source": [
    "As the paper says\n",
    "\n",
    "> In Figure 2, part c), we see that Shannon plays imperfectly in its third move. The edges A3 and B4 both have a flow of 21, while E3 only has a flow of 20. But A3 and B4 are forming a chain, so there is no need for CUT to remove one of them before SHORT has marked the other one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "ef5703cd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    ● = ● = ●   \n",
       "5       ‖   |   \n",
       "4   ●   ● - ●   \n",
       "3   |       ‖   \n",
       "2   ● - ● - ●   \n",
       "1   ‖   |   |   \n",
       "    ● = ● = ●   \n",
       "    A B C D E   \n",
       "A5, c5, C3, a1, B4, e3"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bc.move(\"B4\")\n",
    "bc.move(\"e3\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "98b10852",
   "metadata": {},
   "source": [
    "And now SHORT can win however CUT plays.\n",
    "\n",
    "Finally, here is the Bridg-It diagram corresponding to this position (Figure 2d)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c81ccef9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "    ● - ● - ●   \n",
       "5 ○ - ○ | ○   ○ \n",
       "4 | ● | ●   ● | \n",
       "3 ○   ○ - ○ | ○ \n",
       "2 | ●   ●   ● | \n",
       "1 ○ | ○   ○   ○ \n",
       "    ● - ● - ●   \n",
       "    A B C D E   \n",
       "A5, c5, C3, a1, B4, e3"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "BridgIt(bc.M, bc.moves)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "venv",
   "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.10"
  },
  "vscode": {
   "interpreter": {
    "hash": "e88b5aaf88d49a8b589d2c4926323d1f21c6335d60603c849cf9a05e9f10a105"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}