Загрузка...

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

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

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

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

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

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

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

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

Источник:
Тэги: Мир, Политика, Ученые

Новости по теме

Эстроген может усиливать канцерогенный эффект табачного дыма — ученые

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

Коты не толстеют от жирной пищи, — ученые

Ученые из Университета Глазго и научно-исследовательского центра Waltham, занимающегося разработкой всемирно известных марок кормов домашних животных

В ближайшие полтора года на Земле будут часто происходить магнитные бури, – ученые

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

blog comments powered by Disqus
Новости | Слоты
Новости | Слоты