Продолжаем заставлять ботов бесконечно играть в карты в надежде вытрясти оптимальные настройки для нашей карточной игры. Первая часть эпопеи находится здесь. Очень рекомендуется ознакомиться с ней, иначе будет очень трудно быть с контексте.
Итак, в предыдущих сериях мы:
Познали боль и дисбаланс
Написали логику карточной игры на питоне
Внедрили в игру ботов и заставили их играть друг с другом тысячи и тысячи партий
Описали метрики, которые мы собираем с игры, и представили их аж в трех ипостасях:
Metrics
,BunchMetrics
,AveragedMetrics
Пообещали себе, что доведем дело до конца и получим оптимальные настройки карточной игры
Варьируем игру
По итогам первой статьи у нас получился GameRepeater
, который крутил одну и ту же игру снова и снова тысячи раз, чтобы метрики, снимаемые по итогам партий, были хорошо усреднены и не имели сильных статистических выбросов.
Теперь, имея GameRepeater
в качестве фундамента, мы можем подняться на ступень выше и последовательно запускать множество GameRepeater
ов с разными параметрами игры. После каждого прогона у нас будут усредненные метрики для каждого набора игровых настроек, и можно будет сравнивать, насколько эти настройки близки к нашим идеальным метрикам, которые мы нарисовали себе в голове. Те настройки, которые окажутся ближе всего к идеальным, побеждают. Такова основная идея.
Вопросы, которые на данном этапе у меня возникли к самому себе еще до реализации всего этого добра, были следующими:
А как сравнивать метрики? Нет, серьезно, оказалось, что
AveragedMetrics
, которые мы описали в предыдущей статье, не то что бы можно как-то в лоб сравнить друг с другом, не пойдя гуглить для этого подходящие алгоритмыКакие игровые параметры я хочу перебирать и нащупать оптимальные для них значения, я определился еще в самом начале пути. Но вот как их перебирать? Брутфорсом что ли проходиться по всем возможным значениям? Но даже диапазоны возможных значений для брутфорса все равно придется ставить в какие-то рамки.
В общем, первую проблему я решил оставить на потом, а со второй разобраться сейчас же, поскольку это даст нам возможность довести практически до логического конца основной алгоритм нашего ботоводства.
Итак, начнем с самих настроек игры. Чтобы понять, как их перебирать и комбинировать, нужно видеть, что они из себя представляют:
@dataclass
class GameSettings:
white_player_class: type[PlayerBase]
black_player_class: type[PlayerBase]
slots_count: int
initial_hand_cards: int
initial_deck_cards: int
initial_matches: int
deck: list[Card] = None
Используется этот класс так: вы создаете и заполняете объект класса GameSettings
, а потом отдаете этот объект в GameBase
, которая применит его поля на себя, изменив количество спичек, ботов-игроков и состав колоды.
Теперь о комбинировании и брутфорсе этих настроек. Сам комбинатор (точнее его данные) я вижу так:
@dataclass
class GameSettingsCombinator:
white_player_options: list[type[PlayerBase]]
black_player_options: list[type[PlayerBase]]
slots_count: range
initial_hand_cards: range
initial_deck_cards: range
initial_matches: range
На что обратим внимание:
Для чисел шикарно подошел стандартный питоновский
range
, т.к. он позволяет задать минимум, максимум и даже шаг того, что мы собираемся перебиратьВарианты ботов описываются просто списком классов
Настройку
deck
мы пропустили, потому что это сложно и вообще на десерт: перебор колоды — сложное, комплексное мероприятие, которому мы посвятим отдельный комбинатор
Такой GameSettingsCombinator
можно сконфигурировать например вот так:
settings_combinator = GameSettingsCombinator(
white_player_options=[AiAlphaNormalPlayer],
black_player_options=[AiAlphaNormalPlayer],
slots_count=range(3, 6+1),
initial_hand_cards=range(0, 10+1, 1),
initial_deck_cards=range(10, 40+1, 5),
initial_matches=range(0, 50+1, 5)
)
Здесь я и описал те самые лимиты и шаги настроек, которые меня плюс-минус устраивают.
Теперь мякотка: как бы вы написали метод для GameSettingsCombinator
, который бы рожал все новые и новые варианты, переборы, комбинации всех вышеприведенных настроек? Если кто-то подумал, что это должен быть генератор, то он молодец, ведь я подумал точно так же. Но, я полагаю, в любом случае никто не был готов увидеть то, что я сейчас покажу:
@dataclass
class GameSettingsCombinator:
white_player_options: list[type[PlayerBase]]
black_player_options: list[type[PlayerBase]]
slots_count: range
initial_hand_cards: range
initial_deck_cards: range
initial_matches: range
# omg
def __iter__(self) -> Generator[GameSettings, None, None]:
for white_player_class in self.white_player_options:
for black_player_class in self.black_player_options:
for slots in self.slots_count:
for hand_cards in self.initial_hand_cards:
for deck_cards in self.initial_deck_cards:
for matches in self.initial_matches:
yield GameSettings(
white_player_class,
black_player_class,
slots,
hand_cards,
deck_cards,
matches,
None
)
def get_combinations_count(self) -> int:
return len(self.white_player_options) \
* len(self.black_player_options) \
* len(self.slots_count) \
* len(self.initial_hand_cards) \
* len(self.initial_deck_cards) \
* len(self.initial_matches)
Уффф. Не спрашивайте меня, какова временная сложность у данного "алгоритма", ведь это генератор с ленивыми вычислениями! Хотя кого я обманываю, ведь это ни разу не спасет программу, поскольку она всяко будет выжимать все комбинации до самого конца.
Как будем выжимать комбинации. Классом SettingsTester
, который по сути и есть то, к чему мы стремились все это время:
class SettingsTester:
game_class: type[GameBase]
settings_combinator: GameSettingsCombinator
ideal_metrics: AveragedMetrics
def launch(self):
for settings in self.settings_combinator:
for deck in self.deck_combinator:
executer = GameRepeater(self.game_class, settings, 1000)
executer.launch()
averaged = executer.bunch_metrics.get_average()
# а че дальше-то?
Здесь я привел SettingsTester
ну в очень упрощенной форме, поскольку оригинальная версия делает помимо основной работы много свистелок-перделок в духе подсчета времени, показывания пользователю прогресс-бара в консоли и т.д. Ведь вы же видели генератор, вы понимаете, насколько долго может крутиться такой код? Я точно не помню, но я всегда оставлял работать скрипт на ночь, потому что он мог крутиться часами.
Диаграмма запусков игры обрастает новыми слоями:

Однако, как вы понимаете, SettingsTester
явно не дописан, поскольку сейчас мы умеем добывать метрики, но не умеем вычислять лучшую из них. А без этого смысла в нашем скрипте и во всей проделанной работе мало.
Как сравнивать метрики
Однажды я спросил ChatGPT, как правильно сравнивать похожесть двух чисел, если они лежат в произвольном диапазоне. Похожесть я хотел получить в виде числа от 0.0 до 1.0, где 0.0 — числа совершенно неблизки, 1.0 — идентичны. Бездушная машина убедила меня в том, что для этой задачи уже существует алгоритм имени неизвестного мне ученого. Алгоритм, правда, идет от обратного и высчитывает различность двух величин в диапазоне от 0.0 до 1.0, которые мы с легкостью можем инвертировать для наших целей, вычев полученную разность от единицы. Формула различности была дана мне чатом в таком виде:
В целом у меня не возникло претензий к этому подходу, поскольку я прогнал его на двух с половиной тестовых кейсах, и результаты показались мне убедительными. Давайте вместе с вами еще раз попробуем убедиться в адекватности алгоритма:
Пробуем получить коэффициент разности чисел 10 и 10000. Они определенно очень разные. Уж точно "разнее" 10 и 100 или 10 и 11. А 10 и 10 так и вообще должны дать нам ноль разности. Давайте проверять:
Выглядит неплохо: разные числа достаточно разные, близкие достаточно близкие, nuff said. Из-за того, что в качестве знаменателя мы выбираем наибольшее из чисел, нормализация происходит именно по нему, что в целом меня тоже не смущало, ибо если взять минимальное из чисел, пойдет какая-то белиберда:
В общем, далее я просто получил свою искомую формулу похожести:
и остался доволен результатом.
Странности произошли уже сейчас, когда я стал писать эту статью спустя, наверное, год после беседы с батюшкой. Я, знаете ли, сразу же забыл имя того ученого, которым передо мной козырял ChatGPT. Пришлось пойти поискать в истории переписки, чтобы козырнуть тут перед вами. Но оказалось, что я удалил тот чат — есть у меня привычка периодически подчищать образующийся переписочный бардак.
Я решил пойти в обход и скормил ChatGPT код, полученный на основе его же подсказок, и попросил выдать мне название сего алгоритма. Бездушная машина ответила, что не знает такого алгоритма, но он очень похож на генерального прокурора модифицированный Canberra distance, который выглядит подозрительно похоже на мой (ага, мой), но все же иначе:
Этот подход тоже вполне себе рабочий, уж точно ничем не хуже подхода с , просто нормализация происходит с учетом обоих участников сравнения, что, возможно, правильнее, но не вносит кардинальных изменений в вычисления:
Вы скажете, что вообще-то числа местами прям сильно другие, но для текущей задачи, на мой не особо опытный взгляд, сойдет, как первое решение, так и второе. А вот что на мой не особо опытный взгляд кажется подозрительным, так это ChatGPT. Записывайте за ним, ловите его на слове, насмехайтесь над ним.
Математики, отпишитесь в комментариях, что вы можете сказать по обеим формулам?
Хорошо — как теперь, имея этот математический базис под рукой, сравнить метрики? Они-то у нас не совсем числа — нечто посложнее. Возьмем сначала класс DataRange
. Напомню вам, как он выглядит:
@dataclass
class DataRange:
min: float = 0.0
max: float = 0.0
average: float = 0.0
median: float = 0.0
Как будем вычислять похожесть двух объектов DataRange
? Тут нужно применить немного эвристики под желаемый результат. У меня вышло так:
class DataRange:
...
def get_similarity_coeff(self, other: 'DataRange') -> float:
def safe_max(one, another):
max_val = max(one, another)
if max_val == 0:
max_val = 1
return max_val
def diff_coeff(one, another):
return abs(one - another) / safe_max(one, another)
def similarity_coeff(one, another):
return 1.0 - diff_coeff(one, another)
min_similarity = similarity_coeff(self.min, other.min)
max_similarity = similarity_coeff(self.max, other.max)
med_similarity = similarity_coeff(self.median, other.median)
MEDIAN_WEIGHT = 0.7
MIN_MAX_WEIGHT = (1.0 - MEDIAN_WEIGHT) / 2.0
return MIN_MAX_WEIGHT * min_similarity + MIN_MAX_WEIGHT * max_similarity + MEDIAN_WEIGHT * med_similarity
Что здесь важно: что для конкретно моего класса DataRange
я посчитал верным в вычислении похожести сделать упор на медиану, при этом не оставив за бортом минимум и максимум, которые тоже в общем-то как-то должны влиять на результат. Но согласитесь, если у двух объектов DataRange
[10; 100] и [12; 80] медиана одна и та же — условные 40, — это значит, что два DataRange
должны быть очень близки друг к другу. В конце концов минимум и максимум диапазона — это чаще всего всплески, отклонения значений от среднего или медианы. Поэтому в данном конкретном случае я рассудил и с потолка взял цифру в 70% влияния медианы на вычисление похожести двух DataRange
. Минимум и максимум разделили между собой остаток влияния по 15% на каждого.
Как вы могли заметить, я такой себе математик, со статистикой и анализом данных так же знаком поверхностно (если честно — никак). Поэтому если вы расскажете в комментариях, почему мой подход — дилетантские фантазии, и как это на самом деле должно быть посчитано, мы все от этого выиграем.
Хорошо, у нас есть еще один класс, который хочется сравнивать. Это ProbabilityTable
:
@dataclass
class ProbabilityTable:
table: dict[int, float]
Пример данных, хранящихся в объекте такого класса (схематично):
{
GameOverResult.WHITE_WINS: 0.4,
GameOverResult.BLACK_WINS: 0.6,
}
и
{
GameOverResult.WHITE_WINS: 0.6,
GameOverResult.BLACK_WINS: 0.3,
GameOverResult.DRAW: 0.1,
}
Здесь для сравнения объектов уже можно применить эвристику иного характера. Главный козырь — числа в словаре нормализованы до диапазона [0; 1] по определению, поэтому я рассудил, что их различность можно посчитать простым . Потом высчитываем похожесть через уже знакомую нам инверсию результата
. Потом посчитаем среднеарифметическое по всей мапе, и готово:
class ProbabilityTable:
...
def get_similarity_coeff(self, other: 'ProbabilityTable') -> float:
n = 0
sum = 0.0
for key, value in self.table.items():
if key in other.table:
sum += 1.0 - abs(value - other.table[key])
n += 1
return sum / n if n > 0 else 0
Мы подходим к боссу — класс AveragedMetrics
. Это та цель, которую нам нужно в итоге уметь сравнивать. Вспомним данные класса:
@dataclass
class AveragedMetrics:
rounds: DataRange
result: ProbabilityTable
exausted: DataRange
Видим, что все три поля мы уже умеем сравнивать друг с другом, так что нам остается как-то усреднить все три результата, и готово. Тут можно пойти по простому пути, выбранному в ProbabilityTable
— посчитать среднеарифметическое, а можно пойти по пути посложнее, как в DataRange
— заиметь кастомные веса. Класс AveragedMetrics
— класс достаточно важный для работы всей нашей программы, так что склоняемся в сторону возможности тонко тюнить и реализуем кастомные веса для каждого из полей:
@dataclass
class AveragedMetrics:
rounds: DataRange = field(default_factory=DataRange)
result: ProbabilityTable = field(default_factory=ProbabilityTable) # [GameOverResult -> float]
exausted: DataRange = field(default_factory=DataRange)
_PROPS_COUNT = 3
rounds_similarity_weight : float = 1.0 / float(_PROPS_COUNT)
result_similarity_weight : float = 1.0 / float(_PROPS_COUNT)
exausted_similarity_weight : float = 1.0 / float(_PROPS_COUNT)
def set_weights(self, rounds_similarity_weight : float, result_similarity_weight : float, exausted_similarity_weight : float):
sum = rounds_similarity_weight + result_similarity_weight + exausted_similarity_weight
self.rounds_similarity_weight = rounds_similarity_weight / sum
self.result_similarity_weight = result_similarity_weight / sum
self.exausted_similarity_weight = exausted_similarity_weight / sum
def get_similarity_coeff(self, other: 'AveragedMetrics') -> float:
similar = (\
self.rounds.get_similarity_coeff(other.rounds) * self.rounds_similarity_weight + \
self.result.get_similarity_coeff(other.result) * self.result_similarity_weight + \
self.exausted.get_similarity_coeff(other.exausted) * self.exausted_similarity_weight \
)
return similar
В итоге мы вообще получили лучшее из двух миров: по умолчанию класс считает похожесть через среднеарифметическое (см. _PROPS_COUNT
и его использование). Но при желании мы можем выставить произвольные веса через метод AveragedMetrics.set_weights
.
Я вас поздравляю, теперь мы умеем сравнивать AveragedMetrics
, а следовательно, понимать, какие параметры игры ближе к идеальным метрикам, а какая игра от них совсем отстала. Это был ключевой барьер на нашем пути, который мы с вами преодолели.
Фармим колоду
Помните генератор настроек игры? О да, теперь нам нужен второй такой же. Я долго думал, как вам показать его реализацию для карточной колоды. Потом понял, что в подробностях будет мало пользы и смысла.
Вкратце, в колоде есть сильные, слабые и обычные карты. Они отличаются суммой показателей атаки и жизней. Количество карт в колоде и количество слабых/сильных и обычных карт фиксированное — это инвариант, мы не хотим это менять по любым соображениям — геймплейным, идеологическим или артовым. Что мы хотим перебирать, так это индивидуальные статы атака/жизни для каждой карты. С учетом ее ранга, конечно же. Ну и там есть еще пара нюансов, инвариантов и эвристик, которые достаточно сильно усложняют вычисления комбинаций карт, но в рамках этой статьи нам неинтересны, поскольку не несут никакой пользы.
Поэтому пускай комбинатор колоды останется для нас некоторым черным ящиком с главным комбинаторным методом:
class DeckCombinator:
def __iter__(self) -> Generator[list[Card], None, None]:
...
Главное, что комбинаций у этого комбинатора ничуть не меньше, чем у предыдущего страшного комбинатора настроек игры. А это значит, что скрипт будет крутиться еще дольше.
Комбинаторика готова
Теперь наши недостающие кусочки паззла собраны, и мы можем их вставить в то место, где у нас был затык:
class SettingsTester:
game_class: type[GameBase]
settings_combinator: GameSettingsCombinator
ideal_metrics: AveragedMetrics
def launch(self):
for settings in self.settings_combinator:
for deck in self.deck_combinator:
executer = GameRepeater(self.game_class, settings, 1000)
executer.launch()
averaged = executer.bunch_metrics.get_average()
# а че дальше-то?
Теперь мы в состоянии ответить на вопрос "а че дальше-то?" и довершить SettingsTester
:
def launch(self):
for settings in self.settings_combinator:
for deck in self.deck_combinator:
executer = GameRepeater(self.game_class, settings, 1000)
executer.launch()
averaged = executer.bunch_metrics.get_average()
similarity = self.ideal_metrics.get_similarity_coeff(averaged)
rate = SettingsRate(deepcopy(settings), averaged, similarity)
self.top_settings_list.apply(rate)
То бишь для очередной комбинации настроек мы получили метрики, гоняя ботов в тысячу партий. Мы сравнили метрики с идеальной метрикой и получили некоторое число близости к идеальным метрикам. Дальше это число вместе с другой полезной информацией (которая может пригодиться при пост-аналитике) пакуется в SettingsRate
и уходит дальше в специальный список-рейтинг, который хранит в себе топ-10 лучших игр.
По завершению достаточно продолжительно работающего скрипта мы получаем наш топ-10 настроек для игры, которые дают нам самые близкие к заданному идеалу ощущения от игры. Главное не ошибиться с идеальными метриками!
Зачем нам топ-10, если достаточно взять самый крутой результат? Ну, например, может оказаться, что первая тройка по показателям примерно равна, но настройки, оказавшиеся на втором или третьем месте нам просто больше нравятся с точки зрения.. чего угодно. А иногда хочется понять, каков разрыв в показателях между последовательно идущими настройками. Я в итоге редко брал самый первый результат из топа, просто потому что был какой-то соизмеримый результат чуть похуже. но красивее по цифрам — это ведь тоже важно.
Вот мы и добились поставленной задачи, теперь мы умеем вычислять лучшее. Можно заканчивать?
Майним игру
Заканчивать никак нельзя!
Во-первых, у нас здесь существенное влияние играет рандом, так что всегда есть вероятность, что второй или третий прогон скрипта покажет иные цифры с иными результатами — это нормально.
Что существеннее — в нашей реализации есть две параллельно улучшаемые истории: общие настройки игры и состав колоды. Они даже разнесены по разным генераторам. И в целом они независимы друг от друга.
Очень скоро через ручной прогон скрипта в разных режимах я осознал, что из этой истории можно выжать нечто большее. Смотрите:
Сначала прогоняем наш скрипт с неизменным составом колоды, варьируя только настройки игры
Получаем некоторый результат с лучшими настройками, который куда-то сохраняем
Запускаем скрипт снова, с загруженными улучшенными настройками игры, которые мы в этот раз не изменяем, зато в этот раз мы варьируем состав колоды
Получаем улучшенный состав колоды, который так же куда-то сохраняем
Повторяем процесс с начала, и так до бесконечности
Моя гипотеза заключается в том, что таким образом, мы можем "майнить" настройки игры до бесконечности, постоянно их совершенствуя. В итоге скрипт просто упрется в какой-то лимит идеальной метрики и будет выдавать +/- одинаково хорошие результаты с некоторыми вариациями н уровне шума.
При чем в последующих запусках нашего SettingsTester
а мы можем как пропускать в топ только те результаты, которые стали еще лучше, чем все предыдущее; так и расслабиться и начинать каждый прогон скрипта с нуля, надеясь на то, что оно будет само самоулучшаться. На первый взгляд лишь первый вариант — самый расово верный, но на практике он очень быстро достигает потолка, не давая комбинатору, так сказать, "развиваться", пусть и ценой локального понижения качества.
Еще один приятный бонус такого попеременного подхода заключается в том, что мы существенно снижаем длительность работы одного раунда скрипта, поскольку заменяем вот это:
def launch(self):
for settings in self.settings_combinator:
for deck in self.deck_combinator:
...
на
def launch(self):
if mode == SETTINGS:
for settings in self.settings_combinator:
...
else:
for deck in self.deck_combinator:
...
существенно снижая разовую комбинаторную нагрузку, от которой ранее мой скрипт буквально захлебывался.
Так над нашим слоистым пирогом надстраивается еще одна сущность SettingsMiner
:

Ну вы понели: майнер, который бесконечно гоняет комбинатор, который раз гоняет повторитель, который гоняет игру по 1000 раз. Звучит очень долго, и так оно и есть, ведь бесконечно — это действительно долго. А один раунд
SettingsTester
в зависимости от настроек комбинатора может длиться от десятков минут до часов на неслабом ПК. Звучит здорово.
В очень схематичном виде SettingsMiner
выглядит вот так:
class SettingsMiner:
def __init__(self):
self._read_settigs()
def launch(self):
while True:
self._mine_round()
self._flush_settings()
self._switch_mode()
Из примечательного: каждое улучшение, полученное SettingsMiner
я записываю в файл на жесткий диск. Это необходимо по нескольким причинам. Во-первых, я могу завершить и перезапустить SettingMiner
в любой момент по сути без потери результата. Во-вторых, я имею зафиксированный, записанный результат, который могу применить где-то еще или даже забрать его оттуда в игру.
Что еще веселее, я не просто записываю полученные настройки игры в какой-то конфиг-файл, неееет, я генерирую питон-код в особый файл:
from alpha_game_package.alpha_player import AiAlphaNormalPlayer
from core_types import Card, CardType
from game import GameSettings
auto_refined_cards_pool : dict[str, list[Card]] = { # actual type is dict[type[GameBase], list[Card]]
'AlphaGame': [
Card(CardType.BEAST, 'rat', 1, 3, 1),
Card(CardType.BEAST, 'wasp', 2, 2, 1),
...
Card(CardType.MAGIC, 'black book', 4, 4, 3),
],
}
auto_refined_game_settings : dict[str, GameSettings] = { # actual type is dict[type[GameBase], GameSettings]
'AlphaGame': GameSettings(
white_player_class = AiAlphaNormalPlayer,
black_player_class = AiAlphaNormalPlayer,
slots_count = 5,
initial_hand_cards = 5,
initial_deck_cards = 20,
initial_matches = 5,
deck = auto_refined_cards_pool['AlphaGame'],
print_log_to_stdout = False
),
}
auto_refined_similarity : dict[str, float] = { # actual type is dict[type[GameBase], float]
'AlphaGame': 0.9756566604127581,
}
last_mode : dict[str, float] = { # actual type is dict[type[GameBase], int]
'AlphaGame': 0,
}
Файл потом на лету перезагружается и юзается снова. Это выглядит как-то так:
def _reload_settings(self):
global auto_refined_settings
importlib.reload(auto_refined_settings)
import auto_refined_settings
sleep(1) # to be sure that reimport is done
Во-первых, это круто. Я вообще, знаете ли, ценитель таких вещей. А во-вторых, потом эти настройки легко загружать другими тестовыми скриптами, которые лежат около основного кода и служат для тестовых целей в качестве песочницы. Благодаря этому для них в распоряжении всегда есть лучшие на сегодняшний день настройки, которые можно брать и использовать.
Вдаваться в детали SettingsMiner
я не стану, поскольку ценна здесь именно идея, а реализация достаточно длинна и запутана, но не потому что в ней есть что-то особо ценное, а просто потому что нюансы, хотелки, удобства, какая-никакая архитектура и прочее.
Послевкусие
Послевкусие от всего этого смешанное — возможно, есть способы более быстрые и надежные для нахождения недисбалансных настроек игры. В конце концов, ведь можно было нанять гейм-дизайнера в команду. Но, полагаю, полученный инструмент хоть и напрямую применим исключительно для моей никогда не выпущенной игры, в целом его можно использовать как гайд для подсчета метрик для ваших личных велосипедов.
Помог ли мне этот инструмент в улучшении игры? Да я и сам не знаю :). Разве это важно, если это стало поводом написать столько любопытного кода? К тому же, мне было интересно, а потому не потрачено.