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.

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

YouTube все чаще заменяет людям реальные отношения

Социальные сети, мессенджеры, сайты знакомств компенсируют потребность в общении. Но является ли полноценной такая компенсация?
Подробнее »»

Составление меню: советы

Составление меню: советы
Чтобы составить эффективное меню, важно учесть состав семьи, а также физическое состояние каждого из домочадцев.

Подробнее »»

Как похудеть без диеты и упражнений

За неделю можно сбросить от 500 г до 3 кг
Подробнее »»

Что даёт нам болгарский перец?

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

Как выбрать вечернее платье мечты

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

Читайте также:
27.05 - 07:09

Именинница дня: 7 цитат Маши Ефросининой о детях, женской солидарности и любви к себе

Сегодня, 25 мая, известная украинская телеведущая Маша Ефросинина отмечает свое 40-летие.
Подробнее »»

27.05 - 06:26

Почему вода из крана вредна для кожи 

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

27.05 - 06:01

Как продлить жизнь ароматических свечей

Как продлить жизнь ароматических свечей
Умело подбирая ароматические свечи, можно создать в помещении атмосферу романтическую и торжественную, бодрящую и умиротворенную… А если угадать предпочтения близкого человека и подобрать свечу под инте

Подробнее »»

27.05 - 05:38

14 вегетарианских источников белка

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

27.05 - 05:08

Несколько привычек, от которых лучше отказаться для более качественной жизни

Человеческий разум — вещь забавная. Мы все склонны думать, что прекрасно знаем, как управлять собственным разумом (как минимум, на эмоциональном и поведенческом уровнях), но на деле всё не так просто.
Подробнее »»

27.05 - 05:07

Бучу — чудодейтсвенное растение Южной Африки

Южноафриканское растение Бучу издавна известно своими лекарственными свойствами. Оно использовалось койсанскими народами на протяжении многих веков, которые считали его эликсиром молодости.
Бучу является охраняемым растением Кейпского флористического

Подробнее »»

27.05 - 04:49

Как избавиться от храпа раз и навсегда

Победить храп и апноэ возможно
Подробнее »»

27.05 - 04:03

Топ-5 фильмов, которые стоит посмотреть каждой девушке на этих выходных

Джой

 

Эта картина с оскароносной Дженнифер Лоуренс в главной роли
Подробнее »»

26.05 - 22:41

Зачем человеку гормоны?

В какой клинике можно сдать анализ на гормоны и получить полную консультацию
Подробнее »»

26.05 - 22:28

5 умений, которыми должен обладать успешный человек

У каждого из нас своя «формула успеха». Но какие качества нужно развить, чтобы стать успешным?
Подробнее »»

26.05 - 22:21

Больше, чем тренировки: в чем преимущество уличных тренажеров

Быть в отличной спортивной форме и чувствовать себя бодрым стремится каждый
Подробнее »»

26.05 - 22:08

Чем отличаются пробиотики и пребиотики. И что это такое постбиотики?

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

26.05 - 20:47

Средиземноморская диета может защищать от депрессии

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

26.05 - 20:02

Самое необычное варенье: ТОП-5 фантастических рецептов

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

26.05 - 18:27

Влажные салфетки: стоит ли использовать

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


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

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

Загрузка...