Project ImmScrabble

Description

ImmScrabble to program umożliwiający grę w Scrabble z komputerem. Program został napisany w języku OCaml (do tworzenia interfejsu użytkownika wykorzystałem bibliotekę LablTk). Poziom gry jest wysoki - komputer analizuje wszystkie możliwe ruchy na danym etapie gry. Korzysta w tym celu ze słownika wyrazów polskich (i ich odmian fleksyjnych), który można pobrać ze strony: http://www.kurnik.pl/slownik/growy. Zastosowany algorytm pokrótce opisałem poniżej. Jest to ten sam algorytm, którego użyłem tworząc Zaksiaki. Projekt ten umieszczam tutaj raczej jako ciekwostkę - bogatszą w funkcje wersję programu (napisaną w C++) można pobrać stąd.

Instrukcja

LPM - lewy przycisk myszy
PPM - prawy przycisk myszy

• aby zaznaczyć płytkę kliknij na niej LPM,
• aby odznaczyć płytkę kliknij gdziekolwiek PPM (albo LPM poza obszarem planszy i stojaka),
• aby umieścić płytkę na planszy zaznacz ją, a następnie kliknij LPM w wolne pole na planszy,
• aby przenieść płytkę z jednego pola na inne zaznacz najpierw tę płytkę, a następnie kliknij LPM w wolne pole na planszy,
• gdy ułożysz już słowo w danej turze, kliknij przycisk "Zakończ ruch",
• jeśli chcesz wymienić płytki, kliknij przycisk "Wymień płytki", następnie zaznacz (LPM) te płytki, które chcesz wymienić i kliknij przycisk "Zatwierdź"; jeśli się rozmyślisz odznacz wszystkie zaznaczone płytki (PPM na każdej zaznaczonej płytce) i kliknij przycisk "Zatwierdź",
• aby zakończyć program kliknij przycisk "Wyjdź z gry".

Download

Archived executable: ImmScrabble BIN.zip
Source code: ImmScrabble SRC.zip

Uruchomienie

Program bez problemu uruchamiałem w systemie Microsoft Windows, w którym zainstalowane były biblioteki Tcl/Tk 8.3.

W systemie Microsoft Windows wystarczy wpisać komendę w linii poleceń: ImmScrabble.exe

Aby uruchomić program w systemie Un*x należy wcześniej przekompilować źródła.

Kompilacja

Program bez problemu kompilowałem w systemie Microsoft Windows, w którym zainstalowane były biblioteki Tcl/Tk 8.3 oraz środowisko Ocaml 3.09.0.

Przygotowałem plik make.bat, aby wygodnie było skompilować program w systemie operacyjnym Microsoft Windows.

Możliwe komendy:

   make.bat debug
   make.bat release

Jeśli używasz systemu Un*x i zabierasz się za kompilację kodu OCAML, to chyba poradzisz sobie bez żadnych instrukcji ;)

Algorytm gry komputera

Ogólny schemat

1. Znajdź potencjalne miejsca na planszy, w których można ułożyć płytki nienaruszając reguł Scrabble (computerPlayer#searchPlaces),
2. W każdym z tych potencjalnych miejsc spróbuj ułożyć ze swoich płytek poprawne słowo (computerPlayer#searchMoves),
3. Sprawdż, czy przypadkiem nie powstało więcej, niż jedno słowo i jeśli tak, to zweryfikuj ich poprawność (computerPlayer#searchMove),
4. Dla każdego znalezionego ruchu oblicz wartość punktową i wybierz ten, którego wartość jest największa (computerPlayer#evaluateMove),
5. Jeśli nie znalaziono żadnego, poprawnego ruchu, to zrób jedną z dwóch rzeczy: albo wymień losową liczbę płytek albo spasuj (gdy wymiana płytek jest niedopusczalna lub niemożliwa; computerPlayer#performAction).

Myślę, że bliższego opisu wymagają jedynie punkty 1 i 2.

Ad. 1.

Sam algorytm wyszukiwania potencjalnych miejsc nie jest skomplikowany. Chciałbym jedynie sprecyzować, co rozumiem przez ''potencjalne miejsce''. Otóż jest to takie miejsce na planszy, w którym można ułożyć płytki nienaruszając reguł Scrabble (przykładowo w jednym ruchu płytki można dokładać tylko w jednym wierszu lub tylko w jednej kolumnie). Każde takie miejsce opisywane jest przez parametry:

1. współrzędne $i, $j, które określają gdzie zaczyna się słowo,
2. orientacja (czy słowo jest układane w poziomie, czy w pionie),
3. liczba płytek, które trzeba wyłożyć,
4. całkowita długość powstałego słowa}.

Najłatwiej chyba będzie to zrozumieć patrząc na poniższy rysunek:

Rys. 1. Kilka miejsc na planszy, w których można ułożyć płytki.

Ad. 2.

Gdy dysponujemy już listą potencjalnych miejsc, przystępujemy do szukania słów, które można ułożyć z dostępnych płytek. Oczywiste rozwiązanie polega na sprawdzaniu permutacji płytek na stojaku (nie zawsze wszystkich - zależy to od konkretnego miejsca). Jednak czas potrzebny na sprawdzenie wszystkich możliwości jest zdecydowanie za długi i może wynośić nawet kilka minut.

Rozwiązanie, które wymyśliłem polega na wykorzystaniu struktury danych zwanej uniwersalną strukturą słownikową (w skrócie USS). USS umożliwia szybkie sprawdzanie (w praktyce w czasie stałym), czy dane słowo znajduje się w słowniku, czy też nie. Jednak zastosowanie tej struktury do przeszukiwania opisanego w poprzednim akapicie nie poprawia w sposób znaczący efektywności. Ja wykorzystałem ją w inny sposób. Najpierw jednak przybliżę samą strukturę USS.

Rysunek zastąpi sporo słów i myślę, że krótka jego analiza pozwoli zrozumieć istotę USS:

Rys. 2. Słownik reprezentowany przez USS po dodaniu słów: "akcja", "akcjami", "słowo", "słowni" i "słownik". Znak '*' oznacza, że w danym węźle kończy sie poprawne słowo.

Widzimy, że w ten sposób rzeczywiście szybko możemy rozstrzygnąć problem przynależności słowa do słownika, ale, jak wcześniej wspomniałem, nie jest to wystarczające.

Zauważmy, że możemy inaczej wykorzystać strukturę drzewiastą USS - zamiast sprawdzać bezmyślnie wszystkie permutacje płytek ze stojaka, możemy podczas próby układania słowa utrzymywać wskaźnik na aktualny węzeł w USS. Gdy chcemy dołożyć kolejną płytkę wpierw sprawdzamy, czy istnieje odpowiedni węzeł w drzewie. Jeśli go nie ma (co będzie zdarzać się najczęściej), możemy wycofać się (backtrack) i nie musimy niepotrzebnie wywoływać funkcji rekurencyjnie. Po ułożeniu przewidzianej liczby płytek w danym miejscu możemy od razu sprawdzić, czy powstałe słowo jest poprawne (patrzymy tylko na flagę poprawności węzła). Taki sposób wyszukiwania możliwych ruchów sprawia, że zazwyczaj jesteśmy w stanie przeanalizować je wszystkie w niecałą sekundę.

Dodatkowa uwaga: przy każdym uruchomieniu gry słownik wszystkich dopuszczalnych słów (zawartych w pliku words\_pl.txt) jest wczytywany właśnie do struktury USS.