ˇ ´I TECHNICKE ´ V BRNE ˇ VYSOKE´ UCEN BRNO UNIVERSITY OF TECHNOLOGY
ˇ ´ICH TECHNOLOGI´I FAKULTA INFORMACN ´ ´ U ˚ USTAV INTELIGENTN´ICH SYSTEM FACULTY OF INFORMATION TECHNOLOGY DEPARTMENT OF INTELLIGENT SYSTEMS
ˇ ˇ ˇ SEN ´I ULOH ´ ´I RE S NEURCITOST SOLVING PROBLEMS WITH UNCERTAINTY
´ RSK ˇ ´ PRACE ´ BAKALA A BACHELOR’S THESIS
´ AUTOR PRACE
´ LIBOR HRDY
AUTHOR
´ VEDOUC´I PRACE SUPERVISOR
BRNO 2007
ˇ ˇ Doc. Ing. FRANTISEK V. ZBORIL, CSc.
Zad´ an´ı bakal´ aˇ rsk´ e pr´ ace
Licenˇ cn´ı smlouva Licenˇcn´ı smlouva je uloˇzena v archivu Fakulty informaˇcn´ıch technologi´ı Vysok´eho uˇcen´ı technick´eho v Brnˇe.
Abstrakt V dokumentu je pops´ana implementace logick´e-deskov´e hry Vrhc´aby (anglicky Backgammon), hry pro dva hr´aˇce, pˇriˇcemˇz jeden z hr´aˇc˚ u je zastoupen poˇc´ıtaˇcem. V dokumentu je rozvedena problematika programov´an´ı grafick´eho uˇzivatelsk´eho rozhran´ı pomoc´ı toolkitu WxWidgets a d´ale implementace hern´ıho j´adra (ovl´ad´an´ı hry + UI poˇc´ıtaˇce) s pouˇzit´ım algoritmu ExpectMiniMax, jeˇz se vyuˇz´ıv´a pr´avˇe pro implementaci her jako Vrhc´aby, tedy her, v nichˇz se vyskytuje prvek n´ahody, v tomto konkr´etn´ım pˇr´ıpadˇe hod kostkou.
Kl´ıˇ cov´ a slova WxWidgets, GUI, UI, Alfa-beta, MiniMax, ExpectMiniMax, n´ahoda, hry s neurˇcitost´ı, neurˇcitost, C++
Abstract In this thesis is described implementation of the logical deskgame Backgammon, which is a game for two players, whereas one is substituted by computer. This thesis is focused on the problems of the programming the graphical user interface with help of toolkit WxWidgets and also the implemetnation of the game core (game controls and AI of the computer) by using ExpectMiniMax algorithm, that is used for the implementation of the games with the strong influence of random, games where random plays a big role, in this particular case throwing the cube.
Keywords WxWidgets, GUI, UI, Alpha-beta, MiniMax, ExpectMiniMax, chance, games with uncerntainty, uncerntainty, C++
Citace ˇ sen´ı u Libor Hrd´ y: Reˇ ´loh s neurˇcitost´ı, bakal´aˇrsk´a pr´ace, Brno, FIT VUT v Brnˇe, 2007
ˇ sen´ı u Reˇ ´ loh s neurˇ citost´ı Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem tuto bakal´aˇrskou pr´aci vypracoval samostatnˇe pod veden´ım pana doc. Ing. Frantiˇska V´ıtˇezslava Zboˇrila CSc. a ˇze jsem uvedl vˇsechny liter´arn´ı prameny a publikace, ze kter´ ych jsem ˇcerpal. ....................... Libor Hrd´ y 15. kvˇetna 2007
Podˇ ekov´ an´ı Zde bych r´ad podˇekoval panu doc. Ing. Frantiˇsku V´ıtˇezslavu Zboˇrilovi CSc. za pomoc a rady, kter´e mi poskytl pˇri ˇreˇsen´ı t´eto pr´ace a tak´e za studijn´ı oporu pro pˇredmˇet Z´ aklady umˇel´e inteligence, kter´a se pˇri pr´aci na totmo projektu stala m´ ym hlavn´ım studijn´ım materi´alem.
c Libor Hrd´
y, 2007. Tato pr´ ace vznikla jako ˇskoln´ı d´ılo na Vysok´em uˇcen´ı technick´em v Brnˇe, Fakultˇe informaˇcn´ıch technologi´ı. Pr´ ace je chr´ anˇena autorsk´ym z´ akonem a jej´ı uˇzit´ı bez udˇelen´ı opr´ avnˇen´ı autorem je nez´ akonn´e, s v´yjimkou z´ akonem definovan´ych pˇr´ıpad˚ u.
Obsah ´ 1 Uvod
2
2 Charakteristika souˇ casn´ eho stavu
3
3 Teoretick´ y n´ ahled 3.1 Umˇel´a inteligence . . . . . . . 3.2 Metody ˇreˇsen´ı u ´loh . . . . . . 3.3 Metody hran´ı her . . . . . . . 3.3.1 Jednoduch´e hry . . . . 3.3.2 Sloˇzit´e hry . . . . . . 3.3.3 Alfa-beta proˇrez´av´an´ı 3.3.4 Hry s neurˇcitost´ı . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
4 Praktick´ aˇ c´ ast 4.1 V´ ybˇer hry pro demonstraci - Vrhc´aby 4.2 Anal´ yza probl´emu . . . . . . . . . . . 4.2.1 Vlastn´ı ˇreˇsen´ı . . . . . . . . . . 4.3 Grafick´e uˇzivatelsk´e rozhran´ı . . . . . 4.3.1 Reprezentace hrac´ı plochy . . . 4.3.2 Reprezentace hrac´ıch kostek . . 4.4 Hern´ı j´adro . . . . . . . . . . . . . . . 4.4.1 Poˇc´ateˇcn´ı stav hry . . . . . . . 4.4.2 F´aze hodu kostkou . . . . . . . 4.4.3 F´aze tahu hr´aˇce . . . . . . . . 5 Z´ avˇ er
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
. . . . . . . . . .
. . . . . . .
4 4 5 6 8 8 10 12
. . . . . . . . . .
14 14 15 15 16 17 19 20 20 20 20 22
1
Kapitola 1
´ Uvod ˇ sen´ı u T´ema m´e bakal´aˇrsk´e pr´ace je Reˇ ´loh s neurˇcitost´ı a spad´a do kategorie umˇel´e inteligence. V t´eto dokumentaci, strukturovan´e do dvou hlavn´ıch ˇc´ast´ı, v prvn´ı z nich nazvan´e Teoretick´y n´ ahled nejprve popisuji aktu´aln´ı stav t´eto pr´ace. D´ale se snaˇz´ım uk´azat jednotliv´a odvˇetv´ı vˇedn´ıho oboru UI. V u ´vodu se zamˇeˇruji na oblast Metody ˇreˇsen´ı u ´loh, kterou specializuji v kapitole Metody hran´ı her, kde jsou pops´any nˇekter´e z´akladn´ı metody hran´ı her napˇr. procedury MiniMax a Alfa-beta proˇrez´ av´ an´ı. V samotn´em z´avˇeru t´eto sekce se dost´av´am k popisu problematiky neurˇcitosti a k popisu algoritmu ExpectMiniMax, kter´ y se ˇcasto pouˇz´ıv´a pr´avˇe ve spojen´ı s problematikou neurˇcitosti. Na zaˇc´atku druh´e ˇc´asti popisuji v kapitole V´ybˇer hry pro demonstraci v´ ybˇer demonstraˇcn´ı hry z dan´e mnoˇziny her obsahuj´ıc´ıch prvek n´ahody a tak´e d˚ uvody, kter´e mˇe vedly ke koneˇcn´emu rozhodnut´ı vybrat si hru Vrhc´aby (Backgammon). Pravidla zvolen´e hry jsou shrnuta v pˇr´ıloze A. Osvojen´ı tˇechto pravidel bylo nutn´ ym krokem pro spr´avnou anal´ yzu a n´avrh vlastn´ıho ˇreˇsen´ı, kter´e tvoˇr´ı dalˇs´ı dvˇe kapitoly praktick´e ˇc´asti. Za tˇemito dvˇema body n´asleduje v ˇc´asti s n´azvem Grafick´e uˇzivatelsk´e rozhran´ı popis GUI a jeho koneˇcn´eho n´avrhu. Souˇc´ast´ı kapitoly je i realizace hrac´ı plochy a objekt˚ u, kter´e plocha obsahuje. V n´asleduj´ıc´ı kapitole nazvan´e Hern´ı j´ adro jsou pops´any jednotliv´e stavy hry, kter´e se bˇehem hran´ı pravidelnˇe stˇr´ıdaj´ı. Posledn´ı souˇc´ast´ı dokumentu je z´avˇer, ve kter´em se snaˇz´ım zhodnotit odvedenou pr´aci. Tak´e uv´ad´ım moˇzn´a rozˇs´ıˇren´ı r˚ uzn´ ych ˇc´ast´ı programu vedle pˇr´ınos˚ u, kter´e mi ˇreˇseni t´eto pr´ace dalo. Na konci dokumentu jsou vloˇzeny dvˇe pˇr´ılohy. Pˇr´ıloha A s pravidly hry Vrhc´aby a pˇr´ıloha B obsahuj´ıc´ı adresa´aˇrovou strukturu na pˇriloˇzen´em CD, postup pˇri pˇrekladu programu a struˇcn´ y n´avod k jeho pouˇzit´ı.
2
Kapitola 2
Charakteristika souˇ casn´ eho stavu V r´amci semestr´aln´ıho projektu jsem prostudoval metody ˇreˇsen´ı her s neurˇcitost´ı a z nich jsem si vybral pouˇzit´ı algoritmu ExpectMiniMax (viz 3.3.4). Pro demonstraci jsem si zvolil hru Vrhc´aby (viz kapitola 4.1) a tuto jsem implementoval za pouˇzit´ı jazyka C++. Aktu´aln´ım stavem, kter´ y je pops´an v t´eto dokumentaci, je hrateln´a verze t´eto hry. Jsou implementov´ana vˇsechna z´akladn´ı pravidla nutn´a ke hran´ı jedn´e hry, tzn. kaˇzd´a hra konˇc´ı v´ıtˇezstv´ım jednoho z hr´aˇc˚ u, ale tyto v´ ysledky nejsou d´ale nijak zpracov´av´any. S´erie her se z´avˇereˇcn´ ym vyhodnocen´ım je moˇzn´e rozˇs´ıˇren´ı, kter´e bych r´ad doimplementoval jiˇz jako mimoˇskoln´ı projekt. V t´eto souvislosti bych t´eˇz implementoval modul zvyˇsov´an´ı hodnoty v´ıtˇezstv´ı hry. K tomuto zvyˇsov´an´ı se pouˇz´ıv´a speci´aln´ı s´azec´ı kostka, kter´a se nach´az´ı jiˇz v souˇcasn´e verzi, ale zat´ım nen´ı aktivn´ı. Hra je ovl´ad´ana v´ yhradnˇe myˇs´ı. Aktu´aln´ı grafick´e uˇzivatelsk´e rozhran´ı (d´ale jen GUI) je vytvoˇreno pomoc´ı toolkitu WxWidgets. GUI je tvoˇreno hern´ım menu, stavov´ ym ˇr´adek a interaktivn´ı hrac´ı plochou, kter´a je d´ale rozdˇelena do menˇs´ıch oblast´ı (viz 4.4) reaguj´ıc´ıch na vstup uˇzivatele. Kaˇzd´ y objekt ve hˇre je reprezentov´an obr´azkem ve form´atu png. Tento pˇr´ıstup umoˇzn ˇuje jednoduˇse zmˇenit vzhled hry. Dalˇs´ım moˇzn´ ym rozˇs´ıˇren´ım je pr´avˇe volba vzhledu hrac´ı desky, hrac´ıch kamen˚ u, ˇci kostek ve hˇre. Do GUI jsem n´aslednˇe zakomponoval hern´ı j´adro, kter´e je implementov´ano pro hru hr´ aˇce (uˇzivatele) proti poˇc´ıtaˇci. Skl´ad´a se z d´ılˇc´ıch funkc´ı, kter´e ˇreˇs´ı jednotliv´e probl´emy v pr˚ ubˇehu hry. Jedn´a se napˇr. o zjiˇstˇen´ı korektn´ıho tahu v dan´e situaci nebo nalezen´ı nejlepˇs´ıho tahu pro hr´aˇce ovl´adan´eho poˇc´ıtaˇcem. Nalezen´ı nejlepˇs´ıho tahu tvoˇr´ı vlastn´ı umˇelou inteligenci poˇc´ıtaˇce a je implementov´ano pomoc´ı algoritmu ExpectMiniMax (viz 3.3.4). I tuto oblast je moˇzn´e rozˇs´ıˇrit a sice aplikac´ı procedury alfa-beta proˇrez´ av´ an´ı (viz 3.5) na algoritmus ExpectMiniMax. Uvaˇzovan´ ym rozˇs´ıˇren´ım je napˇr. i zv´ yraznˇen´ı kamene, j´ımˇz se pr´avˇe t´ahne, nebo kostky, jej´ıˇz hodnota je pr´avˇe k tahu pouˇz´ıv´ana. D´ale pak implementace modulu umoˇzn ˇuj´ıc´ıho krok zpˇet.
3
Kapitola 3
Teoretick´ y n´ ahled V t´eto ˇc´asti dokumentace se nejprve zm´ın´ım o umˇel´e inteligenci (d´ale jen UI) coby vˇedn´ım oboru a o jej´ım souˇcasn´em rozdˇelen´ı do d´ılˇc´ıch odvˇetv´ı. N´asleduje n´ahled na oblast metody ˇreˇsen´ı u ´loh, z nichˇz se zamˇeˇr´ım na metody hran´ı her.
3.1
Umˇ el´ a inteligence
Na UI se m˚ uˇzeme d´ıvat bud’ jako na vlastnost umˇele vytvoˇren´eho syst´emu (viz 3.1.1) nebo jako na vˇedn´ı discipl´ınu (viz 3.1.2). Definice 3.1.1 “Umˇel´ a inteligence je vlastnost ˇclovˇekem umˇele vytvoˇren´ych syst´em˚ u vyznaˇcuj´ıc´ıch se schopnost´ı rozpozn´ avat pˇredmˇety, jevy a situace, analyzovat vztahy mezi nimi a tak vytv´ aˇret vnitˇrn´ı modely svˇeta, ve kter´ych tyto syst´emy existuj´ı, a na tomto z´ akladˇe pak pˇrij´ımat u ´ˇceln´ a rozhodnut´ı, pˇredv´ıdat d˚ usledky tˇechto rozhodnut´ı a objevovat nov´e z´ akonitosti mezi r˚ uzn´ymi modely nebo jejich skupinami.” [3] Definice 3.1.2 “Umˇel´ a inteligence je vˇeda o vytv´ aˇren´ı stroj˚ u nebo syst´em˚ u, kter´e budou pˇri ˇreˇsen´ı urˇcit´eho u ´kolu uˇz´ıvat takov´eho postupu, kter´y - kdyby ho dˇelal ˇclovˇek - bychom povaˇzovali za projev jeho inteligence.” [4] D´ale v textu bude UI ch´ap´ana dle znˇen´ı definice jako vˇedn´ı obor, kter´ y nem´a pevnˇe vymezen´ y pˇredmˇet zkoum´an´ı ani teoretick´ y z´aklad. Jedn´a se sp´ıˇse o soubor metod, teoretick´ ych pˇr´ıstup˚ u a algoritm˚ u, slouˇz´ıc´ıch k ˇreˇsen´ı velmi sloˇzit´ ych u ´loh. V´ ysledky tˇechto d´ılˇc´ıch ˇreˇsen´ı slouˇz´ı bud’ jin´ ym vˇedn´ım discipl´ın´am k aplikaci nebo jako z´aklad k formov´ an´ı nov´ ych vˇedn´ıch discipl´ın. Souˇcasn´a UI se pˇrev´aˇznˇe zamˇeˇruje na pr´aci s nejist´ ymi a ne´ upln´ ymi informacemi, na tzv. Softcomputig (zahrnuje neuronov´e s´ıtˇe, genetick´e algoritmy, fuzzy mnoˇziny a fuzzy logiku, hrub´e mnoˇziny, chaos). Tak´e je intenz´ıvnˇe zkoum´ana problematika distribuovan´e UI, tj. problematika agent˚ u a multiagentn´ıch syst´em˚ u. Tyto u ´lohy, kter´ ymi se UI zab´ yv´a, mohou do jist´e m´ıry nahradit nˇekter´e intelektu´aln´ı ˇcinnosti ˇclovˇeka a t´ım se UI rychle rozˇsiˇruje z v´ yzkumn´ ych laboratoˇr´ı do re´aln´eho svˇeta.
4
Aplikaˇcn´ı oblasti UI v dneˇsn´ı dobˇe jsou napˇr´ıklad tyto: • Autonomn´ı pl´anov´an´ı (roboti na mimozemsk´ ych objektech) • Hran´ı her (ˇsachy) • Medic´ınsk´a diagnostika (expertn´ı syst´emy) • Logick´e pl´anov´an´ı (pouˇzito napˇr. pˇri pl´anov´an´ı logistick´ ych operac´ı bˇehem v´alky v Persk´em z´alivu v roce 1991) • Porozumˇen´ı pˇrirozen´emu jazyku (spotˇrebiˇce ovl´adan´e hlasem) • Neuronov´e s´ıtˇe (snaha o napodoben´ı lidsk´eho mozku) • Automatick´e ˇreˇsen´ı sloˇzit´ ych u ´loh (napˇr. luˇstˇen´ı kˇr´ıˇzovek)
3.2
Metody ˇ reˇ sen´ı u ´ loh
Metody ˇreˇsen´ı u ´loh jsou v´ yznamnou problematikou pˇredstavuj´ıc´ı jednu z hlavn´ıch oblast´ı klasick´e UI. Tato oblast se zab´ yv´a konstrukc´ı inteligentn´ıch syst´em˚ u, jejichˇz d˚ uleˇzit´ ym rysem je schopnost vytv´aˇret vnitˇrn´ı model svˇeta a pracovat s n´ım. Je-li d´an poˇc´ateˇcn´ı a c´ılov´ y model prostˇred´ı, je u ´kolem syst´em˚ u UI vyhledat takovou posloupnost akc´ı, jejichˇz aplikac´ı lze doj´ıt od stavu poˇc´ateˇcn´ıho do stavu c´ılov´eho. Kaˇzd´emu modelu odpov´ıd´a urˇcit´ y stav prostˇred´ı, jejich mnoˇzina spolu s mnoˇzinou akc´ı (oper´ator˚ u), kter´e umoˇzn ˇuj´ı stavy u ´lohy mˇenit, tvoˇr´ı stavov´ y prostor. C´ılov´ ych stav˚ u m˚ uˇze b´ yt v´ıce a mohou b´ yt pops´any podm´ınkami, kter´e mus´ı splˇ novat. Reprezentaci ˇreˇsen´e u ´lohy (stavov´eho prostoru) lze zn´azornit r˚ uzn´ ym zp˚ usobem. Nejˇcastˇeji se pouˇz´ıv´a zn´azornˇen´ı orientovan´ ym stromem s uzly, kter´e pˇredstavuj´ı jednotliv´e stavy a hranami, kter´e zn´azorˇ nuj´ı pˇrechody mezi tˇemito uzly. Na obr´azku 3.1 je pˇr´ıklad stavov´eho prostoru, kde uzel A je uzlem koˇrenov´ ym, z´aroveˇ n oznaˇcuje i poˇc´ateˇcn´ı stav a je v hloubce 0. Uzly H, K aˇz U jsou uzly listov´e a uzel R reprezentuje koncov´ y stav v hloubce 3.
Obr´azek 3.1: Uk´azka stavov´eho prostoru 5
Prvn´ım u ´kolem pˇri ˇreˇsen´ı kaˇzd´e u ´lohy je jednoznaˇcn´a formulace jej´ıch c´ıl˚ u a jednoznaˇcn´ a definice oper´ator˚ u, kter´a zahrnuje i pˇr´ıpadn´e podm´ınky omezuj´ıc´ı jejich pouˇzit´ı. Metody ˇreˇsen´ı u ´loh n´am pak nab´ızej´ı postupy, kter´ ymi lze c´ılov´e stavy, resp. posloupnosti oper´ator˚ u vedouc´ı k c´ılov´ ym stav˚ um, nal´ezat a pˇredstavuj´ı tak prostˇredky nepostradateln´e ve vˇsech aplikaˇcn´ıch oblastech UI. Pˇri automatick´em ˇreˇsen´ı u ´loh je tˇreba pro nalezen´ı ˇreˇsen´ı pouˇz´ıt vhodnou metodu (strategii). Pro kaˇzd´ y typ probl´emu se hod´ı jin´e metody. Podle tohoto krit´eria se daj´ı metody ˇreˇsen´ı u ´loh rozdˇelit napˇr. n´asledovnˇe: • Metody zaloˇzen´e na prohled´av´an´ı stavov´eho prostoru (prohled´av´an´ı do ˇs´ıˇrky, prohled´av´an´ı do hloubky, backtracking aj.) • Metody ˇreˇsen´ı u ´loh s omezuj´ıc´ımi podm´ınkami (forward checking, metoda minim´aln´ıho konfliktu) • Metody zaloˇzen´e na rozkladu u ´loh/probl´em˚ u na podprobl´emy (pouˇzit´ı AND/OR graf˚ u) • Metody hran´ı her (algoritmus MiniMax)
3.3
Metody hran´ı her
Metody hran´ı her uveden´e v t´eto kapitole jsou omezeny pouze na hry se dvˇema (proti)hr´ aˇci, kteˇr´ı se po jednotliv´ ych taz´ıch hry pravidelnˇe stˇr´ıdaj´ı. Oba hr´aˇci maj´ı vˇsechny informace o hˇre a jej´ım souˇcasn´em stavu. Tato informace je koneˇcn´a (pozice) a obsahuje t´eˇz u ´daj o tom, kter´ y hr´aˇc pr´avˇe t´ahne. D´ale existuj´ı pravidla hry, jenˇz urˇcuj´ı ke kaˇzd´e pozici pro pr´ avˇe t´ahnouc´ıho hr´aˇce koneˇcn´ y poˇcet pˇr´ıpustn´ ych tah˚ u. Krokem hry (tahem, popˇr. p˚ ultahem) je, kdyˇz si t´ahnouc´ı hr´aˇc vybere jeden z pˇr´ıpustn´ ych tah˚ u a provede jej. T´ım vznikne nov´ a pozice a na tahu je soupeˇr. Hra pokraˇcuje, dokud se nedostane do z´avˇereˇcn´e f´aze, u kter´e mus´ı b´ yt t´eˇz definov´ano, kdo vyhr´al ˇci prohr´al, pˇr´ıp. ˇze jde o rem´ızu. D´ale zm´ınˇen´e metody jsou zaloˇzeny na rozkladu u ´lohy na podprobl´emy, coˇz je pˇrirozen´ a metoda, kterou pˇri ˇreˇsen´ı obt´ıˇzn´ ych probl´em˚ u pouˇz´ıv´a i ˇclovˇek. Pˇri rozkladu m˚ uˇzeme narazit na dva typy podprobl´em˚ u (viz obr´azek 3.2). Probl´em AND (na obr´azku uzel A), kter´ y je ˇreˇsiteln´ y pokud jsou ˇreˇsiteln´e vˇsechny jeho podprobl´emy a probl´em OR (uzel Z), kter´ y je ˇreˇsiteln´ y, je-li ˇreˇsiteln´ y alespoˇ n jeden z jeho podprobl´em˚ u.
Obr´azek 3.2: Podprobl´emy typu AND a OR.
6
Na obr´azku 3.3 je vidˇet pˇr´ıpadn´e ˇreˇsen´ı nesourodosti probl´emu na stejn´e u ´rovni zanoˇren´ı, jeˇz spoˇc´ıv´a v pˇrid´an´ı pomocn´eho uzlu (na obr´azku uzel P) ˇci odebr´an´ı pˇrebyteˇcn´eho uzlu (uzel D). Touto u ´pravou vznikne tzv. “ˇcist´ y” AND/OR graf, kter´ y lze pˇri ˇreˇsen´ı hern´ıch u ´loh proch´azet podobnˇe jako stavov´ y prostor.
Obr´azek 3.3: Pˇr´ıklad pˇrevodu na “ˇcist´ y” AND/OR graf
Pˇri hran´ı her, respektive pˇri aplikaci metod pro hran´ı her, je ˇreˇsen´ ym probl´emem nalezen´ı tahu hr´aˇce, kter´ y pr´avˇe t´ahne (hr´aˇc A). Z pohledu tohoto hr´aˇce bude probl´em ˇreˇsiteln´ y, pokud k jeho v´ yhˇre povede alespoˇ n jeden z jeho moˇzn´ ych n´asleduj´ıc´ıch tah˚ u (probl´em OR). Pˇri dalˇs´ım kroku t´ahne protihr´aˇc (hr´aˇc B), kter´ y se snaˇz´ı zabr´anit ve v´ yhˇre hr´aˇci A. Drˇz´ımeli se pohledu hr´aˇce A, mus´ı b´ yt vˇsechny tahy hr´aˇce B n´asleduj´ıc´ı po tahu hr´aˇce A pro hr´ aˇce B neˇreˇsiteln´e, jinak ˇreˇceno, vˇsechny tahy hr´aˇce B mus´ı b´ yt ˇreˇsiteln´e pro hr´aˇce A (probl´em AND). Hled´an´ı tahu vedouc´ıho k v´ yhˇre tak vede na klasick´e prohled´av´an´ı AND/OR grafu. Kdyˇz se hr´aˇc A dostane znovu na ˇradu, nem˚ uˇze pouˇz´ıt v´ ysledky z pˇredchoz´ıho pr˚ uchodu, protoˇze na rozd´ıl od nov´eho stavu hry nejsou tyto ovlivnˇeny pr´avˇe skonˇcen´ ym tahem hr´ aˇce B, ale mus´ı znovu naj´ıt a vybrat sv˚ uj tah jiˇz z nov´eho konkr´etn´ıho stavu u ´lohy. Po vyhodnocen´ı vˇsech pˇr´ıpustn´ ych tah˚ u si hr´aˇc, kter´ y t´ahne (uvaˇzujme hr´aˇce A), vybere tah s nejlepˇs´ım ohodnocen´ım, kter´e urˇcuje tzv. “funkce zisku” nebo t´eˇz “pˇr´ınosnosti”, kde toto ohodnocen´ı odr´aˇz´ı aktu´aln´ı stav hry ve prospˇech hr´aˇce A. Z toho plyne, ˇze zat´ımco hr´ aˇc A si vyb´ır´a tahy s nejvˇetˇs´ım ohodnocen´ım, hr´aˇc B vyb´ır´a (respektive je toto pˇri strojov´em vyhodnocen´ı uvaˇzov´ano) nejm´enˇe ohodnocen´e tahy, aby hr´aˇci A co nejv´ıce znemoˇznil ˇsanci na v´ yhru. U norm´aln´ıho vyhled´avac´ıho probl´emu by hr´aˇc A prostˇe hledal sekvenci tah˚ u vedouc´ıch do v´ıtˇezn´eho koneˇcn´eho stavu (s pouˇzit´ım funkce pˇr´ınosnosti) a po nalezen´ı cesty by vybral prvn´ı z tah˚ u takov´e sekvence. Protihr´aˇc B ale hru ovlivˇ nuje, proto mus´ı hr´aˇc A naj´ıt strategii vedouc´ı ke koneˇcn´emu stavu bez ohledu na to, co hr´aˇc B dˇel´a. Strategie obsahuje korektn´ı tah (tah podle pravidel) pro hr´aˇce A jako odpovˇed’ na kaˇzd´ y moˇzn´ y tah protihr´aˇce. Existuj´ı cesty k nalezen´ı strategie, i kdyˇz omezen´ım pro v´ ypoˇcet m˚ uˇze b´ yt (a b´ yv´a) ˇcasov´ y limit. Takto popsan´e hry lze rozdˇelit na jednoduch´e, sloˇzit´e a hry s neurˇcitost´ı.
7
3.3.1
Jednoduch´ e hry
Za jednoduch´e hry se povaˇzuj´ı takov´e hry, u nichˇz je moˇzn´e v re´aln´em ˇcase prohledat cel´ y jejich AND/OR graf aˇz do nalezen´ı nˇejak´eho c´ılov´eho stavu (v´ yhra, prohra, rem´ıza). K ˇreˇsen´ı se m˚ uˇze pouˇz´ıt napˇr´ıklad AO algoritmus, kter´ y je z´akladn´ım neinformovan´ ym algoritmem. Podobnˇe jako u prohled´av´an´ı stavov´eho prostoru m˚ uˇzeme i nyn´ı vyˇsetˇrovat ˇreˇsitelnost probl´emu proch´azen´ım AND/OR grafu do hloubky nebo do ˇs´ıˇrky (podle toho, kter´ y z uzl˚ u vyjmeme ze seznamu OPEN). AO algoritmus 1. Sestroj pr´azdn´e seznamy OPEN a CLOSED. Do seznamu OPEN uloˇz poˇc´ateˇcn´ı uzel (probl´em). 2. Vyjmi uzel zleva ze seznamu OPEN a oznaˇc jej jako uzel X. 3. (a) Pokud je uzel (probl´em) X ˇreˇsiteln´ y, pˇridej informaci o jeho ˇreˇsitelnosti jeho pˇredch˚ udc˚ um. Je-li X z´aroveˇ n poˇc´ateˇcn´ım probl´emem, ukonˇci ˇreˇsen´ı jako u ´spˇeˇsn´e vytvoˇr a vrat’ relevantn´ı ˇc´ast AND/OR grafu. (b) Nen´ı-li uzel (probl´em) X ˇreˇsiteln´ y a nelze-li jej rozloˇzit na podprobl´emy, pˇredej informaci o jeho neˇreˇsitelnosti jeho pˇredch˚ udc˚ um. Je-li X z´aroveˇ n poˇc´ateˇcn´ım probl´emem, ukonˇci ˇreˇsen´ı jako ne´ uspˇeˇsn´e. (c) Expanduj X (rozloˇz X na podprobl´emy) a vˇsechny jeho n´asledn´ıky uloˇz do OPEN. 4. Uloˇz X do CLOSED. 5. Je-li seznam OPEN pr´azdn´ y, ukonˇci ˇreˇsen´ı jako ne´ uspˇeˇsn´e, jinak se vrat’ na bod 2. S t´ım, ˇze v pˇr´ıpadˇe ˇreˇsitelnosti nen´ı nutn´e vracet celou ˇc´ast AND/OR grafu, ale pouze tah hr´aˇce A, kter´ y vede k jeho v´ yhˇre.
3.3.2
Sloˇ zit´ e hry
Za sloˇzit´e hry povaˇzujeme hry, u kter´ ych, pro velk´ y poˇcet uzl˚ u v prohled´avac´ım stromu (AND/OR grafu), nen´ı kompletn´ı pr˚ uchod tohoto stromu z ˇcasov´ ych d˚ uvod˚ u re´aln´ y (napˇr. ˇsachy, Vrhc´aby). K ˇreˇsen´ı takov´ ychto her se m˚ uˇze pouˇzit napˇr. algoritmus MiniMax. Z´akladem algoritmu MiniMax je rekurzivn´ı procedura, oznaˇcovan´a tak´e jako MiniMax, kter´a se zavol´a pro aktu´aln´ı stav hry (koˇrenov´ y uzel AND/OR grafu) a hr´aˇce, kter´ y je na tahu (hr´aˇc MAX). Tato procedura vrac´ı ohodnocen´ı uzlu a pro hr´aˇce MAX i tah k uzlu s maxim´aln´ım ohodnocen´ım, tj. tah, kter´ y je v dan´em stavu hry pro tohoto hr´ aˇce nejv´ yhodnˇejˇs´ı. Samotn´e ohodnocen´ı uzlu poˇc´ıt´a jiˇz dˇr´ıve zmiˇ novan´a funkce zisku, kter´a tak ˇcin´ı na z´akladˇe pˇrevodu situace na hrac´ım poli na jedin´e konkr´etn´ı ˇc´ıslo. Funkce zisku se pro kaˇzdou hru liˇs´ı a pˇri jej´ım n´avrhu lze zohlednit napˇr. poˇcet figur, jejich “s´ılu”, pozici na hrac´ı ploˇse apod.
8
Na rozd´ıl od ˇreˇsen´ı jednoduch´ ych her, kdy je moˇzn´e proj´ıt prohled´avac´ım stromem aˇz k uzlu, kter´ y je koncov´ ym stavem u ´lohy, zde procedura MiniMax pˇredpokl´ad´a, ˇze je zad´ana maxim´aln´ı hloubka prohled´av´an´ı (poˇcet zkouman´ ych tah˚ u) a hodnoty termin´aln´ıch uzl˚ u tak neodr´aˇz´ı v´ yhru nebo por´aˇzku.1
Procedura MiniMax 1. Nazvˇeme pˇredan´ y vstupn´ı uzel uzlem X. 2. Je-li uzel X listem (koneˇcn´ ym stavem hry nebo uzlem v maxim´aln´ı hloubce), vrat’ ohodnocen´ı tohoto uzlu. Jinak pokraˇcuj. 3. Je-li na tahu hr´aˇc MAX, tak postupnˇe pro vˇsechny jeho moˇzn´e tahy (bezprostˇredn´ı n´asledn´ıky uzlu X a hr´aˇce MIN) volej proceduru MiniMax a vrat’ maxim´aln´ı z navr´acen´ ych hodnot. Je-li X koˇrenov´ ym uzlem vrat’ i tah, kter´ y vede k nejl´epe ohodnocen´emu bezprostˇredn´ımu n´asledn´ıkovi. 4. Je-li na tahu hr´aˇc MIN, tak postupnˇe pro vˇsechny jeho moˇzn´e tahy (bezprostˇredn´ı n´asledn´ıky uzlu X a hr´aˇce MAX) volej proceduru MiniMax a vrat’ minim´aln´ı z navr´acen´ ych hodnot. Pˇri pouˇzit´ı procedury MiniMax doch´az´ı ke zbyteˇcn´emu vyˇsetˇrov´an´ı velk´e ˇc´asti AND/OR uvodu, kter´ y je bl´ıˇze vysvˇetlen v n´asleduj´ıc´ım pˇr´ıkladu na prografu (viz obr´azek 3.4) z d˚ ceduru MiniMax. V obr´azku jsou vyznaˇceny zbyteˇcnˇe vyˇsetˇrovan´e uzly ˇcervenˇe, takov´ ych uzl˚ u je pˇribliˇznˇe 30% (13 ze 40ti). Tento pˇr´ıklad je z velk´e ˇc´asti pˇrevzat z opory pˇredmˇetu IZU. [1] Pˇ r´ıklad pouˇ zit´ı algoritmu MiniMax Hr´aˇc MAX (koˇrenov´ y uzel A) vol´a proceduru MiniMax na sv˚ uj prvn´ı tah a hr´aˇce MIN (uzel B) a ten vol´a tuto proceduru na sv˚ uj prvn´ı tah a hr´aˇce MAX (uzel C). Hr´aˇc MAX (uzel C) vol´a proceduru MiniMax postupnˇe na vˇsechny sv´e moˇzn´e tahy a hr´aˇce MIN, protoˇze vˇsichni jeho bezprostˇredn´ı n´asledn´ıci jsou uzlov´ ymi listy, procedura MiniMax pouze postupnˇe vrac´ı ohodnocen´ı tˇechto list˚ u a hr´aˇc MAX pak vybere (vr´at´ı) maxim´aln´ı hodnotu z jejich ohodnocen´ı (tj. ˇc´ıslo 8). Hr´aˇc MIN (uzel B) tuto hodnotu akceptuje a vol´a proceduru MiniMax na sv˚ uj druh´ y tah a hr´aˇce MAX (uzel D). Prvn´ı bezprostˇredn´ı n´asledn´ık tohoto uzlu (listov´ y uzel) vrac´ı hodnotu 9. Je zˇrejm´e, ˇze prohled´av´an´ı dalˇs´ıch n´asledn´ık˚ u uzlu D je zbyteˇcn´e, protoˇze jiˇz nyn´ı je jasn´e, ˇze tento uzel vr´at´ı hodnotu ≥ 9, a ˇze hr´aˇc MIN (uzel B), kter´ y si vyb´ır´a tah s minim´aln´ım ohodnocen´ım, si tento tah nevybere, protoˇze ohodnocen´ı jeho prvn´ıho tahu je menˇs´ı. Hr´aˇc MIN (uzel B) pak vol´a proceduru MiniMax na sv˚ uj posledn´ı tah a hr´aˇce MAX (uzel E). Hr´aˇc MAX (uzel E) opˇet vol´a postupnˇe proceduru MiniMax na vˇsechny sv´e bezprostˇredn´ı n´asledn´ıky a z vr´acen´ ych hodnot vybere (vr´at´ı) hodnotu maxim´aln´ı, tj. hodnotu 4. Protoˇze tato hodnota je menˇs´ı neˇz hodnota 8, hr´aˇc MIN (uzel B) si vybere a vr´ at´ı 1
Pˇri oceˇ nov´ an´ı hry s omezenou hloubkou mohou nˇekdy v´est heuristicky slibn´e cesty pozdˇeji ve hˇre do ˇspatn´e situace - jedn´ a se o tzv. horizont efekt.
9
tuto hodnotu. Hr´aˇc MAX (uzel A) hodnotu 4 akceptuje a vol´a proceduru MiniMax na sv˚ uj druh´ y moˇzn´ y tah a hr´aˇce MIN (uzel F). Dalˇs´ı postup pro tento tah je velmi podobn´ y postupu pro prvn´ı tah. Hr´aˇc MIN (uzel F) vol´a postupnˇe proceduru MiniMax na sv´e bezprostˇredn´ı n´asledn´ıky (uzly G, H a I) a vr´at´ı minimum z vr´acen´ ych hodnot, tj. ˇc´ıslo 5. Nˇekter´e listov´e uzly, na obr´azku oznaˇcen´e ˇcervenou barvou, se opˇet vyˇsetˇruj´ı zbyteˇcnˇe, z d˚ uvod˚ u popsan´ ych v´ yˇse. Protoˇze 5 > 4, akceptuje hr´aˇc MAX (uzel A) tuto hodnotu (druh´ y tah je pro nˇej v´ yhodnˇejˇs´ı, neˇz tah prvn´ı) a vol´a proceduru MiniMax na sv˚ uj tˇret´ı tah a hr´aˇce MIN (uzel J). Hr´aˇc MIN (uzel J) vol´ a proceduru MiniMax na sv˚ uj prvn´ı tah a hr´aˇce MAX (uzel K) a od tohoto uzlu dostane navr´acenu hodnotu 3. Proto je jiˇz v tomto okamˇziku zˇrejm´e, ˇze hr´aˇc MIN (uzel J), kter´ y si vyb´ır´a minimum, vr´at´ı koˇrenov´emu uzlu hodnotu ≤ 3 a hr´aˇc MAX (uzel A) si tento tah nevybere. Dalˇs´ı vyˇsetˇrov´an´ı tah˚ u hr´aˇce MIN (uzlu J) je tak zbyteˇcn´e.
Obr´azek 3.4: Uk´azka pouˇzit´ı algoritmu MiniMax pro jednoduch´e hry
3.3.3
Alfa-beta proˇ rez´ av´ an´ı
Podstata algoritmu alfa-beta proˇrez´ av´ an´ı spoˇc´ıv´a v nalezen´ı “ˇspatn´e vˇetve” (tj. horˇs´ı neˇz doposud nalezen´a nejlepˇs´ı) v prohled´avac´ım stromu. D˚ uleˇzit´e pˇritom je, ˇze nepotˇrebujeme vˇedˇet, jak moc ˇspatn´a tato vˇetev je. Nav´ıc n´as ani nezaj´ım´a, zda-li tam nebude lepˇs´ı podvˇetev, protoˇze soupeˇr by se j´ı jistˇe umˇel vyhnout. Z porovn´an´ı algoritm˚ u minimaxu a alfa-beta proˇrez´av´an´ı vypl´ yv´a vlastnost, ˇze algoritmus alfa-beta proˇrez´av´an´ı vrac´ı hodnotu, kterou by vr´atil p˚ uvodn´ı algoritmus, aniˇz by musel proj´ıt cel´ ym stromem, coˇz je pˇresnˇe to, co jsme potˇrebovali z´ıskat. Pˇri aplikaci algoritmu postupujeme tak, ˇze si pamatujeme nˇejak´e maximum (nebo minimum, pokud jde o minimalizuj´ıc´ı u ´roveˇ n) pro mnoˇzinu uzl˚ u na jedn´e u ´rovni a pokud zjist´ıme, ˇze ohodnocen´ı syn˚ u dalˇs´ıho uzlu v ˇradˇe je menˇs´ı (vˇetˇs´ı) neˇz toto maximum (minimum), nepotˇrebujeme tento uzel d´al rozv´ıjet, protoˇze v´ıme, ˇze uˇz minimaxovou hodnotu sv´eho otce neovlivn´ı.
10
Procedura Alfa-beta 1. Je-li X poˇc´ateˇcn´ım/koˇrenov´ ym uzlem, nastav α = −∞, β = ∞ (v praxi nastav hodnoty tˇechto promˇenn´ ych na minim´aln´ı a maxim´aln´ı moˇznou hodnotu). 2. Je-li uzel X listem (koneˇcn´ ym stavem hry nebo uzlem v maxim´aln´ı hloubce) ukonˇci proceduru a vrat’ ohodnocen´ı tohoto uzlu. 3. Je-li uzel typu AND (na tahu je hr´aˇc MIN) jdi na bod 4, jinak pokraˇcuj (uzel je typu OR, na tahu je hr´aˇc MAX): (a) Dokud je α < β, tak postupnˇe pro prvn´ı/dalˇs´ı tah (bezprostˇredn´ıho n´asledn´ıka uzlu X a hr´aˇce MIN) volej proceduru Alfa-beta s aktu´aln´ımi hodnotami promˇenn´ ych α a β. Po kaˇzd´em vyˇsetˇren´em tahu nastav hodnotu promˇenn´e a na maximum z aktu´aln´ı a navr´acen´e hodnoty . (b) Ukonˇci proceduru, vrat’ aktu´aln´ı hodnotu promˇenn´e α a pro koˇrenov´ y uzel vrat’ i tah, kter´ y vede k nejl´epe ohodnocen´emu bezprostˇredn´ımu n´asledn´ıkovi. 4. Uzel je typu AND (na tahu je hr´aˇc MIN): (a) Dokud je α < β, tak postupnˇe pro prvn´ı/dalˇs´ı tah (bezprostˇredn´ıho n´asledn´ıka uzlu X a hr´aˇce MAX) volej proceduru Alfa-beta s aktu´aln´ımi hodnotami promˇenn´ ych α a β. Po kaˇzd´em vyˇsetˇren´em tahu nastav hodnotu promˇenn´e β na minimum z aktu´aln´ı a navr´acen´e hodnoty . (b) Ukonˇci proceduru a vrat’ aktu´aln´ı hodnotu promˇenn´e β. Na obr´azku 3.5 je vidˇet pouˇzit´ı procedury Alfa-beta. Princip pr˚ uchodu je tu stejn´ y jako u algoritmu MiniMax 3.4 s t´ım, ˇze se “proˇreˇzou” vˇetve, kter´e by se pˇri pouˇzit´ı algoritmu MiniMax proch´azeli zbyteˇcnˇe. Pod´ıv´ame-li se v obr´azku na uzel C, hr´aˇc MAX si zde vybere ze sv´ ych synovsk´ ych uzl˚ u ten s maxim´aln´ım ohodnocen´ım (8). Tuto hodnotu vr´at´ı rodiˇcovsk´emu uzlu (B) a hr´ aˇci MIN, kter´ y ji akceptuje a zavol´a proceduru Alfa-beta pro sv˚ uj dalˇs´ı synovsk´ y uzel D a hr´aˇce MAX. V uzlu D se hr´aˇc snaˇz´ı opˇet vybrat maximum ze sv´ ych synovsk´ ych uzl˚ u, ale jiˇz u prvn´ıho naraz´ı na hodnotu, kter´a je vyˇsˇs´ı neˇz hodnota, kterou vr´atil z uzlu C. Z pohledu
Obr´azek 3.5: Uk´azka pouˇzit´ı procedury Alfa-beta 11
hr´aˇce MIN (uzel B), kter´ y vyb´ır´a minimum, je jiˇz ted’ vidˇet, ˇze si uzel D nevybere, protoˇze hodnota, kter´a se z uzlu D vr´at´ı nebude niˇzˇs´ı neˇz 9. Proto se prohled´av´an´ı v uzlu D ukonˇc´ı a vr´at´ı se hodnota 9, kterou ale hr´aˇc MIN (uzel B) vyb´ıraj´ıc´ı minimum neakceptuje. Stejn´ y princip se uplatn´ı v uzlu F, kde si hr´aˇc MIN vyb´ır´a minimum a kde jiˇz po prohled´an´ı prvn´ıho podstromu (uzel G) je pro hr´aˇce MAX (uzel A) zˇrejm´e, ˇze vˇetev zaˇc´ınaj´ıc´ı uzlem F je m´enˇe atraktivn´ı neˇz vˇetev zaˇc´ınaj´ıc´ı uzlem B, ˇc´ımˇz dojde k “odˇr´ıznut´ı” podstrom˚ u maj´ıc´ıch koˇreny v uzlech H a I.
3.3.4
Hry s neurˇ citost´ı
Dalˇs´ım typem her, v nichˇz opˇet hraj´ı dva protihr´aˇci, kteˇr´ı se po jednotliv´ ych taz´ıch hry pravidelnˇe stˇr´ıdaj´ı, maj´ı u ´plnou informaci o stavu hry, hraj´ı ˇcestnˇe a oba si pˇrej´ı zv´ıtˇezit, jsou hry s neurˇcitost´ı. Jedin´ ym a podstatn´ ym rozd´ılem je, ˇze se pˇri hran´ı tˇechto her pouˇz´ıv´ a kostka, respektive kostky, ˇc´ımˇz do hry vstupuje n´ahoda - neurˇcitost. Z´akladn´ı princip algoritmu ExpectMiniMax je na obr´azku 3.6. Hr´aˇc MAX hodil kostkou ˇc´ıslo ˇsest, hodnota na kostce vˇsak nen´ı pro dalˇs´ı postup podstatn´a.
Obr´azek 3.6: Z´akladn´ı princip algoritmu ExpectMiniMax
Hr´ aˇc MAX nyn´ı v´ı, kter´e sv´e tahy na u ´rovni B m˚ uˇze uskuteˇcnit. A z tˇechto tah˚ u si bude vyb´ırat uzel s maxim´aln´ı (funkce Max()). Vyjde z u ´vahy, ˇze hr´aˇc MIN by pro zn´am´ y v´ ysledek hodu vybral tah do stavu (´ uroveˇ n D) s minim´aln´ım ohodnocen´ım. Hr´aˇc MIN vˇsak v´ ysledek sv´eho hodu nezn´a, a proto m˚ uˇze pracovat pouze s ohodnocen´ım oˇcek´avan´ ym, kter´e je na obr´azku oznaˇceno jako expectMin() (oˇcek´avan´e minimum): expectM in() =
X
P (h) ∗ min(D)
Kde h je v´ ysledek hodu kostkou (1, 2, 3, 4, 5, 6), P (h) je pravdˇepodobnost s jakou m˚ uˇze na kostce padnout konkr´etn´ı hodnota h a min(D) je minim´aln´ı hodnota z uzl˚ u na u ´rovni D. 12
Ohodnocen´ı expectMin je tedy d´ano souˇctem ohodnocen´ı po vˇsech moˇzn´ ych v´ ysledc´ıch hodu kostky (´ uroveˇ n C), kdy kaˇzd´e jednotliv´e ohodnocen´ı je d´ano souˇcinem pravdˇepodobnosti dan´eho v´ ysledku hodu kostky a n´asledn´eho minim´aln´ıho ohodnocen´ı stavu, kter´eho je moˇzn´e po dan´em hodu dos´ahnout (´ uroveˇ n D). Podobn´ ym zp˚ usobem se postupuje pˇri vyˇsetˇrov´an´ı oˇcek´avan´eho ohodnocen´ı na u ´rovni D. Hr´aˇc MAX vyb´ır´a maximum z moˇzn´ ych ohodnocen´ı, na obr´azku toto hodnocen´ı oznaˇceno jako expectMax() (oˇcek´avan´e maximum): expectM ax() =
X
P (h) ∗ max(F )
Kde h je opˇet v´ ysledek hodu kostkou, P (h) je pravdˇepodobnost s jakou m˚ uˇze na kostce padnout konkr´etn´ı hodnota h a max(F ) je maxim´aln´ı hodnota z uzl˚ u na u ´rovni F. I pˇresto, ˇze se m˚ uˇze zd´at algoritmus ExpectMiniMax sloˇzit´ y, je opˇet snadno realizovateln´ y rekurzivn´ı procedurou. Procedura ExpectMiniMax 1. Nazvˇeme pˇredan´ y vstupn´ı uzel uzlem X. 2. Je-li uzel X listem (koneˇcn´ ym stavem hry, nebo uzlem v maxim´aln´ı hloubce) vrat’ ohodnocen´ı tohoto uzlu. Jinak pokraˇcuj. 3. Je-li na tahu hr´aˇc MAX, tak postupnˇe pro vˇsechny jeho moˇzn´e tahy (bezprostˇredn´ı n´asledn´ıky uzlu X a hr´aˇce MIN) volej proceduru ExpectMiniMax a vrat’ maxim´aln´ı hodnotu z hodnot expectMax. Je-li X koˇrenov´ ym uzlem vrat’ i tah, kter´ y vede k nejl´epe ohodnocen´emu bezprostˇredn´ımu n´asledn´ıkovi. 4. Je-li na tahu hr´aˇc MIN, tak postupnˇe pro vˇsechny jeho moˇzn´e tahy (bezprostˇredn´ı n´asledn´ıky uzlu X a hr´aˇce MAX) volej proceduru ExpectMiniMax a vrat’ minim´aln´ı hodnotu z hodnot expectMin. I na algoritmus ExpectMiniMax se d´a stejn´ ym efektem aplikovat procedura Alfa-beta proˇrez´ av´ an´ı (viz 3.5).
13
Kapitola 4
Praktick´ aˇ c´ ast Tato ˇc´ast dokumentace zaˇc´ın´a v´ ybˇerem hry pro demonstraci metod, kter´e se pouˇz´ıvaj´ı k ˇreˇsen´ı problematiky neurˇcitosti. N´asleduje anal´ yza a n´avrh ˇreˇsen´ı. Hlavn´ı kapitoly praktick´e ˇc´asti tvoˇr´ı n´avrh a zpracovn´an´ı GUI a popis implementace hern´ıho j´adra.
4.1
V´ ybˇ er hry pro demonstraci - Vrhc´ aby
Vhodn´e hry pro demonstraci metod ˇreˇs´ıc´ıch probl´em neurˇcitost´ı jsem hledal mezi hrami aleatorick´ ymi1 , kter´e jsou zaloˇzen´e na principu n´ahody nebo ˇstˇest´ı nez´avisl´em na v˚ uli jedince. Mezi aleatorick´e hry patˇr´ı hry v kostky, rulety, loterie, Vrhc´ aby, ˇclovˇeˇce nezlob se, domina, Scrablle apod. Zaujaly mˇe pˇredevˇs´ım hry ˇclovˇeˇce nezlob se a Vrhc´ aby2 (viz 4.1), v nichˇz proti sobˇe hraj´ı dva hr´aˇci a snaˇz´ı se porazit jeden druh´eho. U tˇechto her maj´ı oba hr´aˇci po celou dobu hry ˇ ımˇz u ´plnou informaci o jej´ım stavu a pˇri hˇre se pouˇz´ıv´a hrac´ı kostka, respektive kostky. C´ jsou splnˇeny podm´ınky z u ´vodu kapitoly 3.3.4 Hry s neurˇ citost´ı. Pˇri koneˇcn´em rozhodov´an´ı, kterou hru si vybrat, jsem si nakonec zvolil hru Vrhc´ aby z tˇechto d˚ uvod˚ u: • Vrhc´ aby jsem doposud neznal a pravidla mˇe velice zaujala, protoˇze se nepodobala ˇz´adn´ ym, se kter´ ymi jsem se doposud setkal • aˇc v t´eto hˇre hraje n´ahoda podstatnou roli, na rozd´ıl od ˇclovˇeˇce nezlob se v´ ysledek hry mnohem v´ıce z´avis´ı na zkuˇsenosti hr´aˇce a na pouˇzit´e strategii
1
Aleatorick´e hry - z latinsk´eho alea, coˇz v pˇrekladu znamen´ a kostka Vrhc´ aby - anglicky Backgammon - je jedna z nejstarˇs´ıch zn´ am´ ych deskov´ ych her, pˇredpokl´ ad´ a se, ˇze se hr´ ala jiˇz ve starovˇek´em Egyptˇe, Sumeru, Mezopot´ amii ˇci Persii. 2
14
Obr´azek 4.1: Hra Vrhc´aby (Backgammon)
4.2
Anal´ yza probl´ emu
Hlavn´ı probl´em projektu naimplementovat hru Vrhc´aby v jazyce C/C++ s grafick´ ym uˇzivatelsk´ ym rozhran´ım jsem si rozdˇelil na dva z´akladn´ı podprobl´emy, podle nichˇz je koncipov´ ana i tato dokumentace. A sice na implementaci GUI a hern´ıho j´adra. Stˇeˇzejn´ım u ´kolem je naprogramovat hern´ı j´adro, respektive UI poˇc´ıtaˇce, nic m´enˇe celkov´a grafick´ a podoba programu pro mˇe m´a t´eˇz velk´ y v´ yznam. Tak´e jsem se rozhodl zahrnout moˇznost pˇreloˇzit program jak na platformˇe Linux, tak i v operaˇcn´ım syst´emu Windows XP. Z´akladn´ı verze hry by mˇela umoˇzn ˇovat hru hr´aˇce proti poˇc´ıtaˇci. Celkov´ y probl´em implementace je zapotˇreb´ı d´ale rozdˇelit na d´ılˇc´ı podprobl´emy jako napˇr. uˇzivatelsk´e ovl´ad´ an´ı programu ˇci jeho interakce. Je t´eˇz potˇreba vyˇreˇsit jednotliv´e f´aze hry, jako je nalezen´ı korektn´ıch tah˚ u pro hr´aˇce na tahu, realizace tˇechto tah˚ u atd. S programov´an´ım UI poˇc´ıtaˇce, souvis´ı i v´ ybˇer nˇekter´e z metod pro ˇreˇsen´ı u ´loh s neurˇcitost´ı. Tak´e k tvorbˇe GUI je nutn´e si vybrat vhodn´ y n´astroj. S tvorbou GUI souvis´ı i probl´em stanovit jak´ ym zp˚ usobem budou reprezentov´any jednotliv´e objekty na hrac´ı ploˇse a jak bude ˇreˇsena jejich spr´ava (vykreslov´ani, pohyb objektu apod.).
4.2.1
Vlastn´ı ˇ reˇ sen´ı
Pro tvorbu programu jsem si zvolil implementaˇcn´ı prostˇred´ı Linux. V OS Windows XP jsem si nakonfiguroval prostˇred´ı MSYS s pouˇzit´ım pˇrekladaˇce MINGW, kde jsem si pˇrekl´adal zdrojov´e soubory vytvoˇren´e v Linuxu a n´aslednˇe kontroloval kompatibilitu programu s OS Windows. Pro vytvoˇren´ı GUI jsem si na z´akladˇe dˇr´ıvˇejˇs´ı zkuˇsenosti vybral toolkit WxWidgets. V rozhodov´an´ı mi pomohla i skuteˇcnost, ˇze toolkit WxWidgets je multiplatformn´ı. Vlastn´ı program tvoˇr´ı dva hlavn´ı objekty. A sice hlavn´ı okno, objekt frame, obsahuj´ıc´ı hern´ı menu, stavov´ y ˇr´adek a hrac´ı plochu. Hrac´ı plocha je zastoupena objektem scene. Hra se ovl´ad´a v´ yhradnˇe pomoc´ı myˇsi, nepoˇc´ıt´am-li kl´avesov´e zkratky pro rychlejˇs´ı pˇr´ıstup k poloˇzk´am menu. 15
4.3
Grafick´ e uˇ zivatelsk´ e rozhran´ı
Jak jsem uvedl v´ yˇse, pro implementaci GUI jsem si vybral toolkit WxWidgets, ve kter´em jsem implementoval z´akladn´ı objekt programu frame. Tento objekt po spuˇstˇen´ı aplikace vytvoˇr´ı hlavn´ı okno s hern´ım menu, stavov´ ym ˇr´adkem a vytvoˇr´ı i objekt hrac´ı plochy, kde prob´ıh´a vlastn´ı hra. Na obr´azku 4.2 je vidˇet u ´vodn´ı okno zobrazen´e po startu aplikace.
´ Obr´azek 4.2: Uvodn´ ı obrazovka zobrazen´a po spuˇstˇen´ı hry
Vykreslen´ı hrac´ı plochy prob´ıh´a ve funkci OnPaint(), kter´a je vol´ana pˇri zneplatnˇen´ı hrac´ı plochy, vˇetˇsinou nˇekter´e jej´ı ˇc´asti. Zneplatnˇen´ım se mysl´ı napˇr. pˇresun hlavn´ıho okna nebo jeho pˇrekryt´ı jin´ ym oknem a n´asledn´e zobrazen´ı. V tˇechto pˇr´ıpadech je tˇreba pˇrekreslit ta ˇc´ast okna, kter´a byla naruˇsena (zneplatnˇena). Zneplatnˇen´ı se d´a u ´ˇcelnˇe vyvolat i v samotn´em programu. Napˇr. po t´e co byl proveden tah hr´aˇce. Pˇrekreslov´an´ı okna pˇri zmˇenˇe stavu hry prob´ıh´a n´asleduj´ıc´ım zp˚ usobem: Nejprve se zavol´a funkce RedrawBuffer(), kter´a do pomocn´eho bufferu (bitmapy) nejprve zakresl´ı pr´azdnou hrac´ı plochu a pot´e vykresl´ı jednotliv´e hrac´ı kameny. Na z´avˇer vykresl´ı zbyl´e objekty sc´eny (hrac´ı kostky, s´azec´ı kostka, ˇsipka ukazuj´ıc´ı smˇer hry). N´ asledn´ ym vol´an´ım funkce Refresh(), kter´a je ˇclenskou metodou tˇr´ıdy wxWindow, z n´ıˇz je odvozen objekt scene, se zneplatn´ı obsah hrac´ı plochy. Na tuto ud´alost aplikace reaguje zavol´an´ım fce OnPaint() zmiˇ novan´e v´ yˇse. Funkce OnPaint() jiˇz pouze vykresl´ı pomocn´ y buffer do device kontextu okna.
16
Bˇehem hry program pomoc´ı zpr´av reaguje na ˇspatn´ y vstup uˇzivatele (pokus o nespr´avn´ y tah) nebo rad´ı, co m´a uˇzivatel udˇelat. Na obr´azku 4.2) je vidˇet zpr´ava v ˇcerven´em r´ameˇcku. Vzhled vˇsech objekt˚ u ve hˇre je realizov´an pomoc´ı obr´azku ve form´atu png. Vˇsechny obr´azky jsou naˇcteny po startu aplikace z adres´aˇre graphics.
4.3.1
Reprezentace hrac´ı plochy
Jedn´ım z hlavn´ıch probl´em˚ u, kter´ y jsem musel ˇreˇsit, je samotn´e uchov´an´ı stavu hry. To znamen´a jednotliv´e rozloˇzen´ı hrac´ıch kamen˚ u. P˚ uvodn´ı n´avrh objektu hrac´ı plochy spoˇc´ıval v reprezentaci jednotliv´ ych troj´ uheln´ıkov´ ych ploch (kl´ın˚ u) jako samostatn´ ych objekt˚ u. Tyto uchov´avaly poˇcet a typ hrac´ıch kamen˚ u um´ıstˇen´ ych na kl´ınu. Pozdˇeji pˇri implementaci metod manipuluj´ıc´ıch s tˇemito objekty, jako nalezen´ı moˇzn´ ych tah˚ u, realizace tahu nebo pˇri generov´an´ı prohled´avac´ıho stromu se tyto objekty uk´azaly nepˇrehledn´e. Z tohoto d˚ uvodu jsem hrac´ı plochu implementoval jako jednorozmˇern´e homogenn´ı pole, jehoˇz prvky reprezentuj´ı v´ yˇse zmiˇ novan´e kl´ıny. Tato struktura se uk´azala jednak pˇrehlednˇejˇs´ı, ’ tak i m´enˇe n´aroˇcn´a na pamˇet a v neposledn´ı ˇradˇe i rychlejˇs´ı, co se t´ yk´a pˇr´ıstupu k jednotliv´ ym kl´ın˚ um a manipulace s nimi. Pole je sloˇzeno z 28 z´akladn´ıch prvk˚ u a 6 prvk˚ u pouˇzit´ ych pˇri generov´an´ı prohled´avac´ıho stromu. Tuto z´akladn´ı strukturu je moˇzn´e vidˇet na obr´azku 4.3. Jednotliv´e prvky pole maj´ı tento v´ yznam: 0 - uchov´av´a poˇcet kamen˚ u na baru pro hr´aˇce ovl´adan´eho poˇc´ıtaˇcem 1 - 24 - uchov´av´a poˇcet kamen˚ u na oˇc´ıslovan´ ych kl´ınech ve hˇre 25 - uchov´av´a poˇcet kamen˚ u na baru pro hr´aˇce (uˇzivatelem) 26 - reprezentuje pole, kam hr´aˇc vyv´ad´ı sv´e kameny 27 - reprezentuje pole, kam poˇc´ıtaˇc vyv´ad´ı sv´e kameny 28 - pˇr´ıznak vyhozen´ı protihr´aˇcova kamene 29 - u ´daj o prvn´ı kostce pouˇzit´e pro tah 30 - 32 - u ´daj ze kter´eho kl´ınu bylo kostkou 1 - 4 t´aˇz
Obr´azek 4.3: Struktura uchov´avaj´ıc´ı aktu´aln´ı stav hry
17
Z´ akladn´ı prvky pole Na obr´azku 4.4 jsou zv´ yraznˇeny v´ yˇse zmiˇ novan´e z´akladn´ı prvky pole s indexy 0 - 27. Pˇriˇcemˇz u prvk˚ u 1 - 24 jsou zv´ yraznˇeny jen krajn´ı hodnoty. Index jednotliv´ ych kl´ın˚ u se zvyˇsuje od prvku 1 ve smˇeru hodinov´ ych ruˇciˇcek aˇz k prvku 24. Informace, kterou tyto z´akladn´ı prvky uchov´avaj´ı, je poˇcet kamen˚ u na dan´em kl´ınu. Jak je vidˇet na obr´azku na jednom kl´ınu m˚ uˇze b´ yt zobrazeno maxim´alnˇe pˇet hrac´ıch kamen˚ u, ale ve hˇre jich m˚ uˇze st´at na jednom kl´ınu vˇsech 15 najednou. Toto je pˇri vykreslov´an´ı vyˇreˇseno ˇc´ıslic´ı ud´avaj´ıc´ı skuteˇcn´ y poˇcet kamen˚ u um´ıstˇen´ ych na kl´ınu, kter´a se zobrazuje v okamˇziku, kdy poˇcet kamen˚ u pˇrekroˇc´ı 5. I pˇresto, ˇze je toto pole jednorozmˇern´e, uchov´av´a kaˇzd´ y ze z´akladn´ıch prvk˚ u dvˇe informace. Prvn´ı je samozˇrejmˇe poˇcet kamen˚ u um´ıstˇen´ ych na dan´em kl´ınu a druh´a je typ kamene, kde typ ˇr´ık´a, kter´emu hr´aˇci kameny patˇr´ı. Toto je implementov´ano rozd´ıln´ ym znam´enkem u poˇctu kamen˚ u. Poˇcet kamen˚ u hr´aˇce je uchov´av´an s kladnou hodnotou a kameny protihr´aˇce (hr´aˇce ovl´adan´eho poˇc´ıtaˇcem) se z´apornou hodnotou. Podle typu se urˇcuje i vzhled kamene.
Obr´azek 4.4: Hrac´ı plocha s vyznaˇcen´ ymi ˇc´astmi
Speci´ aln´ı prvky pole Prvn´ım ze speci´aln´ıch prvk˚ u je prvek s indexem 28 reprezentuj´ıc´ı pˇr´ıznak, kter´ y se nastav´ı v pˇr´ıpadˇe, vede-li pohyb hrac´ıho kamene hr´aˇce na pol´ıˇcko obsazen´e soupeˇrov´ ym kamenem, jin´ ymi slovy doˇslo-li k vyhozen´ı soupeˇrova kamene. Tento pˇr´ıznak se pouˇz´ıv´a pˇri ohodnocov´ an´ı termin´aln´ıho stavu v prohled´avac´ım stromu, kdy stav hry, v nˇemˇz doˇslo k vyhozen´ı soupeˇrova kamene, je hodnocen pomoc´ı jin´ ych hodnot, neˇz kdyby doˇslo k obyˇcejn´emu pˇresunu kamene. 18
Vˇsechny dalˇs´ı speci´aln´ı prvky spolu u ´zce souvis´ı. Jsou totiˇz vˇsechny pouˇzity pˇri rekonstrukci tahu poˇc´ıtaˇce, pot´e co je nalezen nejlepˇs´ı z tah˚ u. Prvn´ı s indexem 29 ˇr´ık´a, kter´ a z kostek byla pouˇzita pˇri realizaci tahu jako prvn´ı. Zbyl´e ˇctyˇri prvky obsahuj´ı index kl´ınu, ze kter´eho bylo pomoc´ı dan´e kostky taˇzeno s t´ım, ˇze prvn´ı kostku zastupuje prvek s indexem 30, druhou prvek s indexem 31 atd. Problematika hrac´ıch kostek je detailnˇe pops´ana v n´asleduj´ıc´ı podkapitole.
4.3.2
Reprezentace hrac´ıch kostek
Dalˇs´ı objekty, kter´ ymi jsou hrac´ı kostky, s´azec´ı kostka a ˇsipky urˇcuj´ıc´ı smˇer hry jsou jiˇz samostatn´e a nesou si informaci o um´ıstˇen´ı na hrac´ı ploˇse a informaci o sv´em vzhledu. Z obr´azku 4.4 je vidˇet skuteˇcn´ y poˇcet vytvoˇren´ ych objekt˚ u a jejich um´ıstˇen´ı na hrac´ı ploˇse. Jedn´a se o dvˇe pomocn´e ˇsipky oznaˇcen´e v obr´azku p´ısmeny D a E, z nichˇz maxim´alnˇe ˇ jedna m˚ uˇze b´ yt zobrazena na hrac´ı ploˇse. Cerven´ a ˇsipka (D) ukazuje smˇer hry pro hr´ aˇce uˇzivatele a je zobrazena vˇzdy po ˇcas jeho tahu. Modr´a ˇsipka pracuje obdobnˇe pro hr´ aˇce ovl´adan´eho poˇc´ıtaˇcem a m´a sp´ıˇse informativn´ı charakter pro hr´aˇce uˇzivatele, ˇze zrovna nen´ı na tahu. Dalˇs´ım objektem je s´azec´ı kostka (C), jej´ıˇz funkce bude implementov´ana aˇz pro hran´ı s´erie her, pˇri nichˇz se poˇc´ıt´a sk´ore. Tato kostka urˇcuje n´asobek z´akladn´ı hodnoty v´ yhry (viz 5) a m˚ uˇze nab´ yvat hodnot 2, 4, 8, 16, 32 a 64. Zde je tato kostka reprezentov´ana celkem tˇremi kostkami, z nichˇz pr´avˇe jedna je vˇzdy zobrazena. Jej´ı poloha je urˇcena t´ım, kter´ y z hr´aˇc˚ u si naposledy vsadil na svoji v´ yhru. Na konec jsem si nechal hrac´ı kostky pouˇz´ıvan´e bˇehem hry ze vˇsech v´ yˇse zm´ınˇen´ ych objekt˚ u nejˇcastˇeji. Ve skuteˇcnosti se pˇri hˇre pouˇz´ıvaj´ı pouze dvˇe kostky. Pro rozliˇsen´ı hr´aˇce, kter´ y je zrovna na tahu, se tyto dvˇe kostky zobrazuj´ı stˇr´ıdavˇe v lev´e (A) a prav´e ˇc´asti (B) hern´ı plochy. V lev´e pro hr´aˇce ovl´adan´eho poˇc´ıtaˇcem a v prav´e pro hr´aˇce uˇzivatele. Tyto kostky jsou na obr´azku 4.4 zobrazeny s hodnotami 2 a 3. Zbyl´e dvˇe (ˇctyˇri) kostky se zobrazuj´ı pouze v pˇr´ıpadˇe, kdy padne na obou kostk´ach stejn´a hodnota. Pˇri tomto hodu totiˇz pravidla ˇr´ıkaj´ı, ˇze hr´aˇc m´a k dispozici dalˇs´ı dva tahy stejn´e hodnoty nav´ıc. Hrac´ı kostky se objevuj´ı ve tˇrech z´akladn´ıch podob´ach (viz obr´azek 4.5). Prvn´ı vzhled, kdy kostky nemaj´ı ˇz´adnou hodnotu (A) a ˇcekaj´ı na hr´aˇce, kter´ y kliknut´ım do hrac´ı plochy realizuje jejich vrh. Po “hodu” se zobraz´ı jiˇz se svou aktu´aln´ı hodnotou (B). Posledn´ı moˇzn´ y vzhled se objev´ı na kostce po odehr´an´ı jej´ı hodnoty (C).
Obr´azek 4.5: Zobrazen´ı hrac´ıch kostek ve hˇre
19
4.4
Hern´ı j´ adro
Objekt scene se star´a o vykreslov´an´ı hrac´ı plochy a jednotliv´ ych objekt˚ u, jak popisuje pˇredchoz´ı kapitola, ale i o vlastn´ı hran´ı hry, coˇz bude pops´ano v t´eto kapitole. Pˇri hˇre se stˇr´ıd´a 6 z´akladn´ıch stav˚ u (f´az´ı) hry. Jsou to: • poˇc´ateˇcn´ı stav hry • f´aze hodu kostkou (na tahu je hr´aˇc uˇzivatel) • f´aze tahu hr´aˇce (uˇzivatele) • f´aze hodu kostkou (na tahu je poˇc´ıtaˇc) • f´aze tahu hr´aˇce (poˇc´ıtaˇce) • koneˇcn´ y stav hry (jednomu z hr´aˇc˚ u se podaˇrilo zv´ıtˇezit)
4.4.1
Poˇ c´ ateˇ cn´ı stav hry
Poˇc´ateˇcn´ı stav hry reprezentov´an fc´ı NewGameHandler() je vidˇet na obr´azku 4.2, kde aplikace ˇcek´a na kliknut´ı uˇzivatele na hrac´ı plochu. Po t´e, co se tak stane, se pomoc´ı gener´atoru pseudon´ahodn´ ych ˇc´ısel vygeneruje hodnota pro kaˇzdou z kostek. Podle toho, kter´a z hodnot je vyˇsˇs´ı, zda lev´a ˇci prav´a, se pˇrejde bud’ do f´aze hodu kostkou hr´aˇce, pro vyˇsˇs´ı pravou hodnotu, nebo do f´aze hodu kostkou poˇc´ıtaˇce v opaˇcn´em pˇr´ıpadˇe. Poˇc´ateˇcn´ı stav hry tedy pouze vygeneruje hod kostkami a urˇc´ı, kter´ y z hr´aˇc˚ u zapoˇcne hru.
4.4.2
F´ aze hodu kostkou
F´aze hodu kostkou reprezentovan´a fc´ı P1RollHandler() nebo P2RollHandler(), v pˇr´ıpadˇe, ˇze ji pˇredch´azel poˇc´ateˇcn´ı stav, pˇrej´ım´a hodnotu na kostk´ach vygenerovanou v poˇc´ateˇcn´ım stavu nebo sama vygeneruje nov´e hodnoty. Postar´a se prostˇrednictv´ım funkc´ı SetDiceValue() a GetDiceLook() o zobrazen´ı spr´avn´ ych hodnot. N´aslednˇe zavol´a funkci FindPossPlMoves() (v pˇr´ıpadˇe ˇze t´ahne hr´aˇc) nebo funkci FindPossPcMoves(), kter´a vyhled´a na z´akladˇe pravidel a aktu´aln´ım stavu hry vˇsechny pˇr´ıpustn´e tahy pro hodnotu prvn´ı hrac´ı kostky. Pot´e se zmˇen´ı stav hry na f´azi tah hr´aˇce a ˇcek´a se na hr´aˇc˚ uv vstup, v pˇr´ıpadˇe, ˇze je na tahu hr´aˇc. Nebo se po kr´atk´em intervalu samovolnˇe pˇrejde do f´aze tahu hr´aˇce poˇc´ıtaˇce, aby to stihl hr´aˇc postˇrehnout. Neexistuje-li ˇz´adn´ y korektn´ı tah pro prvn´ı hodnotu, opakuje se zm´ınˇen´ y postup pro hodnotu na druh´e kostce a v pˇr´ıpadˇe nalezen´ı alespoˇ n jednoho tahu se pˇrejde do stavu f´aze tahu pˇr´ısluˇsn´eho hr´aˇce s informac´ı, ˇze prvn´ı tah bude realizov´an pomoc´ı druh´e hodnoty. Pokud se ani pro druhou hodnotu nenajde pˇr´ıpustn´ y tah, zmˇen´ı se stav hry na f´azi hodu kostkou protihr´aˇce.
4.4.3
F´ aze tahu hr´ aˇ ce
V t´eto f´azi se obsluha pro hr´aˇce a poˇc´ıtaˇc natolik liˇs´ı, ˇze je pop´ıˇs´ı v samostatn´ ych podkapitol´ach.
20
F´ aze tahu hr´ aˇ ce uˇ zivatele Obsluhu t´eto f´aze zajiˇst’uje funkce P1MoveHandler(), kter´e se pˇred´a parametr obsahuj´ıc´ı souˇradnice bodu, do kter´eho hr´aˇc kliknul lev´ ym tlaˇc´ıtkem myˇsi. Toto je d˚ uleˇzit´e pro dalˇs´ı f´azi obsluhy. Kliknul-li hr´aˇc na jinam neˇz na kl´ın, ze kter´eho je moˇzn´e t´ahnout, je na to upozornˇen zpr´avou v horn´ı ˇc´asti okna, kter´a po dvou vteˇrin´ach zmiz´ı. Kliknul-li na kl´ın, ze kter´eho je moˇzn´ y tah, tento se provede a dojde k pˇrekreslen´ı sc´eny a vyhodnot´ı se dalˇs´ı moˇzn´ y tah pro druhou kostku. Pokud takov´ y tah neexistuje, pˇrejde se do f´aze hodu kostkou protihr´aˇce. F´ aze tahu hr´ aˇ ce poˇ c´ıtaˇ ce Obsluhu t´eto f´aze zajiˇst’uje funkce P2MoveHandler(). V t´eto f´azi je zn´ama hodnota kostky, pro kterou existuje alespoˇ n jeden pˇr´ıpustn´ y tah. A proto prvn´ı vˇec, kter´a se provede, je vygenerov´an´ı stav˚ u hry po vˇsech moˇzn´ ych taz´ıch, o co se star´a funkce CreateNodes(). Tyto stavy jsou uloˇzeny do vektoru a v vz´apˇet´ı budou tvoˇrit koˇrenov´e uzly vygenerovan´ ych prohled´avac´ıch strom˚ u, pˇri hled´an´ı nejl´epe ohodnocen´eho tahu. D´ale n´asleduje jiˇz samotn´e vol´an´ı funkce ExpectMiniMax() (viz 3.3.4) postupnˇe pro vˇsechny vygenerovan´e uzly. Funkce ExpectMiniMax() po pr˚ uchodu prohled´avac´ım stromem do definovan´e hloubky vrac´ı ohodnocen´ı pˇredan´eho uzlu, z nˇehoˇz vybere maximum. V poli, ve kter´em je uloˇzen stav hry po nejl´epe ohodnocen´em tahu je uloˇzena i informace nutn´ a pro rekonstrukci tahu (viz 4.3). N´asleduj´ıc´ım krokem, jak jsem jiˇz pˇredeslal, je rekonstrukce nejl´epe hodnocen´eho tahu. Realizuj´ı se tahy pro jednotliv´e hodnoty na hrac´ıch kostk´ach a to s nutnou prodlevou, aby bylo hr´aˇci uˇzivateli zˇrejm´e, jak poˇc´ıtaˇc t´ahnul. Realizace algoritmu ExpectMiniMax() Algoritmus ExpectMiniMax je realizov´an podle pokyn˚ u uveden´ ych v teoretick´e ˇc´asti t´eto dokumentace (viz 3.3.4). Funkce zisku zastoupen´a ve zdrojov´em k´odu funkc´ı Eval() je implementov´ana dle vzoru uveden´eho na webov´ ych str´ank´ach (viz [5]). Je zaloˇzena na ohodnocen´ı stavu hry po ukonˇcen´ı tahu, s t´ım, ˇze ohodnocen´ı jednoho uzlu (stavu hry) spoˇc´ıv´a v souˇctu vˇsech ohodnocen´ı jednotliv´ ych kl´ın˚ u, na kter´ ych se nach´az´ı nˇejak´ y k´amen. Ohodnocen´ı je z´avisl´e na poˇctu kamen˚ u se na dan´em kl´ınu a tak´e na tom zda pˇri tahu doˇslo k “vyhozen´ı” protihr´aˇcova kamene. K ohodnocen´ı d´ılˇc´ıch kl´ınu jsou pouˇzity konstanty uveden´e v souboru weight.h.
21
Kapitola 5
Z´ avˇ er Po nastudov´an´ı a pˇredevˇs´ım pochopen´ı teorie ˇreˇsen´ı u ´loh s neurˇcitost´ı pomoc´ı algoritmu ExpectMiniMax jsem si jako demonstraˇcn´ı ˇreˇsen´ı vybral implementaci hry Vrhc´aby. Hru se mi podaˇrilo naimplementovat do stavu, ve kter´em je plnˇe hrateln´a. Bohuˇzel z nedostatku ˇcasu, kter´ y jsem musel rozdˇelit mezi v´ıce projekt˚ u ˇreˇsen´ ych prakticky paralelnˇe, jsem nestihl naprogramovat nˇekter´a rozˇs´ıˇren´ı, ˇci vylepˇsen´ı, kter´a mˇe napadala bˇehem ˇcasu, kter´ y jsem tvorbou t´eto pr´ace str´avil. Rozˇs´ıˇren´ı se t´ ykaj´ı prakticky vˇsech z´akladn´ıch ˇc´ast´ı aplikace. Napˇr. v ˇc´asti GUI by moˇzn´ ym rozˇs´ıˇren´ım mohla b´ yt volba vzhledu hrac´ı desky, ˇci hrac´ıch kamen˚ u. Nebo zv´ yraznˇen´ı kamene, kter´ ym se pr´avˇe t´ahne. V ˇc´asti hern´ıho j´adra by to mohlo b´ yt rozˇs´ıˇren´ı t´ ykaj´ıc´ı se hodnot´ıc´ı funkce, ˇci moˇznost zvyˇsov´an´ı hodnoty hry pomoc´ı s´azec´ı kostky, s ˇc´ımˇz je spojena moˇznost hr´at s´erii her a uchov´avat v´ ysledky pro r˚ uzn´e hr´aˇce. Zaj´ımav´ ym vylepˇsen´ım by mohla b´ yt i implementace moˇznosti kroku zpˇet ˇci ukl´ad´an´ı rozehran´e partie. I pˇresto, ˇze spousta moˇznost´ı jak rozˇs´ıˇrit hru z˚ ustala jen na pap´ıˇre, mi tento projekt mnoh´e dal. Pro vytvoˇreni vzhledu jednotliv´ ych objekt˚ u jsem se napˇr. nauˇcil z´aklady Photoshopu. Z´ıskal jsem nov´e zkuˇsenosti s pouˇzit´ım typografick´eho n´astroje LATEX, ve kter´em je vys´azena tato dokumentace. Samotn´e ˇreˇsen´ı probl´emu implementovat hru s umˇelou inteligenc´ı, nav´ıc s prvkem n´ahody, mˇe v mnoh´em obohatilo. Nemal´ y v´ yznam tak´e d´av´ am z´ıskan´ı nov´ ych zkuˇsenost´ı pˇri pl´anov´an´ı ˇcasu pro soubˇeˇzn´e ˇreˇsen´ı v´ıce projekt˚ u. Hra Vrhc´aby je po hˇre Piˇskvorky, kterou jsem implementoval jeˇstˇe jako student stˇredn´ı ˇskoly, teprve druhou hrou, kterou se mi podaˇrilo naprogramovat. Proto bych r´ad v budoucnu nav´azal na z´ıskan´e zkuˇsenosti v oblasti umˇel´e inteligence a pokusil se naimplementovat nˇejakou z dalˇs´ıch zaj´ımav´ ych her.
22
Literatura [1] F. V. Zboˇril a F. Zboˇril. Z´aklady umˇel´e inteligence [studijn´ı opora], v.3 2006 [citov´ano 2007]. Publikace pˇr´ıstupn´a pouze osob´am pˇrihl´aˇsen´ ym do predmˇetu IZU, pˇr´ıstupn´e z https://www.fit.vutbr.cz/study/courses/IZU/. [2] V. Maˇr´ık a kol. Umˇel´ a inteligence 1. Academia, Praha, 1993. ISBN:80-200-0496-3. ˇ ˇ [3] Z. Kotek a kol. Metody rozpozn´ av´ an´ı a umˇel´ a inteligence. CSVTS FE VSSE, Plzeˇ n, 1983. Citov´ano dle [2]. [4] M. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967. Citov´ano dle [2]. [5] WWW str´anky. Benchmark player ’pubeval.c’. http://www.bkgm.com/archive.html. kategorie ’Source Code’. [6] WWW str´ anky. Vrhc´ aby. http://cs.wikipedia.org/wiki/Vrhc%C3%A1by.
23
Pˇ r´ıloha A Pravidla hry Vrhc´ aby [6] Tahy Na zaˇc´atku hry hod´ı kaˇzd´ y hr´aˇc jednou kostkou a ten hr´aˇc, kter´ y hodil vˇetˇs´ı ˇc´ıslo (pˇri stejn´ ych hodnot´ach se h´az´ı znovu), zaˇc´ın´a hru t´ım, ˇze odehraje obˇe hozen´a ˇc´ısla. V dalˇs´ıch kolech jiˇz h´az´ı kaˇzd´ y hr´aˇc obˇema kostkami s´am. Hod se bere jako dvˇe oddˇelen´a ˇc´ısla, urˇcuj´ıc´ı poˇcet pol´ı, o kter´e sm´ı hr´aˇc postoupit zvolen´ ymi kameny. Hr´aˇc m˚ uˇze postoupit jedn´ım kamenem o souˇcet obou ˇc´ısel, ale pouze tak, ˇze nejprve posune k´amen o hodnotu jedn´e kostky (coˇz mus´ı b´ yt s´am o sobˇe platn´ y tah, tzn. k´amen nesm´ı skonˇcit na poli obsazen´em v´ıce neˇz jedn´ım soupeˇrov´ ym kamenem), teprve pot´e o hodnotu druh´e kostky. Pokud na obou kostk´ach padne stejn´e ˇc´ıslo, bere se dvojn´asobnˇe, tzn. jako by padlo na ˇctyˇrech kostk´ach. Tyto ˇctyˇri hodnoty hr´aˇc m˚ uˇze rozdˇelit na posun ˇctyˇr r˚ uzn´ ych kamen˚ u, na posun jednoho kamene o ˇctyˇrn´asobek hozen´e hodnoty (ovˇsem opˇet ve ˇctyˇrech nez´avisl´ ych kroc´ıch!), nebo libovolnou kombinaci tˇechto moˇznost´ı. Hr´aˇc se nesm´ı vzd´at sv´eho tahu, tˇrebaˇze je pro nˇej nev´ yhodn´ y. Pokud existuje nˇejak´ y tah splˇ nuj´ıc´ı pravidla, mus´ı hr´aˇc t´ahnout. Pokud hr´aˇc m˚ uˇze leg´alnˇe hr´at pouze ˇc´ast tahu (napˇr. pouze hodnotu jedn´e kostky), mus´ı odehr´at co nejvˇetˇs´ı ˇc´ast tahu splˇ nuj´ıc´ı pravidla. Pokud hr´aˇc m˚ uˇze odehr´at libovolnou hodnotu z obou kostek, ale nem˚ uˇze hr´at obˇe, mus´ı hr´at tu vyˇsˇs´ı. Vyhazov´ an´ı a vracen´ı do hry Jak uˇz bylo zm´ınˇeno, pokud k´amen skonˇc´ı tah (nebo jeho ˇc´ast danou posunem o hodnotu na jedn´e kostce) na poli, obsazen´em jedn´ım soupeˇrov´ ym kamenem, tento k´amen vyhod´ı, tzn. pˇrem´ıst´ı na bar (tak´e zvan´ y pˇrep´aˇzka ˇci z´avora), coˇz je vyv´ yˇsen´e m´ısto uprostˇred desky. Bar se ch´ape jako pole um´ıstˇen´e pˇred zaˇc´atkem desky, nejvzd´alenˇejˇs´ı od c´ıle. Kdyˇz m´ a hr´aˇc nˇejak´ y k´amen (nebo kameny, poˇcet kamen˚ u na baru nen´ı omezen) na baru a chce je dostat zpˇet do hry, provede to pˇresnˇe tak, jako by dan´ y k´amen opravdu st´al jedno pole pˇred deskou, tzn. napˇr. hodem 1 pˇresune k´amen na prvn´ı pole desky (pochopitelnˇe pokud nen´ı obsazeno soupeˇrem). Dokud m´a hr´aˇc alespoˇ n jeden k´amen na baru, mus´ı tyto kameny dostat do hry pˇred t´ım, neˇz hraje jin´ ym kamenem. Pokud mu hod kostky toto neumoˇzn ˇuje, hod mu propad´a a hr´aˇc nehraje (popˇr. hraje pouze hodnotu na druh´e kostce). Pokud je na nˇekter´em poli dva nebo v´ıce kamen˚ u, je pole obsazeno a soupeˇr na tomto poli nesm´ı ukonˇcit tah ani jeho ˇc´ast. Z tohoto d˚ uvodu je zˇrejm´e, ˇze ˇsest obsazen´ ych pol´ı v ˇradˇe je pro soupeˇre nepˇrekroˇcitelnou pˇrek´aˇzkou (t´eto formaci se ˇr´ık´a prima). Pokud se nav´ıc podaˇr´ı hr´aˇci obsadit vˇsech ˇsest pol´ı ve sv´e dom´ac´ı ohradˇe (tzn. v tom kvadrantu desky, ze kter´eho vyv´ad´ı kameny, coˇz je souˇcasnˇe kvadrant, do kter´eho soupeˇr nasazuje kameny vracej´ıc´ı se z baru) v dobˇe, kdy m´a soupeˇr nˇejak´ y k´amen na baru, soupeˇrovi se nem˚ uˇze 24
podaˇrit vr´atit tento k´amen do hry, takˇze nem˚ uˇze hr´at a dokud tato situace trv´a (dokud nen´ı prima rozpuˇstˇena), ani neh´az´ı kostkami. Vyv´ adˇ en´ı kamen˚ u Ve chv´ıli, kdy jsou vˇsechny kameny hr´aˇce um´ıstˇeny v jeho dom´ac´ı ohradˇe (na posledn´ıch ˇsesti pol´ıch desky), m˚ uˇze hr´aˇc vyv´adˇet kameny mimo desku. To prov´ad´ı tak, ˇze kameny jakoby t´ahne na fiktivn´ı pole tˇesnˇe za deskou, tzn. pokud na kostce padlo napˇr. ˇc´ıslo ˇctyˇri, odstran´ı hr´aˇc jeden k´amen ze ˇctvrt´eho pole. Pokud hr´aˇci padne ˇc´ıslo vyˇsˇs´ı, neˇz je jeho nejvzd´alenˇejˇs´ı k´amen, odstran´ı jeden z kamen˚ u na nejvzd´alenˇejˇs´ım poli. (Tato pouˇcka se net´ yk´a situace, kdy na dan´em poli sice neleˇz´ı ˇz´adn´ y k´amen, ale nˇejak´ y k´amen je jeˇstˇe za dan´ ym polem. Tehdy mus´ı hr´aˇc prov´est bˇeˇzn´ y tah kamenem po desce.) Pokud se v pr˚ ubˇehu t´eto koncovky stane, ˇze se nˇekter´ y z kamen˚ u dostane mimo dom´ac´ı ohradu (soupeˇr ho vyhozen´ım poˇsle na bar), hr´aˇc nem˚ uˇze pokraˇcovat ve vyv´adˇen´ı kamen˚ u do t´e doby, neˇz jsou opˇet vˇsechny jeho zbyl´e kameny v dom´ac´ı ohradˇe. Hra konˇc´ı ve chv´ıli, kdy jeden z hr´aˇc˚ u vyvede z desky posledn´ı k´amen, ˇc´ımˇz se st´ av´ a v´ıtˇezem. Hru je samozˇrejmˇe tak´e moˇzn´e ukonˇcit v jej´ım pr˚ ubˇehu (pˇred hodem hr´aˇce) t´ım, ˇze hr´aˇc nab´ıdne soupeˇri svou rezignaci, kterou soupeˇr m˚ uˇze a nemus´ı pˇrijmout.
25
Pˇ r´ıloha B Adres´ aˇ rov´ a struktura na pˇ riloˇ zen´ em CD - bakalarskaPrace - doc - dokumentace bakal´aˇrsk´e pr´ace - cls - sablona fitthesis.cls a obr´azky v n´ı pouˇzit´e - fig - obr´azky pro dokumentaci - graphics - obr´azkeky vˇsech objektu na hrac´ı ploˇse - include - hlaviˇckov´e soubory - src - zdrojov´e soubory
Postup pˇ ri pˇ rekldau programu Program je pˇreloˇziteln´ y jak v OS Linux, tak v OS Windows XP, napˇr. za pouˇzit´ı syst´emu MSYS v kombinaci s pˇrekladaˇcem MinGW. Jedin´ y poˇzadavek na syst´em je nainstalovan´ y GUI toolkit WxWidgets GTK verze 2.8.0 nebo v´ yˇsˇs´ı. Pˇreklad se spust´ı z pˇr´ıkazov´e ˇr´adky pˇr´ıkazem make. Vznikne spustiteln´ y soubor backgammon (Linux) nebo backgammon.exe (Windows XP).
Struˇ cn´ y n´ avod k pouˇ zit´ı Pˇred spuˇstˇen´ım hry, doporuˇcuji prostudovat pravidla hry Vrhc´aby, kter´a jsou obsahem pˇr´ılohy A. Po spuˇstˇen´ı aplikace zaˇcnˇete hru kliknut´ım lev´ ym tlaˇc´ıtkem myˇsi do hrac´ı plochy. Pˇri hˇre jsou uˇzivateli vypisov´any z´akladn´ı zprv´ay, kter´e mu rad´ı co v dan´e situaci dˇelat. Hru je moˇzn´e myˇs´ı, ovl´ad´an´ı je zcela intuitivn´ı. Pro hod kostkou kliknˇete na kostky, poku jste na tahu objev´ı se na nich hodnota se kterou m˚ uˇzete t´ahnout. Pro pˇresun kamene kliknˇete na k´amen, kter´ ym chcete t´ahnout. Korektnost tahu je automaticky kontrolov´ana. Pro pˇresun se pouˇzije vˇzdy prvn´ı kostka s hodnotou, pro kterou existuje korektn´ı tah.
26
