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

https://stackoverflow.com/questions/1291377

18-09-2019
|

Вопрос

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

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

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

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

Решение

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

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

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

Другие советы

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

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

Независимо от того, какой подход вы используете, вам нужно начать с чего -то действительно простого и глупого. Лучший подход для тупого агента - случайный (генерируйте все возможные движения, выберите один случайным образом). Это послужит отправной точкой для сравнения всех других ваших агентов. Вам нужна сильная структура для сравнения. Что -то, что принимает различные агенты, позволяет играть в некоторое количество игр между ними и возвращает матрицу производительности. На основе результатов вы рассчитываете пригодность для каждого агента. Например, ваша функция 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.

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

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

Прежде всего, вам нужно создать not a terrible Функция оценки. Под этим я подразумеваю, что эта функция должна правильно идентифицировать 3 важных аспекта (выигрыш/рисунок/проигрыш). Это звучит очевидно, но я видел значительное количество ботов, где создатели не смогли правильно настроить эти 3 аспекта.
Затем вы используете свою человеческую изобретательность, чтобы найти некоторые особенности игры игры. Первое, что нужно сделать, это поговорить с игровым экспертом и спросить его, как он доступ к этой позиции.
Если у вас нет эксперта, или вы даже только что создали правила своей игры 5 минут назад, не стоит недооценивать способность человека искать паттерны. Даже после игры в пару игр умный человек может дать вам идеи, как он должен был играть (это не означает, что он может реализовать идеи). Используйте эти идеи в качестве функций.
На данный момент вам не нужно знать, как эти функции влияют на игру. Пример функций: стоимость кусочков, мобильность кусочков, управление важными позициями, безопасность, общее количество возможных движений, близость к отделке.
После того, как вы закодировали эти функции и использовали их отдельно, чтобы увидеть, что работает лучше всего (не спешите сбросить функции, которые сами по себе не выполняют разумные, они могут быть полезны в сочетании с другими), вы готовы экспериментировать с комбинациями.

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

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

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

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

Также проверьте Приобретение стратегии для игры Othello на основе обучения подкреплению (PDF -ссылка), где учитывая правила игры, можно изучить хорошую «функцию выплаты». Это тесно связано с TD-Gammon ...

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

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

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

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

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

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

F (Board1)> F (Board2)

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

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

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

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

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

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

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

Я настоятельно рекомендую просмотреть эти слайды.

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

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

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

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

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

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

Джейкоб

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow