{
  "nbformat": 4,
  "nbformat_minor": 5,
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.12.14"
    },
    "execution": {
      "method": "Python subprocess, exact code cell source",
      "deterministic_replay_passed": true
    },
    "runtime": {
      "packages": [],
      "local_assets": []
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "id": "question",
      "metadata": {},
      "source": [
        "# What a search budget cannot fix after early pruning\n",
        "A nine-leaf tree separates exploration, pruning, and work actually used. More budget cannot recover a branch already discarded.\n",
        "\nDeterministic in-memory search allocation on a constructed tree; no file operations, language model, or reproduction of LATS benchmark scores.\n"
      ]
    },
    {
      "cell_type": "code",
      "id": "experiment",
      "metadata": {},
      "execution_count": 1,
      "source": [
        "\"\"\"What a search budget cannot fix after early pruning\n",
        "Deterministic, standard-library experiment. RESULTS contains the full data.\n",
        "\"\"\"\n",
        "import math\n",
        "\n",
        "leaves = ((2, 3, 4), (5, 6, 7), (0, 8, 10))\n",
        "heuristic_order = (0, 1, 2)\n",
        "\n",
        "def search(mode, budget):\n",
        "    allowed = heuristic_order[:{'greedy': 1, 'beam2': 2, 'uct': 3}[mode]]\n",
        "    visits, totals = [0] * 3, [0.0] * 3\n",
        "    best, used = None, 0\n",
        "    for _ in range(budget):\n",
        "        frontier = [a for a in allowed if visits[a] < len(leaves[a])]\n",
        "        if not frontier:\n",
        "            break\n",
        "        if mode == 'uct':\n",
        "            unseen = [a for a in frontier if visits[a] == 0]\n",
        "            def score(a):\n",
        "                bonus = math.sqrt(2 * math.log(max(1, used)) / visits[a])\n",
        "                return totals[a] / visits[a] + bonus\n",
        "            arm = unseen[0] if unseen else max(frontier, key=score)\n",
        "        else:\n",
        "            arm = min(frontier, key=lambda a: (visits[a], a))\n",
        "        reward = leaves[arm][visits[arm]]\n",
        "        visits[arm] += 1\n",
        "        totals[arm] += reward\n",
        "        used += 1\n",
        "        best = reward if best is None else max(best, reward)\n",
        "    return best, used\n",
        "\n",
        "for budget in (2, 4, 6, 9):\n",
        "    row = {mode: search(mode, budget) for mode in ('greedy', 'beam2', 'uct')}\n",
        "    print('budget', budget, 'best_reward,used', row)\n",
        "assert search('uct', 9) == (10, 9)\n",
        "assert search('greedy', 9) == (4, 3)\n",
        "\n",
        "\n",
        "sweep=[dict(budget=b,mode=m,best_reward=search(m,b)[0],used=search(m,b)[1]) for b in range(1,10) for m in ('greedy','beam2','uct')]\n",
        "# Exhaustive three-branch allocation recovers all nine leaves regardless of ordering.\n",
        "original_order=heuristic_order\n",
        "permuted=[]\n",
        "from itertools import permutations\n",
        "for order in permutations(range(3)):\n",
        "    heuristic_order=order\n",
        "    permuted.append(dict(order=list(order),greedy=search('greedy',9)[0],beam2=search('beam2',9)[0],uct=search('uct',9)[0]))\n",
        "heuristic_order=original_order\n",
        "assert all(r['uct']==10 for r in permuted)\n",
        "RESULTS=dict(leaves=leaves,heuristics=[9,6,2],sweep=sweep,order_sensitivity=permuted)\n",
        "print('Heuristic order permutations:',len(permuted),'; full-budget UCT maximum always 10')\n"
      ],
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "budget 2 best_reward,used {'greedy': (3, 2), 'beam2': (5, 2), 'uct': (5, 2)}\n",
            "budget 4 best_reward,used {'greedy': (4, 3), 'beam2': (6, 4), 'uct': (6, 4)}\n",
            "budget 6 best_reward,used {'greedy': (4, 3), 'beam2': (7, 6), 'uct': (7, 6)}\n",
            "budget 9 best_reward,used {'greedy': (4, 3), 'beam2': (7, 6), 'uct': (10, 9)}\n",
            "Heuristic order permutations: 6 ; full-budget UCT maximum always 10\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "from pathlib import Path\n",
        "import base64\n",
        "print('__NOTEBOOK_IMAGE__svg+xml:' + base64.b64encode(Path('figure.svg').read_bytes()).decode())\n"
      ]
    }
  ]
}