Состязательный поиск и игра

Состязательный поиск — это исследование принятия решений в конкурентных условиях, когда агент должен выбирать ходы в игровом дереве против оппонента, который пытается достичь противоположного результата.

Definition

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

Scope

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

Core questions

• Как правило минимакса определяет оптимальный ход против оптимального оппонента?
• Как альфа-бета-отсечение исключает ветви, не влияя на минимаксное значение?
• Как оценочные функции используются для отсечения поиска на фиксированной глубине в больших играх?
• Когда поиск по дереву Монте-Карло предпочтительнее минимакса с ограничением глубины?

Key concepts

• игровое дерево
• минимаксное значение
• альфа-бета-отсечение
• оценочная (эвристическая) функция
• поиск с ограничением глубины и эффект горизонта
• игры с нулевой суммой и полной информацией
• поиск по дереву Монте-Карло
• упорядочивание ходов

Key theories

Правило принятия решений минимакс

В игре для двух игроков с нулевой суммой каждый игрок выбирает ход, который максимизирует его собственный гарантированный минимальный результат; распространение этих максимальных/минимальных значений вверх по игровому дереву дает оптимальный ход в корне.

Альфа-бета-отсечение

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

Поиск по дереву Монте-Карло

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

Clinical relevance

Состязательный поиск породил знаковые системы ИИ, от шахматных движков, использующих альфа-бета-поиск, до программ Go, основанных на поиске по дереву Монте-Карло, и те же методы используются в автоматизированных переговорах, играх безопасности и любых условиях, моделируемых как состязание между оптимизирующими сторонами.

History

В статье Шеннона 1950 года компьютерные шахматы были представлены как минимаксный поиск с оценочной функцией, а теорема минимакса фон Неймана заложила теоретико-игровую основу. Альфа-бета-отсечение разрабатывалось в 1950-60-х годах и было строго проанализировано Кнутом и Муром (1975). Поиск по дереву Монте-Карло, формализованный в 2000-х годах, привел к следующему скачку в силе игры, особенно в Go.

Key figures

• Claude E. Shannon
• John von Neumann
• Arthur Samuel
• Donald E. Knuth
• Ronald W. Moore

Seminal works

• shannon1950
• knuth1975
• browne2012

Frequently asked questions

Изменяет ли альфа-бета-отсечение ход, который выбрал бы минимакс?

Нет. Альфа-бета-отсечение возвращает точно такое же значение и ход, как и полный минимакс; оно лишь избегает исследования ветвей, которые заведомо не могут повлиять на результат. Его преимущество — скорость, и при хорошем упорядочивании ходов оно может искать примерно в два раза глубже за то же время.

Почему в таких играх, как Go, используется поиск по дереву Монте-Карло вместо минимакса?

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