Минимакс и альфа-бета отсечение: как ИИ обыгрывает вас в настольные игры

Почему вам стоит разобраться в минимаксе и альфа-бета отсечении

Каждый ИИ-противник в настольных играх — от крестиков-ноликов до шахмат — использует одну и ту же идею: перебор дерева игры с предположением, что противник играет оптимально. Этот алгоритм называется минимакс, а альфа-бета отсечение делает его достаточно быстрым для работы в браузере без сервера. Понимание этих алгоритмов не только поможет вам писать игровые боты, но и прокачает навыки рекурсивного мышления, что часто спрашивают на собеседованиях.

Минимакс: одна функция для всей игры

Представьте, что оцениваете позицию с точки зрения ИИ: +1 — победа ИИ, -1 — победа игрока, 0 — ничья. Тогда алгоритм обходит дерево возможных ходов: на ходе ИИ выбирает максимум из значений детей, на ходе игрока — минимум (худший для ИИ исход). Это чередование и есть весь минимакс.

def minimax(node, is_max):
    if node.is_terminal():
        return score(node)  # +1, -1 или 0

    if is_max:  # ход ИИ
        best = -float('inf')
        for child in node.moves():
            best = max(best, minimax(child, False))
        return best
    else:  # ход игрока
        best = float('inf')
        for child in node.moves():
            best = min(best, minimax(child, True))
        return best

Эта функция рекурсивно спускается до терминальных узлов (конец игры), оценивает их, а затем поднимает значения вверх, выбирая оптимальный ход. Для крестиков-ноликов это работает отлично: дерево небольшое, и перебор всех вариантов занимает доли секунды.

Альфа-бета отсечение: тот же ответ, но быстрее

Полный перебор ветвей расточителен. Если вы уже нашли ответ, который опровергает ход, остальные ветви этого хода можно не смотреть — они не изменят решение. Две переменные переносят эту информацию вниз по дереву: alpha (лучший результат, который MAX уже может гарантировать) и beta (лучший результат, который MIN уже может гарантировать). Когда они пересекаются, поиск прекращается.

def alpha_beta(node, alpha, beta, is_max):
    if node.is_terminal():
        return score(node)

    if is_max:
        best = -float('inf')
        for child in node.moves():
            best = max(best, alpha_beta(child, alpha, beta, False))
            alpha = max(alpha, best)
            if beta <= alpha:
                break  # отсечение остальных ветвей
        return best
    else:
        best = float('inf')
        for child in node.moves():
            best = min(best, alpha_beta(child, alpha, beta, True))
            beta = min(beta, best)
            if beta <= alpha:
                break  # отсечение остальных ветвей
        return best

Отсечение никогда не меняет значение в корне — только количество просмотренных узлов. На небольшой позиции в крестиках-ноликах с тремя пустыми клетками полное дерево — 14 узлов, а альфа-бета посещает 10. На полном дереве от первого хода разница впечатляет: 549 945 узлов сокращаются до 36 528 — это 93% экономии. Именно поэтому непобедимый ИИ в крестики-нолики отвечает за 0.3 мс на стороне клиента.

Почему «просто искать глубже» становится дорого

Поиск на d ходов вперед просматривает примерно b^d узлов, где b — коэффициент ветвления (сколько ходов обычно доступно). Эта цифра взрывается:

• Крестики-нолики: b ≈ 4
• Четыре в ряд: b ≈ 4 (максимум 7 столбцов)
• Шашки: b ≈ 2.8
• Отелло: b ≈ 10
• Шахматы: b ≈ 35

Поиск всего на 8 ходов вперед в шахматах — это порядка 35^8 ≈ 2.3 триллиона позиций. Альфа-бета отсечение, плюс упорядочивание ходов, таблицы транспозиций и другие техники, позволяют достигать полезной глубины, не перебирая всё. (Коэффициенты ветвления — приблизительные средние значения из публикаций, например, Allis 1994.)

Та же идея в пяти разных играх

Каждый ИИ-противник — это этот алгоритм с разной доской, разным способом оценки позиции и разными трюками для углубления поиска:

Как применить это на практике

Попробуйте реализовать минимакс для крестиков-ноликов на Python — это отличное упражнение для закрепления рекурсии и понимания игрового дерева. Затем добавьте альфа-бета отсечение и сравните количество посещенных узлов. Начните с малого: напишите функцию оценки, затем полный перебор, и только потом оптимизируйте.

Для вдохновения посмотрите реальный код движка для шашек (около 230 строк на JavaScript) — он использует итеративное углубление с альфа-бета отсечением и quiescence. Всё работает в браузере без зависимостей.

Итак, ваш следующий шаг — открыть редактор и написать минимакс для крестиков-ноликов. Это займет пару часов, но даст глубокое понимание того, как работают ИИ в играх. Удачи!