Magic: The Gathering — это карточная игра, в которой волшебники кастуют заклинания, призывают существ и используют магические объекты, чтобы победить своих противников. В процессе игры два или более игроков собирают по колоде из 60 карт с различными силами. Колоды собираются из пула более 20 000 карт, созданных по мере развития игры. Хотя Magic: The Gathering похожа на ролевые фэнтэзийные игры вроде Dungeons and Dragons, в ней гораздо больше карт и более сложные правила, чем у других карточных игр.

Что приводит к интересному вопросу: насколько сложная MTG, если сравнивать ее с другими реальными играми (то есть теми, в которые люди на самом деле играют, а не какими-нибудь теоретическими)? Сразу оговорюсь, под сложностью здесь подразумевается не сложность понимания игрового процесса, а сложность как глубина и многогранность игры.

Насколько сложная Magic: The Gathering? Сложнее не бывает

Ответ дала работа Алекса Черчилля, независимого исследователя и дизайнера настольных игр из Кембриджа, Великобритания, Стеллы Бидерман из Технологического института Джорджии и Остина Херрика из Университета Пенсильвании.

Его команда измерила вычислительную сложность игры, закодировав ее так, чтобы ее можно было воспроизвести на компьютере или машине Тьюринга. «Эта конструкция установила, что Magic: The Gathering — самая вычислительно сложная игра реального мира, известная в литературе», заявили ученые.

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

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

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

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

В данном случае решение о том, являются ли два числа относительно простыми, может быть найдено за несколько шагов, которые пропорциональны полиномиальной функции входных чисел. Если входное значение равно x, самый важный член полиномиальной функции будет в форме Cx^n, где C и n — константы. Это относится к классу P, что означает полиномиальное время.

Напротив, шахматная задача должна решаться методом грубой силы, и количество необходимых шагов увеличивается пропорционально экспоненциальной функции входных данных. Если вводом будет x, самый важный член экспоненциальной функции имеет вид Cn^x, где C и n — константы. Здесь мы имеем дело с категорией большей сложности EXP, или экспоненциального времени.

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

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

Таким образом, лишь несколько реальных игр имеют нетривиальную сложность. Сюда входят «Палочки» (или «Точки и квадраты»), дженга и тетрис.

Работа ученых показала, что Magic: the Gathering намного более сложная, чем эти три. Метод подсчета, в принципе, прост. Черчилль и его компания начали с преобразования сил и свойств каждой карты в набор шагов, которые можно закодировать.

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

Это проблема определения того, закончит ли компьютерная программа с определенным вводом работу или будет работать вечно. В 1936 году Алан Тьюринг доказал, что ни один алгоритм не сможет определить ответ. Иными словами, эта задача невычислима.

Поэтому результат Черчилля показывает, что определение исхода в игре Magic: the Gathering не поддается расчету. «Это первый результат, который показывает, что существует реальная игра, для которой определение выигрышной стратегии не поддается вычислению», говорят ученые. Это интересная работа, которая поднимает важные фундаментальные вопросы теории игр. К примеру, Черчилль и соавторы говорят, что ведущая формальная теория игр предполагает, что любая игра должна быть вычислимой. Magic: the Gathering не соответствует предположениям, которые обычно делают компьютерные ученые при моделировании игр.