14.05 - 15:04

Названа самая сложная игра


 

Magic: The Gathering оказывается невычислимо сложной игрой.

Исследователи доказали, что настольная карточная игра Magic: The Gathering является самой сложной игрой из всех проанализированных игр, в которые играют люди.

Об этом пишет Хроника.инфо со ссылкой на hvylya.net.

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

hronika.

Ключевые слова:
Читайте также:

Три признака того, что человек – социопат

Социопатия обычно возникает вследствие пережитого в детские годы насилия – физического или эмоционального.
Подробнее »»

Научное исследование: любовь действует на организм подобно наркотику

Согласно последним научным исследованиям выражение «любовь — это наркотик» не просто фигура речи.
Подробнее »»

Лифтинг лица: правда о самых популярных средствах

Кажется, даже дети знают, что такое лифтинг. Настолько часто «плывет» это слово с экранов телевизоров, с очередного рекламного плаката, со страниц модного журнала.
Подробнее »»

12 незначительных признаков проблем в отношениях 

Психологи и эксперты по межличностным отношениям выявили ряд тревожных знаков, на которые нужно срочно обратить внимание, если вы хотите сохранить свой союз.
Подробнее »»

Фуксия из черенка

Фуксия из черенка
Фуксия – растение довольно редкое, ее не часто продают в цветочных магазинах.

Подробнее »»

Читайте также:
22.05 - 21:26

Тренировка от Кортни Кардашьян: простые упражнения, которые можно делать в отпуске

Старшая из сестер Кардашьян рассказала, как поддерживает форму на отдыхе
Подробнее »»

22.05 - 20:35

Бритни Спирс не хочет завершать карьеру и собирается вернуться на сцену

Известная американская певица Бритни Спирс, несмотря на заявления своего менеджера о плохом самочувствии, не собирается завершать карьеру.
Подробнее »»

22.05 - 20:10

Плодовое буйство

Июль и август не особенно богаты на урожай плодов лекарственных растений. Но в эти летние месяцы нас радуют известные и любимые в народе боярышник, черемуха, черника и шиповник. Именно о них пойдет речь сегодня.
Подробнее »»

22.05 - 19:54

Как грамотно объяснить ребенку, что родители разводятся

Расставание папы и мамы может нанести огромную психологическую травму маленькому человеку. Как помочь детям пережить этот сложный период?
Подробнее »»

22.05 - 19:07

Что делать, когда кошка требует жениха

Что делать, когда кошка требует жениха
Ваша любимая кошечка подросла и стала настоящей красавицей.

Подробнее »»

22.05 - 18:43

Фразы, из-за которых вас не любят окружающие

Всем известно, что слова имеют материальную силу. Важно следить за тем, какие фразы вы произносите, чтобы избавить свою и жизнь окружающих от многих неприятностей.
Подробнее »»

22.05 - 18:05

Как стать it-girl: 5 шагов к статусу иконы стиля

В мире, в котором доминирует влияние соцсетей, такое явление как уже не только никого не удивляет, но и является статусом, к которому многие стремятся.
Подробнее »»

22.05 - 17:24

Именины в июне 2019: кто и когда отмечает день ангела

Узнайте, кто отмечает именины в июне 2019, и в какой день можно поздравлять с днем ангела
Подробнее »»

22.05 - 17:07

Лето варит обед. Часть 2

В июле полную силу набирает свекла, о полезных свойствах которой мы говорили не раз. Невозможно представить себе лето без свекольника.
Подробнее »»

22.05 - 16:43

Вышивка бисером: с чего начинать

Картины, вышитые бисером, вызывают восхищение
Подробнее »»

22.05 - 16:33

Канье Уэст и Ким Кардашьян выбрали имя четвертому ребенку

Американский исполнитель Канье Уэст и его возлюбленная Ким Кардашьян назвали имя своего четвертого ребенка.
Подробнее »»

22.05 - 16:28

Ошибки, которые допускают интернет - агентства при разработке сайта

Многие интернет - агентства каждый день в процессе своей работы совершают однотипные ошибки, которые мешают их продуктивной работе, а также становятся причиной непонимания между заказчиком и агентством
Подробнее »»

22.05 - 16:02

Аромалампа: актуальный подарок

Аромалампа: актуальный подарок
Аромалампы сегодня приобрели большую популярность, так как запахи эфирных масел могут улучшить настроение, помочь снять напряжение, способствовать профилактике простуды и других заболеваний.

Подробнее »»

22.05 - 15:32

Эксперты рассказали о причинах, «убивающих» брак

По статистике, отношения 70% пар, обратившихся к психологу, находятся на стадии кризиса.
Подробнее »»

22.05 - 15:08

Эксперты назвали чудо-продукт для уменьшения талии

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


Загрузка...
Loading...

Справочная информация

Загрузка...