Поиск слов в эрудит: Помощник для подбора слов в игре "Эрудит"

Алгоритм генерации хода для игры Эрудит / Хабр

Доброго времени суток, хабр!

В этой статье я расскажу о том, как я создавал искусственный интеллект для игры Эрудит. Подробности под катом.

Эрудит

Эрудит — отечественный аналог всемирно известной игры Scrabble — настольной игры, в которую могут играть от 2 до 4 человек, выкладывая слова из имеющихся у них букв в игровое поле. Игровое поле состоит из 15 х 15, то есть 225 клеток, на которых участники игры составляют слова. Каждое составленное слово приносит очки в зависимости от ценности используемых букв и клеток поля.

Поле для игры Эрудит выглядит так:

Рисунок 1. Поле для игры

Основные правила

Обычно правила оговариваются игроками до начала игры, но имеются некоторые общепринятые правила игры:

• В начале игры каждому игроку даётся по семь фишек. За один ход можно выложить несколько слов. Каждое новое слово должно соприкасаться (иметь общую букву или буквы) с ранее выложенными словами. Слова читаются только по горизонтали слева направо и по вертикали сверху вниз.
• Если игрок не хочет или не может выложить ни одного слова, — он имеет право поменять любое количество своих букв, пропустив при этом ход
• Если за ход игрок использовал все семь фишек, то ему начисляются дополнительные 15 очков.
• Сумма очков каждого хода состоит из суммы очков составленных букв, а также премий, получаемых за размещение букв на премиальных клетках.
• Премиальные клетки для букв: очки буквы, расположенной на зеленой клетке, удваиваются, на желтой – утраиваются.
• Премиальные клетки для слов: если одна из букв слова расположена на синей клетке, сумма очков всего слова удваивается, на красной – утраивается.

Первые шаги

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

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

Пример

Префиксы слова ХАБР:

• Х
• ХА
• ХАБ

Суффиксом слова называется любой последовательный набор букв слова, оканчивающийся последней буквой слова, но не включающий в себя первую.

Пример

Суффиксы слова ХАБР:

• АБР
• БР
• Р

Точки привязки

Рисунок 2. Рассматриваемый ряд

Рассмотрим ряд изображенный на рисунке выше. Необходимо найти все слова, которые можно построить в этом ряду. По правилам игры любое слово должно включать в себя уже имеющуюся букву из ряда. Тогда места, где можно сформировать слово – это пустые клетки, смежные с уже занятыми клетками. Назовем эти клетки точками привязки (англ. acnhor). В данном ряду существует пять точек привязки, которые выделены красным цветом на рисунке ниже.

Рисунок 3. Точки привязки

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

Рисунок 4. Возможное количество букв префикса

Алгоритм нахождения слов в ряду

Для каждой клетки, являющейся точкой привязки – ищем все возможные слова следующим образом:

1. Найти все возможные префиксы, связанные с данной точкой привязки и удовлетворяющие возможной длине префикса, заданной для точки привязки.
2. Для каждого найденного префикса в пункте выше найти все подходящие суффиксы, которые будут формировать вместе с префиксом слово из словаря. Суффиксы строятся используя буквы игрока или уже имеющиеся на поле буквы.

Префикс слова будет содержать либо клетки из руки игрока, либо клетки, уже размещенные на доске, но не одновременно.

Пример

В ходе работы алгоритма может быть найдено слово «КОРАБЛЬ » для точки привязки 4, если у игрока имеются буквы «Б» и «Ь«. В этом случае префиксом будет «КОРА«, суффикс будет построен при помощи двух букв игрока и буквы «Л» на поле

Теперь, имея способ нахождения всех слов на поле, можно перейти непосредственно к описанию алгоритмов генерации хода.

Алгоритмы генерации хода

Я выбрал три алгоритма генерации хода: алгоритм выбора максимального значения, метод полного перебора, метод альфа-бета отсечения.

Алгоритм выбора максимального значения

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

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

Пример

На поле установлена начальная позиция, то есть на поле не размещено еще ни одного слова, на руках игрока имеются следующие буквы: ОБЛМЕОБ. В результате первой итерации алгоритма добавится слово «ОБЛОМ». В результате на руках у игрока останутся буквы Е и Б из которых уже не составить ни одного слова в новой позиции на рисунке ниже:

Рисунок 1. 1. Результат работы алгоритма.

Этот ход принесет игроку 11 очков.

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

Рисунок 1.2. Лучший ход.

Данный ход принесет игроку 38 очков — 23 очка за составленные слова и 15 бонусных за использование всех букв, что в 3,5 раза больше, чем указанный выше ход.

Метод полного перебора

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

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

Метод альфа-бета отсечения

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

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

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

Результаты

Для реализации я использовал язык программирования Java. Словарь состоял из 12 тысяч слов, в программе был представлен в виде обычного Set’a.

Среднее время генерации представлено на диаграмме ниже:

Рисунок 5. Диаграмма времени генерации

Выборка исследования включала в себя 100 различных последовательностей появления букв, выдаваемых игрокам (по принципу стека). В итоге было рассмотрено примерно 1500 различных комбинаций букв на руке и позиций.

Однако выигрыш по времени генерации повлек за собой проигрыш по очкам: алгоритм выбора максимального значения в среднем приносит игроку порядка 30 очков, в то время как остальные методы — порядка 60 очков.

TODO

К сожалению, из рассмотрения были исключены следующие пункты:

• Анализ комбинаций с редкими буквами
• Анализ букв, остающихся после хода
• Анализ дальнейших действий противника
• Буквы, которые следует менять при пропуске хода

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

Литература

• Лекция Peter Norvig по игре Scrabble. Из этого источника заимствовано наибольшее количество идей.
• Правила игры
• Полный перебор wiki
• Великий Томас Кормен: Алгоритмы. Построение и анализ.
• Альфа-бета отсечение

Спасибо за внимание!

Поиск слов в Эрудит — онлайн и бесплатно

Поиск слов в Эрудит — онлайн и бесплатно

Легко находите полезные слова онлайн и бесплатно

Как использовать поиск слов скрэббл

Шаг 1

Вставьте свой набор букв или слов в отведенное место

Шаг 2

Сделайте все необходимые настройки и запустите антикремблер.

Шаг 3

После завершения дескремблирования вы сможете выбрать нужные слова из списка.

Что такое скрэбл-игра и кто в нее играет

Scrabble — это классическая игра, в которую по вечерам проводят несколько поколений семей.

Он известен в 122 странах мира как отличное интеллектуальное развлечение. Scrabble — настольная игра, изобретенная 80 лет назад американским архитектором Альфредом Баттсом. После десяти лет безуспешных попыток внедрения и многочисленных улучшений он наконец получил признание и объединил любителей кроссвордов и анаграмм. Суть игры состоит в том, чтобы составить как можно больше слов из случайно выпавших фишек на игровом поле 15 на 15 квадратов. Слова располагаются сверху вниз или слева направо в соответствии с принципом сканворда. В начале игры игроку дается 7 букв, из которых ему нужно составить слово, желательно из всех букв сразу. Победителем становится игрок, которому удастся составить как можно больше слов из имеющихся у него букв. Чем реже буквы встречаются в словах, тем они ценнее, то есть принесут больше очков.

Эрудит — это игра в слова для 2, 3 или 4 игроков. Игра состоит в составлении слов, которые связаны между собой по принципу кроссворда на игровом поле SCRABBLE, с использованием игральных костей с буквами, имеющими разную ценность в виде очков. Цель игры — набрать как можно больше очков. Игроки соревнуются, размещая свои плитки с буквами в таких комбинациях и положениях, чтобы максимально использовать ценность букв и призовых мест на доске. Общая сумма очков в игре может варьироваться от 400 до 800 очков и более, в зависимости от мастерства игроков. Игра носит характер дуэли: вам нужно использовать бонусные клетки перед противником. Вам понадобится воображение и умение создавать анаграммы (собирать реальные слова из исходного набора букв), но этого может быть недостаточно для победы.

Был ли вам полезен AnyTextEditor?

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

Расшифровать буквы: ЭРУДИТ Найти все слова

Список всех допустимых слов для букв «эрудит»

Введите буквы (максимум: 15, используйте ? или * для пробела)

Выбор словаря NWL — US/CACSW — UKENABLE

Должен включать

Начинается с

Заканчивается на

Слова из 7 букв

• эрудит

РЕКЛАМА

Слова из 6 букв

• Dieter
• пересмотреть
• отозван
• многоуровневый
• уреид

Слова из 5 букв

• сдерживание
• гага
• этюд
• рети
• устал
• дерево
• пытался
• проверено
• матки

РЕКЛАМА

Слова из 4 букв

• олень
• дет
• здесь
• диета
• ужасный
• грязь
• дайте
• др.
• дуэт
• дуэт
• во время
• изменить
• Эйде
• футляр
• ирред
• красный
• тростник
• сеть
• ездить
• обряд
• грубо
• рут
• тройник
• прилив
• привязан
• уровень
• шина
• дерево
• правда
• какашка

Слова из 3 букв

• ди
• умереть
• дит
• срок
• дуй
• здесь
• гнев
• красный
• бесплатно
• Рей
• рет
• избавиться
• улица
• рут
• Тед
• тройник
• галстук
• туй
• урд
• ют

РЕКЛАМА

Слова из 2 букв

• de
• изд.
• эр
• и др.
• идентификатор
• это
• ре
• тэ
• ти
• ут

Word Unscrambler — это простой онлайн-инструмент для расшифровки и разгадывания зашифрованных слов, часто полезно для поиска самых популярных слов для Scrabble, Words with Friends, Wordle, Wordscapes, Wordfeud, TextTwist, Word Cookies, Anagrams и т. д.

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

• Выучить слова из 2 и 3 букв
• Использовать префикс/суффикс
• Выучите Q-слова без U и с U
• Использование крючков, план для бинго

Также ознакомьтесь с некоторыми недавними статьями из нашего блога:

• Word Cookies Help, Tips & Tricks
• Советы по шахматам для начинающих
• Лучшие карточные игры для друзей
• Советы и рекомендации по игре в палача
• 10 советов по судоку для начинающих
• лучших онлайн-игр, в которые можно играть с друзьями
• Советы и стратегия «Угадай, кто»
• Wordle Советы и рекомендации
• 27 слов, которые нужно запомнить для Scrabble
• Советы по разгадыванию кроссвордов
• 5 советов, как набрать больше очков в Words с друзьями
• Объясните анаграммы на примерах
• Стратегия Боггла 101

Соответствующие ссылки

• Советы по выигрышу в Scrabble
• Советы по общению с друзьями
• Слова из четырех букв
• Список слов

Примечание : Не стесняйтесь присылать нам любые отзывы или сообщения о новом внешнем виде нашего сайта. Благодарим Вас за посещение нашего веб-сайта.

ЭРУДИТ Расшифрованные буквы | Анаграмма эрудиции

Расшифровать варианты эрудиции

баллов

Ворд	Очки Эрудита	слов с друзьями
эрудированный	8	9

баллов

Ворд	Очки Эрудита	слов с друзьями
Дитер	7	7
Редуит	7	8
пересмотреть	7	7
в отставке	7	7
тедье	7	7
многоуровневый	7	7
уреид	7	8

баллов

Ворд	Очки Эрудита	слов с друзьями
сдерживающий	6	6
гага	6	6
этюд	6	7
рети	5	5
руди	6	7
устал	6	6
дерево	6	6
трайд	6	6
пытался	6	6
верифицированный	6	7
урди	6	7
урит	5	6
матка	5	6

баллов

Ворд	Очки Эрудита	слов с друзьями
олень	5	5
доп. Добавить комментарий Отменить ответ Ваш адрес email не будет опубликован. Обязательные поля помечены * Комментарий * Имя * Email * Сайт