Ученые определили самую сложную игру

Оказалось, что существование алгоритма, который вычисляет, победит ли данный игрок, эквивалентно проблеме остановки — классической задаче теории алгоритмов, неразрешимость которой доказал Алан Тьюринг в 1936 году

Ученые определили самую сложную игру

Исследователи доказали, что настольная карточная игра 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 не соответствует гипотезам, обычно принимаемым при моделировании игр на компьютерах.

Источник: N+1

Подписывайтесь на канал «Хвилі» в Telegram, на канал «Хвилі» вYoutube, страницу «Хвилі» в Facebook

Последние новости
Зеленский планирует вернуть диктаторские полномочия генпрокурору, — Луценко

Зеленский планирует вернуть диктаторские полномочия генпрокурору, — Луценко

Преемник хочет назначать замов и местных прокуроров сам
Путин сравнил протесты в Москве с «желтыми жилетами»

Путин сравнил протесты в Москве с «желтыми жилетами»

Путин назвал события в Москве «беспорядками» и напомнил о протестах «желтых жилетов» во Франции, во время которых погибли несколько человек
Луценко рассказал, что судей ОАСК прослушивали 7 месяцев

Луценко рассказал, что судей ОАСК прослушивали 7 месяцев

Это только "черная метка" судьям и политикам
Джонсон верит, что Евросоюз пойдет на компромисс по Brexit

Джонсон верит, что Евросоюз пойдет на компромисс по Brexit

По словам Джонсона, в ЕС видели, что парламент Великобритании три раза отклонял соглашение о выходе Великобритании из ЕС,
Tesla Roadster произвел первый полет вокруг Солнца

Tesla Roadster произвел первый полет вокруг Солнца

7 октября 2020 года спорткар пролетит относительно близко к Марсу - на расстоянии всего 7,5 млн км
Стало известно, кто может стать новым главой «Укроборонпрома»

Стало известно, кто может стать новым главой «Укроборонпрома»

Тимофеев является экс-СЕО "Смарт Холдинга" Вадима Новинского, был топ-менеджером компании "Гео Альянс" Виктора Пинчука и государственной "Укргаздобычи", входил в состав правления НАК "Нафтогаз Украины"
Гройсман рассказал, на сколько повысят зарплаты педагогам

Гройсман рассказал, на сколько повысят зарплаты педагогам

Зарплата педагогов в 2020 году повысится от 20 до 70%
Вовк рассказал, почему не возвращается в Украину

Вовк рассказал, почему не возвращается в Украину

Экс-глава НКРЭКУ добавил, что пять месяцев учился в Harvard Business School по программе GMP26
В Киеве «заминировали» Центральный вокзал и автостанцию

В Киеве «заминировали» Центральный вокзал и автостанцию

Сейчас проверяют все железнодорожные вокзалы Киева на наличие подозрительных и опасных предметов
93% акций «Укртелекома» арестовали

93% акций «Укртелекома» арестовали

Банк требует погашения 1,8 млрд гривен долга.
Украина и Израиль хотят распространить ЗСТ и на сферу услуг

Украина и Израиль хотят распространить ЗСТ и на сферу услуг

Украина привлечет опыт Израиля во внедрении инноваций, поддержке стартапов и реализации научно-исследовательских разработок.
Стрижевскую прослушивали по делу Грымчака, — СМИ

Стрижевскую прослушивали по делу Грымчака, — СМИ

Прослушивающее устройство в кабинете Стрижевской было обнаружено на потолке.
Под Киевом в ДТП погиб сотрудник полиции и 7-летняя девочка

Под Киевом в ДТП погиб сотрудник полиции и 7-летняя девочка

Водитель Audi не пострадала.
В Сирии по турецкому конвою нанесли авиаудар, — AP

В Сирии по турецкому конвою нанесли авиаудар, — AP

Анкара «решительно осудила»
Владельцу сгоревшего в Одессе отеля сообщили о подозрении

Владельцу сгоревшего в Одессе отеля сообщили о подозрении

Решается вопрос об избрании меры пресечения подозреваемому
В кабинете зама Луценко нашли прослушку

В кабинете зама Луценко нашли прослушку

СБУ зарегистрировано уголовное производство.
Разумков назвал недостаточой депутатскую зарплату

Разумков назвал недостаточой депутатскую зарплату

Он не готов ответить, какую зарплату считает достойной для нардепа.
Укртелеком продадут с аукциона за долги перед Ощадбанком

Укртелеком продадут с аукциона за долги перед Ощадбанком

Акции Укртелекома арестовали за долг в 1,8 млрд грн
Украинцев больше не будут задерживать на границе Израиля — Зеленский

Украинцев больше не будут задерживать на границе Израиля — Зеленский

Граждане Украины смогут свободно въезжать в Израиль.
В Йемене нашли мумии возрастом около трех тысяч лет

В Йемене нашли мумии возрастом около трех тысяч лет

Мумии обнаружили в окрестностях Саны.
Украинские банки снижают ставки по валютным депозитам

Украинские банки снижают ставки по валютным депозитам

Средняя ставка снизилась для вкладов сроком свыше года (на 0,83 п.п. до 13,87% годовых).
Нетаньяху анонсировал открытие IT-центров в Киеве и Иерусалиме

Нетаньяху анонсировал открытие IT-центров в Киеве и Иерусалиме

Израильские компании сотрудничают с около 50 тыс. украинских компьютерных инженеров.
Испания: Ryanair и профсоюзы попытаются предотвратить забастовку в сентябре

Испания: Ryanair и профсоюзы попытаются предотвратить забастовку в сентябре

Члены экипажей запланировали провести забастовку 1, 2, 6, 8, 13, 15, 20, 22, 27 и 28 сентября, если Ryanair не пойдет на уступки.
Адвокат Грымчака заявила о новых обстоятельствах в деле

Адвокат Грымчака заявила о новых обстоятельствах в деле

Матяш заявила, что при рассмотрении апелляций на решение Деснянского райсуда Чернигова сторона защиты в суде откроет новые обстоятельства.
«Слуга народа» извинилась перед журналисткой за оскорбление

«Слуга народа» извинилась перед журналисткой за оскорбление

Партия «Слуга народа» считает недопустимыми личные оскорбления граждан Украины.
Опознаны тела шестерых погибших в отеле «Токио Стар»: среди них есть гражданка Австралии

Опознаны тела шестерых погибших в отеле «Токио Стар»: среди них…

В "Токио Стар" погибли пять украинцев и гражданка Австралии.
Компания Lamborghini представила два новых суперкара

Компания Lamborghini представила два новых суперкара

Lamborghini выпустит две новые эксклюзивные версии своих суперкаров — Aventador SVJ 63 и Huracan Evo GT.
Зеленский призвал Израиль признать Голодомор актом геноцида украинского народа

Зеленский призвал Израиль признать Голодомор актом геноцида украинского народа

Зеленский обратился к израильской стороне с призывом признать Голодомор актом геноцида украинского народа.
«Космический интернет»: стартап обогнал проекты Маска и Безоса

«Космический интернет»: стартап обогнал проекты Маска и Безоса

OneWeb пока что вывел на орбиту только шесть спутников, но гигантам придется с ними считаться.
В Украине резко упали цены на морковь

В Украине резко упали цены на морковь

Цены на морковь упали благодаря увеличению предложения ранних и средних сортов на рынке.
Читай также
Последние новости

Зеленский планирует вернуть диктаторские полномочия генпрокурору, — Луценко

Путин сравнил протесты в Москве с «желтыми жилетами»

Луценко рассказал, что судей ОАСК прослушивали 7 месяцев

Джонсон верит, что Евросоюз пойдет на компромисс по…

Tesla Roadster произвел первый полет вокруг Солнца

Стало известно, кто может стать новым главой «Укроборонпрома»

Гройсман рассказал, на сколько повысят зарплаты педагогам

Вовк рассказал, почему не возвращается в Украину

В Киеве «заминировали» Центральный вокзал и автостанцию

93% акций «Укртелекома» арестовали

Украина и Израиль хотят распространить ЗСТ и на…

Стрижевскую прослушивали по делу Грымчака, — СМИ

Под Киевом в ДТП погиб сотрудник полиции и…

В Сирии по турецкому конвою нанесли авиаудар, -…

Владельцу сгоревшего в Одессе отеля сообщили о подозрении