{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "39033d94",
   "metadata": {},
   "source": [
    "# Introduction to AI · The machine that reasoned\n",
    "\n",
    "An expert system: a pile of rules, an engine that chains them, and — the part\n",
    "that mattered most — an answer to *why*.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "141daa58",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:14:25.460368Z",
     "iopub.status.busy": "2026-08-17T13:14:25.460294Z",
     "iopub.status.idle": "2026-08-17T13:14:25.799467Z",
     "shell.execute_reply": "2026-08-17T13:14:25.799223Z"
    }
   },
   "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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "df615cdb",
   "metadata": {},
   "source": [
    "## 1. The knowledge, written down\n",
    "\n",
    "Fifteen rules. Each one is `IF all of these THEN that` — and notice that some\n",
    "conclusions are ingredients of other rules. That is what makes it a chain\n",
    "rather than a lookup table.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "9032ec6e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:14:25.800757Z",
     "iopub.status.busy": "2026-08-17T13:14:25.800670Z",
     "iopub.status.idle": "2026-08-17T13:14:25.804862Z",
     "shell.execute_reply": "2026-08-17T13:14:25.804685Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n_rules = 15\n",
      "n_animals = 7\n",
      "n_askable = 18\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: The rule base\n",
    "RULES = [\n",
    "    (['hair'],                                   'mammal'),\n",
    "    (['gives milk'],                             'mammal'),\n",
    "    (['feathers'],                               'bird'),\n",
    "    (['lays eggs', 'flies'],                     'bird'),\n",
    "    (['mammal', 'eats meat'],                    'carnivore'),\n",
    "    (['mammal', 'pointed teeth', 'claws'],       'carnivore'),\n",
    "    (['mammal', 'hooves'],                       'ungulate'),\n",
    "    (['mammal', 'chews cud'],                    'ungulate'),\n",
    "    (['carnivore', 'tawny', 'dark spots'],       'cheetah'),\n",
    "    (['carnivore', 'tawny', 'black stripes'],    'tiger'),\n",
    "    (['ungulate', 'long neck', 'long legs', 'dark spots'], 'giraffe'),\n",
    "    (['ungulate', 'black stripes'],              'zebra'),\n",
    "    (['bird', 'cannot fly', 'long neck', 'long legs'],     'ostrich'),\n",
    "    (['bird', 'cannot fly', 'swims'],            'penguin'),\n",
    "    (['bird', 'good flyer'],                     'albatross'),\n",
    "]\n",
    "\n",
    "ANIMALS = {'cheetah','tiger','giraffe','zebra','ostrich','penguin','albatross'}\n",
    "DERIVED = {c for _, c in RULES}\n",
    "ASKABLE = sorted({f for conds, _ in RULES for f in conds} - DERIVED)\n",
    "\n",
    "record('n_rules', len(RULES))\n",
    "record('n_animals', len(ANIMALS))\n",
    "record('n_askable', len(ASKABLE))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46833a7b",
   "metadata": {},
   "source": [
    "## 2. Forward chaining: from what you saw to what it is\n",
    "\n",
    "Start with observations. Fire every rule whose conditions are all met. That\n",
    "adds new facts, which may let more rules fire. Repeat until nothing changes.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a4c1f2b8",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:14:25.805813Z",
     "iopub.status.busy": "2026-08-17T13:14:25.805746Z",
     "iopub.status.idle": "2026-08-17T13:14:25.809238Z",
     "shell.execute_reply": "2026-08-17T13:14:25.809018Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "demo_observations = hair, eats meat, tawny, dark spots\n",
      "demo_conclusion = cheetah\n",
      "demo_fired = 3\n",
      "demo_rounds = 2\n",
      "demo_chain_depth = 3\n",
      "cheetah\n",
      "  carnivore\n",
      "    mammal\n",
      "      hair\n",
      "    eats meat\n",
      "  tawny\n",
      "  dark spots\n"
     ]
    }
   ],
   "source": [
    "#| caption: Facts in, conclusions out — with the chain kept\n",
    "def forward(facts):\n",
    "    known = set(facts); why = {}; fired = 0; rounds = 0\n",
    "    changed = True\n",
    "    while changed:\n",
    "        changed = False; rounds += 1\n",
    "        for conds, concl in RULES:\n",
    "            if concl not in known and all(c in known for c in conds):\n",
    "                known.add(concl); why[concl] = conds; fired += 1; changed = True\n",
    "    return known, why, fired, rounds\n",
    "\n",
    "obs = ['hair', 'eats meat', 'tawny', 'dark spots']\n",
    "known, why, fired, rounds = forward(obs)\n",
    "\n",
    "record('demo_observations', ', '.join(obs))\n",
    "record('demo_conclusion', next(k for k in known if k in ANIMALS))\n",
    "record('demo_fired', fired)\n",
    "record('demo_rounds', rounds)\n",
    "\n",
    "def explain(fact, why, depth=0):\n",
    "    lines = ['  ' * depth + fact]\n",
    "    for c in why.get(fact, []):\n",
    "        lines += explain(c, why, depth + 1)\n",
    "    return lines\n",
    "\n",
    "chain = explain('cheetah', why)\n",
    "record('demo_chain_depth', max(l.count('  ') for l in chain))\n",
    "print('\\n'.join(chain))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "986b4842",
   "metadata": {},
   "source": [
    "## 3. Backward chaining: only ask what you need\n",
    "\n",
    "The other direction. Pick a goal, work out what would prove it, and ask only\n",
    "those questions — the same instinct as A\\*, in different clothing.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "38653c98",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:14:25.810247Z",
     "iopub.status.busy": "2026-08-17T13:14:25.810168Z",
     "iopub.status.idle": "2026-08-17T13:14:25.911772Z",
     "shell.execute_reply": "2026-08-17T13:14:25.911328Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "avg_questions = 5.6\n",
      "questions_cheetah = 4\n",
      "questions_albatross = 5\n",
      "all_correct = yes\n",
      "ask_everything = 18\n",
      "question_saving = 69%\n",
      "figure questions-asked -> the-machine-that-reasoned.questions-asked.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: Twenty questions, won in four\n",
    "def backward(goal, oracle, asked):\n",
    "    if goal in DERIVED:\n",
    "        for conds, concl in RULES:\n",
    "            if concl != goal: continue\n",
    "            if all(backward(c, oracle, asked) for c in conds):\n",
    "                return True\n",
    "        return False\n",
    "    if goal not in asked:\n",
    "        asked[goal] = oracle(goal)\n",
    "    return asked[goal]\n",
    "\n",
    "TRUTH = {\n",
    "    'cheetah':   ['hair','eats meat','tawny','dark spots'],\n",
    "    'tiger':     ['hair','eats meat','tawny','black stripes'],\n",
    "    'giraffe':   ['hair','hooves','long neck','long legs','dark spots'],\n",
    "    'zebra':     ['hair','hooves','black stripes'],\n",
    "    'ostrich':   ['feathers','cannot fly','long neck','long legs'],\n",
    "    'penguin':   ['feathers','cannot fly','swims'],\n",
    "    'albatross': ['feathers','good flyer'],\n",
    "}\n",
    "\n",
    "counts = {}\n",
    "for animal, truth in TRUTH.items():\n",
    "    asked = {}\n",
    "    for candidate in ['cheetah','tiger','giraffe','zebra','ostrich','penguin','albatross']:\n",
    "        if backward(candidate, lambda f: f in truth, asked):\n",
    "            break\n",
    "    counts[animal] = (candidate, len(asked))\n",
    "\n",
    "avg = sum(n for _, n in counts.values()) / len(counts)\n",
    "record('avg_questions', f'{avg:.1f}')\n",
    "record('questions_cheetah', counts['cheetah'][1])\n",
    "record('questions_albatross', counts['albatross'][1])\n",
    "record('all_correct', 'yes' if all(a == g for g, (a, _) in counts.items()) else 'NO')\n",
    "record('ask_everything', len(ASKABLE))\n",
    "record('question_saving', f'{100*(1-avg/len(ASKABLE)):.0f}%')\n",
    "\n",
    "def plot(ax):\n",
    "    names = list(counts)\n",
    "    vals = [counts[n][1] for n in names]\n",
    "    ax.barh(names, vals)\n",
    "    for i, v in enumerate(vals):\n",
    "        ax.text(v + .25, i, str(v), va='center', fontsize=10)\n",
    "    ax.axvline(len(ASKABLE), ls='--', lw=1.2)\n",
    "    ax.text(len(ASKABLE) - .4, len(names) - 0.6,\n",
    "            f'asking everything: {len(ASKABLE)}', ha='right', fontsize=9)\n",
    "    ax.set_xlim(0, len(ASKABLE) + 1.5)\n",
    "    ax.set_xlabel('questions the system actually asked')\n",
    "save_fig('questions-asked', plot, figsize=(7, 3.6))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad9e9447",
   "metadata": {},
   "source": [
    "## 4. What each rule is worth\n",
    "\n",
    "Which conclusions can the system reach at all, and how deep does it have to\n",
    "chain to get there?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "b4082e1f",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-17T13:14:25.913943Z",
     "iopub.status.busy": "2026-08-17T13:14:25.913814Z",
     "iopub.status.idle": "2026-08-17T13:14:25.971392Z",
     "shell.execute_reply": "2026-08-17T13:14:25.971109Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "max_depth = 3\n",
      "min_depth = 2\n",
      "figure chain-depth -> the-machine-that-reasoned.chain-depth.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: Depth of reasoning per animal\n",
    "depths = {}\n",
    "for animal, truth in TRUTH.items():\n",
    "    _, w, _, _ = forward(truth)\n",
    "    depths[animal] = max(l.count('  ') for l in explain(animal, w))\n",
    "record('max_depth', max(depths.values()))\n",
    "record('min_depth', min(depths.values()))\n",
    "\n",
    "def plot(ax):\n",
    "    names = list(depths)\n",
    "    ax.bar(names, [depths[n] for n in names])\n",
    "    for i, n in enumerate(names):\n",
    "        ax.text(i, depths[n] + .06, str(depths[n]), ha='center', fontsize=10)\n",
    "    ax.set_ylabel('steps of reasoning')\n",
    "    ax.set_ylim(0, max(depths.values()) + .7)\n",
    "    ax.tick_params(axis='x', rotation=30)\n",
    "save_fig('chain-depth', plot, figsize=(7, 3.4))\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
}