{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c91b1e19",
   "metadata": {},
   "source": [
    "# Introduction to AI · Search you can afford\n",
    "\n",
    "Two ideas rescue search from the wall: stop looking early and estimate, and\n",
    "look towards the goal instead of everywhere. Both measured here.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "8b01866e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:05:36.254880Z",
     "iopub.status.busy": "2026-08-17T13:05:36.254494Z",
     "iopub.status.idle": "2026-08-17T13:05:36.543729Z",
     "shell.execute_reply": "2026-08-17T13:05:36.535622Z"
    }
   },
   "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 heapq, random, time\n",
    "from collections import deque\n",
    "import numpy as np\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b0f21b20",
   "metadata": {},
   "source": [
    "## 1. A city with walls in it\n",
    "\n",
    "A grid. Some cells are blocked. Start bottom-left, finish top-right.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e5c9a476",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:05:36.545409Z",
     "iopub.status.busy": "2026-08-17T13:05:36.545281Z",
     "iopub.status.idle": "2026-08-17T13:05:36.558239Z",
     "shell.execute_reply": "2026-08-17T13:05:36.558009Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "map_cells = 1,344\n",
      "map_walls = 136\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'136'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Build the map\n",
    "W, H = 48, 28\n",
    "rng = random.Random(11)\n",
    "grid = [[0]*W for _ in range(H)]\n",
    "for _ in range(16):                       # sparse walls, with gaps to walk through\n",
    "    if rng.random() < .5:\n",
    "        r = rng.randrange(H); c0 = rng.randrange(W-13)\n",
    "        for c in range(c0, c0+13):\n",
    "            if rng.random() > .22: grid[r][c] = 1\n",
    "    else:\n",
    "        c = rng.randrange(W); r0 = rng.randrange(max(1, H-10))\n",
    "        for r in range(r0, min(H, r0+10)):\n",
    "            if rng.random() > .22: grid[r][c] = 1\n",
    "START, GOAL = (H-1, 0), (0, W-1)\n",
    "grid[START[0]][START[1]] = grid[GOAL[0]][GOAL[1]] = 0\n",
    "\n",
    "def neighbours(rc):\n",
    "    r, c = rc\n",
    "    for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):\n",
    "        nr, nc = r+dr, c+dc\n",
    "        if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] == 0:\n",
    "            yield (nr, nc)\n",
    "record('map_cells', f'{W*H:,}')\n",
    "record('map_walls', f'{sum(sum(r) for r in grid):,}')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "684dd6a5",
   "metadata": {},
   "source": [
    "## 2. Look everywhere (breadth-first)\n",
    "\n",
    "Expand the nearest unexplored cell, over and over, in every direction at once.\n",
    "It finds the shortest route. It also looks at almost the whole city.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ec6403c0",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:05:36.559460Z",
     "iopub.status.busy": "2026-08-17T13:05:36.559368Z",
     "iopub.status.idle": "2026-08-17T13:05:36.573417Z",
     "shell.execute_reply": "2026-08-17T13:05:36.573209Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bfs_explored = 1,207\n",
      "bfs_path_len = 75\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'75'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Breadth-first search\n",
    "def bfs():\n",
    "    seen = {START: None}; q = deque([START]); order = []\n",
    "    while q:\n",
    "        cur = q.popleft(); order.append(cur)\n",
    "        if cur == GOAL: break\n",
    "        for n in neighbours(cur):\n",
    "            if n not in seen:\n",
    "                seen[n] = cur; q.append(n)\n",
    "    path, cur = [], GOAL\n",
    "    while cur: path.append(cur); cur = seen.get(cur)\n",
    "    return order, path[::-1]\n",
    "\n",
    "bfs_order, bfs_path = bfs()\n",
    "record('bfs_explored', f'{len(bfs_order):,}')\n",
    "record('bfs_path_len', f'{len(bfs_path):,}')\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4a50c274",
   "metadata": {},
   "source": [
    "## 3. Look towards the goal (A\\*)\n",
    "\n",
    "Same search, one change: prefer the cell whose *total* looks best — the steps\n",
    "already taken plus a guess of the steps still to come. The guess here is the\n",
    "straight-line block distance, which can never overstate the real distance.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d600517d",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:05:36.574522Z",
     "iopub.status.busy": "2026-08-17T13:05:36.574455Z",
     "iopub.status.idle": "2026-08-17T13:05:36.578508Z",
     "shell.execute_reply": "2026-08-17T13:05:36.578278Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "astar_explored = 124\n",
      "astar_path_len = 75\n",
      "same_length = yes\n",
      "astar_factor = 9.7\n",
      "astar_saved_pct = 90%\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'90%'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: A* with a straight-line guess\n",
    "def astar():\n",
    "    def h(rc): return abs(rc[0]-GOAL[0]) + abs(rc[1]-GOAL[1])\n",
    "    seen = {START: None}; g = {START: 0}; order = []\n",
    "    # (total guess, then how far is left) — the second term is a TIE-BREAK.\n",
    "    # Without it, every monotone route across an open grid scores the same\n",
    "    # total, A* has no reason to prefer any of them, and it degenerates\n",
    "    # into breadth-first. Prefer the cell closest to the goal and it commits.\n",
    "    pq = [(h(START), h(START), 0, START)]\n",
    "    while pq:\n",
    "        _, _, gc, cur = heapq.heappop(pq)\n",
    "        order.append(cur)\n",
    "        if cur == GOAL: break\n",
    "        for n in neighbours(cur):\n",
    "            ng = gc + 1\n",
    "            if ng < g.get(n, 10**9):\n",
    "                g[n] = ng; seen[n] = cur\n",
    "                heapq.heappush(pq, (ng + h(n), h(n), ng, n))\n",
    "    path, cur = [], GOAL\n",
    "    while cur: path.append(cur); cur = seen.get(cur)\n",
    "    return order, path[::-1]\n",
    "\n",
    "ast_order, ast_path = astar()\n",
    "record('astar_explored', f'{len(ast_order):,}')\n",
    "record('astar_path_len', f'{len(ast_path):,}')\n",
    "record('same_length', 'yes' if len(ast_path) == len(bfs_path) else 'NO')\n",
    "record('astar_factor', f'{len(bfs_order)/len(ast_order):.1f}')\n",
    "record('astar_saved_pct', f'{100*(1-len(ast_order)/len(bfs_order)):.0f}%')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "942f24de",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:05:36.579621Z",
     "iopub.status.busy": "2026-08-17T13:05:36.579540Z",
     "iopub.status.idle": "2026-08-17T13:05:36.619438Z",
     "shell.execute_reply": "2026-08-17T13:05:36.619154Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "draw_runs_bfs = 94\n",
      "draw_runs_bfs = 94\n",
      "figure flood-bfs -> search-you-can-afford.flood-bfs.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: What breadth-first looked at\n",
    "# Rectangles, not imshow. imshow embeds the grid as a base64 PNG inside the\n",
    "# SVG, and lib/blocks/svg.ts refuses any <image> — so the figure would have\n",
    "# been replaced by its alt text on the page. The test suite caught it.\n",
    "#\n",
    "# Adjacent cells in a row are then merged into ONE rectangle. Drawing 1,200\n",
    "# separate squares produced a 254 KB SVG, which is inlined into the page\n",
    "# twice (light and dark); runs bring it under 30 KB and look identical.\n",
    "from matplotlib.patches import Rectangle\n",
    "from matplotlib.collections import PatchCollection\n",
    "\n",
    "WALL     = (0.55, 0.53, 0.50, 0.55)\n",
    "EXPLORED = (0.91, 0.41, 0.25, 0.30)\n",
    "PATH     = (0.91, 0.41, 0.25, 1.00)\n",
    "\n",
    "def runs(coords):\n",
    "    \"\"\"(row, col) cells -> (row, col_start, width) horizontal runs.\"\"\"\n",
    "    by_row = {}\n",
    "    for r, c in coords: by_row.setdefault(r, []).append(c)\n",
    "    out = []\n",
    "    for r, cs in by_row.items():\n",
    "        cs.sort(); start = prev = cs[0]\n",
    "        for c in cs[1:]:\n",
    "            if c == prev + 1: prev = c; continue\n",
    "            out.append((r, start, prev - start + 1)); start = prev = c\n",
    "        out.append((r, start, prev - start + 1))\n",
    "    return out\n",
    "\n",
    "def cells(coords, colour, ax):\n",
    "    if not coords: return\n",
    "    ax.add_collection(PatchCollection(\n",
    "        [Rectangle((c, r), w, 1) for r, c, w in runs(coords)],\n",
    "        facecolor=colour, edgecolor='none'))\n",
    "\n",
    "def draw(order, path, ax):\n",
    "    walls = [(r, c) for r in range(H) for c in range(W) if grid[r][c]]\n",
    "    seen  = [(r, c) for (r, c) in order if not grid[r][c]]\n",
    "    cells(seen, EXPLORED, ax)\n",
    "    cells(walls, WALL, ax)\n",
    "    cells(path, PATH, ax)\n",
    "    ax.set_xlim(0, W); ax.set_ylim(H, 0)\n",
    "    ax.set_aspect('equal'); ax.set_xticks([]); ax.set_yticks([])\n",
    "    for s in ax.spines.values(): s.set_visible(False)\n",
    "    record('draw_runs_' + ('bfs' if len(order) > 500 else 'astar'), f'{len(runs(seen)):,}')\n",
    "\n",
    "save_fig('flood-bfs', lambda ax: draw(bfs_order, bfs_path, ax), figsize=(7, 4.2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6b16b6d7",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:05:36.620735Z",
     "iopub.status.busy": "2026-08-17T13:05:36.620634Z",
     "iopub.status.idle": "2026-08-17T13:05:36.688728Z",
     "shell.execute_reply": "2026-08-17T13:05:36.688452Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "draw_runs_astar = 37\n",
      "draw_runs_astar = 37\n",
      "figure beam-astar -> search-you-can-afford.beam-astar.{light,dark}.svg\n",
      "figure cells-compared -> search-you-can-afford.cells-compared.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: What A* looked at, on the same map\n",
    "save_fig('beam-astar', lambda ax: draw(ast_order, ast_path, ax), figsize=(7, 4.0))\n",
    "\n",
    "def plot(ax):\n",
    "    bars = ax.bar(['look everywhere\\n(breadth-first)', 'look towards the goal\\n(A*)'],\n",
    "                  [len(bfs_order), len(ast_order)])\n",
    "    bars[1].set_alpha(.55)\n",
    "    for b_, v in zip(bars, [len(bfs_order), len(ast_order)]):\n",
    "        ax.text(b_.get_x()+b_.get_width()/2, v*1.04, f'{v:,}', ha='center', fontsize=10)\n",
    "    ax.set_ylabel('cells examined')\n",
    "    ax.set_ylim(0, len(bfs_order)*1.18)\n",
    "save_fig('cells-compared', plot, figsize=(7, 3.4))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d0359d1",
   "metadata": {},
   "source": [
    "## 4. The other half: stop early and guess\n",
    "\n",
    "A\\* still reaches the goal. Chess cannot — so the second idea is to stop at a\n",
    "fixed depth and *estimate* the position instead of playing it out. Back to\n",
    "tic-tac-toe, where we can check the estimate against perfect play.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6eb1f0a3",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:05:36.689898Z",
     "iopub.status.busy": "2026-08-17T13:05:36.689806Z",
     "iopub.status.idle": "2026-08-17T13:06:52.145998Z",
     "shell.execute_reply": "2026-08-17T13:06:52.145517Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d2_losses = 6\n",
      "d2_wins = 361\n",
      "d2_nodes = 53,832\n",
      "d2_nodes_per_game = 135\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d9_losses = 0\n",
      "d9_wins = 361\n",
      "d9_nodes = 123,959,136\n",
      "d9_nodes_per_game = 309,898\n"
     ]
    }
   ],
   "source": [
    "#| caption: Depth-limited search with a crude estimate\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",
    "def winner(b):\n",
    "    for i,j,k in LINES:\n",
    "        if b[i] is not None and b[i]==b[j]==b[k]: return b[i]\n",
    "    return None\n",
    "def moves(b): return [i for i,c in enumerate(b) if c is None]\n",
    "def play(b,i,m): return b[:i]+(m,)+b[i+1:]\n",
    "\n",
    "def guess(b, me):                       # a two-line evaluation function\n",
    "    them = 'O' if me=='X' else 'X'\n",
    "    s = 0\n",
    "    for i,j,k in LINES:\n",
    "        line = [b[i],b[j],b[k]]\n",
    "        if them not in line: s += line.count(me)\n",
    "        if me   not in line: s -= line.count(them)\n",
    "    return s / 24\n",
    "\n",
    "def limited(b, mark, me, depth, counter):\n",
    "    counter[0] += 1\n",
    "    w = winner(b)\n",
    "    if w: return 1.0 if w==me else -1.0\n",
    "    if not moves(b): return 0.0\n",
    "    if depth == 0: return guess(b, me)\n",
    "    vals = [limited(play(b,m,mark), 'O' if mark=='X' else 'X', me, depth-1, counter)\n",
    "            for m in moves(b)]\n",
    "    return max(vals) if mark==me else min(vals)\n",
    "\n",
    "def move_limited(b, mark, depth, counter):\n",
    "    scored = [(limited(play(b,m,mark),'O' if mark=='X' else 'X',mark,depth-1,counter), m)\n",
    "              for m in moves(b)]\n",
    "    return max(scored)[1]\n",
    "\n",
    "rng2 = random.Random(5)\n",
    "for depth, key in ((2,'d2'), (9,'d9')):\n",
    "    res = {'win':0,'draw':0,'loss':0}; c = [0]\n",
    "    for game in range(400):\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 = move_limited(b, mark, depth, c) if mark == ai else rng2.choice(moves(b))\n",
    "            b = play(b, m, mark); 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",
    "    record(f'{key}_losses', f\"{res['loss']:,}\")\n",
    "    record(f'{key}_wins', f\"{res['win']:,}\")\n",
    "    record(f'{key}_nodes', f'{c[0]:,}')\n",
    "    record(f'{key}_nodes_per_game', f'{c[0]/400:,.0f}')\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
}