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

Оказалось, что существование алгоритма, который вычисляет, победит ли данный игрок, эквивалентно проблеме остановки — классической задаче теории алгоритмов, неразрешимость которой доказал Алан Тьюринг в 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

Последние новости
Кравчук жёстко осадил Порошенко, Тимошенко и Вакарчука

Кравчук жёстко осадил Порошенко, Тимошенко и Вакарчука

Бывший президент Украины Леонид Кравчук прокомментировал объединение трех народных депутатов
Медики рассказали о неожиданной пользе граната для женщин

Медики рассказали о неожиданной пользе граната для женщин

Помогает укрепить кости, мягко пережить менопаузу и прочистить сосуды
Кулеба оценил возможности Зеленского в Париже

Кулеба оценил возможности Зеленского в Париже

Государственный деятель считает, что именно сейчас нужно поддержать Владимира Зеленского
Пожар в Одессе: правоохранители установили двух подозреваемых

Пожар в Одессе: правоохранители установили двух подозреваемых

В досудебном расследовании было опрошено более 150 человек
У Зеленского отмечают, что минские соглашение нужно уточнить

У Зеленского отмечают, что минские соглашение нужно уточнить

Помощник Владимира Зеленского Андрей Ермак прокомментировал ожидания от "нормандского саммита"
Гончарук анонсировал «промышленный безвиз» с ЕС

Гончарук анонсировал «промышленный безвиз» с ЕС

Гончарук рассказал, когда состоится обновление Соглашения об ассоциации Украины и ЕС
Зеленский огласил всеукраинский траур 8 декабря

Зеленский огласил всеукраинский траур 8 декабря

День траура объявлен с целью чествования жертв страшного пожара в Одессе
Замкомандира полка Путина нашли повешенным

Замкомандира полка Путина нашли повешенным

Военного нашли в его квартире мертвым
Бюджетный камерофон Samsung Galaxy A51 показали на фото

Бюджетный камерофон Samsung Galaxy A51 показали на фото

Презентация Galaxy A51 пройдет во Вьетнаме
Кравчук жестко прошелся по «майданным» призывам Парубия

Кравчук жестко прошелся по «майданным» призывам Парубия

Кравчук считает, что существуют такие вопросы, которые невозможно решить на Майдане
«Давите на Путина»: украинцы запустили флешмоб к «нормандскому саммиту»

«Давите на Путина»: украинцы запустили флешмоб к «нормандскому саммиту»

Активисты запустили онлайн-флешмоб, который должен помочь привлечь внимание Меркель и Макрона к конфликту в Украине
Ученые обнаружили рядом с белым карликом «испаряющуюся» планету

Ученые обнаружили рядом с белым карликом «испаряющуюся» планету

Ученые впервые обнаружили планету рядом с белым карликом
Украинцев ждут изменения ПДД: что нужно знать

Украинцев ждут изменения ПДД: что нужно знать

Новый законопрект направлен на защиту прав людей с инвалидностью
Трюдо призвали помочь Украине в борьбе с Путиным

Трюдо призвали помочь Украине в борьбе с Путиным

Общественная организация "Канадская группа содействия демократии в Украине" отправила письмо Джастину Трюдо
Диетолог рассказала, как разогнать метаболизм и сжигать максимум калорий

Диетолог рассказала, как разогнать метаболизм и сжигать максимум калорий

Кроме правильного питания и занятий спортом, стоит пить много воды и мыслить более позитивно
В Европарламенте рассказали о планах на Украину

В Европарламенте рассказали о планах на Украину

Макаллистер заявил, что Украина остается главным приоритетом Европарламента
Синоптик обещает «пенсионерскую» погоду в воскресенье

Синоптик обещает «пенсионерскую» погоду в воскресенье

Сухо, без снега и морозов
В Киеве машина рухнула с моста: подробности и фото с места событий

В Киеве машина рухнула с моста: подробности и фото с…

Автомобиль съехал с моста, перевернулся и приземлился на тротуар
Корниенко прокомментировал «роспуск» Верховной Рады

Корниенко прокомментировал «роспуск» Верховной Рады

По словам главы партии "Слуга народа", роспуск парламента - это эмоциональная реакция президента Владимира Зеленского
Украинцы поддержали массовые протесты в Беларуси против интеграции с Россией: фото

Украинцы поддержали массовые протесты в Беларуси против интеграции с Россией:…

Украинцы сожгли портреты Лукашенко и Путина, а также флаг России
Зарплаты мужчин и женщин в Украине сравнили в цифрах

Зарплаты мужчин и женщин в Украине сравнили в цифрах

В Госстате подсчитали, что зарплата женщин в Украине на 25% ниже, чем зарплата мужчин
Цены на самый популярный овощ рекордно упадут

Цены на самый популярный овощ рекордно упадут

От этого пострадает отечественный производитель
Витренко ответил Медведеву по поводу задолженности Газпрома

Витренко ответил Медведеву по поводу задолженности Газпрома

Витренко рассказал, когда Нафтогаз сможет забрать исковые требования против Газпрома
Названа самая популярная страна для отдыха среди украинцев

Названа самая популярная страна для отдыха среди украинцев

За 2019 год показатель украинских туристов в Турции составит более 1,5 млн человек
Ученые обнаружили загадочный эмбрион возрастом 609 млн лет

Ученые обнаружили загадочный эмбрион возрастом 609 млн лет

Были найдены и другие окаменелости организма на разных стадиях его развития
Данилов рассказал о сценариях для Донбасса после «нормандского саммита»

Данилов рассказал о сценариях для Донбасса после «нормандского саммита»

Данилов заявил, что у Украины есть сценарии на случай любого результата Нормандской встречи
Медведев не принял условия Украины по транзиту газа и озвучил свои

Медведев не принял условия Украины по транзиту газа и озвучил…

Премьер-министр РФ рассказал, на каких условиях возможен транзит газа через Украину
В Запорожье отреставрировали меч времен скифов: фото

В Запорожье отреставрировали меч времен скифов: фото

Запорожские специалисты завершили работы по восстановлению древнего скифского оружия
Гончарук сообщил, когда заработает единая служба спасения «112»

Гончарук сообщил, когда заработает единая служба спасения «112»

Глава Кабмина рассказал, когда будет запущена служба помощи "112"
Украинцы могут не платить по завышенным квитанциям на газ: детали

Украинцы могут не платить по завышенным квитанциям на газ: детали

Облгазы не имеют права на перерасчет
Читай также
Последние новости

Кравчук жёстко осадил Порошенко, Тимошенко и Вакарчука

Медики рассказали о неожиданной пользе граната для женщин

Кулеба оценил возможности Зеленского в Париже

Пожар в Одессе: правоохранители установили двух подозреваемых

У Зеленского отмечают, что минские соглашение нужно уточнить

Гончарук анонсировал «промышленный безвиз» с ЕС

Зеленский огласил всеукраинский траур 8 декабря

Замкомандира полка Путина нашли повешенным

Бюджетный камерофон Samsung Galaxy A51 показали на фото

Кравчук жестко прошелся по «майданным» призывам Парубия

«Давите на Путина»: украинцы запустили флешмоб к «нормандскому…

Ученые обнаружили рядом с белым карликом «испаряющуюся» планету

Украинцев ждут изменения ПДД: что нужно знать

Трюдо призвали помочь Украине в борьбе с Путиным

Диетолог рассказала, как разогнать метаболизм и сжигать максимум…