Как создать хорошую функцию оценки для игры?
Я пишу программы, чтобы иногда играть в настольные игры. Базовая стратегия - стандартное сокращение альфа-бета или подобные поиски, иногда дополняемые обычными подходами к финальным играм или открытиям. Я в основном играл с шахматными вариантами, поэтому, когда приходит время выбирать свою функцию оценки, я использую базовую функцию оценки шахмат.
Однако сейчас я пишу программу для совершенно новой настольной игры. Как выбрать хорошую или даже достойную функцию оценки?
Основные проблемы заключаются в том, что на доске всегда находятся одни и те же фигуры, поэтому обычная материальная функция не будет меняться в зависимости от позиции, и в игру играли менее тысячи раз или около того, поэтому люди не обязательно играют ее достаточно хорошо, чтобы дать понимание. (PS. Я рассматривал подход MoGo, но случайные игры вряд ли закончатся.)
Детали игры: Игра ведется на доске 10 на 10 с фиксированными шестью фигурами на стороне. Части имеют определенные правила движения и взаимодействуют определенным образом, но ни одна фигура никогда не захватывается. Цель игры - собрать достаточное количество фигур в определенных специальных клетках на доске. Цель компьютерной программы состоит в том, чтобы предоставить игрока, который конкурирует или лучше, чем нынешние игроки-люди.
8 ответов
Найдите несколько кандидатов для вашей функции оценки, таких как мобильность (количество возможных ходов) минус подвижность противника, затем попытайтесь найти оптимальный вес для каждой метрики. Генетические алгоритмы, кажется, работают довольно хорошо для оптимизации весов в функции оценки.
Создайте популяцию со случайными весами, сражайтесь с ними друг против друга с ограниченной глубиной и ходами, замените проигравших случайными комбинациями из победителей, перемешайте и повторите, распечатывая среднее количество населения после каждого поколения. Дайте ему поработать, пока вы не будете удовлетворены результатом, или пока не увидите необходимость отрегулировать диапазон для некоторых метрик и повторите попытку, если окажется, что оптимальное значение для одной метрики может быть за пределами вашего исходного диапазона.
Позднее редактирование: более приемлемый, изученный, понятный подход, который я не знал в то время, называется "Дифференциальная эволюция". Потомки создаются от 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 минут назад, не стоит недооценивать способность человека искать узоры. Даже после нескольких игр умный человек может дать вам идеи, как он должен был играть (это не значит, что он может воплотить идеи в жизнь). Используйте эти идеи как функции.
На данный момент вам не нужно знать, как эти функции влияют на игру. Пример особенностей: ценность фигур, подвижность фигур, контроль важных позиций, безопасность, общее количество возможных ходов, близость к финишу.
После того как вы закодировали эти функции и использовали их по отдельности, чтобы увидеть, что работает лучше (не спешите отбрасывать функции, которые сами по себе не работают, они могут быть полезны в сочетании с другими), вы готовы экспериментировать с комбинациями.
Построение лучших оценок путем объединения и взвешивания простых функций. Есть пара стандартных подходов.
Создайте функцию убер на основе различных комбинаций ваших функций. Это может быть линейным
eval = f_1 * a_1 + ... f_n * a_n(f_iфункции,a_iкоэффициенты), но это может быть что угодно. Затем создайте экземпляры многих агентов с абсолютно случайными весами для этой функции оценки и используйте генетический алгоритм, чтобы воспроизводить их друг против друга. Сравните результаты, используя систему тестирования, отбросьте пару явных неудачников и измените пару победителей. Продолжайте тот же процесс. (Это грубый набросок, подробнее о ГА)Используйте идею обратного распространения из нейронных сетей для обратного распространения ошибки с конца игры, чтобы обновить вес вашей сети. Вы можете прочитать больше, как это было сделано с нардами (я не написал ничего подобного, так что извините за краткость).
Вы можете работать без функции оценки! Это может звучать безумно для человека, который слышал только о минимакс / альфа-бета, но есть методы, которые вообще не требуют оценки. Один из них называется " Поиск по дереву Монте-Карло", и, как следует из названия, "Монте-Карло" в названии использует много случайных (он не должен быть случайным, он может использовать ваших предыдущих хороших агентов) игр, чтобы создать дерево. Это огромная тема сама по себе, поэтому я дам вам действительно объяснение высокого уровня. Вы начинаете с корня, создаете свою границу, которую вы пытаетесь расширить. Как только вы что-то расширяете, вы просто случайно переходите к листу. Получив результат из листа, вы получите обратный результат. Делайте это много раз и собирайте статистику о каждом дочернем элементе текущей границы. Выберите лучший. Там есть важная теория, которая относится к тому, как вы балансируете между разведкой и эксплуатацией, и хорошо читать, что есть UCT (алгоритм Upper Confidence Bound)
Я бы посмотрел на контролируемый алгоритм машинного обучения, такой как обучение с подкреплением. Проверьте Укрепление обучения в настольных играх. Я думаю, что это даст вам хорошие направления для изучения.
Также ознакомьтесь со статьей "Приобретение стратегии" для игры "Отелло", основанной на изучении подкрепления (ссылка в формате PDF), где с учетом правил игры можно узнать хорошую "функцию выигрыша". Это тесно связано с TD-Gammon...
Во время обучения сама нейронная сеть используется для выбора движений для обеих сторон... Довольно неожиданным открытием было то, что существенное количество обучения действительно имело место, даже в экспериментах с нулевым начальным знанием, использующих кодирование необработанных досок.
Насколько я понимаю, вы хотите, чтобы хорошая функция статической оценки использовалась на листьях вашего дерева min-max. Если это так, то лучше помнить, что целью этой статической функции оценки является оценка того, насколько хороша эта доска для компьютерного игрока. Так и есть
f(board1) > f(board2)
тогда должно быть верно, что board1 лучше для компьютера (скорее всего, в конечном итоге победит), чем в board2. Конечно, никакая статическая функция никогда не будет полностью правильной для всех плат.
Итак, вы говорите, что "цель игры состоит в том, чтобы иметь достаточно своих фигур в определенных специальных клетках на доске", поэтому первым ударом в f (доска) будет просто подсчитать количество фигур, которые компьютер имеет на этих фигурах. специальные квадраты. Затем вы можете уточнить это больше.
Не зная специфики игры, невозможно дать лучшие догадки. Если бы вы дали нам правила игры, я уверен, что пользователи stackru могли бы прийти с тоннами оригинальных идей для таких функций.
В то время как вы могли бы использовать различные методы машинного обучения, чтобы придумать функцию оценки (TD-Learning, используемый в таких проектах, как gnubackgammon, является одним из таких примеров), результаты определенно зависят от самой игры. Для игры в нарды это действительно хорошо, потому что стохастическая природа игры (игра в кости) заставляет ученика исследовать территорию, которую он может не захотеть делать. Без такого важного компонента вы, вероятно, в конечном итоге получите функцию оценки, которая хороша сама по себе, но не против других.
Поскольку существенные различия могут быть неприменимы, важна ли концепция мобильности, т. Е. Сколько возможных ходов у вас есть? Является ли управление определенной областью доски обычно лучше, чем нет? Поговорите с людьми, которые играют в игру, чтобы узнать некоторые подсказки.
Хотя желательно иметь как можно более полезную функцию оценки, вам также необходимо настроить алгоритм поиска, чтобы вы могли выполнять поиск как можно глубже. Иногда это на самом деле вызывает больше беспокойства, поскольку глубокий поисковик с функцией оценки медицинского обслуживания может переиграть мелкий поиск с хорошей функцией оценки. Все зависит от домена. (например, gnubackgammon играет в экспертную игру с поиском в один слой)
Существуют и другие методы, которые можно использовать для улучшения качества поиска, наиболее важно иметь таблицу транспонирования для кеширования результатов поиска, чтобы иметь правильное сокращение звука.
Я настоятельно рекомендую просмотреть эти слайды.
Если никто еще не понимает игру, вы не сможете получить приличную функцию оценки. Не говорите мне, что стандартная альфа-бета с количеством материалов хороша или даже прилична для шахмат или их вариантов (возможно, шахматы проигравших - исключение).
Вы можете попробовать нейронные сети с обратной связью или аналогичными алгоритмами машинного обучения, но они, как правило, отстой, пока не получат тонны обучения, которое в этом случае, вероятно, недоступно. И даже тогда, если они не сосут, вы не можете получить от них знания.
Я думаю, что нет никакого способа понять игру как можно лучше, и, для начала, оставить неизвестных как случайных в функции оценки (или просто вычеркнуть картину, пока неизвестные не станут более известными).
Конечно, если вы поделитесь дополнительной информацией об игре, вы сможете получить лучшие идеи от сообщества.
Имейте в виду, что не обязательно, что приличная функция оценки даже существует. Для этого утверждения я предполагаю, что оценочная функция должна быть низкой сложности (P).
Вы также должны быть осторожны в своем выборе. Если ваш алгоритм не имеет известного отношения к фактическому значению, стандартные функции AI не будут работать должным образом. Чтобы быть действительным, ваша оценочная функция или эвристика должны быть такими же, как и ниже фактического значения, или они будут направлять ваши решения странным образом (что можно утверждать для шахмат, даже если я думаю, что стандартные очки хороши).
Что я обычно делаю, так это выясняю, на что способен и что требуется. В некоторых играх, таких как sokoban, я использовал минимальное количество ходов бокса, необходимое для того, чтобы получить один бокс (изолированно) от его текущего местоположения до любого из местоположений ворот. Это не точный ответ для количества требуемых ходов, но я думаю, что это довольно хорошая эвристика, так как она никогда не может быть переоценена и может быть предварительно рассчитана для всей доски. При суммировании балла за доску это просто сумма значений для каждого текущего местоположения бокса.
В искусственном симуляторе жизни, который я написал, чтобы развить охоту на пачку и защиту пачки, система начисления баллов, которую я использовал, была только для руководства эволюцией, а не для выполнения какого-либо сокращения. Я дал каждому существу по одному очку за рождение. За каждую точку энергии, которую они потребляли в своей жизни, я дал им одну дополнительную точку. Затем я использовал сумму точек их генерации, чтобы определить, насколько вероятно, что каждая из них будет размножаться. В моем случае я просто использовал долю очков, которые они получили за свое поколение. Если бы я хотел развивать существ, которые были хороши в уклонении, я бы забил за то, что получил очки, съеденные ими.
Вы также должны быть осторожны, чтобы ваша задача не была слишком сложной для достижения цели. Если вы пытаетесь что-то развить, вы должны убедиться, что пространство решений имеет приличный уклон. Вы хотите направить эволюцию в каком-то направлении, а не просто объявить победу, если случится случайное попадание.
Не зная больше о вашей игре, мне было бы сложно рассказать вам, как создать функцию. Существуют ли четкие значения чего-либо, что указывает на победу или проигрыш? У вас есть способ оценить минимальную стоимость, чтобы закрыть разрыв?
Если вы предоставите больше информации, я с радостью постараюсь дать вам больше информации. На эту тему также есть много отличных книг.
Иаков