Наука, наконец, смогла определить, какая из игр является самой сложной в мире. И нет, это не Го, не Sekiro и даже не Battletoads на Nintendo — ученые копнули в саму суть игровых алгоритмов и выяснили, что первое место за игрой Magic: The Gathering.
Да, как это ни странно, но самой сложной игрой ученые признали именно эту настольную карточную классику. Следует сразу сказать — естественно, это не самая хардкорная игра с точки зрения геймплея или массивности правил. Аналитики Алекс Черчилль, Стелла Бидерман из Технологического института Джорджии и Остин Херрик из Пенсильванского университета оценивали Magic: The Gathering с другой точки зрения — математической.
Ученые поставили весьма нетривиальную задачу — создать для MTG алгоритм, который сможет точно вычислить, победит ли тот или иной игрок в данной партии или нет. Однако выяснилось, что это практически невозможно, и получился эквивалент «проблемы остановки» — задачи из учебников по теории алгоритмов. Ученые не могут ее решить, но не от лени или скудоумия — еще в 1936 году великий Алан Тьюринг вывел доказательство ее принципиальной неразрешимости, но тут нужно погрузиться в науку.
Машина Тьюринга в теоретической информатике является абстрактным вычислителем, в котором крутится бесконечная лента с прерывистыми (дискретными) ячейками. Есть в машине также некое устройство с конечным числом внутренних состояний, которое считывает данные с ленты и записывает их. Изменяя количество состояний устройства, можно составлять разные алгоритмы.
С помощью машины имени себя Алан Тьюринг доказал, что невозможно составить алгоритм, который точно предскажет, остановится ли эта машина в вычислениях заложенной в нее информации или нет. Так как теоретически она может производить вычисления бесконечно, Тьюринг пришел к выводу, что эта самая «проблема остановки» нерешаема с помощью машинного алгоритма, поскольку сам алгоритм невозможно вычислить. Вот так все просто.
Но это абстракция, но что насчет реальных алгоритмов — к примеру, в играх? Оказывается, что огромное количество игр имеют с точки зрения математики довольно высокую сложность: «Точки», «Тетрис» и «Дженга» имеют одни из самых высоких показателей.
И вот, наконец, ученые добрались и до Magic: The Gathering — авторы исследования посчитали ее самой интересной с точки зрения анализа из-за огромного количества карт (всего более 20 000) и различных стратегий. Составленная из карт и правил для двух игроков схема была реализована в универсальной машине Тьюринга и выдала эквивалент той самой «проблемы остановки». Черчилль, Бидерман и Херрик таким образом впервые показали реальную игру, в которой невозможно вычислить выигрышную стратегию из-за принципиальной невычисляемости самого алгоритма — все по науке.
Для теории игр вывод аналитиков тоже может быть небезынтересным, поскольку в рамках этой дисциплины существует точка зрения, что нет такой игры, результат которой не может быть теоретически вычислен.
