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.

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

Эксперты назвали полезные свойства хурмы

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

Очищающие и целебные свойства ананаса

Яркий, сочный, тропический фрукт ананас, который в наших широтах употребляется преимущественно в консервированном виде, может похвастаться содержанием витаминов А, С, кальция, фосфора и калия. Будучи богатым клетчаткой и калориями, в нём присутствует мало
Подробнее »»

Как привить первоклассникам любовь к школе: 5 советов

Многие родители совершают ошибки, которые портят отношение ребенка к учебному процессу.
Подробнее »»

Назван самый сексуальный цвет осени 2019

Недавно Институт цвета Pantone назвал 10 самых актуальных цветов сезона осень-зима 2019/20. В свою очередь психологи Рочестерского университета решили провести эксперимент и доказать, цвет делает женщину сексуальной в глазах мужчины
Подробнее »»

Читайте также:
22.08 - 07:43

Меню на 1200 калорий в день: составляем рацион

Похудение – проблема, волнующая многих людей.
Подробнее »»

22.08 - 07:09

10 советов родителям подростков

Как известно, подростковый возраст – один из самых трудных периодов как для самого ребенка, так и для его родителей.
Подробнее »»

22.08 - 06:21

Школьная форма 2019: главные советы по выбору одежды для девочки

Подбираем для ребенка красивую и качественную "униформу".
Подробнее »»

22.08 - 06:06

4 растительных продукта, придающих коже сияние

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

22.08 - 05:47

Правильное питание способно помочь в лечении псориаза - врачи

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

22.08 - 05:01

Как накачать пресс: всего одно упражнение, которое сделает твой живот плоским и рельефным

Ты можешь часами качать пресс, повторять упражнения по 10 подходов, но так и не добиться заветных кубиков.
Подробнее »»

22.08 - 04:38

Смешение чувств: почему некоторые люди могут «слышать» цвета

Такая особенность восприятия называется синестезией: человек неосознанно наделяет явления дополнительными признаками.
Подробнее »»

22.08 - 04:02

В поход – с детьми на выходные!

Лето – идеальная пора для отдыха с детьми на природе.
Подробнее »»

21.08 - 23:37

10 факторов, мешающих похудеть

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

21.08 - 23:06

Секреты и особенности национального секса

Твое сердце разбито японцем, итальянцем или англичанином? Чем он сумел тебя очаровать и как соблазнить?
Подробнее »»

21.08 - 22:19

Можно ли варить вареники и пельмени вместе 

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

21.08 - 22:19

Можно ли варить вареники и пельмени вместе 

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

21.08 - 22:06

Детеныш дюгоня умер из-за пластиковых отходов

В Южном Таиланде осталось всего 250 дюгоней
Подробнее »»

21.08 - 21:57

Запеканка из кабачков с картофелем и помидорами: рецепт дня

Рецепт запеченных овощей в духовке с сыром
Подробнее »»

21.08 - 21:05

Это надо слышать: в Киеве впервые выступит британский певец Джейкоб Бэнкс

На дворе еще лето, а мы уже во всю строим музыкальные планы на зиму. В феврале будем подпевать Джесси из The Neighbourhood, а за пару недель до этого познакомимся с молодым британцем Джейкобом Бэнксом
Подробнее »»


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

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

Загрузка...