Дослідники довели, що настільна карткова гра Magic: The Gathering є найскладнішою грою з усіх проаналізованих ігор, в які грають люди. Виявилося, що існування алгоритму, який обчислює, чи переможе даний гравець, еквівалентно проблемі зупинки - класичній задачі теорії алгоритмів, недозволеність якої довів Алан Тьюрінг в 1936 році. Таким чином, Magic: The Gathering виявляється незвичайно складною грою, пишуть автори в препринті на сайті arXiv.org.
У теоретичній інформатиці для формалізації поняття алгоритму використовується машина Тьюринга - абстрактний обчислювач, який складається з нескінченної стрічки, розбитої на дискретні комірки, і керуючого пристрою, який здатний зчитувати зі стрічки інформацію і записувати її. Пристрій може знаходитися в строго певній кінцевій кількості внутрішніх станів, варіюючи які можна реалізувати різні алгоритми.
За допомогою цієї теоретичної моделі Алан Тьюрінг в 1936 році довів невирішуваність проблеми зупинки, тобто неможливість існування алгоритму, який міг би наперед передбачити, чи зупиниться дана машина Тьюрінга в обчисленнях даної вхідної інформації, або ж буде нескінченно проводити операції, ніколи не приходячи до кінцевої відповіді. Іншими словами, алгоритм машини Тьюринга, що вирішує проблему зупинки, є невичислимим.
Більшість реальних завдань є обчисленими і їх прийнято класифікувати за ступенем ресурсоємності. Найбільш простими є вирішувані за поліноміальний час завдання, які всі разом утворюють безліч P. Для них кількість необхідних кроків машини Тьюрінга для отримання відповіді зростає не швидше nk, де k - константа, а n - кількість займаних вхідними даними комірок на стрічці. Прикладом такого простого завдання є обчислення, чи є два даних натуральних числа взаємно простими, іншими словами, чи є у них загальні ділники крім одиниці.
Прикладом категорії набагато більш складних завдань є EXP, куди входять проблеми, які можна вирішити за експоненціальний час, тобто кількість необхідних операцій зростає не швидше kn, а така функція для досить великих n буде рости набагато швидше, ніж nk незалежно від k. Існує безліч проміжних класів складності алгоритмів, які можуть відрізнятися не тільки витраченим часом, але і простором, тобто кількістю використовуваних для обчислень клітин. Також відомі завдання, для яких алгоритму не існує - такі, як проблема зупинки.
Крім абстрактних математичних обчислень за класами складності можна ранжувати різні ігри, наприклад, шахи, які потрапляють в EXP. При цьому абсолютна більшість вивчених математиками реальних ігор володіє верхньою оцінкою складності і не дотягують до незвичайних завдань, тому більшість досліджень з алгоритмічної теорії ігор в першу чергу розглядали узагальнення стандартних ігор, а не їх існуючі в реальності варіанти. З реальних ігор доведено, що нетривіальною складністю володіють «Точки» («точки і квадрати», «палички»), «Дженга» і «Тетріс».
У роботі незалежного дослідника Алекса Черчілля (Alex Churchill) з Великобританії, а також математиків Стелли Бідерман (Stella Biderman) з Технологічного інституту Джорджії та Остіна Херріка (Austin Herrick) з Пенсільванського університету, представлена математична формалізація гри Magic: The Gathering. Для цього автори за допомогою існуючих карт і правил для двох гравців реалізували універсальну машину Тьюринга, причому визначення переможця в такому випадку еквівалентне проблемі зупинки цієї машини. Це, з одного боку, вперше (за словами авторів роботи) показує приклад реальної гри, в якій визначення виграшної стратегії незвичайне, а з іншого - доводить неможливість у загальному випадку перевірки еквівалентності різних стратегій в даній грі.
Крім інтересу в контексті даної гри, новий результат також може зробити значно вплив на основи теорії ігор, так як переважаюча сьогодні точка зору передбачала, що результат будь-якої гри повинен бути теоретично обчисленим. За словами самих авторів, Magic: The Gathering не відповідає гіпотезам, зазвичай приймаються при моделюванні ігор на комп'ютерах.
Нещодавно ми писали, як рух пішоходів описали за допомогою теорії ігор, а в саму цю математичну концепцію включили рівняння Шредінгера з квантової механіки. Ми робили великий матеріал про Джона Неша, одного з найбільших математиків XX століття, який зіграв визначальну роль у розвитку математичної теорії ігор і загинув у 2015 році. Також ми публікували уривок з книги «Стратегія гри», в якій описується єдина математична формалізація тактики футбольних матчів, важких переговорів, першого побачення і міжнародних конфліктів.