Минимакс

Гарантированный результат игры: максимизируем минимум, который оставит соперник.

время O(b^d)память O(d)уровень: начальный

Что происходит сейчас0/0

Нажмите Play, чтобы запустить сценарий

TypeScript — активная строка подсвечена шагом

1function minimax(node: Node, maximizing: boolean): number {
2  if (isLeaf(node)) return node.value
3 
4  if (maximizing) {
5    let best = -Infinity
6    for (const child of node.children) {
7      best = Math.max(best, minimax(child, false))
8    }
9    return best
10  } else {
11    let best = Infinity
12    for (const child of node.children) {
13      best = Math.min(best, minimax(child, true))
14    }
15    return best
16  }
17}

Проблема

Гарантированный результат игры: максимизируем минимум, который оставит соперник.

Что вы видите

Листья — исходы; MIN-узлы забирают меньшее, MAX — большее из детей.

Как это работает

Рекурсия по дереву игры: на своих ходах берём максимум, на ходах соперника — минимум (худшее для нас). Результат — лучшее, что можно гарантировать при рациональном сопернике.

Пошаговый разбор

01
MIN-уровень
Соперник выберет худшее.
02
MAX-уровень
Мы выбираем лучшее.
03
Корень
Гарантированный результат.

Complexity и ограничения

time

O(b^d)

space

O(d)

Сложность см. в шапке страницы.

Edge cases

Пустой вход
Корректная тривиальная обработка.
Вырожденный случай
Минимум работы — сразу ответ.

Где встречается в реальности

Шахматы

Основа всех движков.

Крестики-нолики

Идеальная игра.

Переговоры

Максиминные стратегии.

Связанные алгоритмы

Перестановки (backtracking)Альфа-бета отсечение

Shorts

«Гарантия против любого соперника: минимакс»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Гарантия против любого соперника: минимакс

Нажмите Play

Бит 1/6 · 0–2 с

Hook

script-setup.ru/algorithms/minimax