Наука, наконец, смогла определить, какая из игр является самой сложной в мире. И нет, это не Го, не Sekiro и даже не Battletoads на Nintendo — ученые копнули в саму суть игровых алгоритмов и выяснили, что первое место за игрой Magic: The Gathering.

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

С помощью машины имени себя Алан Тьюринг доказал, что невозможно составить алгоритм, который точно предскажет, остановится ли эта машина в вычислениях заложенной в нее информации или нет. Так как теоретически она может производить вычисления бесконечно, Тьюринг пришел к выводу, что эта самая «проблема остановки» нерешаема с помощью машинного алгоритма, поскольку сам алгоритм невозможно вычислить. Вот так все просто.
Но это абстракция, но что насчет реальных алгоритмов — к примеру, в играх? Оказывается, что огромное количество игр имеют с точки зрения математики довольно высокую сложность: «Точки», «Тетрис» и «Дженга» имеют одни из самых высоких показателей.
И вот, наконец, ученые добрались и до Magic: The Gathering — авторы исследования посчитали ее самой интересной с точки зрения анализа из-за огромного количества карт (всего более 20 000) и различных стратегий. Составленная из карт и правил для двух игроков схема была реализована в универсальной машине Тьюринга и выдала эквивалент той самой «проблемы остановки». Черчилль, Бидерман и Херрик таким образом впервые показали реальную игру, в которой невозможно вычислить выигрышную стратегию из-за принципиальной невычисляемости самого алгоритма — все по науке.
Для теории игр вывод аналитиков тоже может быть небезынтересным, поскольку в рамках этой дисциплины существует точка зрения, что нет такой игры, результат которой не может быть теоретически вычислен.
Попахивает булщитом.
1 играют не все 20к карт, а условно констрактед или экстендендент.
2 в самой партии карт в целом сильно меньше, две колоды по 60 карт.
3 в самой партии ветвление выбора карт меньше чем хода в ГО. Основная сложность будет на выборе цели карты. Но и тут задача куда проще чем управление персонажами в доте.
А предсказать плохо получается не из-за сложности, а из-за рандома. И к слову обычный предикт на ML вообще о правилах игр ничего не знает. Ты прогоняешь терабайты данных через нейронку, обучаешь её. Вида вот играли этим, против этого, результат такой-то.
1. Зависит от формата в коммандере будут играть гораздо больше сетов
2. В самой партии мы не знаем с какими именно 60 картами придёт к нам оппонент
1 и 2 сути не меняет. Сам посыл статьи не имеет смысла. Если на это смотреть как на мат задачу. Го и шахматы у нас игры с конечным кол-вом вариантов, детерминированные и с полной информацией. BattleToads на таймингах и можно написать бота который иедально проходит. В Секрио есть рандом, но постуи тоже есть идеальное прохождение, когда рандом тебе выпадет идеально.
И вот решают рассматривать игру с рандомом, пвп и с неполной информацией. В сущности сколько там карт или правил, мало влияет на результат. Можно взять доту или старик и получить теже проблемы с куда большими числами.
Ну и если уж на то пошло то кол-во вариантов конечное. МТГ пошаговая. Дота и старик тиковые системы.
Вообще, это обычная комбинаторная NP-полная задача. Конечно, ее можно решить, но только методом перебора, что займет очень много времени. В статье почему-то говориться о принципиальной неразрешимости, что в корне неверно и вводит читателя в заблуждение.
…optimal play in real-world Magic is at least as hard as the Halting Problem…
Да, там речь про поиск оптимального алгоритма. Количество карт ограничено, следовательно, порядок возможных ходов тоже ограничен. Это нп-сложная задача. Как любая карточная игра, только в этой вместо 36 карт 20к
В статье прямым текстом сказано, что это неразрешимая задача. NP-complete задача = не существует полиномиального алгоритма. Неразрешимая задача = не существует алгоритма, который бы гарантированно останавливался на любых вводных данных (по определению это уже и не алгоритм).
Насчёт конечности ходов:
Не уверен, что вы в том положении, чтобы ставить под сомнение статью, написанную под руководством исследователя из Кэмбриджа ;)
Я не спорю с профессором. В оригинальной статье говорится про то, что не удается оценить сложность алгоритма, предсказывающего победителя в конкретной партии (довольно бредовая постановка задачи, потому что игрок может принять неоптимальное решение). Я же написал, что количество возможных партий конечно, потому что количество карт не бесконечно.
С формулировками небольшая проблема, соглашусь. В статье вычисление победителя это то же самое, что и вычисление оптимальной стратегии в партии. Смысл как раз в том, что в MTG нельзя тупо перебрать (np алгоритм, о котром была речь) все возможные ситуации, как во многих других играх. Такой перебор может затянуться до бесконечности.
Бесполезный комент, т.к. в статье не говорится в каких форматах проводили исследования, да и тут все дело в алгоритме, а не в том-что вы считаете или или не считаете.
Сам посыл статьи не имеет смысла. Если на это смотреть как на мат задачу. Го и шахматы у нас игры с конечным кол-вом вариантов, детерминированные и с полной информацией. BattleToads на таймингах и можно написать бота который иедально проходит. В Секрио есть рандом, но постуи тоже есть идеальное прохождение, когда рандом тебе выпадет идеально.
И вот решают рассматривать игру с рандомом, пвп и с неполной информацией. В сущности сколько там карт или правил, мало влияет на результат. Можно взять доту или старик и получить теже проблемы с куда большими числами.
Ну и если уж на то пошло то кол-во вариантов конечное. МТГ пошаговая. Дота и старик тиковые системы.
Хоть бы в оригинальную статью заглянули. Лишь бы авторитетно спиздануть про «нейронки» (хотя ML это гораздо больше, чем они). И машинным обучением тут и не пахнет.
Оригинальная статья о том, что не может существовать детерминистического алгоритма (какого-то чёткого набора инструкций), который бы мог точно сказать, кто выиграет партию. С помощью ML как раз таки было бы возможно построить модель, которая с какой-то неидеальной точностью могла бы предсказать исход.
О каком точно может идти речь, когда игра с неполной информацией и с рандомом? И о какой сложности может идти речь, когда в любой реалтайм игре будет большее кол-во вариантов действийвыборов.
Всё-таки речь идёт о теоретических, абстрактных результатах. Как правило, в любой игре с чёткими правилами, даже с неполной информацией и рандомом, можно (в теории, в реальности мощностей не хватит) перебрать все возможные варианты развития событий и найти оптимальный ход. В статье же доказано, что в MTG этого нельзя сделать даже в теории, обладая бесконечными вычислительными ресурсами.
Учёные в курсе про существование Манчкина?
пофиг на статью….я тут с выхода арены сидел спакойно себе играл своей собственной колодой никого не трогал, и тк я вхож с тусу задротов-настольщиков по 40к, что не далеко от задротов мтг, то я попал на пререлиз нового сета, после него, решил, а давайте, я куплю себе физическую версию своей моноредколоды из аренки??))
Зашел на сайт…прикинул что 75 карт обойдутся мне в ~12к…..подобрал челюсть от того, что там нету файловых, редких и уникальных карт при этом…и решил ну нафиг такое)))
Похоже на статью об типичном открытии «британских учёных». И при чём тут game over на заглавной картинке к статье?
Мы-то знаем, что дотка самая сложная игра…