Какие у вас есть общие советы по созданию бота для участия в соревновании King of the Hill? Какие стратегии вы используете, чтобы перейти от рассмотрения проблемы к созданию вашего бота? Какие структуры данных вы считаете наиболее полезными?

Пожалуйста, оставьте один совет за ответ.

В поисках равновесия по Нэшу

Это очень важная концепция, когда KOTH включает относительно простой набор решений, включает в себя всего несколько игроков (обычно 2) и является детерминированным. Равновесие по Нэшу описывает «тупиковую» позицию: если два игрока определились со своими двумя стратегиями, тогда оба игрока фактически заблокированы в этих позициях: любой игрок, меняющий свою стратегию, просто создает дополнительные уязвимости.

Примеры игр, в которых важны равновесия по Нэшу:

• Rock-Paper-Scissors (-Lizard-Spock), в которой «непобедимой» стратегией является случайная игра
• Морра , у которой есть «спектр» равновесий. Питер Тейлор написал хороший пример в своем ответе здесь .
• Prisoner's Dilemma, кооперативная игра, известная тем, что «каждый теряет» тупик

Как найти равновесие

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

Пример: камень-ножницы-бумага

RPS имеет нечто, называемое «смешанным» равновесием, что означает, что в него вовлечено распределение . Вместо того, чтобы повторять одно и то же движение (что приведет к быстрому поражению), равновесие состоит в том, чтобы разыграть 1/3 камня, 1/3 бумаги и 1/3 ножниц в случайном порядке. Если я играю случайно, мой оппонент ничего не может сделать, чтобы получить преимущество над собой, точка. Если мой оппонент решает не играть случайно, то это только создает уязвимость с его стороны.

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

Используя эту информацию

Равновесие Нэша в игре часто представляет собой «базовую линию», из которой вы должны попытаться действовать. В RPS игра в случайном порядке гарантирует финишную точку в середине колоды. Чтобы перейти к вершине, вы должны начать выявлять слабые стороны других игроков.

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

Обнаружение отклонения от равновесия

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

• Любые варианты выше / ниже других без причины, например, RPS-игрок, который играет рок в два раза чаще, чем ножницы, или тот, кто избегает играть в бумагу. Некоторые относительно простые статистические данные могут обнаружить это.
• Основывая текущее движение от прошлых движений, в некотором предсказуемом образце. Это включает в себя подражателей, "бьет то, что бьет ваш последний ход", боты или "велосипедные" боты. Для этого требуется дополнительная логика, поскольку общее распределение перемещений может быть равномерно распределено, даже если перемещения не случайны. Вы должны попытаться взять запись ходов и найти корреляции, такие как «ход, который я сделал 2 хода назад, и ход, который сделал мой противник сейчас» и «ход, который он сделал 1 ход назад, и ход, который он сделал сейчас» и т. Д.
• Боты, чье распределение ходов основано на вашем. Уязвимость в этих ботов часто не создается (в измеряемой величины) до тех пор , после того, как вы сами не варьировали от случайного распределения. Как правило, ваш собственный бот попадает в эту категорию.

Будьте конкретны в отношении требований для запуска вашего бота

Боты могут быть написаны на разных языках (и версиях этих языков), так что это поможет всем, когда вы:

1. Протестируйте его в среде, указанной OP (или как можно ближе к ней).
2. Протестируйте его во множестве других сред, если это возможно (чтобы помочь другим, кто хочет запустить его).
3. Будьте конкретны в отношении языка и версии, которую вы используете, и объясните, как запустить вашего бота.

В качестве бонуса: если вы используете менее известный язык, сделайте ссылку, чтобы люди могли скачать бинарный файл / источник для его запуска.

Если команда основана, работайте вместе с вашей командой

Хотя вы обычно можете написать бота, который будет работать в одиночку для выполнения задач, чтобы помочь вашей команде, есть гораздо большее преимущество, когда вы координируете как внутри, так и вне игры. Яркий пример этого можно увидеть в игре «Красный против синего» - боевые роботы команды Pixel .

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

Поэтому вне игры планируйте и координируйте со своими товарищами по команде, какие стратегии охватить. Может быть, у кого-то есть бот, который сканирует карту по диагонали? Сделайте ваш просмотр горизонтально (только пример). Внутри игры, если вызов учитывает командное общение, воспользуйтесь этим. Например, в игре с боевыми ботами вы можете отправить сообщение своим товарищам по команде о положении ботов за пределами поля их зрения, а затем побудить их написать своих ботов совместимым способом, чтобы использовать эти сигналы.

Используйте мета-стратегию

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

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

Как вы можете решить это? Вы позволяете своему боту на лету решать, какую стратегию использовать!

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

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

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

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

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