TwiddleLab / Искусственный интеллект / Поиск, игры и планы
Альфа-бета: пропусти то, что не важно
Что ты узнаешь
- Альфа-бета отсечение обходит дерево как минимакс, слева направо, и пропускает любую ветку, которая не может побить уже гарантированное.
- Оно всегда выбирает тот же ход, что и минимакс, но смотрит на меньшее число позиций.
- Порядок ходов важен: пробуй лучшие ходы первыми, и пропустится больше.
- При идеальном порядке оно смотрит примерно на b^(d/2) позиций вместо b^d, поэтому за то же время может искать примерно вдвое глубже.
Как идёт урок
Уже найден ход, который гарантирует 5. Следующий ход позволяет сопернику добиться 2. Нужно ли смотреть остаток этой ветки?
Нажми на скрытые листья, на которые ещё нужно посмотреть. Если таких нет, просто нажми «Проверить».
Обойди дерево слева направо и пропусти то, что не может быть важно.
Пройди по шагам. Считай листья, на которые он смотрит.
Твой ход. Отрежь ветки, которые этому поиску никогда не нужны.
Читай листья слева направо. Проведи поперёк ребра, чтобы его отрезать.
После левой ветки у тебя точно есть 3. В середине соперник уже может добиться 2, значит, эта ветка стоит не больше 2: хуже 3, какими бы ни были 4 и 6. Справа 14 и 5 ничего не решают; решает только последний лист, 2, и после него ничего не осталось.
Этот трюк называется альфа-бета отсечением.
Альфа это лучший счёт, в котором ты уже не сомневаешься; бета лучший, в котором уверен соперник. Когда ветка не может их побить, её отсекают: пропускают. Ответ всегда тот же, что у минимакса. То, какие ходы пробовать первыми, это порядок ходов.
Теперь три уровня. Отрежь всё, что пропускает альфа-бета.
Отрезать можно целую ветку, а не только лист.
Слева соперник может удержать тебя на 5. Второй фиолетовый узел сразу показывает 6, значит, он стоит не меньше 6, и соперник никогда его не выберет: пропусти 9. Справа соперник уже после первого фиолетового узла может удержать тебя на 2, это хуже твоих 5, поэтому остаток этой стороны пропускается.
Игра: переставь ходы так, чтобы альфа-бета посмотрела на 5 листьев или меньше.
Перетащи ветку на другую, чтобы поменять их местами. Листья внутри ветки тоже можно менять.
Шахматный бот с обычным минимаксом за секунду доходит до глубины 6 ходов. А с альфа-бетой и хорошим порядком?
Минимакс смотрит примерно на b^d позиций, альфа-бета в лучшем случае примерно на b^(d/2). Поставь булавку на глубину.
При лучшем возможном порядке альфа-бета смотрит примерно на b^(d/2) листьев (точнее b^ceil(d/2) + b^floor(d/2) - 1). Если d/2 = 6, то d = 12: примерно вдвое глубже за ту же работу. Настоящие боты подбираются к этому, пробуя первыми самые многообещающие ходы.
Какие листья альфа-бета пропустит в этом дереве?
Нажми на каждый лист, на который она не посмотрит.
Левая ветка: соперник выбирает 4, значит, у тебя 4. Середина: после 7 идёт 3, это меньше 4: ветка стоит не больше 3, пропусти 9. Справа: после 8 идёт 2: пропусти 1.
Скоростной раунд: три дерева. Отметь листья, которые пропускает альфа-бета.
Три жизни. В некоторых деревьях пропускается больше, чем в других.
Предыдущий урок: Оценка позиций: оценочные функции · Следующий урок: Монте-Карло: случайные партии · Часть курса: Поиск, игры и планы
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
