Математики вычислили сложность игры "Скрэббл"

Иллюстрация с сайта igroved.ru

Ученые вычислили сложность игры Scrabble ("Скрэббл"), известной в русском варианте как "Эрудит". Статья исследователей пока не принята к публикации в рецензируемом журнале, однако ее препринт доступен на сайте arXiv.org.

Игра "Эрудит" состоит из поля-доски в 15 на 15 клеток и набора из 104 букв. Перед игрой каждый участник (которых может быть от 2 до 4) получает по 7 случайных букв из набора, а на середину игрового поля выкладывается начальное слово, составленное из оставшихся от раздачи букв. Затем игроки по очереди начинают выкладывать на доске собственные слова, например, слева направо и сверху вниз. Главное требование - каждое новое слово должно иметь общую букву или буквы с уже выложенными (все правила можно прочитать здесь).

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

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

В результате ученым удалось установить, что задача относится к классу PSPACE. Это означает, что для обработки входной строки длины n потребуется не более чем p(n) ячеек памяти, где p - некоторый многочлен. Более того, ученые установили, что задача PSPACE-полная, то есть любая другая задача из этого класса за полиномиальное время сводится к данной. В некотором смысле это PSPACE-полные - это самые сложные задачи класса PSPACE.

Некоторое время назад на arXiv.org появился препринт итальянца Джованни Вильетты из Пизанского университета, который подсчитал вычислительную сложность известных компьютерных игр. Среди попавших в исследование игр были Doom, Starcraft, Pac-Man и другие.

Обсудить
Дональд ТрампСвоих не бросаем
План Трампа: спасти богатых и сэкономить на бедных
Валентин Тимаков«Дальний Восток — дорога к рынку АТР»
Валентин Тимаков — о дефиците рабочих в ДФО и пользе «Дальневосточного гектара»
Эффективное решение
Эксперты посчитали, что Парижское соглашение можно выполнить с выгодой для РФ
Деловая колбаса
Улюкаев готовился к долгой и счастливой жизни, а получил восемь лет строгача
Воровской передел
Лидер криминальной России рискует сесть надолго. За его трон развернулась война
Темные времена
Лихие 90-е: спецпроект «Ленты.ру»
«Евреи забили гвоздь в голову русскому человеку»
Шпионы КГБ обвиняли советских рокеров в победе мирового сионизма
Есть почитать че?
Библиотека как мир, гуки и геи в беде, сразу два Линча: топовый артхаус на 2A17
«Все хорошо, но раздели-то их зачем?»
Голые европейцы и другие достоинства современного театра
Не считая Чубакки
«Последние джедаи» наконец вдохнули жизнь в возрожденные «Звездные войны»
Poloвинка
Поездка на передней части будущего седана VW Polo для России
Чудо-Judo
Вспоминаем молодежный трансформер Nissan Judo, о котором все забыли
8 лимузинов, появление на свет которых сложно оправдать
Большие, длинные и чрезвычайно бесполезные
Погружение в кирпич
Мы посидели в новом «Гелике» и не узнали его. А потом вылезли – и узнали
«Меня не убили, просто развели»
Россиянка влюбилась по уши и лишилась жилья
Что-то встало за окном
Строения, вызывающие самые пошлые ассоциации
Его ворсейшество
Бессмертные ковры возвращаются на стены российских квартир
С собой не увезешь
Как живут российские олигархи за границей