GADDAG
GADDAG to struktura danych zaprezentowana przez Stevena Gordona w 1994 r. Do użytku w generowaniu ruchów w Scrabble i innych grach polegających na generowaniu słów, w których takie ruchy wymagają słów, które „zaczepiają się” w istniejące słowa . Często kontrastuje to z algorytmami generowania ruchów wykorzystującymi ukierunkowany acykliczny wykres słów (DAWG), taki jak ten używany przez Mavena . Jest na ogół dwa razy szybszy niż tradycyjne algorytmy DAWG, ale zajmuje około 5 razy więcej miejsca na regulacje słowników Scrabble.
Quackle, program Scrabble o otwartym kodzie źródłowym, używa GADDAG do generowania ruchów.
Opis
Nazwa GADDAG pochodzi od DAG dla skierowanego wykresu acyklicznego , poprzedzonego własną rewersem.
GADDAG to specjalizacja Trie , zawierająca stany i gałęzie do innych GADDAG. Wyróżnia się przechowywaniem każdego odwróconego przedrostka każdego słowa w słowniku. Oznacza to, że każde słowo ma tyle reprezentacji, ile ma liter; ponieważ przeciętne słowo w większości słowników regulujących Scrabble ma długość 5 liter, oznacza to, że GADDAG jest około 5 razy większy niż zwykły DAWG.
Definicja
Dla każdego słowa w słowniku, które jest utworzone przez niepusty przedrostek x i sufiks y, GADDAG zawiera bezpośrednią, deterministyczną ścieżkę dla dowolnego ciągu REV ( x )+ y , gdzie + jest operatorem konkatenacji.
Na przykład dla słowa „ wyjaśnij ” GADDAG będzie zawierał bezpośrednie ścieżki do ciągów znaków
e+zwykły xe+zwykły pxe+położony lpxe+ain alpxe+w ialpxe+n nialpxe
Ta konfiguracja umożliwia wyszukiwanie słowa na podstawie dowolnej litery, która w nim występuje.
Użyj w generowaniu ruchu
Każdy algorytm generowania ruchu musi być zgodny z trzema rodzajami ograniczeń:
- Ograniczenia planszy : można budować tylko poprzez „haczenie” istniejących liter planszy, a płytki można kłaść tylko na pustych polach.
- Ograniczenia dotyczące stojaków : na swoim stojaku można umieszczać tylko kafelki z literami.
- Ograniczenie słownika : wszystkie słowa wynikające z ułożenia płytek istnieją w słowniku gry.
Algorytmy oparte na DAWG wykorzystują drugie i trzecie ograniczenie: DAWG jest zbudowany wokół słownika i jest przeglądany za pomocą kafelków w szafie. Nie odnosi się jednak do pierwszego ograniczenia: załóżmy, że ktoś chce „zahaczyć” literę P w HARPY , a plansza ma 2 spacje przed literą P, należy przeszukać słownik pod kątem wszystkich słów zawierających litery ze stojaka, na którym znajduje się trzecia litera to P. Jest to nieefektywne podczas przeszukiwania DAWG, ponieważ wiele przeszukiwań trie będzie bezowocnych.
Jest to rozwiązane przez przechowywanie prefiksów przez GADDAG: przechodząc przez gałąź P GADDAG, widzi się wszystkie słowa, które mają P gdzieś w swoim składzie, i może „podróżować w górę” przedrostka, aby utworzyć słowo z kafelkami w stojaku. Aby skorzystać z przykładu z § Definicja , wyszukiwanie P powoduje wyświetlenie „ pxe+lain ”. Litery między P a + można umieścić nad literą P na planszy, a resztę pod nią (jeśli pozwala na to miejsce na planszy).