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

Ответ 1

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

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

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

Ответ 2

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

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

Независимо от того, какой подход вы принимаете, вам нужно начать с чего-то действительно простого и немого. Наилучший подход для немого агента - случайный (сгенерируйте все возможные ходы, выберите один случайным образом). Это послужит отправной точкой для сравнения всех ваших других агентов. Для сравнения нужна сильная структура. Что-то, что принимает различные агенты, позволяет играть некоторое количество игр между ними и возвращает матрицу производительности. Исходя из результатов, вы вычисляете пригодность для каждого агента. Например, ваш tournament(agent1, agent2, agent3, 500) функциям 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 что 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 features, a_i), но это может быть что угодно. Затем создайте экземпляр многих агентов с абсолютно случайными весами для этой функции оценки и используйте генетический алгоритм, чтобы воспроизводить их снова друг с другом. Сравните результаты, используя платформу тестирования, отбросьте пару четких проигравших и измените пару победителей. Продолжите тот же процесс. (Это грубая схема, подробнее о GA)

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

f (board1) > f (board2)

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

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

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

Ответ 6

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

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

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

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

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

Ответ 7

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

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

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

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

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

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

Jacob

Ответ 8

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