České vysoké učení technické v Praze Fakulta elektrotechnická
Bakalářská práce
Implementace stolní hry Scrabble Jan Špinka
Vedoucí práce:
Ing. Tomáš Richta
Studijní program: Elektrotechnika a informatika strukturovaný bakalářský Obor: Informatika a výpočetní technika leden 2009
ii
Poděkování Děkuji svému vedoucímu Ing. Tomáši Richtovi za cenné rady a vstřícnost při tvorbě bakalářské práce.
iii
iv
Prohlášení Prohlašuji, že jsem svou bakalářskou práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/200 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).
V Praze dne 20.1.2009
……………………………………………….
v
vi
Anotace Cílem mé práce je implementovat stolní hru Scrabble v s GUI rozhraním, napsanou v jazyce C++, která umožní hru člověka i počítače. Počítač disponuje jednoduchou inteligencí. Pro umělou inteligenci počítače byl zvolen algoritmus od autorů Andrew W. Appel and Guy J. Jacobson a volba tahu je odvislá od nejvyššího bodovém hodnocení.
Abstract The aim of my work is to implement the board game SCRABBLE written in C++ language with GUI interface, which will enable the game of a man and the computer as well. The computer manages the simple intelligence. The algorithm of Andrew W. Appel and Guy J. Jacobson has been chosen for the computer artificial intelligence and the choice of the draw depends on the highest points rating.
vii
viii
Obsah Seznam obrázků ......................................................................................................................... x 1 Úvod ........................................................................................................................................ 1 Co je Scrabble ...................................................................................................................................... 1 Historie ................................................................................................................................................ 1 Scrabble a stroje .................................................................................................................................. 2
2 Cíl bakalářské práce ................................................................................................................ 2 2. 1 Grafické rozhraní .......................................................................................................................... 2 2.2 Snadná modifikace ........................................................................................................................ 2
3 Analýza.................................................................................................................................... 3 3.1 Hra Scrabble .................................................................................................................................. 3 3.2 Programové zpracování aplikace ve Windows .............................................................................. 3 3.3 Slovník platných slov ..................................................................................................................... 4 3.4 Umělá inteligence UI ..................................................................................................................... 4
4 Návrh implementace ............................................................................................................... 4 4.1 Scrabble ......................................................................................................................................... 4 4.1 Herní stroj ...................................................................................................................................... 5 4.2
Slovník slov .............................................................................................................................. 6
4.3 Umělá inteligence .......................................................................................................................... 7
4 Realizace ................................................................................................................................. 9 4.1 Třída Hráč .................................................................................................................................... 9 4.2 Třída HerniPlan ...................................................................................................................... 10 4.3 Třída Pytlik ............................................................................................................................. 10 4.4 Třída Pismeno ........................................................................................................................... 11 4.5 Třída Stojanek......................................................................................................................... 11 4.6 Třídy Slovnik, Uzel, SpojovySeznam ......................................................................... 11 4.7 Třída GeneratorTahu ............................................................................................................. 12 4.8 Třídy GameEngine a Scrabble ........................................................................................... 13 4.9 Podpůrné třídy............................................................................................................................. 13
5
Výsledky testování ............................................................................................................ 14
6 Závěr...................................................................................................................................... 14 7 Seznam použité literatury ...................................................................................................... 15 A Seznam použitých zkratek ................................................................................................... 16 B Obsah přiloženého CD......................................................................................................... 17
ix
Seznam obrázků Obrázek 1.
Grafický vzhled aplikace
5
Obrázek 2.
Datová struktura Trie
7
Obrázek 3.
Datová struktura DAWG
7
x
xi
1 Úvod
Co je Scrabble Scrabble je desková slovní hra pro 2 až 4 hráče. Obsahuje herní plán o velikosti 15×15 polí a 100 písmen. Počet jednotlivých písmen a bodové ohodnocení závisí na jejich četnosti v jazyce. Úkolem hráčů je vytvářet vzájemně zapadající slova za co možná nejvyšší počet bodů. Využívají při tom také prémiová pole násobící hodnotu písmene nebo slova.
Historie Rok 1931 Prvopočátky hry se datují k roku 1931, kde ve městě Poughkeepsie, stát New York. Během hospodářské krize, místní architekt Alfred Mosher Butts, toho času bez práce, se rozhodl se rozvinout svou zálibu v hrách a v jazyku. Butts, jenž stále nosil brýle, neměl v lásce hry s kostkou. Protože v nich šlo vždy pouze o štěstí. Proto Butts vymyslel hru, jež stála z poloviny na štěstí a z poloviny na schopnostech. Koncem roku 1931 měl hotovou základní myšlenku a název: Lexico. Lexico se hrálo bez desky. Hráči získávali body podle délky slova, které vytvořili. Další body se daly získat za písmena označená jako "minor honors" (malé cti): B, F, H, M, P, V, W a Y. Ještě vyšší odměna byla vypsána na využití "major honors" (velkých ctí): J, K, Q, X a Z. Butts pečlivě prošel titulní stránku New York Times, aby mohl stanovit četnost a bodové ohodnocení jednotlivých písmen abecedy. Rok 1938 Buttsova obliba křížovek ho přivedla na myšlenku, propojit písmena s hrací deskou, na které by se slova dala skládat podobně jako v křížovkách. Z Lexika se stalo "New Anagrams", "Alph", "Criss-Cross" a nakonec "Criss-Crosswords". Pravidla stále ještě vypadala jinak než dnes, například první slovo se pokládalo do levého horního rohu hracího plánu. Mnohé původní vlastnosti Buttsovy hry však zůstaly zachovány. Deska měla už tenkrát rozměr 15x15 palců; také písmen bylo 7 a ukládala se do malého zásobníku. Ani způsob skládání slov a hodnoty písmen už se od roku 1938 nezměnily.
1
Rok 1948 Hra proniká na trh a dostává nové jméno „Scrabble“. Byla patentována a 16. prosince 1948 bylo jméno zaregistrováno jako ochranná známka. Moderní Scrabble spatřil konečně světlo světa.
Scrabble a stroje Aplikace hry Scrabble je do prostředí počítačů implementována pomocí algoritmu backtracking (prohledávání s návratem) který generuje tah počítače a jako slovník slouží stromová slovníková struktura Trie případně její vylepšení v podobě DAWG. Autoři algoritmu jsou Andrew W. Appel a Guy J. Jacobson. Tento algoritmus je nejpoužívanějším a domnívám se, že jediným a je základním kamenem pro tvorbu slov a jejich umístění na desku. Existují však být různá vylepšení spočívající ve volbě tahu např. formou genetického algoritmu, kdy v různé fázi hry je aplikováno jiné pravidlo pro výběr tahu.
2 Cíl bakalářské práce Cílem bakalářské práce je zpracovat problematiku tvorby hry s GUI rozhraním a jednoduchou umělou inteligencí v jazyce C++. Ukázka je na příkladě deskové hry Scrabble. Následně pak seznámení se s principy programování pod Windows a prohloubení znalostí programování v C++. Implementování a osvojení si algoritmů a potřebných datových struktur užitých pro danou aplikaci.
2. 1 Grafické rozhraní Hra bude s hráčem komunikovat prostřednictvím GUI a ovládána pomocí myši. Příkazy akce hry budou volena prostřednictvím herního menu.
2.2 Snadná modifikace Hra bude umožňovat modifikaci bonusových polí herní plochy, použitá písmena a jejich bodové ohodnocení, obsah pytlíku písmen a slovník nezávislý na jazyku prostřednictvím jednoduchých textových souborů.
2
3 Analýza Problém tvorby aplikace deskové hry Scrabble, má tyto zásadní oblasti:
3.1 Hra Scrabble Hru Scrabble lze tematicky rozdělit na tyto části: 1. Pravidla hry – stanovení podmínek pro aplikaci a. Stanovení počtu hráčů – min. 2, max. 4 b. Způsob přikládání písmen – následné přiložení písmen, kdy musí aspoň jedno písmeno sousedit s již vyloženým slovem c. Bodové hodnocení tahu – body jsou počítány pouze z vyložených písmen tvořící slovo, v případě bonusových polí d. Cyklus tahu, v daném tahu připadá v úvahu jedna z možností: i. Vlastní tah po vyložení písmen na desku ii. Výměna písmen ve stojánku s písmeny z pytlíku iii. Pas – vynechání tahu iv. Ukončení hry – po vyložení všech písmen ze stojánku, odebrání všech písmen z pytlíku 2. Objekty hry a. Hráč (v tomto případě člověk, počítač) b. Hrací plocha a jednotlivá políčka v ní c. Pytlík s písmeny d. Písmena e. Stojánek s písmeny každého hráče 3. Grafické rozhraní GUI
3.2 Programové zpracování aplikace ve Windows Nezanedbatelným hlediskem je i členění programového kódu hry a obsluhy systému Windows. Byl proto zvolen přístup oddělení programového kódu pro Windows od samotného kódu hry, prostřednictvím herního stroje.
3
3.3 Slovník platných slov Bude potřeba datová struktura pro uložení jednotlivých slov taková, že umožní jejich rychlé hledání. Nabízí se Trie což je prefixový strom, který se používá pro uchovávání asociativního pole, kde klíčem jsou řetězce.
3.4 Umělá inteligence UI Algoritmus reprezentující umělou inteligenci je implementován z „The Worlďs Fastest Scrabble program“ od Andrew W. Appel a Guy J. Jacobson, který generuje tahy hráče počítače a vybírá ten s největším bodovým hodnocením.
4 Návrh implementace V této části se budeme zabývat návrhem jednotlivých částí analyzovaného problému.
4.1 Scrabble Pravidla hry budou realizována v každém cyklu hry. Objekty hry budou reprezentovány jednotlivými třídami viz realizace. Grafické zpracování bude vycházet ze vzhledu herní plochy Scrabble. Barevně budou zvýrazněna pole s bonusovými hodnotami. Modrá 2x bodový součet slova, zelená 3x slovo, růžová 2x písmeno, červená 3x písmeno. Zásobník hráče bude v dolní části obrazovky a manipulace s písmeny v zásobníku a na desce bude prostřednictvím myši. Informace o hráčích budou v pravé části okna, spolu s výpisem zbývajících písmen v pytlíku. Body za písmeno budou zobrazeny spolu s písmenem. Ovládání hry bude prostřednictvím horního menu. Struktura menu bude následující Hra Start
- nová hra
Konec
- ukončení hry
Nastavení
- nastavení počtu hráčů
Lidé
- počet hráčů typu člověk
PC
- počet hráčů typu PC
Ovládání
- ovládání cyklu hry
4
Pas
- vynechání tahu hry
Proveď tah
- provedení tahu
Výměna kamenů Označení pro výměnu
- lze označit více písmen, která pak budou vyměněna
Vyměň
- provede samotnou výměnu
Obrázek 1. Grafický vzhled aplikace
4.1 Herní stroj V první řadě je třeba pro samotný kód hry v prostředí Windows vytvořit herní stroj (engine), který oddělí programovou část hry od kódu pro obsluhu Windows. Výhodou takového zpracování je, přehlednost programového kódu a následná přenositelnost. Herní stroj lze pak využít i pro další hry. Princip fungování programů pod Windows je založen na událostech např. klepnutí myši, stisk klávesy. Tím že se provede klik myši, systém Windows zašle programu zprávu, ve 5
které je uložena informace, jaká událost byla vykonána, v případě kliknutí myši to jsou souřadnice a jaké tlačítko bylo stisknuto. Program pak reaguje na události prostředí, zatím co prostředí přebírá pokyny od programu. Kód herního stroje je založen na Win32 API. Win32 API je poměrně značně rozsáhlá problematika, přesahující rámec této bakalářské práce, nicméně pro vytvoření herního stroje je potřeba jen malá část. Herní stroj tedy rozkládá hru na jednotlivé události: -
Inicializace – je při spuštění hry, vytvoření instance herního stroje
-
Začátek - započetí hry
-
Konec - ukončení hry
-
Aktivace - tato část se provede v případě obnovení aplikace z minimalizace či přesunu z pozadí
-
Deaktivace - provedení kódu v této části při minimalizaci či přesunu na pozadí Vykreslování - zde je kód pro překreslení obrazovky hry
-
Cyklus - herní cyklus, ve kterém se např. překresluje grafika, provádí výpočty. Frekvence snímkování se nastaví konstantou v programu.
4.2 Slovník slov Slovník bude reprezentován stromovou datovou strukturou Trie (trie pochází z anglického „retrieval“ – získávání, vyhledávání). Symboly v uzlech na cestě z kořene do koncového uzlu tvoří řetězec. Tato datová struktura je velmi rychlá ve vyhledávání jednotlivých slov. Trie vyžaduje O(n) paměťového prostoru a umožňuje vyhledávání, vkládání a rušení v čase O(dm), kde n je celková velikost řetězců v množině řetězců a m je velikost zpracovávaného řetězce, d velikost abecedy.
6
Obrázek 2. Datová struktura Trie Úspornější datovou strukturou je však DAWG, což je vlastně deterministický konečný automat. Tento zredukuje počet uzlů na mnohem menší počet, tím sníží paměťové nároky. Nicméně pro použitý slovník dostačuje datová struktura Trie.
Obrázek 3. Datová struktura DAWG
4.3 Umělá inteligence Zde více přiblížím princip algoritmu umělé inteligence. Pro hledání tahů je použit algoritmus zpětného vyhledávání (backtracking). Algoritmus dělí vyhledávání na dvě části: 1. Levou část, která se skládá z písmen nalevo od kotvy. Kotva je čtverec desky vůči kterému hledáme vhodná slova. 2. Pro každou levou část nejdeme veškerá porovnání pravé části. Pravá část jsou písmena napravo od kotvy. 7
Levá část bude obsahovat buď písmena ze zásobníku, nebo bude z písmen již na desce umístěných. Jestli políčko desky předcházející kotvě vlevo je prázdný, pak naplníme levou část ze zásobníku písmen. Pro každou takovou levou část, se pokusíme z kotvy rozšířit pravou část tak, aby výsledná posloupnost písmen tvořila slova. Jestli políčko desky vlevo od kotvy je obsazené, pak toto písmeno nebo tyto písmena v řadě představují levou část, a ji zkusíme rozšířit vpravo písmeny ze zásobníku. Pseudokód algoritmu: LeváČást(ČástSlova, uzel N ve slovníkové struktuře, limit) PraváČást(ČástSlova, N , KotvaPolíčka) if limit > 0 then for každou hranu E vycházející z uzlu N if písmeno l hrany E je v zásobníku then -vyjmi písmeno l ze zásobníku -nechť N’ je uzel na který ukazuje odkaz z N a obsahuje písmeno l -LeváČást (ČástSlova . l , N’ , limit - 1) -Vlož písmeno l zpět do zásobníku
PraváČást(ČástSlova, uzel N ve slovníkové struktuře, políčkoDesky) if políčkoDesky je prázdné then SprávnýTah(ČástSlova) for každou hranu E vycházející z uzlu N if písmeno l hrany E je v zásobníku and písmeno l vyhovuje KřížováKontrola then -vyjmi písmeno l ze zásobníku -nechť N’ je uzel na který ukazuje odkaz z N a obsahuje písmeno l -nechť dalšíPolíčko je políčko vpravo od políčkoDesky -PraváČást(ČástSlova . l, N’, dalšíPolíčko) -Vlož písmeno l zpět do zásobníku else -nechť l je písmeno obsazeného políčkoDesky If N má hranu E směřující k uzlu N’, který obsahuje l then -nechť dalšíPolíčko je políčko vpravo od políčkoDesky - PraváČást(ČástSlova . l, N’, dalšíPolíčko)
8
Legenda k některým pojmům: Limit
– souvislý počet nekotevních polí vlevo od kotvy
hrana E
– odkaz na následující písmeno (uzel) ve slovníkové struktuře
KřížováKontrola –
kontrola platnosti slova jak ve sloupci, tak v řádku vzhledem k políčku hrací desky
Tento algoritmus nalezne pro kotevní políčko veškerá vhodná slova, která ukládá do proměnné ČástSlova. Funkce SprávnýTah bude vyhodnocovat body za daný tah a ukládat slovo pouze s nejvyšším bodovým hodnocením. Přestože algoritmus vyhledává nejvhodnější tah „hrubou silou“, je při dnešní výkonné technice a v případě dostatečně bohatého slovníku pro člověka silným soupeřem.
4 Realizace Popis jednotlivých tříd.
4.1 Třída Hráč Tato třída modeluje hráče hry. Hráč potřebuje vědět jaké má bodové skóre (metoda GetSkore) a také jej nastavit (metoda SetSkore). Pro potřeby herního cyklu, který se liší v případě hry člověka a počítače je třeba znát identitu hráče (metoda isHracClovek). Každý hráč má svůj vlastní stojánek písmen, proto je implementována třída
Stojanek
a
pro
jeho
obsluhu
jsou
metody
GetPismenoVeStojankuHrace(pozice), která vrací písmeno na zadané pozici. Pozice je určena klikem myši do stojánku. Pro informaci hráče, které písmeno ve stojánku si vybral, je toto vysvíceno žlutou barvou. Označení nebo zrušení označení se provádí pomocí metod SetOznacPismenoStojanku a SetOdznacPismenoStojanku. Označení je provedeno levým tlačítkem myši na určeném písmenu a odznačení pravým tlačítkem myši. Vytažení písmene ze stojánku se provede metodou VytahniOznacenePismeno, vyjme označené písmeno a vrací je k dalšímu zpracování, tedy vložení na hrací desku. V případě, že hráč chce písmeno umístěné na desku vrátit zpět do stojánku, vyhoví mu metoda VratPismenoDoStojanku, která po stisku pravého tlačítka myši nad zadaným písmenem v hrací ploše toto předá této metodě ke zpracování a ta jej umístí na poslední pozici stojánku. Po skončení tahu, kdy byla použita písmena ze stojánku je potřeba tento doplnit metoda
9
doplnStojanek se postará o doplnění písmen z pytlíku. Informaci o prázdném stojánku zprostředkuje metoda isPrazdnyStojanek.
4.2 Třída HerniPlan Tato třída provádí operace nad herní plochou. Zprostředkovává vizuální informaci o rozmístění políček a jejich barevné prosvícení zobrazSachovnici informuje také hráče o tom kdo je na tahu a kolik má kdo bodů viz info na pravé straně okna (metoda zobrazInfo). Pro umístění předaného písmene slouží metoda umistiPismeno a pro jeho vyjmutí vyjmiPismeno.
Zobrazení zásobníku hráče je provedeno metodou
zobrazZasobnik . Pro potřeby výpočtů souřadnic políček a identifikace kliku myši následující metody předávají rozměry herního plánu GetKonecSachovniceXY, GetZacatekZasobnikuY,
GetKonecZasobnikuY,
GetKonecZasobnikuX.
Pro korektní průběh hry je nutné rozlišovat písmena již na desku vložená v minulých tazích metoda
isPoleZamceno
od
písmen
umístěných
v aktuálním
tahu
metoda
isPoleObsazeno. Po provedení tahu a jeho kontrole (metoda isPlatnostTahu) zamkne metoda zamkniPole umístěná písmena na desce. Tím znemožní jejich manipulaci v dalších tazích. Při dokončení tahu a kontrole správnosti a platnosti slov za pomocí slovníku, provede metodou BodoveHodnoceniTahu bodové ohodnocení. Pro správnou činnost algoritmu generování tahů je třeba provést křížovou kontrolu správnosti slova, kterou provádí metoda isKrizovaKontrola přes zadané políčko. Slova, která se v tomto poli kříží musí tvořit smysluplné celky. Při vkládání písmen hráče člověka, je prováděna kontrola správnosti umístění. Písmena dle pravidel musí být vedle sebe, toto hlídá metoda isVedlePismena jejíž činností je zjistit zda právě vkládané písmeno sousedí s již vloženým v aktuálním tahu.
4.3 Třída Pytlik Třída pytlík reprezentuje pytlík s písmeny. Písmena jsou načítána z textového souboru pytlík.txt a jsou jim přidělovány bodová hodnocení rovněž z textového souboru hodnoty.txt. Operace nad pytlíkem jako vytažení písmene zajistí metoda vytahniPismeno, vložení písmene vlozPismeno, a informaci o zbývajícím počtu písmen dává GetPocetPismen,
10
pro kontrolu vyprázdnění pytlíku a tím pádem i předzvěst konce hry zajišťuje metoda isPrazdnyPytlik.
4.4 Třída Pismeno Reprezentuje písmeno ve hře. Toto písmeno má název a bodovou hodnotu. Manipulaci s těmito položkami provádí metoda. S názvem to jsou metody GetNazev, SetNazev a s bodovým hodnocením GetBodovaHodnota, SetBodovaHodnota. Metoda nastavení bodů za písmeno se používá pouze při načítání písmen do pytlíku. V průběhu hry nelze body za písmeno měnit.
4.5 Třída Stojanek Reprezentuje zásobník písmen. Manipulace s písmeny ve stojánku je vyjmutí písmene ze stojánku (metoda vytahniPismeno). Písmeno k vyjmutí musí být nejprve označeno označení
provede
SetOdznacPismeno.
metoda Kde
SetOdznacPismeno je
takto
označené
a
odznačení
písmeno
sdělí
metoda metoda
GetPoziceOznacenehoPismene . Do stojánku je třeba také písmena vkládat. Vložení písmene obstará metoda vlozPismeno. Informaci jaké písmeno se nachází na dané pozici vrací metoda GetPismenoVeStojanku.
4.6 Třídy Slovnik, Uzel, SpojovySeznam Tato třídy slouží pro tvorbu a obsluhu slovníku slov. Třída SpojovýSeznam reprezentuje datovou strukturu spojového seznamu. Jeho prvkem je odkaz na následující prvek spojového seznamu a odkaz na následující uzel. Operace nad spojovým seznamem jsou: vrácení následujícího prvku metodou getDalsiPrvek, vrácení odkazu prvku na uzel metodou getUzel a přiřazení odkazu na uzel prvku seznamu metodou setUzel. Třída Uzel v sobě implementuje SpojovySeznam. Uzel představuje jeden prvek stromové slovníkové struktury Trie a SpojovySeznam sdružuje odkazy na následující uzly (písmena slova). Uzel dále obsahuje písmeno. Informaci, jaké písmeno uzel představuje,
11
zprostředkuje metoda getPismeno. Zda uzel (písmeno v něm obsažené) představuje konec slova, pak metoda isKonecSlova vrací TRUE. Nastavení uzlu jako konečného prvku slova zprostředkuje metoda setKonecSlova. Tvorba stromové struktury je zajištěna přidáváním jednotlivých uzlů (metoda pridejPismeno) , a při jeho vytvoření tato metoda vrátí ukazatel na takto nově vytvořený uzel. Pro potřeby vyhledávání slov, je použita metoda isNasledujePismeno, která bere od kořene stromu jednotlivé uzly tak, že projde vnitřní spojový seznam uzlů následníků a ujišťuje, zda obsahují hledaný znak. Pokud jej najde, vrycí odkaz nalezeného písmene (uzlu), v opačném případě nenalezení indikuje NULL. Pro potřeby algoritmu tvorby slov, kdy je třeba projít všechny odkazy na následníky, je vytvořena metoda getNasledujiciUzel. Třída Slovnik v sobě implementuje třídu Uzel a slouží pro operace nad celými slovy. Tato třída také zprostředkovává prostřednictvím metody pridejSlovo vkládání slov datové slovníkové struktury. Slova jsou načítána z textového souboru velky_slovnik.txt. Princip načítání slova z textového souboru je takový, že bere posloupnost písmen a ukončení jakýmkoliv jiným znakem než je písmeno je bráno jako konec slova. Tato činnost je zajištěna pomocí třídy Soubor. Slovnik disponuje schopnostmi jako je isSlovoVeSlovniku, tato metoda předá informaci zda ucelené slovo je obsaženo ve stromové struktuře, poslední písmeno (uzel) musí mít příznak konce slova. Dále je implementována metoda isNasledujePismeno, která bere jednotlivá jí předaná písmena a zjišťuje, zda je nějaký následník, který obsahuje hledané písmeno, pokud ano, vrací TRUE a posouvá se na nalezeného následníka. V případě neúspěchu hledání, resetuje svoje vnitřní stavy vrací FALSE a následné hledání začíná opět od kořene stromu. Pro potřeby algoritmu tvorby slov na hrací desce, je zde k dispozici metoda getNasledujiciPismenaUzlu, která prohledává všechny následníky daného uzlu, vrací jako výsledek jejich písmena a adresy těchto uzlů. Pro potřeby křížové kontroly slova generovaného počítačem je k dispozici metoda isPlatneCastecneSlovo, která z parametru jí předaného slova zjistí, zda je tato část obsažena ve slovníku.
4.7 Třída GeneratorTahu Tato třída ztvárňuje UI implementací výše uvedeného algoritmu. Pro generování levé části slova slouží metoda levaCast a pro rozšíření pravé části slova metoda pravaCast.
12
4.8 Třídy GameEngine a Scrabble Jak již bylo uvedeno výše, třída GameEngine odděluje programový kód pro Windows od samotného kódu hry. Ve třídě GameEngine je kód pro obsluhu Windows a ve třídě Scrabble je kód pro obsluhu hry, strukturován dle návrhu implementace.
4.9 Podpůrné třídy Třída
Soubor
slouží
pro
načítání
dat
z textového
souboru.
Metoda
ctiZnakSouboru čte ze souboru znak po znaku, dokud nedojde na konec souboru. Metoda ctiSlovoSouboru načte ucelený sled písmen a předá jej k dalšímu zpracování, jakýkoliv znak mezi písmeny je brán jako konec slova. Pro čtení bodových hodnot je zde metoda ctiCisloSouboru. Sled jednotlivých číslic je brán jako jedno celé číslo, jakýkoliv jiný znak umístěný mezi tento sled je brán jako konec čísla. Třída Slovo slouží pro zpracování jednotlivých písmen jako celku a je využívána UI při generování slov a rozhodování zda slovo uchovat či zahodit. Disponuje metodami přidání písmene
na
konec
slova
pridejPismeno,
odebrání
písmene
z konce
slova
odeberPismenoZKonceSlova, vymaže celý obsah metoda vymaz. Dále je schopna předat informaci jaké písmeno je na dané pozici ve slově getPismenoSlova, a celkový počet písmen pocetPismen. Pro potřeby rozhodování algoritmu UI uchovává a také vrací bodovou hodnotu slova. Třída Políčko je využívána třídou HerniPlan, který implementuje tuto třídu. Jednotlivá políčka hrací plochy musí uchovávat informaci o bonusech slov (GetBonusSlova, SetBonusSlova)
a písmen (GetBonusPismena, SetBonusPismena) a jaké písmeno je do
nich vloženo(GetPismeno, SetPismeno). Třída LevaCast je pro obsluhu levé části generovaného slova, jelikož tato nemůže být při generování ihned umístěna na hrací desku. To obsluhují metody umistiNaHraciDesku a vyjmiZHraciDesky. Dále metody na přidání a odebrání písmen.
13
5 Výsledky testování Testování hrou, takto by se dala nazvat tato část práce. Testování aplikace bylo provedeno tak, že jsem navolil hráče počítač – počítač a provedl několik zkušebních her, které vykazovaly některé chyby v kódu, které jsem se snažil opravit. Dále byly testovány varianty člověk - počítač a člověk - člověk. Přes veškerou snahu o eliminaci chyb programu se obávám, že vzhledem k rozsáhlosti projektu chyby jsou.
6 Závěr Téma této bakalářské práce jsem si zvolil, z důvodu tvorby aplikace v jazyce C++, ve kterém jsem si chtěl prohloubit znalosti a vyzkoušet tvorbu hry pod operačním systémem Windows. Zajímavá je i problematika UI a její realizace. Cílem práce bylo vytvořit hru Scrabble s GUI, která bude schvalovat a vyhodnocovat tahy hráče. Myslím, že tato část se mi podařilo úspěšně vyřešit, i přes jisté obtíže při návrhu i samotném
programovém
zpracování.
Pro
generování
tahů
počítače
navrhnout
a
implementovat jednoduchou umělou inteligenci. Tato část byla vytvořena za pomocí slovníkové datové struktury Trie, generátoru tahů a rozhodovacího mechanizmu výběru slova s vyšším bodovým hodnocením. Aplikace je napsána v jazyce C++.
14
7 Seznam použité literatury [1] The world's fastest Scrabble program http://portal.acm.org/citation.cfm?id=42420
[2] Michael Morisson, Naučte se programovat počítačové hry za 24 hodin [3] Ing. Miroslav Virius, CSc., Programování v C++. Vydavatelství ČVUT 2004 [4] Scrabble http://cs.wikipedia.org/wiki/Scrabble
[5] Anna Rybínová, Historie Scrabble http://www.hrejsi.cz/scrabble/historie.htm
[6] Genetický algoritmus http://cs.wikipedia.org/wiki/Genetick%C3%BD_algoritmus
[7] Algoritmy zpracování řetězců proteus.fav.zcu.cz/~mautner/Pt/Zpracovani_retezcu_II.ppt
[8] Trie http://cs.wikipedia.org/wiki/Trie
15
A Seznam použitých zkratek Trie
Terminal Nodes are Cicled
DAWG
Directed Acyclic Word-Graph
GUI
Graphical user interface
UI
Umělá inteligence
API
Application Programming Interface
16
B Obsah přiloženého CD Scrabble Scrabble
Adresář s programovým kódem- třídy, rc zdroje
Text BP BP Scrabble.docx BP Scrabble word_97_2003.doc BP Scrabblex.pdf
Texty bakalářské práce Formát Word 2007 Formát Word 97-2003 Formát PDF
Uživatelská příručka Uživatelská příručka.pdf
Uživatelská příručka pro hrání hry
17
