Как ИИ выбирает ход, заглядывая вперёд. Minimax предполагает оптимального противника; αβ-отсечение выкидывает ветки, которые не могут повлиять на результат; MCTS сэмплирует, когда дерево слишком велико для перебора. А фронтир — гибрид: классический поиск с обученной оценкой внутри (AlphaZero, Stockfish NNUE).
~18 мин🔬 поиск + гибрид ML🏠 лаба
Суть за 30 секунд
Поиск по дереву игры выбирает ход, заглядывая вперёд. Minimax (полная информация, ноль-сумма): ты максимизируешь, противник минимизирует; оцени листья, протолкни значения вверх. Это экспонента , поэтому αβ-отсечение выкидывает ветки, которые уже не могут изменить исход — в лучшем случае (вдвое глубже за то же время; так Deep Blue в 1997 обыграл Каспарова + quiescence + таблицы транспозиций + ручная оценка). Когда дерево огромно (Go: ) или нет хорошей оценки — MCTS сэмплирует: спуск по UCB1 (эксплойт↔исследование), симуляция-роллаут, backprop; anytime, параллелится, не требует оценочной функции. Фронтир — гибрид: AlphaGo/AlphaZero/MuZero = MCTS + обученная сеть (policy+value) вместо случайных роллаутов; Stockfish = αβ + NNUE (обученная оценка). Урок для ML-инженера: поиск — это скелет, ML входит обученным компонентом внутрь, а для большинства игр хватает классического поиска (стратегия — не бутылочное горло, реакция — да).
Для игр с полной информацией и нулевой суммой: на своих ходах берёшь max по детям, на ходах противника — min (он играет против тебя оптимально). Оцени листья функцией , протолкни значения снизу вверх, выбери ход к корню с лучшим гарантированным исходом:
Полный перебор стоит (ветвление , глубина ) — для шахмат позиций. Так глубоко не пройти. Спасает отсечение.
αβ-отсечение
Веди две границы: — лучшее, что MAX уже гарантировал, — лучшее, что гарантировал MIN. Как только , оставшихся детей узла можно не смотреть: они не изменят результат (родитель их отвергнет). В идеальном порядке ходов это срезает ветвление до корня:
То есть та же глубина за квадратный корень работы — или вдвое глубже за то же время. Для шахмат сжимается до — миллион-кратно. Порядок ходов критичен: смотри вероятно-лучшие первыми → больше отсечений. Deep Blue (1997, обыграл Каспарова): αβ + quiescence-поиск (досматривать до «спокойной» позиции, против horizon effect) + таблицы транспозиций (кэш позиций) + ручная оценочная функция.
MCTS: когда перебор невозможен
Для Go и нет хорошей ручной оценки — αβ бессилен. Monte Carlo Tree Search строит дерево асимметрично, вкладываясь в перспективные линии, четырьмя шагами: select (спуск по UCB1) → expand (добавить ребёнка) → simulate (роллаут до конца) → backpropagate (обновить статистику побед). Выбор ребёнка балансирует эксплойт и исследование:
( — победы узла, — его посещения, — посещения родителя, — вес исследования). Это тот же explore-exploit, что в бандитах. MCTS — anytime (дольше крутишь — лучше ход), параллелится (независимые роллауты) и не требует оценочной функции (только правила и итог).
Фронтир: обученная функция внутри поиска
Прорыв не в замене поиска сетью, а в сети внутри поиска. AlphaGo: MCTS + CNN policy (какие ходы смотреть) + value (насколько хороша позиция), заменяя случайные роллауты обученной оценкой. AlphaZero (2017): то же из self-play, без человеческих партий, PUCT-MCTS — освоил шахматы/сёги/Go. MuZero: убрал даже правила — учит модель среды и планирует в ней (обобщается на Atari). Stockfish 12 (сен 2020): классический αβ + NNUE (обученная оценка вместо ручной) — выигрывал у v11 в ~10× больше партий. Паттерн один: обученный компонент (policy/value/model) слотится в классический скелет поиска.
🕹 Что открыть — и что заметить
Шахматный движок minimax + αβ + NNUE вживую
Любой Stockfish-клиент (Lichess «Analysis») показывает eval-бар и глубину. Eval-бар — это и есть minimax-значение листа, протолкнутое к корню; глубина — сколько полуходов насчитал αβ.
🎮 Сделай: открой анализ партии на Lichess, включи движок и смотри, как с ростом глубины eval меняется (иногда резко — нашлась тактика глубже горизонта). Это αβ, копающий глубже за счёт отсечений, и NNUE, оценивающий листья. Заметь: это пошаговая игра — в экшене так не считают.
Go / AlphaGo MCTS + сеть
Go невозможно перебрать αβ (b≈250, нет простой оценки). AlphaGo/KataGo используют MCTS с обученными policy/value — интуиция направляет, какие линии «воображать».
🎮 Заметь: в KataGo-анализе посмотри «visits» на кандидатах-ходах — это счётчики посещений MCTS; сеть-policy задаёт приор (что смотреть), роллауты/value уточняют. Больше visits → увереннее оценка. Это explore-exploit в действии.
Экшен-игра почему тут НЕ ищут
Шутер/слэшер не строит дерево игры на каждый кадр — ему нужна реакция за 16 мс, а не стратегия на 20 ходов вперёд. Тут правят FSM/BT, не minimax.
🎮 Заметь: в любом экшене враг реагирует мгновенно по правилам (увидел→среагировал), без «раздумий». Поиск по дереву тут был бы и дорог, и не нужен: бутылочное горло — время реакции, а не глубина плана. Вот почему MCTS в проде редок.
🏠 Лаба — minimax и αβ вживую
Интерактивная лаба без кода: дерево игры со случайными листьями. Считай minimax снизу вверх, включи αβ-отсечение и смотри, какие ветки гаснут (их не смотрят), и на сколько падает число посещённых узлов. Покрути порядок ходов — увидишь, как «лучшие первыми» кратно усиливают отсечение. Открыть лабу →
Формула сжатия (b→√b) и UCB1 — в тексте и хардкоре; здесь — потрогать отсечение руками.
Хардкор · сложность αβ, порядок ходов, MCTS/PUCTможно пропустить
Почему именно √b и при чём порядок
Идеальное αβ достигает только при идеальном упорядочивании (лучший ход первым в каждом узле): тогда достаточно одного ребёнка-максимайзера и всех детей-минимайзера, и наоборот. В худшем порядке отсечений нет вовсе — снова . Поэтому движки вкладываются в move ordering: killer-эвристика, history-эвристика, лучший ход из таблицы транспозиций, MVV-LVA для взятий. Плюс iterative deepening: сначала мелкий поиск даёт порядок для глубокого. Quiescence-поиск досматривает форсированные линии (взятия/шахи), чтобы не оборвать оценку на середине размена (horizon effect).
MCTS: UCB1 → PUCT с приором сети
Ванильный UCB1 исследует равномерно. AlphaGo/Zero заменяют его на PUCT: , где — приор сети-policy: исследование смещается к ходам, которые сеть считает перспективными, а не равномерно. Value-сеть заменяет случайный роллаут оценкой позиции. Это на порядки сокращает нужные симуляции — интуиция режет ширину, поиск даёт глубину и коррекцию. MuZero идёт дальше: планирует в выученном латентном пространстве состояний, не зная истинных правил, — MCTS поверх обученной динамики.
Хардкор · поиск + обучение и «когда ML не нужен»можно пропустить
Поиск — скелет, ML — вставка
Общий паттерн 2016→: классический алгоритм поиска + обученный компонент внутри. AlphaZero = MCTS + (policy, value); Stockfish = αβ + NNUE-eval; и он же в LLM — inference-time search (tree-of-thought, verifier-guided decoding, self-consistency): разворачиваешь кандидатов, оцениваешь обученным verifier/value, откатываешь — это MCTS-образная форма. Учить всё end-to-end без структуры поиска обычно хуже: поиск даёт гарантии, интерпретируемость и обобщение по глубине, которых чистая сеть не даёт. Знание, куда вставить обучение (оценка? приор? модель?), а что оставить классическим, — ключевая инженерная развилка.
Когда поиск/ML вообще не нужен
Для большинства шипнутых игр никакого дерева не строят: реактивные FSM/BT/GOAP + скрипты дают предсказуемый, отлаживаемый, дешёвый ИИ, а стратегическая глубина — не бутылочное горло (реакция и «честность» важнее). Minimax/MCTS оправданы там, где игра про глубокий просчёт (шахматы, Go, пошаговая стратегия) и есть время думать. Обучение (NNUE/policy) добавляют, лишь когда пространство слишком велико для ручной оценки (Go). Дисциплина спрашивать «нужен ли тут вообще поиск, и нужна ли внутри него сеть?» — это ровно суждение классика vs ML, ядро всего модуля.
Аналогия
Minimax — как планировать спор, считая, что оппонент всегда даст ответ, худший для тебя: выбираешь дебют, ведущий к наименее плохому худшему случаю. αβ-отсечение — не дочитывать линию, как только ясно, что она уже хуже имеющегося варианта: бросаешь ветку в момент, когда она не может побить твоё лучшее. MCTS — когда дерево ответов необъятно: мысленно «доигрываешь» много случайных продолжений самых перспективных дебютов, ведёшь счёт, какие дебюты чаще ведут к добру, и тратишь больше воображения на хорошо выглядящие (исследование vs эксплойт). AlphaGo — то же, но с обученной интуицией, которая подсказывает, какие линии воображать и насколько позиция хороша, вместо случайных доигрываний.
Почему это важно
Для тебя как ML-инженера это карта того, как обучение и классический поиск сочетаются в самых сильных системах принятия решений — от AlphaZero до inference-time-поиска в LLM: поиск даёт скелет, гарантии и глубину, сеть — интуицию и оценку. И это же — витрина главного суждения курса: для большинства игр поиск/ML не нужен вовсе (реактивные правила предсказуемее и дешевле), а обучение оправдано лишь там, где пространство неохватно вручную. Понимать, куда вставлять обучение и когда не вставлять, — ценнее, чем уметь обучать.
🔁 Куда это ведёт — связи с твоим ML
Урок — про планирование поиском с обученным компонентом внутри и про дисциплину не обучать там, где structure дешевле.
ML / AI (твой домен): MCTS-с-обученной-оценкой — это шаблон planning + learning: AlphaZero/MuZero и вся model-based RL (Dreamer, планирование в латентной динамике) — MCTS/траекторная оптимизация поверх выученной модели. Сейчас тот же паттерн пришёл в LLM как inference-time search: tree-of-thought, verifier/PRM-guided decoding, self-consistency, best-of-N — разворачивай кандидатов, оценивай обученным value/verifier, откатывай (MCTS-форма). αβ/minimax = классический скелет, куда ML вставляется оценкой (NNUE) или приором (policy) — общий паттерн «алгоритм + обученный компонент» (RAG = поиск + LLM; retrieval + reranker). UCB1/PUCT = explore-exploit ядро, тот же, что в бандитах, RL-исследовании, A/B-аллокации и successive-halving для HPO. А честная нота «когда ML не ответ»: чаще хватает поиска/скриптов без обучения (детерминизм, дебаг, стоимость); учить стоит лишь оценку/модель там, где ручной оценки не хватает (Go) — это то самое суждение, ради которого весь курс.
Алгоритмы: ветвление и отсечение (branch-and-bound), таблицы транспозиций = мемоизация, iterative deepening — общая техника оптимизационного поиска.
Дизайн ИИ-противника: глубина поиска — прямой регулятор сложности (мельче поиск = слабее и «человечнее» бот).
Принцип: дай задаче скелет поиска, вставляй обучение точечно (оценка/приор/модель) и только там, где structure не справляется; не обучай то, что дешевле запрограммировать.
🔧 Запусти и поковыряй
🏠 Лаба «minimax + αβ» в браузере
Открой lab-minimax.html: считай minimax, включай αβ, меняй порядок листьев и глубину — смотри, какие узлы отсекаются и на сколько падает счётчик. Доведи отсечение до «идеального» порядка и сравни число узлов с √ от полного.
🧪 Собери мини-движок ~40 мин, опц.
Напиши minimax+αβ для крестиков-ноликов или Connect-4 (десятки строк). Замерь число вызовов eval с отсечением и без → увидишь √b на практике. Затем добавь тривиальную обученную оценку (хоть линейную по фичам) вместо ручной — почувствуй паттерн Stockfish/NNUE в миниатюре.
Чеклист: в лабе довёл αβ до идеального порядка и сравнил с √ полного; понял UCB1 как explore-exploit; связал MCTS+сеть с AlphaZero/inference-time-поиском; сформулировал, когда поиск/ML тут НЕ нужен.
Связи
основа
Pathfinding: A* — тоже поиск, но кооперативный одиночный (A* = информированный best-first); minimax — состязательный.
дальше
RL-агенты — self-play, что обучает policy/value внутри AlphaZero; и почему чистый RL редко шипят.
итог
Классика vs ML — куда вставлять обучение, а что оставить классическим поиском.
смежное
Сложность — глубина поиска как прямой регулятор силы бота.
Вопросы пытливого ума
Minimax или MCTS — когда что?
Зависит от ветвления, наличия хорошей оценочной функции и того, «тактическая» игра или «стратегическая». Minimax + αβ силён, когда ветвление умеренное (шахматы ~35), есть приличная оценочная функция позиции, и игра тактическая (короткие форсированные линии решают) — αβ доминирует, потому что точно просчитывает до горизонта. MCTS берёт верх, когда ветвление огромно (Go ~250, где αβ не углубится), нет хорошей ручной оценки (в Go позицию трудно оценить статически), и/или игра стратегическая (важно общее «чувство» позиции, а не форсаж) — MCTS не нужна оценочная функция (роллауты дают оценку эмпирически) и он anytime/параллелен. На практике сильнейшие системы комбинируют: MCTS + обученная value/policy (AlphaZero) для Go; αβ + NNUE (Stockfish) для шахмат — то есть в шахматах αβ всё ещё выигрывает у чистого MCTS, а в Go — наоборот. Эмпирика: если можешь дёшево и точно оценить позицию — αβ; если нет, но можешь симулировать — MCTS.
Насколько реально αβ ускоряет и почему это не «просто константа»?
Это не константный множитель, а смена показателя экспоненты: с до при идеальном порядке. Практически это значит: за то же время αβ уходит вдвое глубже, чем голый minimax, а каждый лишний уровень глубины — это качественный скачок силы (видишь тактику на ход дальше). Для шахмат разница между и — миллион-кратная, то есть разница между «не досчитать за час» и «за долю секунды». Оговорка: — лучший случай при идеальном упорядочивании ходов; в худшем порядке отсечений нет и ты снова в . Поэтому реальные движки половину усилий тратят на move ordering (killer/history-эвристики, транспозиции, iterative deepening), чтобы приблизиться к идеальному √b. Без хорошего порядка αβ почти бесполезно.
AlphaZero — это «просто» MCTS?
Нет — это MCTS, у которого вырезали случайность и вставили обучение в две ключевые точки. Ванильный MCTS исследует более-менее равномерно (UCB1) и оценивает листья случайными роллаутами до конца партии. AlphaZero заменяет и то, и другое обученной сетью: policy-голова даёт приор «какие ходы вообще стоит смотреть» (через PUCT смещает поиск, режет ширину), value-голова оценивает позицию напрямую (заменяет роллаут — не нужно доигрывать до конца). Сеть обучается из self-play: сыграли партии текущей версией → целевые policy = распределение посещений MCTS, целевой value = исход → переобучили → сильнее → повторили. То есть поиск и сеть улучшают друг друга по кругу. «Просто MCTS» дал бы слабую игру в Go; именно обученные policy/value делают поиск на порядки эффективнее (меньше симуляций на ход). MuZero снимает и последнее допущение — знание правил: учит модель динамики и планирует в ней. Суть: MCTS — двигатель, но топливо — обученная интуиция.
Как это переносится на inference-time-поиск в LLM?
Почти дословно — это ренессанс той же идеи «поиск + обученная оценка». Разворачивание рассуждений LLM деревом (tree-of-thought) = expand в MCTS; оценка промежуточных шагов обученным verifier/PRM (process reward model) = value-сеть, оценивающая лист; выбор, какие ветви разворачивать, по этим оценкам = select по UCB/PUCT; best-of-N и self-consistency — упрощённые формы (широкая выборка + голосование/оценка вместо полноценного дерева). Это ровно AlphaZero-структура, перенесённая с игр на рассуждения: базовая модель даёт policy-приор (какие продолжения вероятны), verifier даёт value (какое ближе к верному), поиск тратит inference-compute, чтобы из фиксированной модели выжать более качественный ответ — как AlphaZero тратит симуляции, чтобы усилить сеть. И тот же трейд-офф: больше поиска = лучше ответ, но дороже (латентность/compute) — привет бюджету латентности. Освоив minimax/MCTS, ты уже понимаешь скелет современного test-time-scaling.
Что почитать
Russell & Norvig, «AIMA», гл. 5 (Adversarial Search) — minimax, αβ, каноничное изложение.
Browne et al., «A Survey of Monte Carlo Tree Search Methods» (2012) — MCTS и UCB1/UCT.