Magic: The Gathering is Turing Complete
2019 Alex Churchill, Stella Biderman, Austin Herrick
[arxiv]

Этой работе уже несколько лет, но её последствия до сих пор недооценивают. Доказали, что настольная карточная игра Magic: The Gathering (MTG) — Тьюринг-полная! На ней можно реализовать любой алгоритм!

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

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

Как заставили карты считать?

Суть Тьюринг-полноты MTG в том, что её правила могут выразить колоду, в которой закодированы состояния машины Тьюринга, и которая будет исполнять алгоритмы автоматически, без участия игроков, только лишь следуя правилам карточек. Мы выбираем и раскладываем колоду на первом ходу, после чего она сама проводит игру и параллельно выполняет вычисления.

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

Во-вторых, вся автоматика построена на триггерах карт, а символы на ленте закодированы через тип фишки-существа (например, Aetherborn или Sliver). За перезапись отвечает карта, которая говорит: «Когда умирает Aetherborn, создайте Sliver». Это шаг машины Тьюринга.

Чтобы реализовать ветвление (состояния), используют карту Cloak of Invisibility, которая временно скрывает карту-триггер со стола и делает неактивными.

Завершение — это победа, которая запускается триггером на синюю фишку, которой никогда нет на столе, но при её появлении активируется Coalition Victory.

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

Вот где будет настоящий фронтир для ИИ.

А самое главное знаете что? На MTG можно запустить DOOM 😄