ГАДДАГ

GADDAG , — это структура данных представленная Стивеном Гордоном в 1994 году для использования при создании ходов для Scrabble и других игр с генерацией слов, где такие ходы требуют слов, которые «подключаются» к существующим словам. Это часто контрастирует с алгоритмами генерации ходов, использующими направленный ациклический граф слов (DAWG), такой как тот, который используется Maven . Обычно он в два раза быстрее традиционных алгоритмов DAWG, но занимает примерно в 5 раз больше места для регулирования словарей Scrabble. ^{[ 1 ]}

Quackle, программа Scrabble с открытым исходным кодом, использует GADDAG для генерации ходов. ^{[ 2 ]}

Описание

Название GADDAG происходит от DAG, обозначающего направленный ациклический граф , с префиксом собственного реверса. ^{[ 1 ]}

GADDAG — это специализация Trie , содержащая состояния и ветви других GADDAG. Он отличается тем, что хранит каждый перевернутый префикс каждого слова в словаре. Это означает, что каждое слово имеет столько же представлений, сколько и букв; поскольку среднее слово в большинстве нормативных словарей Scrabble имеет длину 5 букв, это делает GADDAG примерно в 5 раз больше, чем простой DAWG.

Определение

Для любого слова в словаре, образованного непустым префиксом x и суффиксом y, GADDAG содержит прямой детерминированный путь для любой строки REV ( x )+ y , где + — оператор конкатенации.

Например, для слова « explain » GADDAG будет содержать прямые пути к строкам.

e+xplain
xe+plain
pxe+lain
lpxe+ain
alpxe+in
ialpxe+n
nialpxe

Эта настройка позволяет искать слово по любой букве, которая в нем встречается.

Использование при генерации ходов

Любой алгоритм генерации ходов должен соответствовать трем типам ограничений:

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

Алгоритмы на основе DAWG используют преимущества второго и третьего ограничения: DAWG строится вокруг словаря и проходится с использованием плиток в стойке. Однако это не позволяет устранить первое ограничение: предположим, что кто-то хочет «подцепить» букву P в HARPY , а на доске есть 2 пробела перед буквой P, необходимо найти в словаре все слова, содержащие буквы со стойки, где буква П. третья Это неэффективно при поиске в DAWG, так как многие поиски в дереве будут бесплодными.

Эта проблема решается хранилищем префиксов GADDAG: проходя по ветви P GADDAG, можно увидеть все слова, в составе которых есть буква P , и можно «подняться» по префиксу, чтобы сформировать слово с плитками в стойке. Если использовать пример из раздела § Определение , то при поиске P выдается « pxe+lain ». Буквы между P и + можно разместить на над буквой P доске , а остальные — под ней (если позволяет место на доске).

См. также

Ссылки

^ Jump up to: ^а ^б Гордон, Стивен А. (1994). «Более быстрый алгоритм генерации ходов в Scrabble» (PDF) . Программное обеспечение: практика и опыт . 24 (2): 219–232. дои : 10.1002/спе.4380240205 . S2CID 7620517 .
^ Джейсон Кац-Браун; Джон О'Лафлин. «Как Квакл играет в скрэббл» . Проверено 2 июля 2018 г.

[gordon-paper-1] Jump up to: ^а ^б Гордон, Стивен А. (1994). «Более быстрый алгоритм генерации ходов в Scrabble» (PDF) . Программное обеспечение: практика и опыт . 24 (2): 219–232. дои : 10.1002/спе.4380240205 . S2CID 7620517 .

[quackle-2] Джейсон Кац-Браун; Джон О'Лафлин. «Как Квакл играет в скрэббл» . Проверено 2 июля 2018 г.

[ 1 ]

[ 2 ]