SCRABBLE PRO MOBILNÍ TELEFONY

ˇ Í TECHNICKE´ V BRNEˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY

ˇ ÍCH TECHNOLOGIÍ FAKULTA INFORMACN ˇ ÍTACOV ˇ ´ ´ ´ U ˚ USTAV POC YCH SYSTEM FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER SYSTEMS

SCRABBLE PRO MOBILNÍ TELEFONY

´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS

´ AUTOR PRACE AUTHOR

BRNO 2007

ˇ ˇ ˇ CKA ONDREJ KANE

ˇ Í TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY

ˇ ÍCH TECHNOLOGIÍ FAKULTA INFORMACN ˇ ˇ ´ ´ ´ ´ U ˚ USTAV POCITACOVYCH SYSTEM FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF COMPUTER SYSTEMS

SCRABBLE PRO MOBILNÍ TELEFONY SCRABBLE FOR CELLUAR PHONES

´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS

´ AUTOR PRACE

ˇ ˇ ˇ CKA ONDREJ KANE

AUTHOR

´ VEDOUCÍ PRACE SUPERVISOR

BRNO 2007

¨ Ing. RUDOLF SCHONECKER

Abstrakt Práce zkoumá moˇznosti vyhledávac´ıch algoritm˚u a slovn´ıkových datových struktur na platformách s omezeným výpoˇcetn´ım výkonem a dostupnou pamˇet´ı (typicky jde o mobiln´ı telefony) a ukazuje jejich výhody a nevýhody v souvislosti s touto platformou. Konkrétnˇe se zabývá jejich uplatnˇen´ım ve známé stoln´ı hˇre SCRABBLE. Pouˇz´ıvá Appel-Jacobson˚uv vyhledávac´ı algoritmus na hledán´ı moˇzných tah˚u. Algoritmus má k dispozici slovn´ık se vˇsemi slovy, který je uloˇzen v tzv. struktuˇre DAWG, která umoˇznˇ uje slova rychle vyhledávat a souˇcasnˇe zajiˇst’uje kompresi obsaˇzených slov, takˇze je velikost slovn´ıku v pamˇeti vzhledem k c´ılové platformˇe dostateˇcnˇe malá. Výsledná Java aplikace pro mobiln´ı telefon (MIDP 2.0) pˇridává grafické rozhran´ı a ovládán´ı hry a umoˇznˇ uje tak hran´ı hry SCRABBLE jak proti umˇelé inteligenci, tak proti jinému cˇ lovˇeku.

Kl´ıcˇ ová slova Scrabble, Univerzáln´ı slovn´ıková struktura, USS, DAWG, Appel-Jacobson˚uv algoritmus, prohledáván´ı stavového prostoru, Umˇelá inteligence, Hern´ı heuristiky

Abstract This paper deals with an usage of searching algorithms and lexical data structures for platforms with limited computing power and accessible memory (celluar phones and similar) in SCRABBLE brand crossword game. There are also shown its advantages and disadvantages on this platform. The Appel-Jacobson searching algorithm is used to search possible moves. The lexicon with all words is available for this algorithm. It’s stored in Directed Acyclic Word Graph (DAWG), which provides fast data searching and data compression too, so the size of the lexicon is comparatively small considering the target platform. The final Java application for celluar phones (MIDP 2.0) adds graphical interface and game control so it provides playing SCRABBLE brand crossword game against artificial intelligence or against human.

Keywords Scrabble, Trie, Directed Acyclic Word Graph, DAWG, Appel-Jacobson algorithm, Backtracking games, Artificial intelligence, Game heuristics

Citace Ondˇrej Kanˇecˇ ka: Scrabble pro mobiln´ı telefony, bakaláˇrská práce, Brno, FIT VUT v Brnˇe, 2007

Scrabble pro mobiln´ı telefony Prohlásˇen´ı Prohlaˇsuji, zˇ e jsem tuto bakaláˇrskou práci vypracoval samostatnˇe pod veden´ım Ing. Rudolfa Schöneckera ....................... Ondˇrej Kanˇecˇ ka 14. kvˇetna 2007

Podˇekován´ı Dˇekuji Ing. Rudolfovi Schöneckerovi za odborné veden´ı bakaláˇrské práce, za poskytován´ı rad a materiál˚u.

c Ondˇrej Kanˇecˇ ka, 2007.

Tato práce vznikla jako sˇkoln´ı d´ılo na Vysokém uˇcen´ı technickém v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Práce je chránˇena autorským zákonem a jej´ı uˇzit´ı bez udˇelen´ı oprávnˇen´ı autorem je nezákonné, s výjimkou zákonem definovaných pˇr´ıpad˚u.

Obsah ´ 1 Uvod

3

2

˚ Jiné zpusoby implementace 2.1 70. a 80. léta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Pouˇzit´ı statistických metod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

Reprezentace slovn´ıku 3.1 Univerzáln´ı slovn´ıková struktura 3.1.1 Implementace USS . . . 3.1.2 Hledán´ı slova . . . . . . 3.2 DAWG . . . . . . . . . . . . . 3.2.1 Z USS do DAWG . . . 3.3 Uloˇzen´ı slovn´ıku v souboru . . 3.3.1 Struktura uzlu . . . . . .

4

5

5 5 6

. . . . . . .

7 7 7 8 8 10 11 11

. . . . . . . .

12 12 12 12 13 13 13 15 15

Výbˇer tahu 5.1 Pouˇzité heuristiky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Testován´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16 17 17

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

˚ algoritmus Appel-Jacobsonuv 4.1 Pˇr´ıprava hrac´ı plochy . . . . . . . . . . . . . . 4.1.1 Redukce problému do jednoho rozmˇeru 4.1.2 Cross-Check mnoˇziny . . . . . . . . . 4.1.3 Anchors - spojovac´ı pol´ıcˇ ka . . . . . . 4.2 Generován´ı samotného tahu . . . . . . . . . . 4.2.1 Levá cˇ a´ st . . . . . . . . . . . . . . . . 4.2.2 Oˇsetˇren´ı výjimek . . . . . . . . . . . . 4.2.3 Implementaˇcn´ı doporuˇcen´ı . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

. . . . . . .

. . . . . . . .

ˇ 6 Cesk´ y Scrabble

19

7

20 20 20 21 21 22 22

Implementace 7.1 Prototypové programy . . 7.2 Objektový návrh . . . . . 7.3 Oddˇelené grafické rozhran´ı 7.4 Omezen´ı c´ılové platformy 7.4.1 Práce se soubory . 7.4.2 Velikost pol´ı . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

1

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

7.4.3 8

Otev´ırán´ı souboru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Závˇer

22 23

2

Kapitola 1

´ Uvod Doba, kterou právˇe proˇz´ıváme, bývá nazývána dobou informaˇcn´ıch technologi´ı. Velkou zásluhu na tom maj´ı osobn´ı poˇc´ıtaˇce, které dnes slouˇz´ı k práci nebo k zábavˇe témˇeˇr v kaˇzdé domácnosti. Jeˇstˇe d˚uleˇzitˇejˇs´ı uplatnˇen´ı se pro nˇe nacház´ı v r˚uzných spoleˇcnostech a instituc´ıch. Provoz mnoha firem je na nich dnes pˇr´ımo závislý a k základn´ımu vzdˇelán´ı cˇ lovˇeka patˇr´ı i znalost ovládán´ı osobn´ıch poˇc´ıtaˇcu˚ , pˇresnˇeji aplikac´ı, které jsou na nich vykonávané. K masovému rozˇs´ıˇren´ı osobn´ıch poˇc´ıtaˇcu˚ doˇslo v USA v 80. letech, u nás k tomu doˇslo o deset let pozdˇeji. V souˇcasné dobˇe proˇz´ıváme jistou paralelu, tentokrát jde ale o mobiln´ı telefony a podobná pˇrenosná zaˇr´ızen´ı. Dnes jsou mobiln´ı telefony jeˇstˇe v´ıce rozˇs´ıˇrené neˇz osobn´ı poˇc´ıtaˇce. To je zp˚usobeno jejich cenou a také to plyne z jejich urˇcen´ı - jde o vˇec, u které se pˇredpokládá, zˇ e j´ı bude vlastnit a pouˇz´ıvat jedna osoba. Nejde tedy o pomˇer jedno zaˇr´ızen´ı na jednu domácnost (jako u PC), ale o pomˇer jedno zaˇr´ızen´ı na jednu osobu. Trh s mobiln´ımi telefony je dnes velice perspektivn´ı, stejnˇe tak jako trh s aplikacemi pro nˇe urˇcenými. Tato pˇrenosná zaˇr´ızen´ı bývaj´ı oznaˇcována jako zaˇr´ızen´ı s omezeným výpoˇcetn´ım výkonem. Je to proto, zˇ e jsou porovnávána s dneˇsn´ımi osobn´ımi poˇc´ıtaˇci, které pˇredstavuj´ı pro vˇetˇsinu lid´ı výpoˇcetnˇe nejsilnˇejˇs´ı stroje - r˚uzné servery pro vˇedecké výpoˇcty apod. nejsou zaˇr´ızen´ı pouˇz´ıváná masovˇe mezi lidmi. Svým výpoˇcetn´ım výkonem a dostupnou pamˇet´ı se mobiln´ı telefony vrac´ı zpˇet do 80. let. Technologicky ale nijak nezaostáváj´ı za osobn´ımi poˇc´ıtaˇci, jejich omezen´ı plynou z platformy, kterou pˇredstavuj´ı a u které souˇcasnˇe urˇcuj´ı vývoj. U této platformy jde pˇredevˇs´ım o minimalizaci hardwarových prostˇredk˚u, tj. snaha zmenˇsovat fyzické rozmˇery jednotlivých hardwarových komponent a souˇcasnˇe zmenˇsovat jejich poˇcet. I zde vˇsak plat´ı, zˇ e výpoˇcetn´ı výkon neustále roste. Moˇznosti mobiln´ıch telefon˚u jsou dále rozˇsiˇrovány pouˇz´ıván´ım operaˇcn´ıch systém˚u (Symbian, MS Windows Mobile Phone Edition apod.). Výpoˇcetn´ı výkon prvn´ıch osobn´ıch poˇc´ıtaˇcu˚ byl znatelnˇe menˇs´ı neˇz dnes, ale i tyto stroje byly uˇz schopny provádˇet matematicky nároˇcné operace. Pro mobiln´ı telefony a podobná zaˇr´ızen´ı dneˇsn´ı doby plat´ı v podstatˇe to samé. K dispozici je mnoˇzina aritmetických, logických, bitových a relaˇcn´ıch operac´ı. Mikroprocesor mobiln´ıho telefonu umoˇznˇ uje programátorovi uˇzivatelských aplikac´ı to, co CPU osobn´ıho poˇc´ıtaˇce. Z tohoto pohledu se tedy nemus´ıme nijak omezovat c´ılovou platformou a m˚uzˇ eme vytváˇret aplikace, které sekvenˇcnˇe provádˇej´ı mnoho r˚uzných matematických operac´ı, i kdyˇz doba jejich provádˇen´ı je nˇekolikanásobnˇe vˇetˇs´ı neˇz u dneˇsn´ıch PC. Hlavn´ım c´ılem projektu bylo vytvoˇrit hru SCRABBLE pro mobiln´ı telefon, která umoˇznˇ uje hran´ı proti umˇelé inteligeci. V tomto pˇr´ıpadˇe pˇredstavuje cˇ asovˇe nároˇcné velké mnoˇzstv´ı sekvenˇcnˇe provádˇených matematických operac´ı prohledáván´ı stavového prostoru, které je tˇreba provádˇet kv˚uli generován´ı tah˚u umˇelé inteligence. Z uvedených vlastnost´ı aplikace je moˇzné odvodit d´ılˇc´ı c´ıle práce, kterých bylo tˇreba dosáhnout. Jde pˇredevˇs´ım o tˇri hlavn´ı problémy:

3

• Naj´ıt vhodný algoritmus na vyhledávan´ı moˇzných tah˚u. • Naj´ıt vhodnou heuristiku na výbˇer z nalezených tah˚u. • Naj´ıt vhodnou reprezentaci slovn´ıku, ve kterém jsou uloˇzena vˇsechna validn´ı slova. Konkrétn´ı ˇreˇsen´ı tˇechto problém˚u je popsáno v kapitolách 3, 4 a 5.

4

Kapitola 2

˚ Jiné zpusoby implementace Scrabble je typ hry s neúplnou informac´ı - neznáme p´ısmena, která maj´ı naˇsi soupeˇri v zásobn´ıku. Pouze na konci hry, kdyˇz uˇz v sácˇ ku nejsou zˇ a´ dné kameny, m˚uzˇ eme toto odvodit a teoreticky tedy pouˇz´ıt algoritmus pro hry s u´ plnou informac´ı (napˇr. MinMax). Ve vyhledávac´ım algoritmu výsledné aplikace se toto ˇreˇsen´ı nevyskytuje. Pracuje se pouze s algoritmy s neúplnou informac´ı. Dále jsou popsány r˚uzné formy implementace hry Scrabble. Jedná se o programy napsané v sedmdesátých a osmdesátých letech, po nich následuje popis jednoho zcela odliˇsného zp˚usobu ˇreˇsen´ı výbˇeru tahu.

2.1

70. a 80. léta

Programy, které hraj´ı Scrabble a samy generuj´ı tahy se zaˇcaly psát s rozvojem samotné discipl´ıny umˇelé inteligence. Jistý zvrat ve vývoji znamenal Appel-Jacobson˚uv algoritmus (viz 3) v kombinaci se slovn´ıkem USS cˇ i DAWG (viz 4). Vˇetˇsina dneˇsn´ıch aplikac´ı [8] pouˇz´ıvá tento algoritmus. V sedmdesátých a osmdesátých letech vzniklo nˇekolik v´ıce cˇ i ménˇe u´ spˇesˇných program˚u na hran´ı Scrabblu, které nevyuˇz´ıvaj´ı Appel-Jacobson˚uv algoritmus a které stoj´ı za zm´ınku: MONTY Komerˇcn´ı produkt vhodný pro mnoˇzstv´ı poˇc´ıtaˇcu˚ a zaˇr´ızen´ı té doby. Pouˇz´ıvá strategický i taktický koncept hran´ı. Expertn´ı hrácˇ i ho trvale porázˇ eli. Peter Turcan napsal hrácˇ e Scrabblu, který prohledává slova ve slovn´ıku podle jejich délky a zaˇc´ıná nejdelˇs´ımi. Pro kaˇzdý tah se rozhoduje zda a kde by mˇel být um´ıstˇen na hrac´ı ploˇse. Jeho program neusiluje a o nˇejaký nepˇr´ıjemný tah pro soupeˇre ale pouˇz´ıvá ohodnocuj´ıc´ı funkci, která je v´ıce d˚umyslná neˇz jen výbˇer nejlépe ohodnoceného tahu. Bere v u´ vahu aktuáln´ı skóre hrácˇ u˚ , aktuáln´ı stav hrac´ı plochy a kameny zbylé v zásobn´ıku. Peter Weinberger napsal generátor tah˚u, který nejdˇr´ıve ohodnot´ı kaˇzdé pol´ıcˇ ko na hrac´ı ploˇse uloˇz´ı informaci o p´ısmenech a pozic´ıch, které vyhovuj´ı (podobnˇe jako u Appel-Jacobsona). Pak jsou uloˇzeny dalˇs´ı informace o zásobn´ıku a hrac´ı ploˇse jako celku. Potom se pod´ıvá na kaˇzdé slovo ve slovn´ıku a rychlými globáln´ımi testy kaˇzdé nevyhovuj´ıc´ı slovo vyˇrad´ı. Zbylá slova jsou podrobena rychl´ım lokáln´ım test˚um (pro kaˇzdé pol´ıcˇ ko) a vyˇrad´ı ty, která nelze um´ıstit na jednotlivé pozice. P´ısmena kaˇzdého zbylého slova jsou zkouˇsena na kaˇzdé pozici a zjiˇst’uje se, zda tvoˇr´ı validn´ı tahy. Program nemá zˇ a´ dný strategický koncept - jednoduˇse vyb´ırá nejlépe ohodnocený tah. Stuart Shapiro napsal nˇekolik program˚u hraj´ıc´ıch Scrabble v jazyc´ıch SIMULA a Pascal. Pouˇz´ıvaj´ı slovn´ıky uloˇzené jako strom, kde kaˇzdý uzel reprezentuje p´ısmeno (3.1). Pr˚uchod stromem od 5

koˇrene generuje slovo, které je tvoˇreno z p´ısmen procházených uzl˚u. P´ısmena se pˇri pr˚uchodu objevuj´ı pˇribliˇznˇe v poˇrad´ı podle hodnoty p´ısmene ve Scrabblu (sestupnˇe). D˚uvod, proˇc se výsˇe hodnocená p´ısmena dávaj´ı bl´ızˇ e ke koˇreni stromu je, aby se nejhodnotnˇejˇs´ı slova naˇsla dˇr´ıve(v pˇr´ıpadˇe cˇ a´ steˇcného pr˚uchodu slovn´ıkem). Generátor tah˚u nezkouˇs´ı vˇsechny moˇzné pozice na hrac´ı ploˇse, pouze pozice pˇredem posouzené. Jakmile je tah shledán vyhovuj´ıc´ım (pˇrinejmenˇs´ım podle minimáln´ıho skóre), je vybrán. U popsaných algoritm˚u jsou doby generován´ı tah˚u r˚uzné. Záleˇz´ı na velikosti jejich slovn´ık˚u. Na soucˇ asných stroj´ıch jsou to ˇra´ dovˇe sekundy aˇz des´ıtky sekund. Appel-Jacobson˚uv algoritmus se výraznˇe odliˇsuje právˇe rychlost´ı a v porovnán´ı s nimi je mnohonásobnˇe rychlejˇs´ı. Záleˇz´ı ale na konkrétn´ım tahu. Pokud má hrácˇ k dispozici zˇ ol´ık nebo dokonce oba dva, pak se velikost prohledávaného prostoru m˚uzˇ e enormnˇe zvˇetˇsit a naj´ıt nejlepˇs´ı tah netrvá desetiny sekund, ale des´ıtky sekund.

2.2

Pouˇzit´ı statistických metod

Za zm´ınku stoj´ı ˇreˇsen´ı [4], kdy je pro výbˇer tahu na zaˇca´ tku a ve stˇredn´ı cˇ a´ sti hry pouˇzit algoritmus pro hry s u´ plnou informac´ı v kombinaci s metodou Monte Carlo. Algoritmus je v tomto pˇr´ıpadˇe nˇekolikrát proveden a jeho r˚uzné výsledky jsou statisticky vyhodnoceny. Podle tohoto statistického výsledku lze zjistit tah, který bude pravdˇepodobnˇe nejvýhodnˇejˇs´ı. Podstata metody Monte Carlo ale spoˇc´ıvá v mnohonásobném proveden´ı daného algoritmu. Kolikrát se algoritmus provede, závis´ı na poˇzadované pˇresnosti. Z toho lze tuˇsit, zˇ e toto ˇreˇsen´ı nen´ı vhodné pro naˇse u´ cˇ ely, kde nám jde pˇredevˇs´ım o rychlost nalezen´ı nejvýhodnˇejˇs´ıho tahu.

6

Kapitola 3

Reprezentace slovn´ıku Bˇehem generován´ı tahu poˇc´ıtaˇcem se prohledáván´ım do hloubky hledaj´ı vˇsechny moˇzné kombinace p´ısmen v zásobn´ıku a na hrac´ı ploˇse, které tvoˇr´ı slova uloˇzená ve slovn´ıku. Vzhledem ke zp˚usobu prohledáván´ı a k tomu, zˇ e je kladen velký d˚uraz na rychlost prohledáván´ı a v neposledn´ı ˇradˇe i na velikost slovn´ıku, je reprezentace slovn´ıku napˇr. jako abecednˇe seˇrazený seznam slov nevhodná. Vhodná struktura pro tyto u´ cˇ ely je tzv. univerzáln´ı slovn´ıková struktura (USS, Trie). Tuto strukturu lze dále pˇrevést na tzv. strukturu DAWG (Directed Acyclic Word Graph), která poskytuje srovnatelnou rychlost hledán´ı slov, ale velikost takto uloˇzeného slovn´ıku m˚uzˇ e být i nˇekolikrát menˇs´ı neˇz USS.

3.1

Univerzáln´ı slovn´ıková struktura

Jde o druh stromu, který d´ıky svým vlastnostem automaticky zajiˇst’uje datovou kompresi v pamˇeti a neomezuje pˇr´ıstup k uloˇzeným informac´ım. Viz [10]. Základn´ı myˇslenka USS vycház´ı z následuj´ıc´ıho zjiˇstˇen´ı: souˇca´ st´ı mnoha slov jsou stejné koˇreny a slova se r˚uzn´ı pouze svými pˇredponami a pˇr´ıponami. Vezmˇeme napˇr´ıklad skupinu slov: KROCAN, KROKET, KRAJKA, KRONIKA, KRAJ. Pokud je uloˇz´ıme ve tvaru stromu podle obrázku 3.1, pak m´ısto p˚uvodn´ıch 29 znak˚u jich uloˇz´ıme 17. V pˇr´ıpadˇe obsáhlejˇs´ıho slovn´ıku bude zisk jeˇstˇe vˇetˇs´ı. Pˇredpokládáme, zˇ e ve slovn´ıku uloˇz´ıme ve velké m´ıˇre série slov zaˇc´ınaj´ıc´ıch stejnými p´ısmeny - napˇr. u´ plné skloˇnován´ı podstatných jmen atd.

3.1.1

Implementace USS

Implementace se ponˇekud liˇs´ı od bˇezˇ ných zp˚usob˚u ukládán´ı slov. Neukládaj´ı se zde totiˇz slova nebo jejich cˇ a´ sti a pˇresto je u´ cˇ el splnˇen. V jazyce C m˚uzˇ e deklarace struktury USS vypadat napˇr takto: typedef struct slovnik { struct slovnik *t[N+1]; } USS; Jedná se o deklaraci rekurzivn´ıho typu, jehoˇz jediným prvkem je pole ukazatel˚u na hodnoty stejného typu. Znaku “A” odpov´ıdá prvek t[0], znaku “B” zase t[1] atd. Konstanta N znaˇc´ı poˇcet rozliˇsovaných p´ısmen. Posledn´ı prvek s indexem N indikuje koncový uzel - to je uzel, ve kterém konˇc´ı nˇejaké slovo. Hlavn´ı princip USS je objasnˇen na pˇr´ıkladu znázornˇeném na obrázku 3.2.

7

K R A

O

J

C

K

N

K

A

E

I

A

N

T

K

EOW

EOW

EOW

EOW

A

EOW

Obrázek 3.1: Komprese dat v USS

Abychom mohli provést názorný rozbor, omez´ıme poˇcet znak˚u abecedy na 6: A, K, L, O, P, S. P´ısmeno “A” pˇredstavuje prvn´ı ukazatel v kaˇzdém uzlu. P´ısmeno “S” je potom pˇredposledn´ı ukazatel. Posledn´ı ukazatel znaˇc´ı konec slova (EOW - End Of Word). Hodnota o konci slova nabývá jen dvou stav˚u ANO/NE (konˇc´ı/nekonˇc´ı), proto je v obrázku oznaˇcována jako TRUE / FALSE. Kaˇzdý uzel obsahuje pole t o rozmˇeru 7. Pokud je posledn´ı ukazatel roven hodnotˇe TRUE, znamená to, zˇ e v tomto m´ıstˇe dané slovo konˇc´ı. Které slovo to je lze zjistit pr˚uchodem stromu od koˇrene. Z koˇrenového uzlu se lze dostat do jakéhokoliv jiného uzlu. Chceme se tedy dostat z koˇrenového uzlu do konkrétn´ıho koncového uzlu. Bˇehem pr˚uchodu si zaznamenáváme ukazatele, které procház´ıme (tedy p´ısmena, která reprezentuj´ı). Aˇz se dostaneme do koncového uzlu, ukonˇc´ıme pr˚uchod stromem a p´ısmena hledaného slova máme zaznamenána. V pˇr´ıkladu na obrázku 3.2 jsou tedy uloˇzena tyto slova: KOLA, KOLAPS, KOLO, LOS, SAKO.

3.1.2

Hledán´ı slova

Pokud hledáme nˇejaké konkrétn´ı slovo, pak procház´ıme strom od koˇrene a v kaˇzdém uzlu cˇ teme hodnotu pˇr´ısluˇsného ukazatele, která znaˇc´ı adresu synovského uzlu. Index pˇr´ısluˇsej´ıc´ı k aktuálnˇe procházenému p´ısmenu urˇcuje, ze kterého ukazatele máme adresu cˇ´ıst. (V koˇrenovém uzlu je aktuáln´ı p´ısmeno prvn´ı p´ısmeno slova.) Bˇehem pr˚uchodu stromem pak mohou nastat tyto dvˇe situace: 1. Dostaneme se aˇz ke koncovému uzlu - hledané slovo je ve slovn´ıku. 2. Naraz´ıme na ukazatele s hodnotou NULL a nem˚uzˇ eme tedy dále procházet strom. Hledané slovo proto nen´ı ve slovn´ıku.

3.2

DAWG

Struktura DAWG je podobná USS. Také zde existuj´ı uzly, jejichˇz pr˚uchodem hledáme slova ve struktuˇre obsaˇzená. Algoritmus hledán´ı slova je stejný a pokud z˚ustane stejná i struktura uzl˚u, pak lze zcela stejný algoritmus pouˇz´ıt na hledán´ı slov v DAWG a souˇcasnˇe v USS. Rozd´ıl mezi DAWG

8

A

K

L

NULL

A

K

L

O

NULL NULL NULL

A

K

L

NULL NULL

A

K

K

O

P

L

O

K

S

L

P

L

S

O

P

O

S

P

S

K

L

O

P

A

S

L

O

K

L

P

K

L

EOW FALSE

S

A

EOW

O

P

S

O

P

S

K

L

O

P

S

K

L

O

P

S

EOW

NULL NULL NULL NULL NULL FALSE

NULL NULL FALSE

EOW

A

FALSE

NULL

A

EOW

NULL NULL NULL NULL NULL NULL TRUE

A

EOW

P

NULL NULL NULL NULL NULL

A

EOW

K

NULL NULL NULL

A

EOW

NULL TRUE

K

L

O

K

L

O

NULL NULL NULL

A

EOW


P

S

EOW

NULL NULL NULL NULL FALSE

K

L

P

S

EOW

NULL NULL FALSE

O

P

S

EOW


EOW FALSE

NULL NULL NULL NULL NULL

A

EOW

NULL NULL FALSE

NULL NULL NULL NULL

A

S

NULL NULL NULL FALSE

NULL NULL

A

P

NULL NULL FALSE

O

NULL NULL

S

EOW


Obrázek 3.2: Zápis ˇretˇezc˚u v USS

a USS je v tom, zˇ e USS tvoˇr´ı strom, zat´ımco DAWG tvoˇr´ı graf, podobný graf˚um koneˇcných automat˚u. Na obrázku 3.3 je vidˇet rozd´ıl uloˇzen´ı slov dvou slov VANA a VONA. Rozd´ıl tedy spoˇc´ıvá v tom, zˇ e zat´ımco v USS je komprese dat zaloˇzena na totoˇznosti zaˇca´ tk˚u slov, u struktury DAWG vzniká komprese dat i d´ıky stejným p´ısmen˚um na konci slova. Z obrázku 3.3 je vidˇet, zˇ e poˇcet uzl˚u ve struktuˇre DAWG je menˇs´ı, neˇz v USS. V tomto pˇr´ıpadˇe je dokonce nejmenˇs´ı moˇzný. Lze totiˇz vytvoˇrit mnoho DAWG struktur nad urˇcitou stejnou mnoˇzinou slov, ale pouze jedna má minimáln´ı poˇcet uzl˚u. Z toho také plyne hlavn´ı význam DAWG: Zat´ımco rychlost vyhledáván´ı slov v USS a DAWG je v podstatˇe stejná, tak velikost slovn´ık˚u DAWG bývá menˇs´ı, neˇz u USS. Závis´ı na typu uloˇzených slov, jaký je pomˇer mezi velikostmi tˇechto dvou struktur (obsahuj´ı-li stejnou mnoˇzinu slov). V pˇr´ıpadˇe velké podobnosti slov m˚uzˇ e být DAWG nˇekolikanásobnˇe menˇs´ı neˇz USS.

USS

DAWG

V

V

A

O

A

N

N

N

A

A

A

EOW

EOW

O

EOW

Obrázek 3.3: Rozd´ıl mezi DAWG a USS

9

3.2.1

Z USS do DAWG

Zajisté existuje mnoho zp˚usob˚u, jak vytvoˇrit DAWG strukturu. Následuje popis vytvoˇren´ı slovn´ıku DAWG s minimáln´ım poˇctem uzl˚u pomoc´ı jiˇz vytvoˇreného slovn´ıku USS dle [5]. Pˇred zaˇca´ tkem konverze z USS na DAWG je tˇreba si oznaˇcit nˇekteré u´ daje u kaˇzdého uzlu v USS: • Maska ukazatelu˚ - Informace o kaˇzdém ukazateli, zda nˇekam ukazuje nebo má hodnotu NULL. • Zanoˇren´ı - Poˇcet pˇrechod˚u z koˇrenového uzlu do daného uzlu. Koˇren má zanoˇren´ı 0. • Hloubka potomka - Nejvyˇssˇ´ı poˇcet uzl˚u, pˇres které projdete z daného uzlu do listového uzlu. Listy maj´ı hloubku potomka 0. Hlavn´ı d˚uvod oznaˇcován´ı uzl˚u je, zˇ e podle toho lze rychle zjistit, zda jsou uzly identické. Podle masky ukazatel˚u a hloubky potomka je moˇzné toto urˇcit jednoznaˇcnˇe. Proˇc to tak je bude zˇrejmé dále. Poté, co si oznaˇc´ıme uzly, si jeˇstˇe vytvoˇr´ıme pomocná pole uzl˚u. V kaˇzdém takovém poli budou uzly (jejich odkazy/reference) se stejnou hloubkou potomka. Nyn´ı máme uzly oznaˇcené a seˇrazené. Zaˇcneme s uzly s hloubkou potomka 0. Jestliˇze uzly X a y jsou identické (vˇsechny uzly s hloubkou potomka 0 jsou identické, protoˇze maj´ı stejnou masku ukazatel˚u a stejnou hloubku potomka 0), potom kaˇzdý uzel, který obsahuje ukazatel (má potomka) na uzel Y pˇresmˇeruji (pˇrep´ısˇi ukazatel) na uzel X. Kdyˇz hledáme uzly, které by mohly obsahovat ukazatele na uzel X nebo Y , pak staˇc´ı tyto uzly hledat v poli s uzly s hloubkou potomka 1 a nemus´ıme procházet celou strukturou USS. Jeˇstˇe nebylo vysvˇetleno to, proˇc pˇresmˇerujeme ukazatele na uzel X a ne na Y . Obecnˇe bychom si mohli vybrat mezi uzly náhodnˇe, ale v tomto projektu je slovn´ık uloˇzen v souboru a plat´ı zde proto urˇcitá pravidla, která jsou objasnˇena v kapitole o uloˇzen´ı slovn´ıku v souboru (3.3) a která také vyuˇz´ıvaj´ı u´ daj zanoˇren´ı uzlu. Pokud se jeˇstˇe vrát´ıme k pˇr´ıkladu z obrázku 3.3, pak by struktura DAWG po této prvn´ı fázi, kdy uˇz vˇsechny uzly s hloubkou potomka 1 ukazuj´ı na jediný uzel s hloubkou potomka 0 (list), vypadala jako fáze 1 znázornˇená na obrázku 3.4. Analogicky se poté provád´ı to samé s uzly s hloubkou potomka 1. Ted’ jiˇz v´ıme, proˇc staˇc´ı k urˇcen´ı identiˇcnosti dvou uzl˚u pouze u´ daje o masce ukazatel˚u a o hloubce potomka. Je to proto, zˇ e pokud jsou tyto dva u´ daje stejné, pak v´ıme, zˇ e vˇsechny ukazatele tˇechto dvou uzl˚u ukazuj´ı na identickou mnoˇzinu uzl˚u (ukazatel uzlu A s indexem i ukazuje na stejný uzel, jako ukazatel uzlu B se stejným indexem). A ukazuj´ı na identickou mnoˇzinu uzl˚u proto, protoˇze tyto uzly byly uˇz v pˇredeˇslých fáz´ıch konverze sjednoceny. Vˇsechny fáze konverze USS na DAWG ukazuje obrázek 3.4. fáze 0

fáze 1

fáze 2

V

V

V

A

O

A

O

A

N

N

N

N

N

A

A

A

EOW

EOW

EOW

A

EOW

Obrázek 3.4: Fáze tvorby DAWG z USS

10

O

3.3

Uloˇzen´ı slovn´ıku v souboru

Slovn´ık pˇredstavuje perzistentn´ı data. Aplikace, která se slovn´ıkem pracuje, ho mus´ı nejdˇr´ıve naˇc´ıst ze souboru nebo m˚uzˇ e pracovat pˇr´ımo se souborem. Slovn´ık je tvoˇren mnoˇzinou uzl˚u (DAWG cˇ i USS), které jsou uloˇzeny za sebou v souboru. Prvn´ı je uloˇzen koˇrenový uzel, následuj´ı uzly se zanoˇren´ım 1 atd. Hodnoty ukazatel˚u uzl˚u jsou kladná celá cˇ´ısla, která odkazuj´ı na adresu v souboru, kde je uloˇzen poˇca´ teˇcn´ı byte odkazovaného uzlu. Aby byla tato cˇ´ısla co nejmenˇs´ı, neukládá se do nich absolutn´ı adresa uzlu (pozice od poˇca´ tku souboru) ale relativn´ı adresa uzlu v˚ucˇ i uzlu, ze kterého cˇ teme hodnotu ukazatele (o kolik bajt˚u se mus´ı poskoˇcit z aktuáln´ı pozice v souboru). To, zˇ e je odkazovaný uzel vˇzdy uloˇzen na vyˇssˇ´ı adrese v souboru neˇz uzel, který na nˇej ukazuje, je v pˇr´ıpadˇe DAWG struktury dáno t´ım, zˇ e se pˇresmˇerovávaj´ı ukazatele vˇzdy na uzel s vyˇssˇ´ım zanoˇren´ım ve struktuˇre USS, zat´ımco uzel s menˇs´ım zanoˇren´ım se z DAWG struktury vylouˇc´ı. Viz 3.2.1. V pˇr´ıpadˇe USS se toto ˇreˇsit nemus´ı, protoˇze ukazatele konkrétn´ıho uzlu zde vˇzdy ukazuj´ı na uzel se zanoˇren´ım o 1 vˇetˇs´ım.

3.3.1

Struktura uzlu

Velký pod´ıl na velikosti slovn´ıku má kromˇe pˇrirozené komprese, vznikaj´ıc´ı d´ıky podobnosti slov, také struktura samotného uzlu. Uzel nese informace o hodnotách ukazatel˚u. Ukazatel˚u je ale pomˇernˇe velký poˇcet (v cˇ eském Scrabblu jich je celkem 40). Mnoho tˇechto ukazatel˚u ale v˚ubec nikam neukazuje - slovo zde konˇc´ı. Nejv´ıce ukazatel˚u je nastavených v uzlech s menˇs´ım zanoˇren´ım a postupnˇe pˇribývá tˇech, které maj´ı hodnotu NULL. Posledn´ı v ˇradˇe jsou listy, které nemaj´ı ani jednoho ukazatele nastaveného. Záleˇz´ı na podobnosti slov, ale pr˚umˇerný poˇcet nastavených ukazatel˚u v uzlu je 2 aˇz 5 (ze 40). Proto existuje hodnˇe zbyteˇcných ukazatel˚u, které nikam neodkazuj´ı a zab´ıraj´ı zbyteˇcnˇe m´ısto ve slovn´ıku. Toho vyuˇz´ıvá zp˚usob uloˇzen´ı uzlu, pouˇz´ıvaný v projektu. Nenastavené ukazatele uchovávaj´ı totiˇz jenom informaci o tom, zˇ e nikam neukazuj´ı. Tato informace nemus´ı zab´ırat prostor velikosti ukazatele ale jen jednoho bitu. Proto se pˇred samotné ukazatele vkládá na poˇca´ tek uzlu jeden reˇzijn´ı byte, který nese informaci o poˇctu nastavených ukazatel˚u (0-39) a informaci o konci slova (ANO/NE). Po pˇreˇcten´ı reˇzijn´ıho bytu tedy v´ıme, kolik dalˇs´ıch byt˚u uloˇzených bezprostˇrednˇe za t´ımto reˇzijn´ım bytem patˇr´ı k danému uzlu. Ukazatel má velikost 3 byty a jsou v nˇem uchovávány dvˇe informace: hodnota samotného ukazatele (18 bit˚u) a index (p´ısmeno, které pˇredstavuje) ukazatele (6 bit˚u). Ukazatele jsou v uzlu uloˇzeny vzestupnˇe (podle jejich index˚u) a toho vyuˇz´ıváme pˇri binárn´ım vyhledáván´ı ukazatele s konkrétn´ım indexem. Obrázek 3.5 ukazuje strukturu uzlu názornˇe. režijní byte

ukazatel A

počet ukazatelů

konec slova

...

ukazatel B

relativní adresa index

1 bit

6 bitů

7 bitů

18 bitů

Obrázek 3.5: Struktura uzlu uloˇzeného v souboru

11

Kapitola 4

˚ algoritmus Appel-Jacobsonuv V této kapitole jsou popsány kroky pˇr´ıpravy hrac´ı plochy pro aplikaci Appel-Jacobsonova algoritmu a algoritmus samotný. Následuje popis algoritmu pˇrevzatý z [1]. K dispozici je stále p˚uvodn´ı program [9] psaný v jazyce C pro operaˇcn´ı systém UNIX.

4.1

Pˇr´ıprava hrac´ı plochy

Aby bylo vyhledáván´ı slov co nejrychlejˇs´ı, je tˇreba pˇred samotným generován´ım tahu zjistit nˇekteré u´ daje o hrac´ı ploˇse. Zrychlen´ı a hlavnˇe zjednoduˇsen´ı celého algoritmu spoˇc´ıvá také v redukci problému do jednoho rozmˇeru.

4.1.1

Redukce problému do jednoho rozmˇeru

Slova ve Scrabblu se mohou tvoˇrit bud’ zprava doleva nebo shora dol˚u. M˚uzˇ eme se omezit jen na tvoˇren´ı slov zprava doleva t´ım, zˇ e si vytvoˇr´ıme druhou hrac´ı plochu, která k n´ı bude transponovaná. Algoritmus tedy nejprve bude vyhledávat slova na prvn´ı a potom na druhé ploˇse (na poˇrad´ı nezáleˇz´ı). Tyto hern´ı plochy se mus´ı samozˇrejmˇe po kaˇzdém tahu synchronizovat. To znamená, zˇ e p´ısmeno vloˇzené na prvn´ı hrac´ı plochu na souˇradnice x,y se vloˇz´ı i na transponovanou hrac´ı plochu, ale na souˇradnice y,x.

4.1.2

Cross-Check mnoˇziny

Kdyˇz vloˇz´ıme nové slovo (omezili jsme se jen na zprava doleva), pak novˇe vloˇzená p´ısmena mus´ı navazovat i na slova ve vertikáln´ım smˇeru, která jsou na ploˇse jiˇz um´ıstˇená. Pˇred kaˇzdým tahem tedy mus´ıme znát pol´ıcˇ ka, která mohou tvoˇrit i slova ve vertikáln´ım smˇeru. Jsou to pol´ıcˇ ka um´ıstˇená pˇr´ımo pod, nebo nad nˇejakým jiˇz zaplnˇeným pol´ıcˇ kem. Jinými slovy u kaˇzdého pol´ıcˇ ka na hrac´ı ploˇse mus´ıme znát mnoˇzinu p´ısmen (Cross-Check mnoˇzinu), které lze na toto pol´ıcˇ ko vloˇzit, aby p´ısmena tvoˇrily i vertikáln´ı slova. Tato cˇ innost je cˇ asovˇe nároˇcná, mnohdy trvá déle, neˇz samotné generován´ı slova. Chceme-li cˇ as strávený výpoˇctem Cross-Check mnoˇzin eliminovat, mus´ıme si uvˇedomit následuj´ıc´ı. Pˇred prvn´ım tahem nemus´ıme tyto mnoˇziny poˇc´ıtat - z pohledu Cross-Check mnoˇzin lze na kaˇzdé pol´ıcˇ ko vloˇzit jakékoliv p´ısmeno. Po vloˇzen´ı slova s pozic´ı prvn´ıho p´ısmene na x,y a s délkou slova d m˚uzˇ eme omezit poˇcet pol´ıcˇ ek na hrac´ı ploˇse, na kterých se novˇe poˇc´ıtaj´ı Cross-Check mnoˇziny. Jsou to pol´ıcˇ ka na x-ových souˇradnic´ıch od x do x + d − 1. Y-ové pozice existuj´ı pak maximálnˇe dvˇe pro kaˇzdou x-ovou pozici. Jsou to prvn´ı prázdná pol´ıcˇ ka, ke kterým se dostaneme pr˚uchodem po hrac´ı ploˇse nahoru nebo dolu z kaˇzdého novˇe vloˇzeného pol´ıcˇ ka. Pokud je slovo vloˇzeno na hern´ı plochu 12

vertikálnˇe, pak se situace zjednoduˇsuje pouze na jednu x-ovou souˇradnici a sloˇzitˇejˇs´ı cˇ a´ st se zase mus´ı provádˇet nad transponovanou hrac´ı plochou.

4.1.3

Anchors - spojovac´ı pol´ıcˇ ka

Anchor pol´ıcˇ ka jsou pol´ıcˇ ka, která spojuj´ı cˇ a´ st slova jiˇz vloˇzeného na plochu a cˇ a´ st slova novˇe vytvoˇreného. Pˇresná definice zn´ı: “Nejlevˇejˇs´ı novˇe vloˇzené pol´ıcˇ ko pˇripojené k pol´ıcˇ ku, které je jiˇz zaplnˇené.” Jedno vkládané slovo má tedy jedno anchor pol´ıcˇ ko/p´ısmeno a na jednom ˇra´ dku m˚uzˇ e být nˇekolik anchor pol´ıcˇ ek. Anchor pol´ıcˇ ka jsou tedy vˇsechna prázdná pol´ıcˇ ka soused´ıc´ı (zprava, zleva, shora, zdola) s jiˇz zaplnˇeným pol´ıcˇ kem. Jako u Cross-Check mnoˇzin je tˇreba pˇred kaˇzdým tahem tyto pol´ıcˇ ka znát.

4.2

Generován´ı samotného tahu

Pro kaˇzdý ˇra´ dek hrac´ı plochy se problém redukuje na následuj´ıc´ı jednorozmˇerný problém: 1. Daná p´ısmena, která lze pouˇz´ıt. 2. Obsah aktuáln´ıho ˇra´ dku na hrac´ı ploˇse. 3. Cross-Checky a anchor pol´ıcˇ ka na aktuáln´ım ˇra´ dku. 4. Vygenerovat vˇsechna moˇzná slova na aktuáln´ım ˇra´ dku. Pro kaˇzdé anchor pol´ıcˇ ko na kaˇzdém ˇra´ dku hrac´ı plochy (i na transponované) je tˇreba provést samotné hledán´ı slov, které se skládá ze dvou cˇ a´ st´ı: 1. Naj´ıt vˇsechny moˇzné levé cˇ a´ sti slova. (Levá cˇ a´ st je nalevo od anchor pol´ıcˇ ka.) 2. Ke kaˇzdé levé cˇ a´ sti slova naj´ıt vˇsechny správné pravé cˇ a´ sti slova. (Pravá cˇ a´ st je napravo od anchor pol´ıcˇ ka, vˇcetnˇe anchor pol´ıcˇ ka.) Jde tedy o prohledáván´ı do hloubky (backtracking).

4.2.1

Levá cˇ a´ st

O levé cˇ a´ sti slova plat´ı: 1. Jej´ı zaˇca´ tek (nejlevˇejˇs´ı pol´ıcˇ ko) je bud’ na konci hrac´ı plochy nebo pˇred jiným anchor pol´ıcˇ kem. (Délka levé cˇ a´ sti m˚uzˇ e tedy být i nulová.) 2. Je tvoˇrena bud’ z novˇe vloˇzených pol´ıcˇ ek nebo z jiˇz zaplnˇených pol´ıcˇ ek, ale nikdy ne dohromady. (To plyne z definice anchor pol´ıcˇ ka a z prvn´ıho bodu.) Pokud levou cˇ a´ st tvoˇr´ı jiˇz vloˇzená pol´ıcˇ ka, pak se tato cˇ a´ st slova jiˇz nemus´ı generovat, jednoduˇse staˇc´ı pouˇz´ıt p´ısmena na daných pol´ıcˇ kách. 3. Jej´ı pol´ıcˇ ka jsou jednoduchá Cross-Check pol´ıcˇ ka. To znamená, zˇ e na pol´ıcˇ ko lze vloˇzit jakékoliv p´ısmeno, které máme samozˇrejmˇe v daném tahu ve svém zásobn´ıku. (To také plyne z definice anchor pol´ıcˇ ka a z prvn´ıho bodu.) U levé cˇ a´ sti lze tedy urˇcit jej´ı maximáln´ı délku (viz bod 1). Funkce, která generuje levou cˇ a´ st slova je v pseudokódu zapsána takto: (Funkce pracuje se slovn´ıkem, který je reprezentován strukturou USS nebo DAWG.) 13

Lev´ aˇ C´ ast(ˇ C´ astSlova, uzel U, limit) { Rozˇ siˇ rujDoprava(ˇ C´ astSlova, U, AnchorPol´ ıˇ cko) jestliˇ ze limit > 0 { pro kaˇ zd´ y platn´ y pˇ rechod P z uzlu U { jestliˇ ze p´ ısmeno p, kter´ e reprezentuje pˇ rechod P m´ ame v z´ asobn´ ıku { vyjmi p´ ısmeno p ze z´ asobn´ ıku necht’ U’ je uzel dosaˇ zen´ y z pˇ rechodu P ˇ ˇ Lev´ aC´ ast(C´ astSlova+p, U’, limit-1) vloˇ z p´ ısmeno p zpˇ et do z´ asobn´ ıku } } } } Necht’ k je maximáln´ı délka levé cˇ a´ sti slova. Tuto funkci voláme pro kaˇzdé anchor pol´ıcˇ ko hrac´ı ˇ ast(“”, koˇrenový uzel, k). plochy takto: LeváC´ Uvaˇzujme funkci Korektn´ıTah(slovo), které pˇredáváme validn´ı slovo a tato funkce jej ukládá. Jednoduchá funkce si m˚uzˇ e pamatovat jen nejlépe ohodnocený tah. Funkce generuj´ıc´ı pravé cˇ a´ sti slova je zapsána takto: Rozˇ siˇ rujDoprava(ˇ C´ astSlova, uzel U, pol´ ıˇ cko Q) { jestliˇ ze pol´ ıˇ cko Q je pr´ azdn´ e { jestliˇ ze U je koneˇ cn´ y uzel { Korektn´ ıTah(ˇ C´ astSlova) } pro kaˇ zd´ y platn´ y pˇ rechod P z uzlu U { jestliˇ ze p´ ısmeno p, kter´ e reprezentuje pˇ rechod P m´ ame v z´ asobn´ ıku a jestliˇ ze p´ ısmeno p se nach´ az´ ı v Cross-Check mnoˇ zinˇ e dan´ eho pol´ ıˇ cka { vyjmi p´ ısmeno p ze z´ asobn´ ıku necht’ U’ je uzel dosaˇ zen´ y z pˇ rechodu P necht’ Q’ je pol´ ıˇ cko napravo od pol´ ıˇ cka Q ˇ Rozˇ siˇ rujDoprava(Ca ´stSlova+p, U’, Q’) vloˇ z p´ ısmeno p zpˇ et do z´ asobn´ ıku } } } jinak { necht’ p je p´ ısmeno na pol´ ıˇ cku Q 14

jestliˇ ze U m´ a platn´ y pˇ rechod, kter´ y je reprezentov´ an p´ ısmenem p a tento pˇ rechod smˇ eˇ ruje k uzlu U’ { necht’ Q’ je pol´ ıˇ cko napravo od pol´ ıˇ cka Q ˇ Rozˇ siˇ rujDoprava(C´ astSlova+p, U’, Q’) } } }

4.2.2

Oˇsetˇren´ı výjimek

Existuj´ı nˇekteré výjimky, které je tˇreba v kódu oˇsetˇrit: ˇ ast a pol´ıcˇ ko nalevo od anchor pol´ıcˇ ka je uˇz • Prázdné prefixy - Pokud voláme funkci LeváC´ zaplnˇené, pak levou cˇ a´ st negenerujeme, ale pouˇzijeme p´ısmena vloˇzená nalevo od anchor pol´ıcˇ ka. To znamená, zˇ e voláme pˇr´ımo funkci RozˇsiˇrujDoprava s prvn´ım parametrem, který obsahuje p´ısmena z levé cˇ a´ sti (mus´ıme zachovat poˇrad´ı p´ısmen). Druhý parametr je uzel, ke kterému se dostaneme pr˚uchodem p´ısmen levé cˇ a´ sti od koˇrene. Posledn´ı je dané anchor pol´ıcˇ ko. ˇ ıky - Tyto kameny reprezentuj´ı kterékoliv p´ısmeno. Vˇzdy, kdyˇz nenajdeme ve svém záso• Zol´ bn´ıku poˇzadované p´ısmeno, tak se jeˇstˇe pod´ıváme, zda nemáme zˇ ol´ık. Pokud ano, pak ho necháme reprezentovat hledané p´ısmeno. Kdyˇz pak zˇ ol´ık vkládáme zpˇet do zásobn´ıku, tak mu vrac´ıme jeho mnohotvárnost.

4.2.3

Implementaˇcn´ı doporuˇcen´ı

Je dobré zvˇetˇsit sˇ´ırˇku hrac´ı plochy o jedno pol´ıcˇ ko doprava. Pol´ıcˇ ka napravo budou m´ıt prázdnou Cross-Check mnoˇzinu (ˇza´ dné p´ısmeno nelze vloˇzit) a souˇcasnˇe budou prázdná (ˇza´ dné p´ısmeno na nˇe nen´ı vloˇzené). Tyto pol´ıcˇ ka slouˇz´ı jako zarázˇ ky pˇri hledán´ı pravých cˇ a´ st´ı slov. Pˇri poˇc´ıtán´ı Cross-Check mnoˇzin je také výhodné pro kaˇzdé prázdné pol´ıcˇ ko souˇcasnˇe poˇc´ıtat bodové ohodnocen´ı vertikáln´ıch slov, které mohou pˇri tahu vzniknout. Je to souˇcet hodnot vˇsech pol´ıcˇ ek tvoˇr´ıc´ıch sled pol´ıcˇ ek s pol´ıcˇ ky pˇr´ımo nad a pod daným prázdným pol´ıcˇ kem.

15

Kapitola 5

Výbˇer tahu ´ Ukolem Appel-Jacobsonova algoritmu je nalézt vˇsechny validn´ı tahy z dostupných p´ısmen a z aktu´ a´ ln´ıho stavu hrac´ı plochy. Ukolem hern´ıch heuristik je vybrat jeden z tˇechto tah˚u a vloˇzit jej na hrac´ı plochu. To znamená, zˇ e ve hˇre je uplatnˇen i jistý strategický prvek, který hodnot´ı tah nejen podle jeho bodového ohodnocen´ı, ale i podle jeho um´ıstˇen´ı na hrac´ı ploˇse. Heuristika, která jednoduˇssˇe vyb´ırá nejlépe ohodnocený tah se nazývá hladová strategie. V této práci je význam hern´ıch heuristik dvoj´ı. Prvn´ı je nalézt takové heuristiky, aby se u nich projevila strategická schopnost umist’ovat tahy na hern´ı plochu tak, zˇ e jsou schopny porázˇ et hladovou strategii s v´ıce jak 50% pravdˇepodobnost´ı. Druhý význam je v podstatˇe opaˇcný. Jde o heuristiky, které u´ myslnˇe vyb´ıraj´ı tahy s menˇs´ım bodovým ohodnocen´ım a v souboji s hladovou strategi´ı jsou vˇetˇsinou poraˇzeny. Jde o zp˚usob simulován´ı hrácˇ e s menˇs´ı slovn´ı zásobou. Oba typy heuristik maj´ı spoleˇcné to, zˇ e nevyb´ıraj´ı vˇzdy tahy s nejvyˇssˇ´ım bodovým ohodnocen´ım. Obˇe to ale dˇelaj´ı z jiného d˚uvodu. Prvn´ı se t´ım snaˇz´ı porazit ostatn´ı heuristiky, druhá se jimi snaˇz´ı být poraˇzena. I kdyˇz hladová strategie pˇredstavuje nejjednoduˇssˇ´ı zp˚usob, jak vybrat tah, jde souˇcasnˇe o velice u´ cˇ innou strategii. Vˇsechny ostatn´ı heuristiky, které ji maj´ı porázˇ et, totiˇz mohou vyb´ırat tahy se stejným nebo menˇs´ım bodovým ziskem. Lze nalézt zp˚usob, jak ji výraznˇe porázˇ et [4]. Tento zp˚usob je ale zaloˇzen na statistickém vyhodnocován´ı dat, která se z´ıskávaj´ı nˇekolikanásobným bˇehem patˇriˇcných algoritm˚u a je tedy cˇ asovˇe nároˇcný a nevhodný pro pouˇzit´ı v této práci. Vhodnˇejˇs´ı jsou heuristiky, které se pˇrirozenˇe snaˇz´ı bránit soupeˇri vkládat výhodné tahy na hrac´ı plochu. Zp˚usob˚u, jak toho doc´ılit, je mnoho a jsou r˚uznˇe u´ cˇ inné. Mohou brát v u´ vahu stav hrac´ı plochy, stav zásobn´ıku, vlastn´ı a soupeˇrovo skóre, fázi hry (zaˇca´ tek, konec), apod. Jak konkrétnˇe by se mˇela taková heuristika chovat, se dá pochopit z nˇekterých vybraných tip˚u (které jsou v tomto projektu vyuˇzity a které lze naj´ıt v manuálu pro hru), jak hrát správnˇe Scrabble: ˇ N, ˇ Tˇ jsou nejlépe hodnocená p´ısmena v sácˇ ku. Neschovávejte si je, hrajte je • “P´ısmena X, D, pokud moˇzno co nejdˇr´ıve. Tato p´ısmena maj´ı svou vysokou bodovou hodnotu právˇe pro svou obt´ızˇ nou um´ıstitelnost. Na druhou by bylo sˇkoda nevytˇezˇ it z nich maximum. Pokuste se naj´ıt nejlepˇs´ı um´ıstˇen´ı ve slovˇe s prémi´ı.” • “Nejlepˇs´ım kamenem je zˇ ol´ık. Výraznˇe zvyˇsuje moˇznost vytvoˇren´ı tahu ze vˇsech sedmi kamen˚u a tak z´ıskán´ı padesátibodové prémie. Neuˇz´ıvejte vˇsak zˇ ol´ıka pˇr´ıliˇs lehkovázˇ nˇe. Je lepˇs´ı uchovat si jej do chv´ıle, kdy budete moci vytvoˇrit tah s minimálnˇe 30bodovým ziskem.” • “Tahy s trojnásobnou slovn´ı prémi´ı jsou ve hˇre velmi d˚uleˇzité a mnohdy rozhoduj´ı o celkovém výsledku. Takˇze neusnadˇnujte svému soupeˇri moˇznost jejich realizace.” • “Hrácˇ , který hraje jen obˇcas, nerad mˇen´ı kameny s od˚uvodnˇen´ım, zˇ e nechce ztrácet zbyteˇcnˇe 16

tah. Pokud ale opakovanˇe hrajete tahy s bodovým ziskem 5 bod˚u cˇ i ménˇe z d˚uvodu málo vhodných kamen˚u, pak je výmˇena pravdˇepodobnˇe nejlepˇs´ım ˇreˇsen´ım.” • “Na konci hry, kdy se skóre jiˇz pomalu uzav´ırá, je cˇ asto velmi d˚uleˇzité dohrát jako prvn´ı. Vaˇsemu soupeˇri z˚ustanou v zásobn´ıku kameny, jejichˇz hodnotu odeˇcte od svého bodového zisku a vám naopak tyto body skóre vylepˇs´ı.”

5.1

Pouˇzité heuristiky

Ve hˇre bylo pouˇzito nˇekolik heuristik. Jejich r˚uzné kombinace byly testovány, aby se nalezla taková celková heuristika, která pˇredˇc´ı hladovou strategii. • Vkládán´ı zˇ ol´ıku˚ - Je nevýhodné vytvárˇet tahy, ve kterých jsou pouˇzity zˇ ol´ıky a které maj´ı souˇcasnˇe malé bodové ohodnocen´ı. Proto pokud má být slovo obsahuj´ıc´ı zˇ ol´ık nebo zˇ ol´ıky vloˇzeno na hrac´ı plochu, mus´ı m´ıt urˇcité minimáln´ı bodové ohodnocen´ı. Podle doporuˇcen´ı, jak hrát správnˇe Scrabble (viz 5) je toto minimum 30 bod˚u. Tato heuristika m˚uzˇ e výraznˇe zvýsˇit skóre hrácˇ e, který vlastn´ı zˇ ol´ıka. Na druhou stranu zˇ ol´ıky ve hˇre existuj´ı pouze dva a jejich ovlivnˇen´ı hry je proto velice náhodné (to je ale jejich u´ cˇ el) - r˚uzn´ı hrácˇ i dostanou bˇehem hry rozd´ılný poˇcet zˇ ol´ık˚u. • Minimáln´ı bodový zisk tahu - V pˇr´ıpadˇe, zˇ e hrácˇ vkládá slovo, které má bodový zisk menˇs´ı, neˇz nˇejaká hranice, m˚uzˇ e se rozhodnout slovo nevloˇzit a radˇeji zvol´ı výmˇenu zásobn´ıku. Pouˇz´ıvaná heuristika mˇen´ı celý zásobn´ık, aby byl po výmˇenˇe v zásobn´ıku co nejv´ıce vyrovnaný poˇcet souhlásek a samohlásek. Právˇe jejich nevyrovnanost je totiˇz nejˇcastˇejˇs´ı d˚uvod, proˇc nelze vytvoˇrit delˇs´ı slovo s vyˇssˇ´ım bodovým ziskem. Minimáln´ı bodová hranice, kdy se zásobn´ık jeˇstˇe nevymˇenˇ uje, byla pˇredmˇetem testován´ı (viz 5.2). • Bezpeˇcný tah - Bezpeˇcný tah je takový tah, který neumoˇzn´ı soupeˇri na tento tah navázat a obsadit napˇr. pol´ıcˇ ko s trojnásobnou slovn´ı hodnotou. Takový tah má vˇetˇsinou menˇs´ı bodovou hodnotu, neˇz bodovˇe nejlepˇs´ı tah v daném tahu hrácˇ e. Znamená to, zˇ e m´ısto tahu s nejvˇetˇs´ım bodovým ziskem se heuristika rozhodne poloˇzit jiný tah s ménˇe body, ale má jistotu, zˇ e neumoˇzn´ı soupeˇri vytvoˇrit bonusový tah (viz dalˇs´ı bod). Z nalezených bezpeˇcných tah˚u se snaˇz´ı um´ıstit vˇzdy ten bodovˇe nejlepˇs´ı. • Bonusový tah - Bonusový tah má alespoˇn jedno p´ısmeno vloˇzeno na bonusovém pol´ıcˇ ku, napˇr. opˇet na trojnásobné slovn´ı prémii. Hrácˇ s touto heuristikou se pˇrednostnˇe snaˇz´ı pokládat tahy na bonusová pol´ıcˇ ka (vyb´ırá nejvýsˇe hodnocený tah) a dává jim tak pˇrednost pˇred bodovˇe nejlépe hodnocenými tahy. Zároveˇn tak ale znemoˇznˇ uje soupeˇri poloˇzit slovo na toto bonusové pol´ıcˇ ko. • Nejdelˇs´ı tah - Hrácˇ se snaˇz´ı vytváˇret co nejdelˇs´ı slova. Vˇetˇsinou neplat´ı, zˇ e nejdelˇs´ı slovo je zároveˇn slovo s nejvyˇssˇ´ım bodovým ziskem. Tato heuristika je pouˇz´ıvána v závˇereˇcné fázi hry, kdyˇz uˇz je v sácˇ ku ménˇe jak sedm hrac´ıch kamen˚u a hrácˇ i tedy uˇz nemohou mˇenit své zásobn´ıky. M´ısto toho se hrácˇ snaˇz´ı poloˇzit co nejdelˇs´ı slovo, aby tak mohl dˇr´ıve uzavˇr´ıt hru, nebo alespoˇn aby mu bylo po skonˇcen´ı hry odeˇcteno ménˇe bod˚u z jeho celkového skóre.

5.2

Testován´ı

Testován´ım heuristik a jejich kombinac´ı se hledala nejlepˇs´ı heuristika, která by s co nejvˇetˇs´ı pravdˇepodobnost´ı porázˇ ela hladovou strategii. Aby byly výsledky testován´ı objektivn´ı, hráli proti sobˇe 17

v jedné hˇre vˇzdy jen dva hrácˇ i. Náhodným prvkem ve hˇre je tahán´ı p´ısmen ze sácˇ ku, proto nebylo moˇzné dostat pˇresný výsledek pouze z jedné hry mezi stejnými soupeˇri. Vˇzdy se hrálo alespoˇn 150 her. Výhodu ve hˇre má ten hrácˇ , který pokládá prvn´ı slovo. Proto mˇeli oba hrácˇ i stejný poˇcet prvn´ıch tah˚u. Pˇri testován´ı se zjistilo, zˇ e výsˇe popsané heuristiky bezpeˇcný tah, bonusový tah a nejdelˇs´ı tah pokládaj´ı vˇetˇsinou tahy s výraznˇe menˇs´ım bodovým ziskem, neˇz hladová strategie. Takové heuristiky byly jeˇstˇe ménˇe u´ spˇesˇné, neˇz hladová strategie. Proto bylo tˇreba nastavit jistou maximáln´ı bodovou hranici rozd´ılu mezi vybraným a nejlépe hodnoceným tahem. Kdyˇz je tato hranice pˇrekrocˇ ena, chová se heuristika jako hladová strategie a pokládá nejlépe hodnocený tah. To se dˇeje pˇribliˇznˇe v polovinˇe tah˚u. Heuristiky, které takto vyb´ıraj´ı tahy, jsou schopny (kdyˇz je hranice rozd´ılu správnˇe nastavena) s vˇetˇs´ı jak 50% pravdˇepodobnost´ı porazit hladovou strategii. V tabulce 5.1 jsou zobrazeny výsledky test˚u, kdy proti sobˇe vˇzdy hrály vybraná heuristika a hladová strategie. Prvn´ı sloupec ukazuje nastaven´ı heuristiky. Hodnoty v poˇrad´ı znaˇc´ı: 1. Maximáln´ı bodový rozd´ıl nejdelˇs´ıho a bodovˇe nejlepˇs´ıho tahu. 2. Minimáln´ı bodová hodnota slova, které se m˚uzˇ e poloˇzit na hrac´ı plochu. Pˇri menˇs´ı hodnotˇe uˇz se vymˇenˇ uje zásobn´ık. 3. Maximáln´ı bodový rozd´ıl bezpeˇcného a bodovˇe nejlepˇs´ıho tahu. 4. Maximáln´ı bodový rozd´ıl bonusového a bodovˇe nejlepˇs´ıho tahu Z výsledk˚u je patrné, zˇ e nejlépe nastavené heuristiky dokázˇ´ı porázˇ et hladovou strategii s asi 56% pravdˇepodobnost´ı. Jiné heuristiky jsou vyrovnané a nˇekteré jsou naopak hladovou strategi´ı ve vˇetˇsinˇe pˇr´ıpad˚u poraˇzené. To je zp˚usobeno t´ım, zˇ e maj´ı nastavené velké hodnoty nˇekterých nebo i vˇsech parametr˚u. Vyb´ıraj´ı tedy s vˇetˇs´ı pravdˇepodobnost´ı tahy, které jsou sice strategiˇctˇeji um´ıstˇené ˇ ım vyˇssˇ´ı na hern´ı plochu, ale maj´ı o pˇr´ıliˇs mnoho bod˚u ménˇe, neˇz maximálnˇe bodovˇe ziskový tah. C´ hodnoty parametr˚u jsou nastaveny, t´ım menˇs´ı obt´ızˇ nost hrácˇ e-poˇc´ıtaˇce. Parametry

Poˇcet her

-1 3 1 6 1616 1 3 1 10 1525 -1 0 2 5 2616 2 10 1 6

150 150 150 150 150 150 150

Výhry poˇcet % 82 54,6 78 52 58 38,6 80 53,3 79 52,6 84 56 75 50

Rem´ızy poˇcet % 4 2,6 0 0 0 0 2 2,3 1 1,3 1 1,3 0 0

Prohry poˇcet % 64 42,6 72 48 92 61,3 68 45,3 70 46,6 65 42,6 75 50

Tabulka 5.1: Hladová strategie proti r˚uzným heuristikám

18

Kapitola 6

ˇ Cesk´ y Scrabble V porovnán´ı s anglickým jazykem je cˇ eˇstina jazyk velmi ohebný. Slova maj´ı mnoho r˚uzných tvar˚u. Skloˇnuj´ı se, cˇ asuj´ı se, maj´ı r˚uzné pˇredpony a pˇr´ıpony. Nav´ıc má cˇ eˇstina v´ıce p´ısmen. Tyto jej´ı vlastnosti s sebou pˇrinásˇ´ı r˚uzné nevýhody, které bylo tˇreba ˇreˇsit v projektu. Pokud bychom chtˇeli, aby násˇ program generoval vˇsechna pˇr´ıpustná slova podle pravidel Scrabblu [7], pak bychom museli m´ıt vˇsechna tyto slova ve vˇsech tvarech uloˇzena ve slovn´ıku. Problém je v enormn´ı velikosti takového slovn´ıku. Slovn´ık s cˇ eskými slovy pouze v základn´ım tvaru má pˇribliˇznˇe 58 000 slov. Rozˇs´ıˇrený slovn´ık se vˇsemi tvary tˇechto slov jich má pak asi 1 200 000. I kdyˇz budou slova uloˇzena ve struktuˇre DAWG, kde se uplatn´ı podobnost slov (komprese slov vzroste, protoˇze se zvˇetˇs´ı poˇcet podobných slov), bude velikost tohoto slovn´ıku stále nˇekolikanásobnˇe vˇetˇs´ı. To napˇr. celkovˇe zpomal´ı generován´ı tah˚u, ale hlavnˇe se tu projev´ı nevýhody c´ılové platformy (7.4). Tento problém má nˇekolik (bohuˇzel jenom cˇ a´ steˇcných) ˇreˇsen´ı: 1. Lze pouˇz´ıt tzv. lematizátory. Jsou to programy, které dokázˇ´ı slovo z nˇejakého tvaru pˇrevést na tvar základn´ı. Vyuˇz´ıvaj´ı pˇritom vzor˚u slov a podobnˇe. V tomto smˇeru ale v cˇ eˇstinˇe existuje mnoho výjimek a ne u vˇsech slov se dá pouˇz´ıt jejich vzor k nalezen´ı správného tvaru. To cˇ in´ı lematizátory opˇet do jisté m´ıry závislé na velkých slovn´ıc´ıch. 2. Pokud validujeme slovo, které nen´ı v základn´ım tvaru a které tedy nemáme uloˇzené ve slovn´ıku, m˚uzˇ eme validovat pouze cˇ a´ st slova (nˇekolik poˇca´ teˇcn´ıch p´ısmen). V tomto pˇr´ıpadˇe tedy nelze zjistit, zda je celé slovo opravdu validn´ı cˇ i nikoliv. 3. Slovn´ık m˚uzˇ e obsahovat slova ve vˇsech tvarech jen do urˇcité délky slova. Slova delˇs´ı neˇz je jistá hranice jsou uloˇzena jen v základn´ım tvaru. Posledn´ı ˇreˇsen´ı je také pouˇzito v tomto projektu. Slovn´ık obsahuje vˇsechny tvary maximálnˇe pˇetip´ısmenných slov. To je d˚uleˇzité protoˇze vˇetˇsina slov um´ıstˇených na hrac´ı ploˇse maj´ı délku do pˇeti p´ısmen. Tˇechto slov je asi 28 500. Celkem je pak ve slovn´ıku uloˇzeno 83 000 slov a velikost DAWG slovn´ıku obsahuj´ıc´ı tuto mnoˇzinu slov je asi 330 kB. Aby nebyl hrácˇ -ˇclovˇek omezen mnoˇzinou uloˇzených slov, lze ve výsledné aplikaci validaci slov vypnout a slovn´ık je pak vyuˇz´ıván pouze pˇri generován´ı tahu poˇc´ıtaˇcem.

19

Kapitola 7

Implementace Výsledná aplikace se snaˇz´ı simulovat vˇsechny prvky obsaˇzené ve hˇre. Oproti stoln´ı hˇre pˇridává moˇznost hrát proti umˇelé inteligenci (nebo nechat hrát UI proti sobˇe). Grafické rozhran´ı tvoˇr´ı vlastn´ı kreslic´ı plocha i standardn´ı formuláˇrové prvky dostupné v MIDP 2.0. Ovládán´ı hry je intuitivn´ı a je popsáno v nápovˇedˇe aplikace. Pro ukládán´ı dat, tak aby byla pˇr´ıstupná i po vypnut´ı a znovu spuˇstˇen´ı aplikace, slouˇz´ı tzv. RMS (Record Management System), cˇ esky systém pro správu záznam˚u. Ve hˇre lze takto ukládat nastaven´ı jednotlivých hrácˇ u˚ .

7.1

Prototypové programy

Bylo tˇreba vytvoˇrit dva prototypové programy (konzolové aplikace v jazyce C). Prvn´ı slouˇzil k vytvoˇren´ı samotného slovn´ıku DAWG ze seznamu slov (uloˇzených v obyˇcejné textové podobˇe). Dále se na nˇem testovala vhodná struktura uzlu slovn´ıku DAWG. Druhý program byl urˇcen k testován´ı heuristik pro výbˇer tahu. Obsahoval tedy Appel-Jacobson˚uv algoritmus na generován´ı tah˚u vˇcetnˇe vˇsech nezbytných funkc´ı pro ohodnocen´ı tahu, pro obsluhu zásobn´ıku (doplˇnován´ı, mˇenˇen´ı obsahu), pro vkládán´ı tahu na hrac´ı plochu a pro celkový bˇeh programu (hrácˇ i se stˇr´ıdali v jednotlivých taz´ıch a na konci hry se zapsaly výsledky).

7.2

Objektový návrh

Vˇsechny fyzické objekty, které se objevuj´ı ve skuteˇcné hˇre, jsou implementovány jako objekty i v aplikaci. Jde o hern´ı plochu, zásobn´ık s kameny, sácˇ ek s kameny, slovn´ık a hrácˇ e. Aplikace definuje jeˇstˇe dalˇs´ı tˇr´ıdy, následuje popis vˇsech tˇr´ıd. • GameBoard - Udrˇzuje informace o stavu hrac´ı plochy. Obsahuje dvojrozmˇerné pole prvk˚u (15 x 15), které uchovávaj´ı r˚uzné informace o kaˇzdém pol´ıcˇ ku. Obsahuje metody pro cˇ ten´ı a zapisován´ı informac´ı do tˇechto pol´ıcˇ ek. Nejd˚uleˇzitˇejˇs´ı z nich je nastavován´ı Cross-Check mnoˇzin a jejich cˇ ten´ı. • Rack (zásobn´ık s kameny) - Udrˇzuje informace o stavu hrácˇ ova zásobn´ıku. Protoˇze pˇri generován´ı tah˚u poˇc´ıtaˇcem se se zásobn´ıkem neustále manipuluje (vkládaj´ı a vyj´ımaj´ı se p´ısmena), je obsah reprezentován jako pole integer˚u o velikosti 40 (poˇcet p´ısmen). Prvek pole znaˇc´ı cˇ etnost daného p´ısmene v zásobn´ıku. Kromˇe vkládán´ı a vyj´ımán´ı p´ısmen obsahuje zásobn´ık dalˇs´ı metody jako doplnˇen´ı zásobn´ıku p´ısmeny ze sácˇ ku, výmˇenu vˇsech nebo nˇekterých p´ısmen.

20

• Bag (sácˇ ek s kameny) - Obsahuje metody pro vyj´ımán´ı a vkládán´ı p´ısmen. Ze sácˇ ku se vˇzdy vyjme náhodné p´ısmeno - generuje se náhodné cˇ´ıslo s rozsahem jako poˇcet p´ısmen zbylých v sácˇ ku. Po vyjmut´ı se cˇ a´ st obsahu sácˇ ku posouvá tak, aby pˇri dalˇs´ım vyj´ımán´ı staˇcilo generovat pouze jedno náhodné cˇ´ıslo, které znaˇc´ı vybrané p´ısmeno (jeho pozici v sácˇ ku). • DAWG (slovn´ık) - Pˇredstavuje rozhran´ı pro práci se slovn´ıkem. Pracuje pˇr´ımo se soubory, ve kterých jsou slovn´ıky uloˇzeny. Nejd˚uleˇzitˇejˇs´ı je metoda pro cˇ ten´ı obsahu uzl˚u. Ta se pouˇz´ıvá jak pˇri generován´ı tah˚u poˇc´ıtaˇcem, tak pˇri validaci slova vloˇzeného cˇ lovˇekem. Obsah slovn´ıku je nemˇenný, neexistuj´ı metody pro zapisován´ı. • Player - Obsahuje informace o nastaven´ı hrácˇ e a o taz´ıch, které hrál. • ScrabbleMidlet - Potomek tˇr´ıdy Midlet. Obsahuje vˇsechny screeny (seznamy, formulárˇe a varovná hlásˇen´ı), která jdou ve hˇre zobrazit. Dále obsahuje výkonný kód vˇsech pˇr´ıkaz˚u, která náleˇz´ı k jednotlivým screen˚um. • GameService - Obsahuje vˇetˇsinou statické metody, se kterými pracuj´ı instance vˇsech ostatn´ıch tˇr´ıd. • BoardCanvas (kreslic´ı plátno) - Potomek tˇr´ıdy Canvas. Obstarává vykreslován´ı hrac´ı plochy a zásobn´ıku s kameny (ty jsou stále na obrazovce). Obsahuje kód, který je provádˇen pˇri stisku jednotlivých kláves na mobiln´ım telefonu. • Move - Reprezentuje tah um´ıstˇený hrácˇ em na hrac´ı plochu. Ukládá informace o rozm´ıstˇen´ı novˇe vloˇzených kamen˚u. Obsahuje metody pro validaci slova vloˇzeného cˇ lovˇekem a pro vkládán´ı tahu na hrac´ı plochu. • MoveGenerator - Implementuje Appel-Jacobson˚uv algoritmus na generován´ı tah˚u. Dˇed´ı tˇr´ıdu Thread, protoˇze generován´ı tah˚u bˇezˇ´ı jako samostatné vlákno. Je to proto, aby bylo moˇzné bˇehem tahu poˇc´ıtaˇce ovládat hru.

7.3

Oddˇelené grafické rozhran´ı

Z pˇredchoz´ı kapitoly je zˇrejmé, zˇ e na grafickém rozhran´ı se pod´ıl´ı jedna tˇr´ıda a vykreslován´ı na obrazovku je tedy zcela nezávislé na pouˇzitých algoritmech. To je bˇezˇ ný zp˚usob implementace vyuˇz´ıvaj´ıc´ı objektovˇe orientovaného programován´ı. Takový návrh umoˇznˇ uje snadnˇejˇs´ı u´ drˇzbu a aktualizace r˚uzných cˇ a´ st´ı aplikace. Nˇekteré komponenty ale nen´ı tak snadné od sebe oddˇelit. Napˇr´ıklad algoritmus pro generován´ı tah˚u pracuje se slovn´ıkem DAWG - pˇredpokládá tedy urˇcitou strukturu slovn´ıku.

7.4

Omezen´ı c´ılové platformy

C´ılová aplikace je psána v rozˇs´ıˇren´ı Javy J2ME (Java 2 MicroEdition), které vyhovuje standardu MIDP 2.0 [6]. Tento standard je podporovaný zejména mobiln´ımi telefony, pagery, palmtopy a podobnými zaˇr´ızen´ımi. To s sebou obecnˇe pˇrinásˇ´ı jistá omezen´ı oproti osobn´ım poˇc´ıtaˇcu˚ m. Jde pˇredevˇs´ım o menˇs´ı velikost a rychlost operaˇcn´ı pamˇeti. Výpoˇcetn´ı výkon je také nˇekolikanásobnˇe menˇs´ı. Omezen´ı spojená s velikost´ı prostoru pro ukládán´ı soubor˚u vˇsak nebyla pˇri této práci nijak na obt´ızˇ .

21

7.4.1

Práce se soubory

Ve standardu MIDP 2.0 nejsou pˇr´ıtomny jisté tˇr´ıdy pro práci se souborem (napˇr. RandomAccessFile). Jsou zde pouze tˇr´ıdy pro tzv. n´ızkoúrovˇnovou práci se souborem. Tyto tˇr´ıdy neumoˇznˇ uj´ı jednoduchou zmˇenu pozice v souboru na urˇcité m´ısto nebo dotazován´ı na aktuáln´ı pozici v souboru. Jsou tu pouze metody pro oznaˇcen´ı aktuáln´ı pozice a nastaven´ı pozice na tuto znaˇcku. Tento zp˚usob pohybu kurzoru po souboru je ale zcela nedostaˇcuj´ıc´ı pro práci se slovn´ıkem DAWG nebo USS. Proto je tˇreba cˇ a´ st nebo celý slovn´ık uloˇzit do promˇenné v programu a s tou pak neomezenˇe pracovat.

7.4.2

Velikost pol´ı

V pˇredchoz´ı cˇ a´ sti bylo ˇreˇceno, zˇ e je tˇreba slovn´ık zkop´ırovat do promˇenné v programu. Typicky jde o pole byt˚u. Pamˇet’, kterou m˚uzˇ e program alokovat má ale také jistou maximáln´ı velikost. Záleˇz´ı na typu zaˇr´ızen´ı, jaká tato velikost je. Aby byla aplikace spustitelná na vˇetˇsinˇe zaˇr´ızen´ı, mus´ı se velikost pole, do kterého se ukládá slovn´ık, nˇejak omezit. Lze to udˇelat tak, zˇ e se slovn´ık rozdˇel´ı na v´ıce menˇs´ıch slovn´ık˚u. Efektivn´ı je, kdyˇz jsou slovn´ıky rozdˇeleny podle délky slov. Rozdˇel´ıme slovn´ık napˇr. na dva menˇs´ı. V prvn´ım jsou slova s maximáln´ı délkou napˇr. 6, ve druhém pak zbytek. Pˇri generován´ı tahu se naˇcte nejprve prvn´ı slovn´ık, a po jeho pr˚uchodu pak druhý. Bˇehem jednoho generován´ı tahu poˇc´ıtaˇcem resp. pˇri validaci slova vloˇzeného cˇ lovˇekem se slovn´ık naˇc´ıtá ze souboru právˇe jednou resp. nejvýsˇe ˇ strávený naˇc´ıtán´ım slovn´ıku do promˇenné je ve srovnán´ı s generován´ım tahu témˇeˇr jednou. Cas zanedbatelný.

7.4.3

Otev´ırán´ı souboru

Pˇri otev´ırán´ı souboru, který obsahuje slovn´ık, doˇslo k výjimce. Ta byla zp˚usobena nedostatkem pamˇeti. Soubor se proto musel rozdˇelit na nˇekolik cˇ a´ st´ı a ty se pak zvlásˇt’ otev´ıraly a postupnˇe ukládaly do promˇenné v programu.

22

Kapitola 8

Závˇer Hlavn´ım c´ılem této práce bylo vytvoˇrit hru Scrabble pro mobiln´ı telefon, která se snaˇz´ı simulovat hran´ı stejnojmenné stoln´ı hry. Parametry hry odpov´ıdaj´ı oficiáln´ım pravidl˚um Scrabblu [7]. Jde napˇr. o poˇcet hrácˇ u˚ , správné rozmˇery hrac´ı plochy, rozm´ıstˇen´ı bonusových pol´ı na hrac´ı ploˇse, poˇcet p´ısmen ve hˇre, jejich cˇ etnosti a bodové ohodnocen´ı. Dále pak jde o zp˚usoby vkládán´ı slov na hrac´ı plochu vˇcetnˇe jejich správného bodového ohodnocen´ı. Je zahrnuta moˇznost výmˇeny p´ısmen v zásobn´ıku i moˇznost vynechán´ı tahu. Aplikace se svým vzhledem a moˇznostmi snaˇz´ı eliminovat nˇekterá omezen´ı plynouc´ı z c´ılové platformy, na které je implementována. To znamená, zˇ e se snaˇz´ı neomezovat hrácˇ e a umoˇznˇ uje mu udrˇzovat si pˇrehled o hern´ı ploˇse a jeho zásobn´ıku s p´ısmeny. ´ Ukolem hrácˇ e je vkládat na hrac´ı plochu smysluplná slova tak, aby mˇel na konci hry vˇetˇs´ı skóre, neˇz jeho soupeˇri. Po vloˇzen´ı slova aplikace sama slovo validuje (rozhodne o tom, zda novˇe poloˇzená p´ısmena tvoˇr´ı slovo cˇ i ne). Ve hˇre to znamená, zˇ e p´ısmena bud’ umoˇzn´ı nebo neumoˇzn´ı vloˇzit na hern´ı plochu. Hrácˇ em m˚uzˇ e být cˇ lovˇek a nebo poˇc´ıtaˇc (umˇelá inteligence). To znamená, zˇ e aplikace je schopna tahy vytváˇret, validovat a z vytvoˇrených validn´ıch tah˚u jeden vybrat a vloˇzit jej na hrac´ı plochu. Prvn´ım krokem bylo naj´ıt vhodný slovn´ık - tedy vhodnou mnoˇzinu slov, v˚ucˇ i které by program porovnával zadaná slova a testoval jejich validitu. Ohledy se musely brát pˇredevˇs´ım na velikost výsledného slovn´ıku a to jak z d˚uvodu omezen´ı pamˇeti, tak kv˚uli tomu, zˇ e s velikost´ı slovn´ıku roste prohledávaný prostor a tedy i doba potˇrebná k nalezen´ı slova. Po urˇcen´ı vhodného rozsahu slovn´ıku bylo tˇreba naj´ıt vhodnou reprezentaci (formát) slovn´ıku a slovn´ık samotný vytvoˇrit. Hra generuje tahy, to znamená, zˇ e prohledává stavový prostor, který je tvoˇren slovn´ıkem. Chceme-li tah vygenerovat za rozumnou dobu, pak odezva slovn´ıku mus´ı být co nejmenˇs´ı. Pˇresnˇeji ˇreˇceno jeho odpovˇed’, zda dané slovo existuje. Výsledná aplikace je ale spouˇstˇena v prostˇred´ı s omezenými zdroji (pamˇet’, výkon). Mobiln´ı telefony a r˚uzná pˇrenosná zaˇr´ızen´ı se r˚uzn´ı svými prostˇredky. Pokud chceme, aby byla hra spustitelná na vˇetˇsinˇe tˇechto zaˇr´ızen´ı, je tˇreba se pˇrizp˚usobit. Velikost slovn´ıku by se tedy mˇela pohybovat v ˇra´ dech kilobajt˚u. Je ale pravda, zˇ e tato pˇrenosná zaˇr´ızen´ı se zdokonaluj´ı a jejich výpoˇcetn´ı výkon a dostupná pamˇet’ roste. Proto by mohl m´ıt násˇ slovn´ık velikost mnohonásobnˇe vˇetˇs´ı a aplikace by stále byla spustitelná na vˇetˇsinˇe tˇechto zaˇr´ızen´ı. Slovn´ık tedy mus´ı být jednoduˇse rychlý a malý. Obˇe tyto podm´ınky splˇnuje tzv. Univerzáln´ı slovn´ıková struktura. Jeˇstˇe lepˇs´ı kompresn´ı vlastnosti poskytuje tzv. struktura DAWG (Directed Acyclic Word Graphs), která je pouˇzita i v tomto projektu. Struktura DAWG poskytuje relativnˇe rychlý a malý slovn´ık, vhodný pro pouˇzit´ı v této práci. Existuje vˇsak dalˇs´ı slovn´ıková struktura podobná struktuˇre DAWG nazývaná GADDAG [3]. I tato struktura má podobu koneˇcného automatu. na rozd´ıl od DAWG je toto dvousmˇerný graf. To znamená, zˇ e kaˇzdý uzel kromˇe dopˇredných ukazatel˚u obsahuje nav´ıc zpˇetné ukazatele na vˇsechny uzly, které zase obsahuj´ı dopˇredný ukazatel na tento uzel. T´ım vzniká dvousmˇerná vazba podobnˇe 23

jako napˇr. v lineárnˇe vázaném dvousmˇerném seznamu. Kv˚uli zpˇetným ukazatel˚um je GADDAG vˇetˇs´ı neˇz DAWG (typický slovn´ık s anglickými slovy je pˇetkrát vˇetˇs´ı), ale rychlost vyhledáván´ı se m˚uzˇ e aˇz zdvojnásobit. Rychlost se zvýsˇ´ı d´ıky moˇznosti procházet slovn´ık v opaˇcném smˇeru. Tento druh prohledáván´ı je specifický pro hru Scrabble, protoˇze slova navazuj´ı na p´ısmena, která jsou jiˇz um´ıstˇena na hrac´ı ploˇse. Generován´ı tah˚u by se d´ıky tomuto ˇreˇsen´ı tedy výraznˇe zrychlilo, pˇriˇcemˇz velikost slovn´ık˚u by byla stále pˇrijatelná i na platformách pouˇz´ıvaných pro mobiln´ı telefony a podobná pˇrenosná zaˇr´ızen´ı. T´ımto smˇerem lze tedy dále pokraˇcovat v této práci. Máme-li slovn´ık, mus´ıme napsat algoritmy, které s n´ım pracuj´ı. Forma vyhledávac´ıch algoritm˚u je pˇr´ımo závislá na struktuˇre slovn´ıku, se kterým pracuj´ı. Jde o jednosmˇernou závislost vyhledávac´ıch algoritm˚u na slovn´ıku protoˇze stavový prostor, který algoritmus prohledává, je tvoˇren právˇe slovn´ıkem. Naproti tomu slovn´ık nen´ı nijak závislý na vyhledávac´ıch algoritmech. Poˇzadavky kladené na tyto algoritmy jsou podobné jako poˇzadavky na slovn´ık. Algoritmus mus´ı být rychlý (toho doc´ıl´ıme maximáln´ım oˇrezán´ım hledaného prostoru) a nesm´ı být nároˇcný na pamˇet’. Algoritmus pouˇz´ıvaný v této práci se nazývá Appel-Jacobson˚uv a d´ıky tomu, zˇ e oˇrezává prohledávaný stavový prostor maximáln´ı mˇerou, splˇnuje uvedené podm´ınky velice dobˇre. Nejjednoduˇssˇ´ı a mnohdy i nejefektivnˇejˇs´ı je vloˇzit v daném tahu na hern´ı plán slovo, které je ze vˇsech nalezených slov nejlépe ohodnocené (hladová strategie). Tento zp˚usob výbˇeru tahu je vˇetˇsinou pro bˇezˇ né hrácˇ e témˇeˇr neporazitelný. Jedn´ım z c´ıl˚u této práce je testovat r˚uzné hern´ı heuristiky, které vyb´ıraj´ı tah nejen podle jeho bodového ohodnocen´ı, ale i podle jeho um´ıstˇen´ı na hern´ı ploˇse nebo podle fáze hry (zaˇca´ tek, konec). Tyto heuristiky tedy do jisté m´ıry napodobuj´ı logické uvaˇzován´ı hrácˇ e-ˇclovˇeka. Mˇely by být schopny hrát vyrovnané partie s hladovou strategi´ı a dokonce ji pˇredˇcit. Aby bylo hodnocen´ı heuristik spravedlivé, mus´ı samozˇrejmˇe vˇsechny pracovat se stejným slovn´ıkem. Rozˇsiˇrován´ı práce lze soustˇredit na hledán´ı nových a vylepˇsen´ı stávaj´ıc´ıch heuristik pro výbˇer tahu. Aby byla u´ spˇesˇnost heuristik proti hladové strategii co nejvyˇssˇ´ı, je také potˇreba je vyladit - tedy naj´ıt k nim správné parametry. Ty lze naj´ıt tak, zˇ e r˚uzné kombinace heuristik s r˚uznˇe nastavenými parametry necháme hrát proti sobˇe. T´ım jsme schopni nalézt jednu v´ıtˇeznou heuristiku. Jde tedy o princip tzv. genetického algoritmu. Podle [2] lze dosáhnou aˇz 63% u´ spˇesˇnosti s hladovou strategi´ı. V této práci bylo dosaˇzeno pouze 56% pravdˇepodobnosti (viz 5.2). Ve výsledné aplikaci je moˇznost zvolit obt´ızˇ nost hrácˇ e-poˇc´ıtaˇce. Jde o napodobovan´ı chován´ı hrácˇ e s menˇs´ı slovn´ı zásobou. To znamená, zˇ e je pouˇzita heuristika s opaˇcným u´ cˇ elem neˇz pˇredchoz´ı heuristiky - jej´ım u´ kolem je vyb´ırat tahy zámˇernˇe s menˇs´ım bodovým ohodnocen´ım tak, aby na konci hry byl bodový zisk hrácˇ e pouˇz´ıvaj´ıc´ıho tuto heuristikou menˇs´ı neˇz u ostatn´ıch hrácˇ u˚ .

24

Literatura [1] Andrew W. Appel and Guy J. Jacobson. The world’s fastest scrabble program. http://www.gtoal.com/wordgames/jacobson+appel/aj.pdf, 1988. Dostupná v kvˇetnu 2007. [2] Filip Dvoˇra´ k. Nastaven´ı heuristik. http://ksvi.mff.cuni.cz/~mraz/nn/nnpres07/Scrabble.pdf. Dostupná v kvˇetnu 2007. [3] Steven A. Gordon. A faster scrabble move generation algorithm. http://www.cs.ubc.ca/rr/proceedings/spe91-95/spe/vol24/issue2/spe880.pdf, 1994. Dostupná v kvˇetnu 2007. [4] Jan Pomikálek. Monte carlo metoda ve hˇre scrabble. http://nlp.fi.muni.cz/~xpomikal/scrabble/, 2004. Dostupná v kvˇetnu 2007. [5] WWW stránky. Directed acyclic word graphs. http://www.wutka.com/dawg.html. Dostupná v kvˇetnu 2007. [6] WWW stránky. Mid profile. http://java.sun.com/javame/reference/apis/jsr118/. Dostupná v kvˇetnu 2007. [7] WWW stránky. Oficiáln´ı pravidla scrabble. http://scrabble.hrejsi.cz/cgi/cas/index.pl?volba=pravidla/index.htm. Dostupná v kvˇetnu 2007. [8] WWW stránky. Scrabble - source code. http://www.gtoal.com/wordgames/scrabble.html. Dostupná v kvˇetnu 2007. [9] WWW stránky. Appel-jacobson original form. http://www.gtoal.com/wordgames/gatekeeper/crab.sh.txt, 1992. Dostupná v kvˇetnu 2007. [10] Piotr Wróblewski. Algoritmy, datové struktury a programovac´ı techniky. Computer Press, 2004. ISBN 80-251-0343-9.

25

Pˇr´ıloha Pravidla Scrabblu Jde o stoln´ı hru, kde spolu mohou hrát aˇz cˇ tyˇri hrácˇ i. Ti se snaˇz´ı vkládat na hrac´ı plochu p´ısmena, která maj´ı kaˇzdý zvlásˇt’ ve svém zásobn´ıku. Vˇsechna p´ısmena na hrac´ı ploˇse mus´ı po kaˇzdém tahu tvoˇrit skuteˇcná slova a to bud’ zprava doleva nebo shora dol˚u. Kaˇzdé vloˇzené slovo (kromˇe prvn´ıho) mus´ı navazovat na nˇejaké jiˇz vloˇzené p´ısmeno. Hru tvoˇr´ı tˇri základn´ı prvky: • sácˇ ek se vˇsemi kameny • zásobn´ık s kameny (kaˇzdý hrácˇ má k dispozici jeden) • hrac´ı plocha, na kterou se kameny vkládaj´ı

Jak zaˇc´ıt hru Vˇsechny hrac´ı kameny jsou vloˇzeny do sácˇ ku. Na zaˇca´ tku hry si kaˇzdý hrácˇ vytáhne ze sácˇ ku jeden hrac´ı kámen. Hrácˇ , který si vytáhne kámen s p´ısmenem nejbliˇzsˇ´ım zaˇca´ tku abecedy, zaˇc´ıná. Vytaˇzené kameny se vrát´ı do sácˇ ku. Kaˇzdý hrácˇ si pak vylosuje sedm nových hrac´ıch kamen˚u a uloˇz´ı si je do zásobn´ıku. Zaˇc´ınaj´ıc´ı hrácˇ provede prvn´ı tah a pak táhnou postupnˇe dalˇs´ı hrácˇ i. Kaˇzdý hrácˇ má ve svém tahu na výbˇer: um´ıstˇen´ı slova na hrac´ı plochu nebo výmˇenu kamen˚u nebo vynechán´ı tahu (“PASS”).

Výmˇena kamenu˚ Kaˇzdý hrácˇ m˚uzˇ e vyuˇz´ıt svého tahu k výmˇenˇe nˇekterých cˇ i vˇsech svých kamen˚u. Nejdˇr´ıve vyjme vybrané kameny ze zásobn´ıku, pak vylosuje stejný poˇcet kamen˚u ze sácˇ ku, um´ıst´ı je do zásobn´ıku a nakonec zbylé kameny vrát´ı do sácˇ ku. Podm´ınkou výmˇeny je minimálnˇe sedm hrac´ıch kamen˚u v sácˇ ku, a to i v pˇr´ıpadˇe, zˇ e hrácˇ chce mˇenit jen jeden hrac´ı kámen.

“PASS” (vynechán´ı tahu) Nam´ısto tvoˇren´ı slov na hern´ım plánu nebo výmˇeny kamen˚u m˚uzˇ e hrácˇ ohlásit PASS - tj. vynechat tah. To m˚uzˇ e udˇelat vˇzdy, podle svého uvázˇ en´ı, at’ je cˇ i nen´ı schopen z p´ısmen ve svém zásobn´ıku utvoˇrit nová slova. Ale pokud vˇsichni hrácˇ i ohlás´ı PASS ve dvou po sobˇe následuj´ıc´ıch kolech, hra konˇc´ı.

Um´ıstˇen´ı prvn´ıho slova Prvn´ı hrácˇ zkombinuje dva cˇ i v´ıce kamen˚u, vytvoˇr´ı slovo a poloˇz´ı je na hern´ı plán, aby slovo bylo cˇ itelné zleva doprava cˇ i shora dol˚u a jeden z kamen˚u leˇzel na stˇredovém poli. Slova poloˇzená diagonálnˇe jsou neplatná. 26

Vˇsechny kameny hrané v jednom tahu mus´ı být poloˇzeny pouze v jedné linii, a to vodorovnˇe nebo svisle.

Pˇr´ıpustná slova U bˇezˇ né hry hrácˇ i rozhoduj´ı o správnosti slova podle vybraných slovn´ık˚u, na kterých se vˇsichni shodnou. V této práci je k dispozici jeden slovn´ık s 83 000 slov a hrácˇ i-poˇc´ıtaˇce podle nˇej tvoˇr´ı slova. Hrácˇ -ˇclovˇek si m˚uzˇ e vypnou validaci jeho slov a nemus´ı hrát podle tohoto slovn´ıku.

Hrac´ı plán Hrac´ı plán tvoˇr´ı 15 x 15 pol´ıcˇ ek, na která se vkládaj´ı hrac´ı kameny s p´ısmeny. Mezi normáln´ımi pol´ıcˇ ky existuj´ı také prémiová pole s r˚uznými bonusy pro skórován´ı. P´ısmenné prémie znásobuj´ı bodové hodnocen´ı p´ısmen na nˇe poloˇzených. Jsou dva druhy: dvojnásobné a trojnásobné p´ısmenné prémie. Slovn´ı prémie znásobuj´ı bodovou hodnotu celých slov na nˇe poloˇzených. Opˇet existuj´ı dva druhy: dvojnásobné a trojnásobné slovn´ı prémie. Pokud je slovo vloˇzeno souˇcasnˇe na p´ısmennou i slovn´ı prémii, vypoˇcte se nejprve hodnota slova se zapoˇcten´ım p´ısmenných prémi´ı a slovn´ı prémie pak násob´ı celou tuto hodnotu slova. Pokud je v jednom tahu slovo poloˇzeno na v´ıce slovn´ıch prémi´ı souˇcasnˇe, pak se tyto prémie násob´ı. Bonus prémiového pole se zapoˇc´ıtává pouze v tahu, kdy je na toto pole poloˇzen hrac´ı kámen.

Hrac´ı kameny Hra obsahuje 100 hrac´ıch kamen˚u, 98 kamen˚u s jednotlivými p´ısmeny abecedy a dva kameny pˇredstavuj´ıc´ı zˇ ol´ıky (mohou pˇredstavovat jakékoliv p´ısmeno). ˇ ık nemá zˇ a´ dnou bodovou hodnotu. Kaˇzdý hrac´ı kámen má svou bodovou hodnotu. Zol´

Poˇc´ıtán´ı bodu˚ Bodový zisk tahu je souˇctem hodnot jednotlivých kamen˚u v novˇe vytvoˇrených slovech v daném tahu vˇcetnˇe bonus˚u vypl´ıvaj´ıc´ıch z um´ıstˇen´ı kamene na prémiové pole. Hrácˇ , který v jednom tahu uˇzije vˇsech sedmi svých kamen˚u, obdrˇz´ı prémii 50 bod˚u. Tato prémie se pˇripoˇcte k bod˚um z´ıskaným v tomto tahu aˇz po zapoˇcten´ı vˇsech prémi´ı.

Ukonˇcen´ı hry Hra konˇc´ı, pokud jsou vˇsechny kameny rozebrány mezi hrácˇ i a jeden z hrácˇ u˚ uˇz nemá ani jeden kámen. Konec nestane také tehdy, pokud vˇsichni hrácˇ i ve dvou po sobˇe jdouc´ıch kolech vyhlás´ı “PASS”. Na konci hry se skóre kaˇzdého z hrácˇ u˚ sn´ızˇ´ı o hodnotu kamen˚u, které mu zbyly v zásobn´ıku. Pokud nˇekterému z hrácˇ u˚ nezbyl v zásobn´ıku zˇ a´ dný kámen, k jeho skóre se pˇriˇctou hodnoty vˇsech kamen˚u, které zbyly ostatn´ım hrácˇ u˚ m.

27

Ovládán´ı programu Vytvárˇ en´ı hrácˇ u˚ Po prvn´ım spuˇstˇen´ı hry je tˇreba vytvoˇrit nˇejaké hrácˇ e, aby bylo s kým hrát. U hrácˇ e lze nastavit tyto tˇri parametry: 1. Jméno - slouˇz´ı pro identifikaci hrácˇ e 2. Ovládán´ı - hrácˇ je ovládán bud’ cˇ lovˇekem nebo umˇelou inteligenc´ı 3. Obt´ızˇ nost - v pˇr´ıpadˇe ovládán´ı hrácˇ e UI lze nastavit 5 u´ rovn´ı obt´ızˇ nosti Kdyˇz je vytvoˇren alespoˇn jeden hrácˇ , lze spustit samotnou hru.

Postup hran´ı hry Na zaˇca´ tku hry se provád´ı výbˇer hrácˇ u˚ , kteˇr´ı se j´ı zúcˇ astn´ı. Je nutno vybrat alespoˇn jednoho a nejvýsˇe cˇ tyˇri hrácˇ e (podle pravidel). C´ılem hry je tvoˇrit slova z p´ısmen v zásobn´ıku a vkládat je na hern´ı plochu. Zásobn´ık a hern´ı plocha jsou dva nejd˚uleˇzitˇejˇs´ı prvky a jsou proto neustále zobrazeny, aby o nich mˇel hrácˇ v pr˚ubˇehu celé hry pˇrehled. Hrácˇ -ˇclovˇek vloˇz´ı na hrac´ı plochu p´ısmena a potvrd´ı je. T´ım se spust´ı validace novˇe vloˇzeného slova. V pˇr´ıpadˇe validn´ıho tahu se slovo vloˇz´ı na hern´ı plochu a pokraˇcuje se ve hˇre. V opaˇcném pˇr´ıpadˇe se hra m˚uzˇ e dostat do dvou stav˚u: 1. Slovo je správnˇe vloˇzeno na hern´ı plochu (podle pravidel), ale nevyskytuje se ve slovn´ıku. Tento stav je hrácˇ i indikován tak, zˇ e novˇe vloˇzené kameny s p´ısmeny zmˇen´ı svou barvu na cˇ ervenou. Hrácˇ potom mus´ı sv˚uj tah upravit a pokusit se o nový. 2. Slovo nen´ı na hern´ı plochu vloˇzeno podle pravidel. Takové slovo se i pˇresto m˚uzˇ e vyskytovat ve slovn´ıku, ale pravidla Scrabblu tah neumoˇznˇ uj´ı vloˇzit. Jsou to tahy, kdy napˇr. slovo nenavazuje na jiˇz vloˇzené p´ısmeno, slovo nen´ı um´ıstˇeno v jednom ˇra´ dku cˇ i sloupci, atd. V tomto pˇr´ıpadˇe se zobraz´ı upozornˇen´ı vysvˇetluj´ıc´ı neuznán´ı tahu a hrácˇ mus´ı zvolit tah jiný. Bˇehem tahu poˇc´ıtaˇce (kdy prohledává stavový prostor slovn´ıku) lze neustále sledovat hrac´ı plochu a pohybovat se po n´ı. Hrácˇ -ˇclovˇek se pˇri tomto stavu dostane do pozice pozorovatele a je mu znemoˇznˇeno jakkoliv zasahovat do hry (kromˇe ukonˇcen´ı hry). Na kaˇzdý tah je vymezen urˇcitý cˇ asový interval (pro cˇ lovˇeka i UI). Pokud do této doby hrácˇ nezahraje validn´ı tah nebo nevymˇen´ı p´ısmena v zásobn´ıku, automaticky se jeho tah bere jako “PASS”.

28

Obrázek 8.1: Ukázka ze hry

29

SCRABBLE PRO MOBILNÍ TELEFONY

Recommend Documents