Конспект: перебор в играх

Понятия

Дерево игры - дерево, у которого уровни по очереди принадлежат разным игрокам.

Минимакс - свёртка дерева игры: максимум на своём ходу, минимум на ходу противника. Значение корня - результат при идеальной игре ОБЕИХ сторон.

Негамакс - та же свёртка, записанная один раз: значение считается с точки зрения того, кто ходит, и при спуске меняет знак. Только для игр с нулевой суммой.

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

Оценка позиции - дешёвая формула вместо результата партии; подставляется на горизонте поиска.

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

Число Гранди позиции - mex чисел Гранди позиций после хода; ноль - проигрыш ходящего. Теорема Шпрага-Гранди - сумма независимых игр имеет число Гранди XOR чисел частей. Ним - XOR размеров кучек; выигрышный ход делает его нулём.

Что унести

МИНИМАКС
ход наш        → max по детям
ход противника → min по детям
лист           → результат партии (или ОЦЕНКА, если дерево обрезано)
цена: порядка b^d - столько листьев у дерева

НЕГАМАКС (игра с нулевой суммой)
значение = max по ходам ( − значение(после хода) )

АЛЬФА-БЕТА
вниз едет интервал (альфа, бета) - значения, которые ещё могут повлиять
узел max:  альфа = max(альфа, найденное)
узел min:  бета  = min(бета,  найденное)
любой узел: альфа >= бета → выход, остальные ходы не смотрим

значение корня НЕ меняется - это тест на правильность реализации
из отсечённого узла возвращается ГРАНИЦА, а не точное значение

Идеальный порядок даёт ровно b^⌈d/2⌉ + b^⌊d/2⌋ − 1 листьев - замер совпал с формулой до единицы (53 при b=3 d=6, 63 при b=2 d=10, 127 при b=4 d=6). Практический смысл - УДВОЕНИЕ глубины при тех же ресурсах. Худший порядок, наоборот, делает альфа-бету дороже минимакса по шагам.

КРЕСТИКИ-НОЛИКИ 3×3 (замер на движке)
пустая доска         минимакс 549 946 узлов, 49,4 млн шагов
                     альфа-бета 18 297 узлов, 1,73 млн шагов   в 30 раз меньше
значение пустой доски = 0, ничья

X в углу, O в центре      7 332 узла / 667 518 шагов → 844 узла / 80 928 шагов
X в клетке 0, O в клетке 1  8 232 узла / 777 493 шага  → 749 узлов / 74 205 шагов
                          значение 1: ответ стороной на угол - проигрыш

КОГДА ДЕРЕВО НЕ КОНЧАЕТСЯ
обрезка по глубине + оценка позиции = прогноз, а НЕ доказательство
сила программы ≈ глубина × качество оценки

итеративное углубление 1, 2, ... d:  дороже одного прогона в b/(b−1) раза
    замер: 1,5 (b=4) ... 2,6 (b=2)
    даёт: готовый ответ в любой момент + подсказку по порядку ходов
таблица транспозиций: хранить значение + глубину + ТИП (точное / не выше / не ниже)
поиск спокойствия: на горизонте доигрывать взятия и шахи - лекарство от горизонта

Ответ обрезанного поиска не сходится, он скачет, и совпадение ответов на соседних глубинах ничего не доказывает: на другом дереве глубины 3, 4 и 5 дали 81, 81 и 81 при настоящем значении 36.

Ловушки джокера

Свернул оба уровня максимумом. Получается ответ на вопрос «а если противник подыграет»: в крестиках-ноликах такой перебор обещает выигрыш X, тогда как настоящее значение пустой доски 0.

Забыл откат хода. Та же ловушка, что во всём разделе: поставил - сыграл - СНЯЛ. Доска одна, и испорченное состояние протекает в соседние ветки.

Проверил конец игры после цикла по ходам. Терминальные случаи всегда идут первыми, иначе программа «продолжает игру» на уже выигранной доске.

Перепутал знаки или границы в негамаксе. При спуске меняются и знак, и места границ: -ab(..., -beta, -alfa). Ошибка даёт неверный ответ молча.

Положил границу в кеш как точное значение. Всплывёт там, где интервал другой, и испортит ответ. Хранить тип значения обязательно.

Решил, что обрезанный поиск что-то доказывает. Доказывает только поиск до терминальных позиций. Остальное - прогноз с точностью оценки.

Углубляешься, не трогая оценку. Каждый уровень дорожает в b раз и приносит всё меньше, если оценка плохая.

Ждёшь от альфа-беты выигрыша при любом порядке ходов. При худшем порядке она дороже минимакса - замер 11 432 шага против 10 489. Упорядочивание ходов - часть алгоритма, а не украшение.

Поверил, что приём «все используют», сработает и у тебя. Подсказка «лучший ход прошлой итерации» на наших деревьях со случайной оценкой не дала ничего (544 узла против 552), хотя в шахматных движках она обязательна. Проверять надо на своей задаче.

Куда это ведёт

Это была последняя глава раздела. Дальше - конспект: все приёмы сокращения перебора в одной таблице, по силе и по цене, от генерации объектов до альфа-беты, плюс дерево решений «какой приём брать на какой задаче».