Как создать хорошую оценочную функцию для игры?

Question

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

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

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

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

Answer 1

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

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

Позднее редактирование: Более приемлемый, изученный, понятный подход, который я не знал в то время, называется «Дифференциальная эволюция». Потомство создается от 3 родителей вместо 2, таким образом, что позволяет избежать проблемы преждевременной конвергенции в среднем.

Answer 2

Я бы посмотрел на контролируемый алгоритм обучения машине, такой как обучение усилению. Выезд Reinforcement learning in board games. Я думаю, что это даст вам хорошие направления для изучения.

Кроме того, ознакомьтесь с Strategy Acquisition for the Game Othello Based on Reinforcement Learning (PDF-ссылка), где, если заданы правила игры, можно узнать хорошую «функцию выплаты». Это тесно связано с TD-Gammon ...

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

Answer 3

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

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

В искусственной симуляции, которую я написал, чтобы развить охоту и защиту пакетов, система подсчета очков, которую я использовал, была направлена ​​только на эволюцию, а не на какую-либо обрезку. Я дал каждому существу одно очко за то, что родился. Для каждой точки энергии, которую они потребляли в своей жизни, я дал им еще один момент. Затем я использовал сумму очков своего поколения, чтобы определить, насколько вероятен каждый из них для воспроизведения. В моем случае я просто использовал пропорцию общих точек своего поколения, которые они приобрели.Если бы я хотел развить существ, которые были бы хороши в уклоне, я бы забил бы за то, что получил от них очки.

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

Не зная больше о вашей игре, мне было бы трудно сказать, как построить функцию. Есть ли четкие значения того, что указывает на победу или потерю? У вас есть способ оценить минимальные затраты, чтобы закрыть пробел?

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

Jacob

Answer 4

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

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

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

Конечно, если бы вы поделились дополнительной информацией об игре, вы могли бы получить лучшие идеи от сообщества.

Answer 5

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

е (совет1)> е (комитетом2)

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

Итак, вы говорите, что «Цель игры состоит в том, чтобы иметь достаточное количество ваших предметов на определенных специальных площадках на доске», поэтому первый удар на f (доска) просто состоял бы в подсчете количества штук компьютер имеет на этих специальных площадях. Тогда вы сможете усовершенствовать его.

Не зная специфику игры, ее невозможно дать лучшие догадки. Если вы дадите нам правила игры, я уверен, что пользователи stackoverflow смогут придумать массу оригинальных идей для таких функций.

Answer 6

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

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

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

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

Я настоятельно рекомендую посмотреть these slides.

Answer 7

Имейте в виду, что неслучайно верно, что достойная функция оценки даже существует. Для этого утверждения я предполагаю, что оценочная функция должна быть низкой сложности (P).

Answer 8

Начну с некоторых основ и перейду к более сложному материалу позже.

Основной агент и среда тестирования

Независимо от того, какой подход вы принимаете вы должны начать с чем-то очень простой и немой. Наилучший подход для немого агента - случайный (сгенерируйте все возможные ходы, выберите один случайным образом). Это послужит отправной точкой для сравнения всех ваших других агентов. Для сравнения нужна сильная структура. Что-то, что принимает различные агенты, позволяет играть некоторое количество игр между ними и возвращает матрицу производительности. Исходя из результатов, вы вычисляете пригодность для каждого агента. Например ваша функция tournament(agent1, agent2, agent3, 500) будет играть 500 игр между каждой парой агента (играет на первой/второй) и возвращает вам что-то вроде:

x   -0.01  -1.484 | -1.485 
0.01   x   -1.29 | -1.483 
1.484  1.29   x  | 2.774 

Вот, например, я использую 2 очка за победу, 1 очко за ничью озвучивания функцию, и в конце просто суммируя все, чтобы найти пригодность. Эта таблица сразу сообщает мне, что agent3 является лучшим, а agent1 на самом деле не отличается от agent2.

Итак, как только эти две важные вещи настроены, вы готовы экспериментировать с вашими оценочными функциями.

---

Давайте начнем с выбора функций

1. Прежде всего, вам нужно создать not a terrible функцию оценки. Под этим я подразумеваю, что эта функция должна правильно идентифицировать 3 важных аспекта (win/draw/loss). Это звучит очевидно, но я видел значительное количество ботов, где создатели не смогли правильно настроить эти 3 аспекта.

2. Затем вы используете свою человеческую изобретательность, чтобы найти некоторые особенности состояния игры. Первое, что нужно сделать, это поговорить с игровым экспертом и спросить его, как он получает доступ к позиции.

3. Если у вас нет эксперта или вы только что создали правила своей игры 5 минут назад, не стоит недооценивать способность человека искать паттеры. Даже после игры в пару игр умный человек может дать вам идеи, как он должен был играть (это не значит, что он может реализовать идеи). Используйте эти идеи как функции.

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

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

Создание лучших оценок путем объединения и взвешивания простых функций. Существует несколько стандартных подходов.

1. Создайте функцию uber, основанную на различных комбинациях ваших функций. Он может быть линейным eval = f_1 * a_1 + ... f_n * a_n (f_i функции, a_i коэффициентов), но это может быть что угодно. Затем создайте экземпляр многих агентов с абсолютно случайными весами для этой функции оценки и используйте генетический алгоритм, чтобы воспроизводить их снова друг с другом. Сравните результаты, используя платформу тестирования, отбросьте пару четких проигравших и измените пару победителей. Продолжите тот же процесс. (Это грубая схема, подробнее о GA)

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

Вы можете работать без функции оценки! Это может показаться безумным для человека, который только слышал о минимакс/альфа-бета, но есть методы, которые вообще не требуют оценки. Один из них называется Monte Carlo Tree Search, а в качестве Монте-Карло в названии предполагает, что он использует много случайных (он не должен быть случайным, он может использовать ваши предыдущие хорошие агенты), играя для генерации дерева. Это огромная тема сама по себе, поэтому я дам вам свое действительно высокоуровневое объяснение.Вы начинаете с корня, создаете свою границу, которую вы пытаетесь расширить. Как только вы что-то расширяете, вы просто случайно попадаете на лист. Получив результат из листа, вы возвращаете результат. Делайте это много раз и собирайте статистику о каждом ребенке нынешней границы. Выберите лучший. Там существует значительная теория, которая касается того, как вы балансируете между разведкой и эксплуатацией и хорошо читаете, что существует UCT (алгоритм с верхним доверием)