Lab · потрогать руками
Minimax и αβ-отсечение вживую
Дерево игры глубины 3 (MAX→MIN→MAX→листья). Значения листьев случайны. Считай minimax снизу вверх, включи αβ-отсечение и смотри, какие листья гаснут (их не смотрят) и на сколько падает число посещённых листьев. Перемешай порядок — увидишь, как он решает всё.
Как пользоваться
Зелёные узлы — MAX (берёт максимум), розовые — MIN (минимум). Значения проталкиваются от листьев к корню. Жми αβ-отсечение: листья, которые αβ не смотрит (родитель уже отверг ветку), гаснут и помечаются ✂, а счётчик показывает, сколько листьев реально посещено из 8. Перемешать меняет порядок тех же значений — и число посещённых листьев прыгает: при удачном порядке отсечение сильнее (ближе к √). Новое дерево — новые значения.
MAX (максимум)
MIN (минимум)
отсечено (✂ не смотрим)
Попробуй: включи αβ и жми «Перемешать» несколько раз при тех же значениях. Число посещённых листьев меняется от ~5 до 8 — это и есть роль move ordering: смотри вероятно-лучшие первыми, и отсечений больше. Полный minimax всегда смотрит все 8.
Что заметить
αβ даёт тот же ответ, но смотрит меньше
Значение в корне при αβ всегда совпадает с полным minimax — отсечение выкидывает только ветки, которые не могут изменить результат (родитель их отвергнет). Но число посещённых листьев падает: αβ пропускает поддеревья, как только текущая граница (α для MAX, β для MIN) делает их бесполезными. Это «та же глубина за меньшую работу» — или, при фиксированном времени, «глубже за тот же бюджет».
Порядок решает всё
Жми «Перемешать» — значения те же, меняется лишь порядок листьев, а число посещённых прыгает. При идеальном порядке (лучший ход первым в каждом узле) αβ приближается к √ от полного дерева (тут ~4–5 листьев из 8 вместо 8); при худшем — смотрит почти все. Поэтому настоящие движки половину сил тратят на move ordering (killer/history-эвристики, таблицы транспозиций), чтобы приблизиться к лучшему случаю.
Почему гаснут именно эти листья?
αβ идёт слева направо. В MIN-узле, как только найден лист ≤ α (лучшего, что MAX уже гарантировал левее), остальных детей смотреть незачем: MAX всё равно не пойдёт в эту ветку (она не лучше уже найденного) — β-отсечение. Симметрично α-отсечение в MAX-узле при листе ≥ β. Погашенные листья — это ходы, которые рационально не рассматривать, потому что противник/ты их уже не выберет.