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

Код для этой статьи находится здесь: https://github.com/gaffney2010/goofspiel-python

Гуфшпиль

Гуфшпиль — простая игра, которую иногда обсуждают в теории игр. Есть 2 или более игроков и набор карт. Карты по одной отображаются в центре стола, и каждый игрок делает ставку на нее, разыгрывая карту в руке. У каждого игрока тот же набор карт, что и в отображаемой колоде, и каждую карту можно сыграть только один раз. Самая высокая ставка выигрывает карту и получает очки, равные стоимости карты. Например, с двумя игроками (Алиса и Чен) и картами {2, 3, 4}, тогда у Алисы и Чена в руке будут карты с номерами 2, 3 и 4, и они будут использовать их, чтобы делать ставки на карты 2. , 3 и 4. Это может выглядеть так:

  • Карта 2: Алиса предлагает 3, а Чен предлагает 2. Алиса выигрывает карту 2.
  • Карта 3: Алиса делает ставку 2, а Чен делает ставку 4. Чен выигрывает карту 3.
  • Карта 4: Алиса предлагает 4, а Чен предлагает 3. (У них на руках остаются только карты.) Алиса выигрывает карту 4.

Теперь у Алисы есть 6 очков за выигрышные карты 2 и 4. У Чена есть 3 очка за выигрышную карту 3. Алиса выигрывает игру за то, что у нее больше очков после того, как все карты вышли.

Ради этой статьи мы скажем, что все ставки должны быть определены до начала игры. Например, Алиса должна решить в начале игры (до того, как она увидит какое-либо решение Чена), что ей будет предложено 3 за 2, 2 за 3 и 4 за 4.

Также скажем, что ничья разделяет очки. Например, в игре с тремя игроками, если Алиса предлагает 2 очка за карту 4, а Бенджамин и Чен предлагают по 3 очка каждый, то Бенджамин и Чен выиграют по 2 (из 4) очков, а Алиса получит 0 очков.

Стратегия меняется для разного количества игроков и разного набора карт. Причина, по которой эта игра интересна теоретику игр, заключается в том, что практически любую фиксированную стратегию можно победить. Убедите себя, что в версии для 2 игроков с картами {2, 3, 4} вы всегда можете победить своего противника, если знаете, как он будет играть; так что нет непревзойденной стратегии. Как и в случае с камнем-ножницами-бумагой, игроки пытаются угадать ходы друг друга. Однако, в отличие от игры «камень-ножницы-бумага», некоторые стратегии (например, высокие ставки за старшие карты) хорошо работают против случайной игры. Отклонение от этих хороших стратегий — это большая ставка на ходы ваших противников. Это может сделать игру немного более захватывающей, а стратегии — богаче.

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

Мы не будем просто программировать хороших игроков с самого начала по нескольким причинам:

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

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

Описанная нами эволюция естественна для генетических алгоритмов.

Генетические алгоритмы

Генетические алгоритмы вдохновлены тем, как работает эволюция в природе. Генетический алгоритм пытается найти оптимальное решение некоторой функции оценки. Сначала создается набор случайных решений-кандидатов. Затем он сохраняет лучшие решения (то есть лучшие в оптимизации функции оценки) и убивает остальные. Количество сохраненных решений называется коэффициентом выживания. Убитые решения заменяются размножением уцелевшими решениями. Разведение — это способ комбинирования двух решений таким образом, чтобы получить свойства обоих. Например, если решения-кандидаты являются просто векторами, усреднение может быть способом их размножения. Делая это, мы создаем больше кандидатов с хорошими качествами, эффективно ища более оптимальную часть пространства состояний. Обычно (хотя и необязательно) существует фаза мутации, которая изменяет каждую стратегию в новой популяции в качестве формы регуляризации. (Регуляризация означает что-то вроде избегания чрезмерной привязанности к хорошему, но не отличному решению.) Мутация вектора может означать добавление небольшого случайного вектора. Эти шаги повторяются много раз, так называемые поколения. Примечание. Более крупный класс алгоритмов пропускает этап размножения и только мутирует.

Это много терминологии, и это может показаться слишком техническим, но идея здесь на самом деле короткая и простая: угадайте возможные решения вашей проблемы; затем многократно комбинировать (или «разводить») лучшие решения.

В нашем случае «решения» — это стратегии. Поскольку все ставки делаются до начала игры, стратегия представляет собой выбор ставок, по одной на каждую карту. Оптимальные стратегии — это стратегии, которые выигрывают игры. Не очевидно, как стратегии размножаются или видоизменяются; поэтому мы потратим некоторое время на изучение этого в следующих двух разделах.

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

Разведение

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

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

Первый алгоритм разведения мы называем разведение-предпочтения. Этот алгоритм сначала представляет стратегию как упорядоченный список предпочтений. Например, выше Алиса предложила 3 ​​за 2, 2 за 3 и 4 за 4. Мы могли бы записать это как 3 ‹ 2 ‹ 4. Такой порядок полностью определяет стратегию торгов.

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

Мама: 1 ‹ 2 ‹ 3 ‹ 4 ‹ 5

Папа: 5 ‹ 1 ‹ 2 ‹ 3 ‹ 4

Мы случайным образом берем некоторый диапазон элементов у мамы, оставляя остальные пока пустыми.

□ < □ < 3 < 4 < □

Затем восполняем недостающие элементы 5, 1 и 2, используя приказ папы.

5 < 1 < 3 < 4 < 2.

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

Второй алгоритм разведения мы называем breeding-pairs. Интуиция подсказывает, что предпочтения на самом деле представляют собой большой набор парных порядков: «мы ценим x больше, чем y» и т. д. Таким образом, чтобы вывести две стратегии, мы просто берем некоторые из этих пар от каждого родителя.

Однако мы не можем делать это небрежно, иначе мы могли бы получить x ‹ y ‹ z ‹ x. Таким образом, с каждым шагом мы должны добавлять любые подразумеваемые транзитивные отношения и добавлять новые отношения только с использованием пар, которые еще не упорядочены. Это будет понятнее на примере.

Скажем, у нас есть два заказа:

Мама: 1 ‹ 2 ‹ 3 ‹ 4 ‹ 5

Папа: 5 ‹ 1 ‹ 2 ‹ 3 ‹ 4

Теперь мы начинаем рисовать пары наугад.

1-я пара от Мамы: 2 ‹ 4

2-я пара от папы: 2 ‹ 3

3-я пара от Мамы: 3 ‹ 5

На данный момент у нас есть частичное упорядочение, которое выглядит так.

Затем рисуем:

4-я пара от папы: 1 ‹ 2

5-я пара от Мамы: 3 ‹ 4

6-я пара от папы: 5‹4

(Обратите внимание, что в примере показаны пары, исходящие попеременно от мамы и папы, но в реализации каждая новая пара выбирается независимо от любого родителя 50/50.)

Это всего лишь один пример, а не обоснование этого алгоритма. 1 ‹ 2 ‹ 3 ‹ 5 ‹ 4 кажется разумным потомком данных мамы и папы, но также можно получить что-то странное, например 2 ‹ 4 ‹ 5 ‹ 1 ‹ 3. Однако, чтобы получить любой элемент, отличный от 5, порядка, вам нужно вытянуть пару пятерок довольно рано, что маловероятно.

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

Мутация

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

Например, чтобы изменить стратегию 1 ‹ 2 ‹ 3 ‹ 4 ‹ 5, мы могли бы повторить описанный выше алгоритм размножения пар, где с каждым шагом есть 90% шанс, что мы возьмем пару из стратегии 1 ‹ 2 ‹ 3 ‹ 4‹5 и вероятность 10%, что мы возьмем пару из стратегии 5‹4‹3‹2‹1.

10% в приведенном выше примере — это единственный параметр нашего алгоритма мутации. Мы называем это степенью мутации, и ее изменение определяет степень изменения стратегий в конце каждого поколения. При 0% мутации нет, а при 50% результирующая стратегия не имеет никакого отношения к неизмененной стратегии.

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

Другие параметры

Помимо выбора стратегии разведения и степени мутации, мы должны выбрать значения для:

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

Первые результаты

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

Если бы мы просто оставили работающий генетический алгоритм работать в течение длительного времени, он бы циклически переключался между стратегиями, постоянно пытаясь оставаться на один ход впереди своего противника. Представьте себе, например, повторную игру с двумя игроками, делающими ставки на карты 2, 3 и 4. Для начала оба игрока могут предпочесть 2 ‹ 3 ‹ 4, но первый игрок, узнавший о предпочтениях 4 ‹ 2 ‹ 3, победит в этой игре. стратегия. В ответ другой игрок мог выучить 3 ‹ 4 ‹ 2. Противник, в свою очередь, снова выучил 2 ‹ 3 ‹ 4. И игроки будут просто ходить по таким раундам.

Я хочу проверить, что наш генетический алгоритм обучается, но со стратегиями, преследующими друг друга и никогда не достигающими значимого преимущества, трудно отличить фактическое обучение от случайных изменений. Поэтому для проверки мы вместо этого фиксируем целевую стратегию 1 ‹ 2 ‹ … ‹ n и оцениваем, насколько хорошо генетический алгоритм может изучить эту целевую стратегию. Обоснование этого таково: в краткосрочной перспективе лучше всего играть против того набора противников, который у вас есть. Хотя оптимальные предпочтения будут меняться по мере изменения противников, алгоритм, который может запоминать предпочтения, должен иметь возможность неоднократно адаптироваться к движущейся цели.

Функция оценки, которую мы пытаемся максимизировать для карт 1, …, n, выглядит следующим образом:

СУММА [ мин(карта_i, ставка_i) — ставка_i ]

Это всегда неположительное целое число, которое является максимальным (значение = 0), когда предпочтения равны 1 ‹ 2 ‹ … ‹ n, что делает его хорошей мерой того, насколько близок список предпочтений к упорядоченному. Это может быть не самая принципиальная мера упорядоченности (по сравнению, скажем, с тау Кендалла), но ее легко вычислить, и ее можно вычислять по одному элементу за раз, что соответствует нашему существующему коду.

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

  • Предпочтения в отношении размножения в сравнении с племенными парами. Априори мы ожидали, что пары для размножения будут работать лучше, но включили в качестве эталона более традиционные предпочтения для разведения.
  • Степень мутации 0,0–0,4.
  • Начальное население 5 или 10. На практике мы начнем с игроков в игре, то есть 2–5 игроков. Мы включили значение 10, чтобы лучше понять чувствительность к этому параметру.
  • 15 или 150 поколений. В большинстве случаев мы наблюдаем очень быструю сходимость. Мы включили эти два значения, чтобы продемонстрировать это.
  • Общая популяция 25 и выживаемость 10/25. Эти параметры не ищутся.

Для каждого набора параметров мы проводим 100 испытаний (с набором карточек 1, 2, …, 20) и сообщаем средний лучший результат для полученной совокупности.

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

Вот результат случайного поиска.

Из данных мы можем узнать несколько вещей:

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

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

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

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

Игра

Теперь мы переключаемся на игру. Показатели для оптимизации здесь весёлые, и мы подойдем к оптимизации менее научно.

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

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

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

Окончательные результаты

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

  • Алгоритм разведения пар со степенью мутации = 0,2
  • 3 поколения игры, маленькие, чтобы не учиться слишком быстро
  • Максимальная популяция 4 с коэффициентом выживаемости 2. Эти низкие числа необходимы, потому что счет, который мы пытаемся оптимизировать, является результирующим счетом, когда все население вместе играет в 7-card goofspiel. Гуфшпиль для 20 игроков — это совсем другая стратегия, чем для 2 или 4 игроков, поэтому мы не могли увеличить популяцию без изменения стратегии. Вероятно, было бы лучше оценивать стратегии по тому, насколько хорошо они играют против случайного другого игрока из популяции 1-на-1, но пока мы довольны результатами.
  • Задайте начальную популяцию для каждой эволюции двумя дополнительными случайными ботами.

Мы играли в игру с этими настройками, и вот что получилось.

Мы заметили, что противник борется за 6, и подумали, что если мы упустим это, то сможем более агрессивно преследовать другие значения.

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

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

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

На этот раз я решил повторно преследовать 4. Также я заметил, что в каждом раунде оба игрока делают высокие ставки на 7, а бот-игрок все выше и выше. Я думал, что это означает, что мы застряли в схеме, когда мы оба тратим самую высокую ставку на 7, только чтобы сравнять счет и каждый раз получать половину очков. Поэтому я смело решил, что на этот раз поставлю только 1 балл.

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

Я не знаю, как именно он решил поставить 2 на этой карте, тогда как я выбрал только 1. Это может быть какой-то выживший ген, который не может полностью обесценить карту. Или это может быть просто удача. Это маловероятно, но, возможно, он столкнулся со стратегией, подобной моей, которая предлагала только 1 на 7. Какой бы ни была причина, проигрыш стал неожиданностью, и я почувствовал, что компьютер перехитрил меня.

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