Движок Arcana для Magic: The Gathering споткнулся об эмблему Лилианы: шаг в 35 секунд

Автор эссе давно увлечён Magic: The Gathering как математическим и вычислительным пространством. Он называет игру очень сложной, даже полной по Тьюрингу, и перечисляет претензии к существующим реализациям. У Arena, по его словам, каталог карт заведомо неполон (нет карт из большей части истории игры), подбор соперников в рейтинговой игре ужасен, а производительность низкая, особенно когда на стеке много эффектов. У MTGO каталог полный, но интерфейс устарел и неудобен. Forge, независимая реализация, на первый взгляд многообещающа, но игра ИИ там слабая, мультиплеер глючный, интерфейс неинтуитивный, а скорость всё ещё не идеальна.

Теоретизировать о том, как улучшить игру ИИ в Magic, автор начал уже в 2024 году, а за реализацию взялся только в середине 2026-го. Сначала он оценил Forge и решил, что довести его до производительности, достаточной для среды экспериментов с обучением с подкреплением (RL), нереально. Поэтому он написал собственный движок правил Arcana, сразу заложив поддержку мультиплеера.

Главная проблема для любой реализации Magic, по мысли автора, в способностях карт: они могут нарастать экспоненциально, и число проверок, нужных, чтобы убедиться, что побочных эффектов больше не осталось, тоже растёт экспоненциально. Автор вспоминает, что это экспоненциальное поведение «укусило» его неожиданным образом.

Предыстория: одна из любимых колод автора построена на Scute Swarm, карте, которая при выходе новой земли удваивает число своих копий. На практике соперник обычно останавливает рост рано. Но если добавить карты, дающие жизнь за каждое новое существо, артефакт, удваивающий создаваемые жетоны, и эффект, удваивающий получаемую жизнь, получится экспоненциально растущий запас жизни. Стартовое значение у игрока в Magic равно 20, а самый высокий запас жизни, которого автор достигал в партиях на бумажных картах с другими колодами, около 150. Автор приводит расчёт для одного Scute, двух карт Soul Warden и Essence Warden, одного удвоителя жетонов и одного удвоителя жизни, при шести и более землях: после восьми выкладываний земель получается 6 561 Scute и 26 240 набранной жизни. Порог в шесть земель нужен потому, что при меньшем числе земель Scute создаёт обычного насекомого 1/1, а при шести и более копию с той же способностью. Arcana Scute Swarm пока сознательно не поддерживает, так что проблемы создала другая карта.

Это Лилиана, Последняя Надежда (Liliana, the Last Hope). Её «ультимейт» (самая дорогая способность) создаёт эмблему, которая остаётся в игре, даже если планесвокера убрали. В конце каждого вашего хода эмблема срабатывает: при разрешении она считает подконтрольных вам зомби и создаёт столько же новых плюс ещё двух. Если на поле шесть зомби, появятся восемь новых, всего станет четырнадцать. Если стартовать без зомби при одной эмблеме и ничего больше не менять, после восьми срабатываний получится 510 зомби. В отличие от Scute Swarm, убрать зомби недостаточно: эмблема остаётся и следующим же срабатыванием создаёт армию заново (минимум двух новых зомби).

Arcana реализует это правило в лоб: считает зомби, вычисляет x = 2 + число зомби и в цикле порождает отдельный эффект CreateToken для каждого нового жетона. Затем движок обрабатывает все появления, включая проверки правил и срабатывающие от них способности, так что работа растёт вместе с армией.

Столкнулся автор с этим при тестировании. Чтобы решить, какие пробелы в правилах Arcana чинить дальше, он взял 64 колоды формата Pioneer и список из 37 карт с известными проблемами. Колоды образуют 2 016 различных пар; каждую пару сыграли дважды (каждая колода по разу ходила первой), всего 4 032 партии. По принципу, похожему на фаззинг, весь этот набор запланировали ещё 100 раз с разными случайными зёрнами (seed), причём оба игрока выбирали действия случайно, чтобы поймать панику, падение или зависание движка. Все примерно 400 000 партий независимы, поэтому автор гоняет их на кластере. Но в этот раз девять заданий упёрлись в двухчасовой лимит. Случайное зерно и две колоды позволили воспроизвести зависшую партию на ноутбуке и замерить отдельные шаги.

В этой партии один из игроков активировал ультимейт Лилианы на 34-м ходу. Когда армия выросла до тысяч зомби, одно срабатывание эмблемы заняло на ноутбуке автора 35 секунд, и это был один шаг движка. Оба игрока уже дали способности разрешиться; перед следующим решением Arcana должна была выставить на поле каждого нового зомби и проверить, что вызвало его появление. Автор начинает разбирать первую такую проверку, способность evolve (эволюция): движку нужно найти все существа игрока, у которых она есть и которым новый зомби с большей силой или выносливостью даёт право на +1/+1. Для этого код обходит весь список объектов на поле. Видимый текст обрывается на середине этого объяснения, поэтому итоговая причина задержки и способ исправления в доступной части не показаны.

Ключевые факты

  • Автор пишет собственный движок правил Magic: The Gathering под названием Arcana: Forge он счёл негодным по производительности как среду экспериментов с RL; к реализации автор приступил в середине 2026 года.
  • Тестовый прогон: 64 колоды Pioneer, 2 016 пар, 4 032 партии, повторённые ещё 100 раз со случайными зёрнами, около 400 000 независимых партий со случайными действиями игроков на кластере.
  • Девять заданий упёрлись в двухчасовой лимит; в воспроизведённой партии при тысячах зомби одно срабатывание эмблемы Лилианы, Последней Надежды заняло 35 секунд на ноутбуке автора.
  • Эмблема создаёт новых зомби по числу имеющихся плюс два; при старте с нуля это 510 зомби после восьми срабатываний, и армия отстраивается заново, даже если всех убрать.
  • Расчёт для Scute Swarm в авторских допущениях даёт после восьми выкладываний земель 6 561 Scute и 26 240 жизни; Arcana эту карту пока сознательно не поддерживает.

Почему это важно

История хорошо показывает, где автоматическая проверка правил сложной карточной игры упирается в вычислительные пределы: способности, которые порождают друг друга, дают экспоненциальный рост работы. Одно срабатывание в 35 секунд на единственном шаге движка делает такой движок непригодным для массовых экспериментов, где нужны сотни тысяч партий. Автор строит Arcana именно как среду для RL на Magic, поэтому производительность для него условие работы, а не придирка.

Кому это важно

Разработчикам игровых движков и симуляторов правил, исследователям обучения с подкреплением, которым нужна быстрая среда для настольных или карточных игр, а также игрокам в Magic, которым интересна вычислительная сторона игры и причины, по которым Arena, MTGO и Forge ведут себя так, как ведут.

Как это применить

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

Можно ли доверять

Это личное эссе независимого разработчика о собственном проекте: оценки Arena, MTGO и Forge и описание результатов Arcana даны со слов автора и качественно, без замеров производительности этих программ. Цифры по Scute Swarm и Лилиане приведены при заданных допущениях и посчитаны автором, а не получены в реальных партиях. Видимый текст обрывается на середине объяснения, поэтому причина 35-секундного шага и выводы автора здесь не видны.

Риски и подводные камни

Самое важное ограничение: источник обрезан, и в пересказе нет ни окончательного диагноза, ни исправления. Цифра в 35 секунд относится к ноутбуку автора без указания его характеристик, а число зомби названо лишь как «тысячи». Расчёты по Scute Swarm и эмблеме верны только в оговорённых допущениях (в частности, что ничто другое не меняет число жетонов и зомби). Arcana пока не поддерживает Scute Swarm, а у автора есть список из 37 карт с известными проблемами в правилах, так что нынешний движок остаётся неполным.

«Как мы все знаем, экспоненциальное поведение, враг нас, простых смертных специалистов по информатике.»

— автор эссе