Заставляем ботов бесконечно играть в карты

Суть проблемы

Как-то раз я занимался любимым делом — баловался написанием мини-игр в стол. На этот раз у меня на повестке была карточная игра-клон Inscryption. Ну, ее бледная копия с размытыми целями и перспективами. Но было понятно, что кор-механика игры — это карточный бой, и он должен быть увлекательным и засасывающим игрока надолго.

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

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

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

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

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

Тогда я подумал, окей, если в Inscryption сначала ходит игрок, а потом его противник, то я могу сделать так же — красть так красть. Но теперь первый походивший игрок имел преимущество, и это было тоже дисбалансно. Забавно, что такого же рода преимущество есть у белого игрока в шахматы, но там это преимущество уж очень несущественно и размазывается за кучей последующих ходов. А тут у нас 4-5 несчастных слота и десяток карт.

Идея

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

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

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

Формализуем задачу

Перед тем, как получить возможность хоть что-то начать писать, предстояло пройти неудобный этап. Дело в том, что все эти ваши “давайте сравним результаты игр с разными правилами и решим, как из них лучше” — это что-то на гуманитарном. Нам нужны цифры; нам нужно то, что можно пощупать руками; нам нужны параметры и метрики. А нас таковых нет, и откуда их взять так сразу не сообразишь.

Вот давайте сходу: боты отыграли тысячу партий игры с одними правилами, потом отыграли еще одну тысячу партий игры с немного видоизмененными правилами. Что именно мы будем подсчитывать для первой тысячи игр? А для второй? А даже если предположим, что мы что-то насчитали, как мы будем это сравнивать и решать, какой из вариантов лучше? То-то же — задача уже с порога не обещает быть простой.

Начнем писать хоть что-то

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

Так вот, нам все это не пригодится — мы будем писать все с нуля на питоне. Почему? Потому что это отдельная исследовательская задача, которой будут только мешать обвесы в виде движка, ассетов, анимаций и визуальных эффектов. Нам нужен грубый, страшный скрипт, выполняемый в дремучей консоли, который как послушная рабочая лошадка все нам посчитает. И потом с этими прекрасными выверенными результатами мы сможем вернуться в наш удобный движок и реализовать кор-механику карточной игры один раз и навсегда (нет).

Давайте договоримся

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

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

Пишем игру

Чтобы ботам было во что играть, нужно описать правила игры.

Опишем необходимые тезисы и требования, чтобы понять, как архитектурно сложить картину воедино:

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

• Какие-то правила у игры хочется менять. Т.е. мы хотим, чтобы у игры было несколько вариаций. Я рассудил, что вариаций игры будет 2-3, и называться они будут Alpha, Beta, Gamma и т.д.

• Раз у игры есть несколько вариаций, значит и разновидностей ботов будет столько же: Alpha-бот, Beta-бот, Gamma-бот и т.д. Каждый умеет играть в конкретную вариацию игры. Но хочется несколько усложнить задачу: хочется, чтобы, например, Alpha-бот был не один, а целый выводок: AlphaIdiot, AlphaNormie, AlphaStronk. В теории это даст нам возможность, варьируя сложность бота, смотреть, насколько существенно будет сказываться более сильный/слабый интеллект на успехе в самой игре. И на основе этих наблюдений тоже можно было бы делать какие-то выводы о качестве и балансе игры

• То ради чего мы собственно собрались — параметры игры. Их-то мы и хотим автоматически вычислить. Мы надеемся, что игровые боты смогут подсказать нам такие игровые параметры для каждой вариации игры, что все они будут сбалансированными и честными (с нашей субъективной точки зрения, конечно). В моем случае параметрами будут такие вещи как: количество слотов для карт на игровой доске, количество карт в колоде игрока, состав колоды игрока, стартовое количество карт в руке игрока, стартовое количество спичек игрока, количество спичек в общаке.

Если принять во внимание все пожелания из списка выше, можно прийти к тому, что скелет класса с игрой должен выглядеть примерно так:

class GameBase:
    black_player: PlayerBase
    white_player: PlayerBase
    
	table: Table

	...

	# methods

Разберем это небольшой кусочек кода практически дословно:

• Название GameBase намекает, что это базовая версия игры. От нее будут наследоваться все AlphaGame, BetaGame, GammaGame и пр. В самом классе GameBase будут находиться методы, касающиеся неизменных правил игры

• Аналогично с игроками: PlayerBase — родительский класс для всех наших GammaIdiot, AlphaNormie, BetaStronk. В наследниках в основном будут находиться свои версии ИИ-ходов. Например, у Idiot-версии метод make_move может просто положить рандомную карту из своей руки на случайный слот игрового стола. Этот же метод у Stronk-версии будет проводить тщательный анализ своих карт и карт противника и, руководствуясь какой-то тактикой, делать продуманный ход или вовсе пасовать

• В table спрятаны все данные, сопряженные с данными игры: слоты, колоды, спички. Они нас сейчас не особо интересуют

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

Код игры

Код любой из вариаций игр — AlphaGame, BetaGame, GammaGame и пр. — будет реализовываться по одной и той же схеме:

• Наследуемся от GameBase

• Реализовываем машину состояний конкретной игры

Со стейт-машиной любые правила игры становится писать легко и приятно. Вот, допустим, я решил написать AlphaGame. Сначала я своими словами описываю, какие у игры будут правила и состояния:

## Start conditions

- 2 cards in a hand
- 10 cards in a deck
- 5 matches
- unlimited matches bank
- 5 slots

## Game states

- WHITE_RESOURCE_TAKE. Options:
    - Card from deck to hand
    - Match from bank
    - Do nothing and skip
- WHITE_MOVE. Options:
    - Place a new card to a board by paying matches
    - Do nothing and skip
- BLACK_RESOURCE_TAKE. Mirrors WHITE_RESOURCE_TAKE
- BLACK_MOVE. Mirrors WHITE_MOVE
- WHITE_STRIKE. Sequence:
    - Choose attacker card and victim card
    - Attack
    - Counter-attack if victim survives
- BLACK_STRIKE. Mirrors WHITE_STRIKE

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

class State(Enum):
    WHITE_RESOURCE_TAKE = 0
    WHITE_MOVE = 1
    BLACK_RESOURCE_TAKE = 2
    BLACK_MOVE = 3
    WHITE_STRIKE = 4
    BLACK_STRIKE = 5
    GAME_OVER = 6

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

Потом пишем класс игры, которая по сути целиком является стейт-машиной. Без разного отвлекающего шума это выглядит как-то так:

class AlphaGame(GameBase):
    state: State

    def launch(self):
        self.state = State.WHITE_RESOURCE_TAKE
        super().launch()

    def update(self) -> bool: # false - game ended
        match self.state:
            case State.WHITE_RESOURCE_TAKE:
                self.white_resource_take()
            case State.WHITE_MOVE:
                self.white_move()
            case State.BLACK_RESOURCE_TAKE:
                self.black_resource_take()
            case State.BLACK_MOVE:
                self.black_move()
            case State.WHITE_STRIKE:
                self.white_strike()
            case State.BLACK_STRIKE:
                self.black_strike()
            case State.GAME_OVER:
                return False
            
        return True

А в базовом классе располагается крутилка сией стейт-машины:

class GameBase:
    def launch(self):
        while self.update():
            pass

Если вышли из цикла, значит игра завершилась. Собственно и все, остается только по-отдельности реализовать все эти self.white_resource_take(), self.white_move(), self.black_strike() и т.п., и ваша игра готова! В этих методах и содержится сам геймплейный код: ходы ботов-игроков, смена состояний стейт машины.

Чтобы было показательнее, давайте рассмотрим один такой метод: white_strike():

def white_strike(self):
	(attacker_slot, victim_slot) = self.white_player.strike()

	self._cards_combat(attacker_slot, victim_slot, Side.WHITE)
	self.change_state(State.BLACK_STRIKE)

Здесь мы как раз видим все виды действий:

• Вызов логики бота в self.white_player.strike()

• Геймплейные расчеты игры в _cards_combat

• Смена состояния игры в self.change_state(State.BLACK_STRIKE)

Т.к. боты-игроки у нас могут быть разного типа, метод self.white_player.strike() будет выполнять разный код в зависимости от типа бота. Например, мой AlphaIdiotPlayer реализует этот метод так:

def strike(self) -> tuple[int, int]: # (attacker_slot, victim_slot)
	attacker_slot = self.table.slots.get_random_slot(self.side, SlotStatus.OCCUPIED)
	victim_slot = self.table.slots.get_random_slot(self.side.get_opposite(), SlotStatus.OCCUPIED)

	return (attacker_slot, victim_slot)

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

Метрики

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

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

• Честная игра — это когда на длинной дистанции шансы выигрыша двух равносильных игроков сводятся к 50/50

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

• Если игра часто приводит к какой-то патовой ситуации или невозможности доиграть — это прям плохо, и так не надо

На этом мои идеи исчерпались, поэтому я решил, что набор моих метрик будет состоять из этих трех параметров, которые я облачил в цифры:

class GameOverResult(Enum):
    NONE = 0
    WHITE_WINS = 1
    BLACK_WINS = 2
    DRAW = 3
    INIFNITY = 4

@dataclass
class Metrics:
    rounds: int = 0
    result: GameOverResult = GameOverResult.NONE
    exausted: bool = False

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

Напомню, как выглядит запуск игры в коде:

class GameBase:
    def launch(self):
        while self.update():
            pass

То есть достаточно запустить game.launch(), и игра будет сыграна. В нужных местах в коде будет несложно расставить врезки, которые предназначены для подсчета наших метрик. Эту задачу мы оставим за рамками статьи, ведь посчитать количество пройденных раундов и зафиксировать результат игры — тривиальные действия. Что важно для нас — одна пройденная игра выдает нам один объект с метриками Metrics.

Массово играем в игру

Чтобы честно провести замеры игры с конкретными правилами и параметрами, я буду заставлять ботов играть в одну и ту же игру раз за разом. Скажем, 1000 одинаковых игр должна вырисовать вполне себе стабильную статистическую картину. По итогу проведения 1000 игр, мы получим 1000 объектов Metrics. Что с ними делать, я поначалу не совсем понимал. Поэтому поначалу решил просто собирать эти объекты в отдельную SoA-структуру:

@dataclass
class BunchMetrics:
    rounds: list[int] = field(default_factory=list[int])
    results: list[GameOverResult] = field(default_factory=list[GameOverResult])
    exausted: list[bool] = field(default_factory=list[bool])
    
    def add_metrics(self, metric: Metrics):
        self.rounds.append(metric.rounds)
        self.results.append(metric.result)
        self.exausted.append(metric.exausted)

Крутилка нашей игры — достаточно простой и лаконичный класс, просто приведу его базовое исполнение:

class GameRepeater:
    game: GameBase
    bunch_metrics: BunchMetrics
    execute_count: int

    def launch(self):
        for _ in range(self.execute_count):
            self.game.launch()
            self.bunch_metrics.add_metrics(self.game.get_metrics())
            self.game.reset()

Просто гоняем одну и ту же игру (внутри которой прописаны одни и те же боты) и собираем метрики.

Диаграммно это можно выразить так:

Позже вы поймете, зачем мне эта незамысловатая эта диаграмма.

Как усредниться

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

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

Итак, мы имеем BunchMetrics. Как превратить его в Metrics?

Первая очевидная мысль — тотально усреднить и получить один объект Metrics. Но этот подход сразу заходит в тупик. Посмотри на метрики снова:

@dataclass
class Metrics:
    rounds: int = 0
    result: GameOverResult = GameOverResult.NONE
    exausted: bool = False

Количество раундов усредняемо, но вот усреднить bool можно лишь очень условно. С GameOverResult же и вовсе беда. Как можно усреднить enum? Более того, даже если взять самый простой случай — количество раундов — если мы просто возьмем все значения и усредним, получив одно единственное число, мы потеряем нехилый пласт информации. Смотрите:

• Что если лучше смотреть не на среднее, а на медиану?

• Что если медиана сильно разнится со средним? Может быть это тоже может что-то подсказать?

• Что если две игры из тысячи вылились в 200+ раундов?

• Что если десять игр из тысячи сыгрались в один раунд?

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

@dataclass
class DataRange:
    min: float = 0.0
    max: float = 0.0
    average: float = 0.0
    median: float = 0.0

И это выглядит как движение в верном направлении:

• Данные из BunchMetrics легко превратить в DataRange для каждой из метрик

• DataRange предоставляют нам широкий простор для анализа происходящего

Есть, правда, одна проблема: есть поле, которое не вписывается в концепцию DataRange:

results: list[GameOverResult] = field(default_factory=list[GameOverResult])

Проблема: когда я буду диктовать идеальные метрики, я хочу сказать что-то в духе:

Мое желаемое идеальное распределение результатов игры следующее: белый игрок выигрывает с вероятностью в 49.75%, черный игрок выигрывает с вероятностью в 49.75%, ничья — 0.5%, остальные исходы – 0%

DataRange никак не подходит, нужно что-то другое. Хорошо, что когда проговариваешь идею словами, она часто ложится на код почти “как есть”, поэтому довольно быстро я родил то, что описал выше:

@dataclass
class ProbabilityTable:
    table: dict[int, float] = field(default_factory=dict[int, float]) # key -> probability proportion
    
    def inc_value(self, key: int, value: float):
        if key not in self.table:
            self.table[key] = 0.0
        self.table[key] += value

    def normalize(self):
        sum = 0.0
        for val in self.table.values():
            sum += val
        
        for key in self.table:
            self.table[key] /= sum
        self.normalized = True

    def get_probability(self, key: int) -> float:
        if not self.normalized:
            self.normalize()
        
        return self.table[key]

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

Теперь мы в состоянии ввести новую убер-сущность. Знакомьтесь — AveragedMetrics:

@dataclass
class AveragedMetrics:
    rounds: DataRange = field(default_factory=DataRange)
    result: ProbabilityTable = field(default_factory=ProbabilityTable) # [GameOverResult -> float]
    exausted: DataRange = field(default_factory=DataRange)

А класс BunchMetrics обзавелся новым методом, который умеет порождать усредненные данные:

@dataclass
class BunchMetrics:
	...    
    def get_average(self) -> 'AveragedMetrics':
        res = AveragedMetrics()

        res.rounds = DataRange.MakeFromList(self.rounds)
        res.result = ProbabilityTable.MakeFromList(self.results)
        res.exausted = DataRange.MakeFromList(self.exausted)

        return res

Методы DataRange.MakeFromList и ProbabilityTable.MakeFromList не представляют из себя никакого ракетостроения, поэтому их реализацию мы опустим.

Ну и после всех этих махинаций с данными я пришел к еще одному правильному выводу: идеальные метрики так же стоит представлять в виде класса AveragedMetrics. Например:

ideal_metrics = AveragedMetrics(
	rounds = DataRange(min=5, max=15, average=10, median=10),
	result = ProbabilityTable(
		table = {
			GameOverResult.BLACK_WINS: 0.4975,
			GameOverResult.WHITE_WINS: 0.4975,
			GameOverResult.DRAW: 0.005,
		},
	),
	exausted = DataRange(min=0, max=0, average=0, median=0),
)

Какие выгоды:

• Во-первых только так вы и сможете нормально описать, что вы хотите от вероятностей исходов игры — через таблицу вероятностей. Через класс Metrics такие данные выразить просто невозможно

• Вы можете задавать не только идеальное среднее или медианное значение, но и желаемое минимальное и максимальное, что так же дает простор для более гранулярной настройки

Что дальше

А что дальше, вы узнаете в следующей статье! Нда, вот так вот. Что вы узнаете в следующем выпуске:

• Мы будем комбинаторно перебирать правила игры и выбивать метрики

• Мы научимся сравнивать две AveragedMetrics. Да, если вы призадумаетесь, то это ни разу не просто. Почему? А подумайте, как сравнить две почти похожие метрики AveragedMetrics и как выразить результат такого сравнения

• По метрикам определим ту самую игру с идеальными параметрами

• Построим бесконечный майнер лучших правил игры из лучших через генерацию и подмену части python-кода (шок-контент)

• Наконец-то сделаем игру, которая будет не дисбалансной