{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f101731a",
   "metadata": {},
   "source": [
    "# Introduction to AI · The machine that looked ahead\n",
    "\n",
    "Tic-tac-toe, played out completely: every game that could ever happen. Then\n",
    "minimax, then what pruning saves — and the wall that stops the same idea\n",
    "working on chess.\n",
    "\n",
    "Every figure and number the lesson prints comes from here. Nothing is asserted.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b371bd15",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:40:30.136729Z",
     "iopub.status.busy": "2026-08-17T12:40:30.136318Z",
     "iopub.status.idle": "2026-08-17T12:40:30.408127Z",
     "shell.execute_reply": "2026-08-17T12:40:30.407679Z"
    }
   },
   "outputs": [],
   "source": [
    "# hide — plumbing so this file runs both in the repo and in Colab.\n",
    "try:\n",
    "    from _figkit import save_fig, record\n",
    "except ImportError:  # Colab — no repo, no problem\n",
    "    def save_fig(name, plot, **kw):\n",
    "        import matplotlib.pyplot as plt\n",
    "        fig, ax = plt.subplots(figsize=kw.get('figsize', (7, 4.2))); plot(ax); plt.show()\n",
    "    def record(key, value):\n",
    "        print(f'{key} = {value}'); return value\n",
    "\n",
    "import random, time\n",
    "import numpy as np\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9657a79",
   "metadata": {},
   "source": [
    "## 1. The rules, in ten lines\n",
    "\n",
    "A board is nine cells. Somebody has won if they hold one of eight lines.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "4fb38d6b",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:40:30.411190Z",
     "iopub.status.busy": "2026-08-17T12:40:30.410963Z",
     "iopub.status.idle": "2026-08-17T12:40:30.415026Z",
     "shell.execute_reply": "2026-08-17T12:40:30.414618Z"
    }
   },
   "outputs": [],
   "source": [
    "#| caption: The whole game, as code\n",
    "LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]\n",
    "EMPTY = (None,) * 9\n",
    "\n",
    "def winner(b):\n",
    "    for i, j, k in LINES:\n",
    "        if b[i] is not None and b[i] == b[j] == b[k]:\n",
    "            return b[i]\n",
    "    return None\n",
    "\n",
    "def moves(b):\n",
    "    return [i for i, c in enumerate(b) if c is None]\n",
    "\n",
    "def play(b, i, mark):\n",
    "    return b[:i] + (mark,) + b[i+1:]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d086d64f",
   "metadata": {},
   "source": [
    "## 2. Every game that could ever happen\n",
    "\n",
    "Walk the whole tree. Not a sample — all of it.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ae023efb",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:40:30.417299Z",
     "iopub.status.busy": "2026-08-17T12:40:30.417094Z",
     "iopub.status.idle": "2026-08-17T12:40:30.774043Z",
     "shell.execute_reply": "2026-08-17T12:40:30.773824Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "total_games = 255,168\n",
      "total_nodes = 549,946\n",
      "games_x_wins = 131,184\n",
      "games_o_wins = 77,904\n",
      "games_drawn = 46,080\n",
      "walk_seconds = 0.3\n",
      "nodes_per_second = 1,572,546\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'1,572,546'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Enumerate the complete game tree\n",
    "depth_nodes = [0] * 10\n",
    "stats = {'nodes': 0, 'games': 0, 'x': 0, 'o': 0, 'draw': 0}\n",
    "\n",
    "def walk(b, mark, d):\n",
    "    stats['nodes'] += 1\n",
    "    depth_nodes[d] += 1\n",
    "    w = winner(b)\n",
    "    if w or not moves(b):\n",
    "        stats['games'] += 1\n",
    "        stats['x' if w == 'X' else 'o' if w == 'O' else 'draw'] += 1\n",
    "        return\n",
    "    for m in moves(b):\n",
    "        walk(play(b, m, mark), 'O' if mark == 'X' else 'X', d + 1)\n",
    "\n",
    "t0 = time.time()\n",
    "walk(EMPTY, 'X', 0)\n",
    "elapsed = time.time() - t0\n",
    "\n",
    "record('total_games', f\"{stats['games']:,}\")\n",
    "record('total_nodes', f\"{stats['nodes']:,}\")\n",
    "record('games_x_wins', f\"{stats['x']:,}\")\n",
    "record('games_o_wins', f\"{stats['o']:,}\")\n",
    "record('games_drawn', f\"{stats['draw']:,}\")\n",
    "record('walk_seconds', f'{elapsed:.1f}')\n",
    "record('nodes_per_second', f\"{stats['nodes']/elapsed:,.0f}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "48766bf0",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:40:30.775132Z",
     "iopub.status.busy": "2026-08-17T12:40:30.775048Z",
     "iopub.status.idle": "2026-08-17T12:40:31.025805Z",
     "shell.execute_reply": "2026-08-17T12:40:31.025592Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "figure tree-by-depth -> the-machine-that-looked-ahead.tree-by-depth.{light,dark}.svg\n",
      "nodes_move_1 = 9\n",
      "nodes_move_4 = 3,024\n",
      "nodes_move_7 = 148,176\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'148,176'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: How the tree fans out, move by move\n",
    "def plot(ax):\n",
    "    d = list(range(9))\n",
    "    v = depth_nodes[:9]\n",
    "    ax.bar([str(i) for i in d], v)\n",
    "    for i, val in enumerate(v):\n",
    "        ax.text(i, val * 1.15, f'{val:,}', ha='center', fontsize=8.5)\n",
    "    ax.set_yscale('log')\n",
    "    ax.set_ylim(0.6, max(v) * 6)\n",
    "    ax.set_xlabel('moves played')\n",
    "    ax.set_ylabel('positions to consider (log scale)')\n",
    "save_fig('tree-by-depth', plot, figsize=(7, 4.0))\n",
    "\n",
    "record('nodes_move_1', f'{depth_nodes[1]:,}')\n",
    "record('nodes_move_4', f'{depth_nodes[4]:,}')\n",
    "record('nodes_move_7', f'{depth_nodes[7]:,}')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2111353d",
   "metadata": {},
   "source": [
    "## 3. Minimax: assume they play well\n",
    "\n",
    "Score a finished game +1 if X won, -1 if O won, 0 for a draw. Then work\n",
    "backwards: on X's turn take the best score available, on O's turn take the\n",
    "worst — because O is trying to beat you.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "4243ae2f",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:40:31.026990Z",
     "iopub.status.busy": "2026-08-17T12:40:31.026897Z",
     "iopub.status.idle": "2026-08-17T12:40:31.357036Z",
     "shell.execute_reply": "2026-08-17T12:40:31.356744Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "perfect_play_value = a draw\n",
      "minimax_nodes = 549,946\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'549,946'"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Minimax, and what perfect play is worth\n",
    "def minimax(b, mark, counter):\n",
    "    counter[0] += 1\n",
    "    w = winner(b)\n",
    "    if w == 'X': return 1\n",
    "    if w == 'O': return -1\n",
    "    if not moves(b): return 0\n",
    "    scores = [minimax(play(b, m, mark), 'O' if mark == 'X' else 'X', counter)\n",
    "              for m in moves(b)]\n",
    "    return max(scores) if mark == 'X' else min(scores)\n",
    "\n",
    "plain = [0]\n",
    "value = minimax(EMPTY, 'X', plain)\n",
    "record('perfect_play_value', {1: 'X wins', -1: 'O wins', 0: 'a draw'}[value])\n",
    "record('minimax_nodes', f'{plain[0]:,}')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fe24f7e",
   "metadata": {},
   "source": [
    "## 4. Does it actually never lose?\n",
    "\n",
    "Claiming is cheap. Play it a thousand times against an opponent that moves at\n",
    "random, five hundred as each side, and count.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "0b3c0e16",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:40:31.358125Z",
     "iopub.status.busy": "2026-08-17T12:40:31.358048Z",
     "iopub.status.idle": "2026-08-17T12:43:37.971538Z",
     "shell.execute_reply": "2026-08-17T12:43:37.971218Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "vs_random_games = 1,000\n",
      "vs_random_wins = 913\n",
      "vs_random_draws = 87\n",
      "vs_random_losses = 0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'0'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: 1,000 games against a random opponent\n",
    "def best_move(b, mark):\n",
    "    c = [0]\n",
    "    scored = [(minimax(play(b, m, mark), 'O' if mark == 'X' else 'X', c), m)\n",
    "              for m in moves(b)]\n",
    "    return (max if mark == 'X' else min)(scored)[1]\n",
    "\n",
    "rng = random.Random(7)\n",
    "res = {'win': 0, 'draw': 0, 'loss': 0}\n",
    "for game in range(1000):\n",
    "    ai = 'X' if game % 2 == 0 else 'O'\n",
    "    b, mark = EMPTY, 'X'\n",
    "    while winner(b) is None and moves(b):\n",
    "        m = best_move(b, mark) if mark == ai else rng.choice(moves(b))\n",
    "        b = play(b, m, mark)\n",
    "        mark = 'O' if mark == 'X' else 'X'\n",
    "    w = winner(b)\n",
    "    res['draw' if w is None else 'win' if w == ai else 'loss'] += 1\n",
    "\n",
    "record('vs_random_games', f\"{sum(res.values()):,}\")\n",
    "record('vs_random_wins', f\"{res['win']:,}\")\n",
    "record('vs_random_draws', f\"{res['draw']:,}\")\n",
    "record('vs_random_losses', f\"{res['loss']:,}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9189846b",
   "metadata": {},
   "source": [
    "## 5. Pruning: proving a branch cannot matter\n",
    "\n",
    "If one reply already beats anything this branch could give you, you do not\n",
    "need to finish reading the branch. That is alpha-beta, and it changes nothing\n",
    "about the answer.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "207c57fc",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:43:37.973978Z",
     "iopub.status.busy": "2026-08-17T12:43:37.973862Z",
     "iopub.status.idle": "2026-08-17T12:43:38.035300Z",
     "shell.execute_reply": "2026-08-17T12:43:38.035063Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "alphabeta_nodes = 18,297\n",
      "alphabeta_same_answer = yes\n",
      "pruning_factor = 30\n",
      "pruning_saved_pct = 96.7%\n",
      "figure what-pruning-saves -> the-machine-that-looked-ahead.what-pruning-saves.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: Same move, a fraction of the work\n",
    "def ab(b, mark, alpha, beta, counter):\n",
    "    counter[0] += 1\n",
    "    w = winner(b)\n",
    "    if w == 'X': return 1\n",
    "    if w == 'O': return -1\n",
    "    if not moves(b): return 0\n",
    "    if mark == 'X':\n",
    "        best = -2\n",
    "        for m in moves(b):\n",
    "            best = max(best, ab(play(b, m, 'X'), 'O', alpha, beta, counter))\n",
    "            alpha = max(alpha, best)\n",
    "            if beta <= alpha: break\n",
    "        return best\n",
    "    best = 2\n",
    "    for m in moves(b):\n",
    "        best = min(best, ab(play(b, m, 'O'), 'X', alpha, beta, counter))\n",
    "        beta = min(beta, best)\n",
    "        if beta <= alpha: break\n",
    "    return best\n",
    "\n",
    "pruned = [0]\n",
    "value_ab = ab(EMPTY, 'X', -2, 2, pruned)\n",
    "\n",
    "record('alphabeta_nodes', f'{pruned[0]:,}')\n",
    "record('alphabeta_same_answer', 'yes' if value_ab == value else 'NO')\n",
    "record('pruning_factor', f'{plain[0] / pruned[0]:.0f}')\n",
    "record('pruning_saved_pct', f'{100 * (1 - pruned[0] / plain[0]):.1f}%')\n",
    "\n",
    "def plot(ax):\n",
    "    bars = ax.bar(['look at everything\\n(minimax)', 'prove what cannot matter\\n(alpha-beta)'],\n",
    "                  [plain[0], pruned[0]])\n",
    "    bars[1].set_alpha(.55)\n",
    "    for b_, v in zip(bars, [plain[0], pruned[0]]):\n",
    "        ax.text(b_.get_x() + b_.get_width()/2, v * 1.06, f'{v:,}', ha='center', fontsize=10)\n",
    "    ax.set_ylabel('positions examined')\n",
    "    ax.set_ylim(0, plain[0] * 1.2)\n",
    "save_fig('what-pruning-saves', plot, figsize=(7, 3.6))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8b67176d",
   "metadata": {},
   "source": [
    "## 6. The wall\n",
    "\n",
    "Same idea, bigger board. The two comparison figures are published estimates,\n",
    "not measurements — the tic-tac-toe bar is the only one this notebook counted.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "1a2c233d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T12:43:38.036498Z",
     "iopub.status.busy": "2026-08-17T12:43:38.036429Z",
     "iopub.status.idle": "2026-08-17T12:43:38.081179Z",
     "shell.execute_reply": "2026-08-17T12:43:38.080770Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "figure the-wall -> the-machine-that-looked-ahead.the-wall.{light,dark}.svg\n",
      "ttt_zeroes = 5.4\n",
      "chess_years = 2e+106\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'2e+106'"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Orders of magnitude\n",
    "import math\n",
    "TTT   = stats['games']\n",
    "CHESS = 1e120   # Shannon 1950, game-tree complexity\n",
    "ATOMS = 1e80    # observable universe, standard estimate\n",
    "\n",
    "def plot(ax):\n",
    "    labels = ['tic-tac-toe\\n(counted here)', 'atoms in the\\nobservable universe', 'chess\\n(Shannon)']\n",
    "    vals = [math.log10(TTT), math.log10(ATOMS), math.log10(CHESS)]\n",
    "    bars = ax.barh(labels, vals)\n",
    "    bars[0].set_alpha(1.0); bars[1].set_alpha(.45); bars[2].set_alpha(.75)\n",
    "    for i, v in enumerate(vals):\n",
    "        ax.text(v + 1.5, i, f'10^{v:.0f}', va='center', fontsize=10)\n",
    "    ax.set_xlim(0, 138)\n",
    "    ax.set_xlabel('zeroes  (each step right is ten times bigger)')\n",
    "save_fig('the-wall', plot, figsize=(7, 3.0))\n",
    "\n",
    "record('ttt_zeroes', f'{math.log10(TTT):.1f}')\n",
    "years = CHESS / (stats['nodes'] / elapsed) / (60*60*24*365)\n",
    "record('chess_years', f'{years:.0e}')\n"
   ]
  }
 ],
 "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.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}