ИИ соперника: минимакс, отсечения и таблица позиций

Если ты знаешь, что дают альфа-бета отсечения и таблица позиций и почему порядок ходов важен, листай до «Теперь сам».

Как думаешь, сколько ходов смотреть

На острове 16 камней. Ходящий берёт 1, 2 или 3, выигрывает тот, кто возьмёт последний. Компьютер хочет сыграть безошибочно - перебрать все варианты до конца партии. Сколько позиций ему придётся посмотреть?

Ответь себе до чтения. Партия - до 16 ходов, на каждом до трёх вариантов: дерево игры растёт почти как 3ⁿ, и полный перебор на 16 камнях - десятки тысяч узлов, на 30 - около 118 миллионов. Но разных ПОЗИЦИЙ всего 17: «осталось n камней». Чей ход, в ключ можно не класть: правила для обоих игроков одинаковы, а оценка дана с точки зрения ходящего. Все узлы дерева - это 17 позиций, пришедших разными путями. Если оценку позиции запомнить, остальные пути к ней ничего не стоят.

На что это похоже

Шахматист, который считает варианты. Он не досчитывает до конца ход, который после ответа соперника явно хуже уже найденного: «этот ход я не сделаю, потому что у него есть ответ хуже моего плана» - и переходит к следующему. А позицию, до которой дошёл двумя порядками ходов, он узнаёт и не пересчитывает.

Механизм: отрицательный максимум, отсечение, таблица

Оценку удобно давать с точки зрения ходящего: +1 - выигрывает, −1 - проигрывает. Тогда минимакс записывается одной функцией: оценка позиции - максимум по ходам от минус оценки позиции после хода, потому что после хода ходит соперник. Это форма из раздела 16, без отдельных «макс» и «мин».

Альфа-бета передаёт вглубь окно [alfa, beta]: alfa - то, что ходящий себе уже гарантировал, beta - то, больше чего соперник ему не позволит выше по дереву. Как только найден ход с оценкой ≥ beta, остальные ходы этой позиции можно не смотреть: соперник в эту позицию не пойдёт. Ответ не меняется - меняется работа, и тем сильнее, чем раньше попался лучший ход.

Таблица позиций - запоминание из раздела 15 для игр: оценку позиции кладут в словарь и при повторном приходе берут готовую. В игре «камни» ключ - число камней. В «Архипелаге» ключ - вся карта, и тут пригождается хеш Зобриста из прошлого урока: он обновляется ходом и стоит несколько операций.

Правило

ИИ соперника перебирает дерево игры минимаксом. Альфа-бета отсечение не меняет ответа и сокращает перебор, сильнее всего - при хорошем порядке ходов. Таблица позиций схлопывает пути, пришедшие в одну позицию, - и на играх, где позиций мало, а путей много, превращает экспоненту в число позиций.

Разбор: три способа на 8, 13 и 16 камнях

Полный минимакс, альфа-бета и минимакс с таблицей позиций. Оценки обязаны совпасть, узлы - нет.

# Игра «камни»: на острове n камней, игроки по очереди берут 1, 2 или 3.
# Кто взял последний камень - выиграл. Оценка позиции для ходящего:
# 1 - выигрыш, -1 - проигрыш.
uzlov = [0]

def minimaks(n):
    # полный перебор дерева игры (раздел 16)
    uzlov[0] = uzlov[0] + 1
    if n == 0:
        return -1         # камней нет: предыдущий взял последний
    luchshee = -1
    for k in [1, 2, 3]:
        if k <= n:
            luchshee = max(luchshee, -minimaks(n - k))
    return luchshee

def alfa_beta(n, alfa, beta):
    # отсечение: как только нашли ход не хуже beta, дальше не смотрим
    uzlov[0] = uzlov[0] + 1
    if n == 0:
        return -1
    for k in [1, 2, 3]:
        if k <= n:
            alfa = max(alfa, -alfa_beta(n - k, -beta, -alfa))
            if alfa >= beta:
                return alfa
    return alfa

def s_tablicej(n, tablica):
    # таблица позиций: одна и та же позиция приходит разными путями
    uzlov[0] = uzlov[0] + 1
    if n in tablica:
        return tablica[n]
    if n == 0:
        return -1
    luchshee = -1
    for k in [1, 2, 3]:
        if k <= n:
            luchshee = max(luchshee, -s_tablicej(n - k, tablica))
    tablica[n] = luchshee
    return luchshee

for n in [8, 13, 16]:
    uzlov[0] = 0
    a = minimaks(n)
    u1 = uzlov[0]
    uzlov[0] = 0
    b = alfa_beta(n, -1, 1)
    u2 = uzlov[0]
    uzlov[0] = 0
    c = s_tablicej(n, {})
    print(n, "камней: оценка", a, b, c)
    print("   узлов: перебор", u1, "| отсечения", u2, "| таблица",
          uzlov[0])

8 камней: оценка -1 -1 -1
   узлов: перебор 177 | отсечения 113 | таблица 22
13 камней: оценка 1 1 1
   узлов: перебор 3736 | отсечения 800 | таблица 37
16 камней: оценка -1 -1 -1
   узлов: перебор 23249 | отсечения 5601 | таблица 46

Оценки совпали во всех трёх способах: 8 и 16 камней - проигрыш ходящего, 13 - выигрыш. Это и есть теория игры: позиция проигрышна, когда камней кратно 4 - что ни возьми, соперник дополнит до 4. Перебор растёт примерно вшестеро на каждые три камня. Отсечения режут работу от полутора раз на 8 камнях до четырёх-пяти на 13-16, но растут так же быстро - экспоненту они не отменяют. Таблица прибавляет три узла за камень: позиций n + 1, и из каждой три хода. Граница правила: таблица схлопывает дерево, только если позиций мало. В «Архипелаге» позиций астрономически много, и таблица держит лишь часть - поэтому её дополняют ограничением глубины и оценкой позиции «на глаз», когда до конца партии не досчитать.

Разбор: порядок ходов решает

Та же альфа-бета на 17 и 18 камнях с тремя порядками ходов: «1-2-3», «3-2-1» и «лучший первым» - взять столько, чтобы осталось кратное 4.

uzlov = [0]

def hody(n, poryadok):
    # порядок, в котором пробуем ходы: 1-2-3, 3-2-1 или «сначала лучший»
    if poryadok == "лучший первым" and n % 4 != 0:
        out = [n % 4]                # оставить сопернику кратное 4
        for k in [1, 2, 3]:
            if k != n % 4:
                out.append(k)
        return out
    if poryadok == "3-2-1":
        return [3, 2, 1]
    return [1, 2, 3]

def alfa_beta(n, alfa, beta, poryadok):
    uzlov[0] = uzlov[0] + 1
    if n == 0:
        return -1
    for k in hody(n, poryadok):
        if k <= n:
            alfa = max(alfa, -alfa_beta(n - k, -beta, -alfa, poryadok))
            if alfa >= beta:
                return alfa
    return alfa

for n in [17, 18]:
    for poryadok in ["1-2-3", "3-2-1", "лучший первым"]:
        uzlov[0] = 0
        o = alfa_beta(n, -1, 1, poryadok)
        print(n, "камней,", poryadok + ":", "оценка", o, "| узлов",
              uzlov[0])

17 камней, 1-2-3: оценка 1 | узлов 5602
17 камней, 3-2-1: оценка 1 | узлов 758
17 камней, лучший первым: оценка 1 | узлов 242
18 камней, 1-2-3: оценка 1 | узлов 11204
18 камней, 3-2-1: оценка 1 | узлов 602
18 камней, лучший первым: оценка 1 | узлов 242

Оценка везде та же, работа различается в 46 раз. Отсечение срабатывает, когда хороший ход найден рано: с ним окно сужается, и остальные ходы обрезаются почти сразу. При «1-2-3» выигрышный ход часто идёт последним, и до него альфа-бета честно перебирает проигрышные. Отсюда главный инженерный приём игровых программ: сначала пробовать ходы, которые были лучшими в прошлый раз или выглядят сильными. Граница правила: «лучший первым» здесь известен из теории; в настоящей игре его не знают, и порядок берут из таблицы позиций и прошлых итераций - угадывают, а не знают наверняка.

Что ломается без этого

ИИ, который думает минуту. Полный перебор без отсечений и таблицы на глубине 8 - и ход компьютера длится дольше хода человека.

Отсечения при плохом порядке. Альфа-бету включили, а выигрыша почти нет: ходы перебираются в порядке номеров, и лучший всегда последний.

Таблица без «чей ход». Позиция с ходом белых и та же с ходом чёрных делят ключ - и ИИ берёт оценку для чужой очереди.

Зачем это в работе

Шахматные движки, планировщики, где у среды есть «противник» (худший случай нагрузки), проверка протоколов перебором состояний, решатели головоломок - везде дерево вариантов, отсечения и таблица уже виденных состояний. А «пробуй сначала то, что сработало прошлый раз» - общий принцип ускорения перебора.

Теперь сам

1. В игре можно брать 1, 2, 3 или 4 камня. Какие позиции проигрышны для ходящего?
2. Сколько узлов посмотрит минимакс с таблицей на 30 камнях, если из каждой позиции три хода?
3. Почему альфа-бета не может дать ДРУГУЮ оценку, чем полный минимакс?