´ UNIVERZITA PALACKEHO V OLOMOUCI KATEDRA INFORMATIKY
Tom´aˇs K¨uhr
ˇ ´ITACOV ˇ EHO ´ ´ CE ˇ ALGORITMY REALIZUJ´IC´I POC HRA v jednoduch´ych deskov´ych hr´ach
ˇ ıjen 2011 R´
Abstrakt N´ asleduj´ıc´ı text obsahuje detailn´ı popis algoritmu Minimax, kter´ y se pouˇz´ıv´a pˇri realizaci rozhodov´ an´ı poˇc´ıtaˇcov´eho hr´aˇce v jednoduch´ ych deskov´ ych hr´ach, a jeho vylepˇsen´ı – Alfa-Beta oˇrez´ av´ an´ı, kter´e znaˇcnˇe sniˇzuje ˇcasovou n´aroˇcnost Minimaxu. Pro oba algoritmy zde uv´ad´ıme jejich podrobnˇe okomentovan´ y pseudok´od a nˇekolik konkr´etn´ıch pˇr´ıklad˚ u v´ ypoˇctu nejlepˇs´ıho tahu. U ˇcten´ aˇr˚ u se pˇredpokl´adaj´ı pouze z´akladn´ı znalosti procedur´aln´ıho paradigma programov´an´ı (vˇetven´ı, cykly, funkce), kter´e jsou nutn´e pro porozumˇen´ı nˇekter´ ym ˇc´astem tohoto textu.
Text vznikl na Katedˇre informatiky Pˇr´ırodovˇedeck´e fakulty Univerzity Palack´eho v Olomouci pˇredevˇs´ım pro potˇreby student˚ u pˇredmˇet˚ u Projektov´ y semin´aˇr 1 a 2. Autor m˚ uˇze b´ yt kontaktov´an elektronickou poˇstou na adrese
. Pokud zjist´ıte jak´ekoli pˇreklepy, chyby ˇci jin´e nedostatky, dejte mi pros´ım vˇedˇet. Toto d´ılo podl´eh´a licenci Creative Commons Attribution – NonCommercial – ShareAlike 3.0 Czech Republic. Pro zobrazen´ı kopie t´eto licence, navˇstivte “http://creativecommons.org/licenses/by-nc-sa/3.0/cz/”. c Tom´aˇs K¨ Copyright � uhr, 2011
Obsah 1. Pr˚ ubˇ eh hry a jeho 1.1. Z´akladn´ı pojmy ˇ a d´ama . . 1.2. Cesk´ 1.3. Hern´ı strom . .
zobrazen´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Algoritmus Minimax 2.1. Princip algoritmu . . . . 2.2. Implementace algoritmu 2.3. Ohodnocovac´ı funkce . . 2.4. Gener´ator tah˚ u . . . . .
1 1 1 2
. . . .
5 5 5 10 13
3. Alfa-beta oˇ rez´ av´ an´ı 3.1. Princip algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Implementace algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15 15 16
Literatura
21
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
i
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
ii
Seznam obr´ azk˚ u 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.
ˇ a d´ama. . . . . . . . . . . . . . . . . . . . . Z´akladn´ı postaven´ı kamen˚ u ve hˇre Cesk´ Pˇr´ıklad pozice s b´ıl´ ym hr´aˇcem na tahu, ˇsipky naznaˇcuj´ı moˇzn´e tahy. . . . . . . . . Uk´azka jednoho z moˇzn´ ych skok˚ u b´ıl´e d´amy. . . . . . . . . . . . . . . . . . . . . . . Hern´ı strom. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pozice odpov´ıdaj´ıc´ı uzl˚ um hern´ıho stromu na obr´azku 4. . . . . . . . . . . . . . . . ˇ a d´ama, ˇcern´ Pozice z hry Cesk´ y na tahu. . . . . . . . . . . . . . . . . . . . . . . . . Hern´ı strom odpov´ıdaj´ıc´ı pozici z obr´azku 6. . . . . . . . . . . . . . . . . . . . . . . Hern´ı strom ilustruj´ıc´ı v´ ypoˇcty zjednoduˇsen´eho Minimaxu. . . . . . . . . . . . . . Hern´ı strom ilustruj´ıc´ı v´ ypoˇcty komplexn´ıho Minimaxu. . . . . . . . . . . . . . . . ˇ a d´ama, na tahu je ˇcern´ Pozice ze hry Cesk´ y hr´aˇc . . . . . . . . . . . . . . . . . . . Hern´ı strom ilustruj´ıc´ı v´ ypoˇcet Minimaxu pro pozici z obr´azku 10. . . . . . . . . . Statick´e “tabulky” pro ohodnocov´an´ı um´ıstˇen´ı b´ıl´eho pˇeˇsce (vlevo nahoˇre), ˇcern´eho pˇeˇsce (vpravo nahoˇre) b´ıl´e d´amy (vlevo dole) a ˇcern´e d´amy (vpravo dole). . . . . . Ilustrace pˇridˇelov´an´ı bonus˚ u za um´ıstˇen´ı v bl´ızkosti jin´ ych figur. . . . . . . . . . . Hern´ı pozice pro ilustraci v´ ypoˇctu ohodnocen´ı. . . . . . . . . . . . . . . . . . . . . Ilustrace beta-ˇrezu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pˇr´ıklad alfa-oˇrez´an´ı. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Poˇc´ateˇcn´ı pozice k pˇr´ıkladu 3.2., na tahu je b´ıl´ y hr´aˇc. . . . . . . . . . . . . . . . . Hern´ı strom z pˇr´ıkladu 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
2 3 3 4 4 6 6 7 9 10 10 11 12 12 15 16 19 20
iv
1
1.
Pr˚ ubˇ eh hry a jeho zobrazen´ı
V t´eto kapitole se bl´ıˇze sezn´am´ıme se z´akladn´ımi pojmy, kter´e souvis´ı s problematikou deskov´ ych her a pouˇz´ıvaj´ı se pˇri popisu algoritm˚ u pro v´ ypoˇcet nejlepˇs´ıho tahu poˇc´ıtaˇcov´eho hr´aˇce. Uk´ aˇzeme si tak´e zp˚ usob, jak´ ym lze snadno zobrazit a popsat “vˇsechny” moˇzn´e hern´ı situace. Toto zobrazen´ı pr˚ ubˇehu hry n´am pak pom˚ uˇze ilustrovat v´ ybˇer nejlepˇs´ıho tahu prob´ıran´ ymi algoritmy. ˇ a d´ama, kter´a bude v r´amci V t´eto u ´vodn´ı kapitole je pro u ´plnost uveden i souhrn pravidel hry Cesk´ tohoto textu pouˇzita pro ilustrace pr˚ ubˇeh˚ u v´ ypoˇct˚ u popisovan´ ych algoritm˚ u.
1.1.
Z´ akladn´ı pojmy
Abychom mohli algoritmy uveden´e v n´asleduj´ıc´ıch kapitol´ach popsat struˇcnˇe a pˇritom zcela jednoznaˇcnˇe, ujasn´ıme si zde nejprve nˇekolik pojm˚ u, kter´e budeme pozdˇeji pˇri popisov´an´ı hern´ıch situac´ı a jednotliv´ ych krok˚ u algoritm˚ u pouˇz´ıvat. Zde je nutn´e tak´e podotknout, ˇze algoritmy popisovan´e v tomto textu jsou pouˇziteln´e pouze pro hry 2 hr´aˇc˚ u, kteˇr´ı spolu soupeˇr´ı (v´ yhra prvn´ıho hr´ aˇce znamen´a automaticky prohru hr´aˇce druh´eho a naopak). Algoritmy d´ale vyˇzaduj´ı, aby se oba hr´ aˇci pˇri sv´ ych taz´ıch pravidelnˇe stˇr´ıdali. Tahem bude v n´asleduj´ıc´ım textu vˇzdy myˇsleno pˇrem´ıstˇen´ı figury patˇr´ıc´ı hr´aˇci, kter´ y je aktu´ alnˇe na tahu. Toto pˇrem´ıstˇen´ı mus´ı samozˇrejmˇe odpov´ıdat pravidl˚ um dan´e hry. Pokud to pravidla dan´e hry vyˇzaduj´ı m˚ uˇze b´ yt bˇehem tahu jednoho hr´aˇce manipulov´ano i s kameny hr´aˇce druh´eho (napˇr. odstranˇen´ı pˇreskoˇcen´ ych soupeˇrov´ ych kamen˚ u z desky). Tato “definice” tahu nen´ı bohuˇzel jedin´a, se kterou se ˇcten´aˇri mohou v literatuˇre popisuj´ıc´ı tuto problematiku setkat. V nˇekter´ ych publikac´ıch se n´ami “definovan´ y” tah oznaˇcuje pojmem p˚ ultah, tahem se pak rozum´ı dvojice p˚ ultah˚ u. Pojmem pozice budeme d´ale rozumˇet stav hry v dan´em okamˇziku. Pozice je tedy jednoznaˇcnˇe urˇcena rozm´ıstˇen´ım figur na hrac´ı desce a urˇcen´ım hr´aˇce, kter´ y je pr´avˇe na tahu. Poˇ c´ ateˇ cn´ı pozic´ı rozum´ıme pozici pˇred proveden´ım prvn´ıho tahu. Pojmy vyhr´ avaj´ıc´ı pozice, prohr´ avaj´ıc´ı pozice a rem´ızov´ a pozice se pak pouˇz´ıvaj´ı k oznaˇcen´ı pozic na konci hry, obecnˇe o nich tak´e hovoˇr´ıme jako o koncov´ ych pozic´ıch. U vyhr´avaj´ıc´ı a prohr´avaj´ıc´ı pozice je pochopitelnˇe nutn´e uv´est, kter´ y hr´aˇc vyhr´al ˇci prohr´al (napˇr. “vyhr´avaj´ıc´ı pozice z pohledu b´ıl´eho hr´aˇce”).
1.2.
ˇ Cesk´ a d´ ama
ˇ a d´ama je jednou z mnoha variant svˇetozn´am´e hry D´ama. Jak jiˇz bylo v u Cesk´ ´vodu kapitoly zm´ınˇeno, budeme tuto hru v n´asleduj´ıc´ım textu pouˇz´ıvat pro ilustrace hern´ıch situac´ı a pr˚ ubˇehu v´ ypoˇctu popisovan´ ych algoritm˚ u. K tomuto u ´ˇcelu byla ˇcesk´a d´ama zvolena pˇredevˇs´ım pro sv´a jednoduch´a pravidla, svou rozˇs´ıˇrenost a podobnost s vˇetˇsinou deskov´ ych, jejichˇz implementace b´ yv´ a n´ apln´ı projektov´ ych semin´aˇr˚ u. N´ıˇze uveden´a pravidla hry jsou pˇrevzata z webov´ ych str´anek ˇ e federace d´amy [1], kde je tak´e moˇzn´e snadno dohledat kompletn´ı verzi pravidel hry Cesk´ ˇ a Cesk´ d´ ama. Struˇ cn´ a pravidla ˇ cesk´ e d´ amy • Hraje se na desce s rozmˇerem 8×8 pol´ı, kaˇzd´ y hr´aˇc m´a na zaˇc´atku hry 12 kamen˚ u. • Rozestaven´ı kamen˚ u na zaˇc´atku hry ukazuje obr´azek 1. • Kameny se t´ahne po diagon´al´ach, vˇzdy o jedno pole vpˇred. • Dokonˇc´ı-li k´amen tah na posledn´ı ˇradˇe, mˇen´ı se v d´amu. D´ama se pohybuje po diagon´al´ach dopˇredu i dozadu. • Kameny se sk´aˇce jen dopˇredu, d´ama m˚ uˇze sk´akat pˇres libovoln´ y k´amen na diagon´ale dopˇredu i dozadu a dokonˇcit skok na kter´emkoli poli za pˇreskoˇcen´ ym kamenem.
2
Pr˚ ubˇeh hry a jeho zobrazen´ı
• Sk´ ak´an´ı je povinn´e a figura po dokonˇcen´ı tahu nesm´ı m´ıt dalˇs´ı moˇznost skoku. Je-li v´ıce moˇznost´ı sk´ak´an´ı, m˚ uˇze si hr´aˇc vybrat bez ohledu na mnoˇzstv´ı pˇreskoˇcen´ ych kamen˚ u soupeˇre. • D´ ama m´a pˇri sk´ak´an´ı vˇzdy pˇrednost pˇred kamenem. • Partii vyhr´av´a hr´aˇc, jehoˇz soupeˇr nem˚ uˇze prov´est tah podle pravidel (nem´a jiˇz ˇz´adn´e figury nebo jsou jeho figury zablokov´any). • Partie skonˇc´ı nerozhodnˇe po dohodˇe hr´aˇc˚ u nebo kdyˇz se ve hˇre vyskytne 3-kr´at stejn´a pozice. 8 7 6 5 4 3 2 1 a
b
c
d
e
f
g
h
ˇ a d´ama. Obr´azek 1. Z´akladn´ı postaven´ı kamen˚ u ve hˇre Cesk´
Z´ apis tah˚ u Pˇri popisov´an´ı pr˚ ubˇehu hry naraz´ıme na probl´em, jak jednoznaˇcnˇe a dostateˇcnˇe struˇcnˇe popsat prov´ adˇen´e tahy. U her prob´ıhaj´ıc´ıch na ˇctvercov´e nebo obd´eln´ıkov´e desce se nejˇcastˇeji vyuˇz´ıv´a poˇc´ ateˇcn´ıch p´ısmen anglick´e abecedy k jednoznaˇcn´emu oznaˇcen´ı sloupc˚ u a ˇc´ısel k jednoznaˇcn´e identifikaci ˇr´adku. Dvojice p´ısmene a ˇc´ısla pak jednoznaˇcnˇe urˇcuje pole na hrac´ı desce. Posloupnost “identifik´ ator˚ u” pol´ı pak opˇet jednoznaˇcnˇe pop´ıˇse cel´ y proveden´ y tah. ˇ´ıklad 1.1. V pozici na obr´azku 2. je b´ıl´ � Pr y k´amen um´ıstˇen na poli c1, ˇcern´e kameny na pol´ıch c5 a f2, ˇcern´a d´ama je pak na poli e5. B´ıl´ y hr´aˇc z t´eto pozice m˚ uˇze prov´est tah c1-b2 nebo c1-d2. ˇ´ıklad 1.2. Hern´ı pozice zaznamenan´a na obr´azku 3. se od t´e z obr´azku 2. liˇs´ı pouze � Pr um´ıstˇen´ım b´ıl´e d´amy na pole a3; na tahu zde je opˇet b´ıl´ y hr´aˇc. B´ıl´a d´ama zde dle pravidel mus´ı prov´est nˇekter´ y z moˇzn´ ych skok˚ u a3-e7, a3-f8, a3-d6-f4, a3-d6-h2 nebo a3-d6-g3-e1. Posledn´ı zm´ınˇen´ y skok je na obr´azku naznaˇcen ˇcerven´ ymi ˇsipkami.
1.3.
Hern´ı strom
V t´eto ˇc´asti si uk´aˇzeme zobrazen´ı “vˇsech” moˇznost´ı, kter´ ymi se m˚ uˇze z dan´e pozice hra ub´ırat, pomoc´ı tzv. hern´ıho stromu. Slovo “vˇsech” je zde z´amˇernˇe uvedeno v uvozovk´ach, protoˇze nen´ı v moˇznostech ˇclovˇeka ani poˇc´ıtaˇce zobrazit, proj´ıt nebo vz´ıt do u ´vahy vˇsechny moˇzn´e pozice, kter´e se mohou vyskytnout v bˇeˇzn´ ych deskov´ ych hr´ach, v rozumn´em ˇcase. Hern´ı stromy budeme v tomto textu pouˇz´ıvat pro ilustraci pr˚ ubˇeh˚ u v´ ypoˇct˚ u prob´ıran´ ych algoritm˚ u.
1.3.
3
Hern´ı strom
8 7 6 5 4 3 2 1 a
b
c
d
e
f
g
h
Obr´azek 2. Pˇr´ıklad pozice s b´ıl´ ym hr´aˇcem na tahu, ˇsipky naznaˇcuj´ı moˇzn´e tahy. 8 7 6 5 4 3 2 1 a
b
c
d
e
f
g
h
Obr´azek 3. Uk´azka jednoho z moˇzn´ ych skok˚ u b´ıl´e d´amy. Konstrukce hern´ıho stromu je relativnˇe jednoduch´a. Koˇrenem stromu je vˇzdy uzel odpov´ıdaj´ıc´ı aktu´ aln´ı pozici. Pokud z t´eto pozice existuje nˇejak´ y tah (v r´amci pravidel dan´e hry), pˇrid´ame do stromu uzel odpov´ıdaj´ıc´ı pozici vznikl´e z aktu´aln´ı pozice proveden´ım tohoto tahu. Tyto dva uzly pak spoj´ıme orientovanou hranou, pˇriˇcemˇz b´ yv´a zvykem tuto hranu popsat tahem, kter´ y z pozice odpov´ıdaj´ıc´ı poˇc´ateˇcn´ımu uzlu vede k pozici odpov´ıdaj´ıc´ı koncov´emu uzlu t´eto hrany. Takto m˚ uˇzeme do stromu pˇridat uzly odpov´ıdaj´ıc´ı vˇsem tah˚ um z aktu´aln´ı pozice a pot´e rekurzivnˇe zkoumat tak´e tahy z pozic odpov´ıdaj´ıc´ıch novˇe pˇridan´ ym uzl˚ um. Z popisu konstrukce hern´ıho stromu je zˇrejm´e, ˇze poˇcet uzl˚ u stromu (a tedy i poˇcet pozic, kter´e mohou ve hˇre nastat) roste exponenci´alnˇe s jeho v´ yˇskou (ta odpov´ıd´a poˇctu tah˚ u, tedy d´elce hry). Vzhledem k tomu, ˇze partii bˇeˇzn´e deskov´e hry obvykle tvoˇr´ı des´ıtky aˇz stovky tah˚ u a ˇze z kaˇzd´e pozice m˚ uˇze existovat i vˇetˇs´ı mnoˇzstv´ı tah˚ u, je zobrazen´ı ˇci prozkoum´an´ı cel´eho hern´ıho stromu prakticky nemoˇzn´e. ˇ a d´ama. Pozice odˇ´ıklad 1.3. Na obr´azku 4. je zobrazena ˇc´ast hern´ıho stromu hry Cesk´ � Pr pov´ıdaj´ıc´ı uzl˚ um pak tvoˇr´ı obr´azek 5.
4
Pr˚ ubˇeh hry a jeho zobrazen´ı
P0 d2-c3
d2-e3
P1
P2
c5-b4
c5-d4
P3
c5-d4
P4
c3-a5
c5-b4
P5
P6
c3-e5
P7
P8 Obr´azek 4. Hern´ı strom.
P0
P1
8
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1 b
c
d
e
f
g
1 a
h
P4
8
b
c
d
e
f
g
h
P5
8 7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1 b
c
d
e
f
g
P7
8
b
c
d
e
f
g
h
P8
8 7
7
6
6
6
5
5
5
4
4
4
3
3
3
2
2
2
1
1 b
c
d
e
f
g
h
c
d
e
f
g
h
a
b
c
d
e
f
g
h
a
b
c
d
e
f
g
h
8
7
a
b
1 a
h
a
8
7
a
P6
8
7
a
P3
P2
8
7
1 a
b
c
d
e
f
g
h
Obr´azek 5. Pozice odpov´ıdaj´ıc´ı uzl˚ um hern´ıho stromu na obr´azku 4.
5
2.
Algoritmus Minimax
V t´eto kapitole bude pops´an z´akladn´ı algoritmus Minimax, kter´ y je v mnoha modifikac´ıch vyuˇz´ıv´ an pˇri hled´an´ı nejlepˇs´ıch tah˚ u poˇc´ıtaˇcov´ ych hr´aˇc˚ u v nejr˚ uznˇejˇs´ıch deskov´ ych hr´ach. Tento algoritmus je dobˇre pops´an jak tiˇstˇenou literaturou (napˇr´ıklad [2]), tak internetov´ ymi zdroji [3, 4].
2.1.
Princip algoritmu
Minimax je jednoduch´ y, ale velmi mocn´ y algoritmus, kter´ y prozkoum´av´a ˇc´ast hern´ıho stromu odpov´ıdaj´ıc´ıho aktu´aln´ı pozici a nalezne “nejlepˇs´ı” moˇzn´ y tah pro hr´aˇce, kter´ y je aktu´alnˇe na tahu. Jak bylo jiˇz naznaˇceno v´ yˇse, nelze u bˇeˇzn´ ych deskov´ ych her prozkoum´avat cel´ y hern´ı strom (v rozumn´em ˇcase). Minimax tedy postupuje od koˇrene stromu (aktu´aln´ı pozice) do pˇredem stanoven´e maxim´ aln´ı hloubky v´ ypoˇctu (odpov´ıd´a v´ yˇsce prozkoum´avan´e ˇc´asti hern´ıho stromu). Minimax nejprve ohodnot´ı pozice odpov´ıdaj´ıc´ı list˚ um prozkoum´avan´eho hern´ıho stromu pomoc´ı heuristick´e ohodnocovac´ı funkce. Prozat´ım pˇredpokl´adejme, ˇze tuto funkci jiˇz m´ame k dispozici. Ohodnocovac´ı funkce je silnˇe z´avisl´a na konkr´etn´ı deskov´e hˇre, o principech jej´ıho vytv´aˇren´ı pojedn´ av´ a 2.3. kapitola. Pokud jiˇz m´ame ohodnocen´e pozice odpov´ıdaj´ıc´ı list˚ um stromu, vypoˇc´ıt´ame z nich ohodnocen´ı pozic odpov´ıdaj´ıc´ı jejich rodiˇc˚ um. Tato ˇc´ast v´ ypoˇctu algoritmu je zaloˇzena na principu minimalizace moˇzn´ ych ztr´at. Algoritmus “pˇredpokl´ad´a”, ˇze oba z hr´aˇc˚ u budou hr´at sv´e “nejlepˇs´ı” moˇzn´e tahy. Ohodnocen´ı pozice, kde je na tahu aktu´aln´ı hr´aˇc (tj. hr´aˇc, kter´ y je na tahu tak´e v pozici, z n´ıˇz hled´ame “nejlepˇs´ı” tah), je tedy vypoˇcteno jako maximum z ohodnocen´ı vˇsech jej´ıch n´ asledovn´ık˚ u. Naopak ohodnocen´ı pozice, kde je na tahu soupeˇr, se vypoˇc´ıt´a jako minimum z ohodnocen´ı n´ asledovn´ık˚ u t´eto pozice, protoˇze nejlepˇs´ı tah soupeˇre je z pohledu aktu´aln´ıho hr´aˇce ten nejhorˇs´ı. Odtud vznikl i n´azev algoritmu Minimax. Postup popsan´ y v pˇredch´azej´ıc´ım odstavci m˚ uˇzeme opakovat, dokud nejsou ohodnoceny vˇsechny pozice odpov´ıdaj´ıc´ı n´asledovn´ık˚ um koˇrene stromu, ˇcili vˇsechny pozice, do kter´ ych se lze dostat z aktu´aln´ı pozice proveden´ım jednoho tahu. Z tˇechto pozic vybereme tu s maxim´aln´ım ohodnocen´ım a tah, kter´ ym se hra m˚ uˇze do t´eto pozice dostat, pak vr´at´ıme jako “nejlepˇs´ı” moˇzn´ y tah. ˇ´ıklad 2.1. Uvaˇzujme pozici na obr´azku 6. a nastaven´ı hloubky algoritmu Minimax � Pr na hodnotu 4. Pˇri v´ ypoˇctu nejlepˇs´ıho tahu z t´eto pozice tedy bude postupnˇe prozkoum´av´an hern´ı strom aˇz do t´eto hloubky. Tuto ˇc´ast hern´ıho stromu ilustruje obr´azek 7. Listov´e pozice, kter´e jsou na obr´azku zv´ yraznˇeny ˇcervenou barvou, z´ıskaj´ı sv´a ohodnocen´ı (zobrazena jako popisky uzl˚ u) prostˇrednictv´ım vol´an´ı heuristick´e ohodnocovac´ı funkce (viz kapitola 2.3.). Ohodnocen´ı ostatn´ıch uzl˚ u pak je pak vypoˇc´ıt´ano jako maximum, pokud je v dan´e pozici na tahu ˇcern´ y hr´aˇc (modr´e zv´ yraznˇen´ı ve stromu), nebo jako minimum, pokud je na tahu b´ıl´ y (zv´ yraznˇeno zelenˇe), z ohodnocen´ı jejich pˇr´ım´ ych n´asledovn´ık˚ u. Pˇri tomto v´ ypoˇctu postupujeme od list˚ u smˇerem ke koˇreni stromu. U koˇrene stromu n´as pak pochopitelnˇe jiˇz tolik nezaj´ım´a jeho ohodnocen´ı, ale tah, kter´ y vede k jeho nejv´ yˇse ohodnocen´emu n´asledovn´ıkovi. Tento tah, kter´ y je na obr´azku 7. zv´ yraznˇen ˇcervenou hranou, je vr´acen Minimaxem jako nejlepˇs´ı moˇzn´ y tah z aktu´aln´ı pozice.
2.2.
Implementace algoritmu
Pˇrestoˇze jsme si princip algoritmu Minimax uk´azali na vytvoˇren´em hern´ım stromu (dan´e maxim´ aln´ı hloubky s koˇrenem odpov´ıdaj´ıc´ı aktu´aln´ı pozici), nebudeme pˇri jeho implementaci hern´ı strom potˇrebovat ani sestrojovat. Algoritmus Minimax totiˇz ˇreˇs´ı prozkoum´av´an´ı pozic elegantnˇe jednoduchou rekurzivn´ı funkc´ı, jej´ıˇz zjednoduˇsenou verzi popisuje algoritmus 2.1. Rekurzivn´ı funkce minimax popsan´a v algoritmu 2.1. m´a dva vstupn´ı parametry – aktu´aln´ı pozici a hloubku, do kter´e se m´a hern´ı strom prozkoum´avat. Podm´ınka na 2. ˇr´adku je mezn´ı podm´ınkou rekurze, v´ ypoˇcet zde se “zastav´ı” ve chv´ıli, kdy pˇredan´a pozice odpov´ıd´a konci hry (ˇcili jiˇz nelze prov´adˇet ˇz´adn´e tahy) nebo kdyˇz se posloupnost rekurzivn´ıch vol´an´ı funkce dostane
6
Algoritmus Minimax
8 7 6 5 4 3 2 1 a
b
c
e
d
f
g
h
ˇ a d´ama, ˇcern´ Obr´azek 6. Pozice z hry Cesk´ y na tahu. 95 d8-e7
d8-c7
95 e5-d6 98 e7-c5 98
-12 e5-f6
e5-d6
95 e7-g5 95
e5-f6
99
-12 c7-b6
c7-e5 99
c7-d6
-15
-12
f6-e7
f6-g7
f6-e7
f6-g7
-15
-10
-12
-9
Obr´azek 7. Hern´ı strom odpov´ıdaj´ıc´ı pozici z obr´azku 6. do poˇzadovan´e hloubky hern´ıho stromu. Ohodnocov´an´ı na ˇr´adku 3 je vˇzdy prov´adˇeno z pohledu hr´ aˇce, kter´ y je v dan´e pozici na tahu. N´asleduje stˇeˇzejn´ı ˇc´ast algoritmu realizuj´ıc´ı rekurzivn´ı pr˚ uchod hern´ıho stromu do hloubky. Promˇenn´a ohodnocen´ı je na 5. ˇr´adku inicializov´ana na nejmenˇs´ı moˇznou hodnotu, coˇz je bˇeˇznˇe pouˇz´ıvan´ y postup pˇri v´ ypoˇctu maxima z vˇetˇs´ıho mnoˇzstv´ı ˇc´ısel. Pot´e jsou vygenerov´any veˇsker´e pozice, do kter´ ych se m˚ uˇze hra prostˇrednictv´ım jednoho tahu z pˇredan´e pozice dostat. Zde se implicitnˇe pˇredpokl´ad´a existence nˇejak´eho gener´atoru moˇzn´ ych tah˚ u, ze kter´ ych pak vytvoˇr´ıme potomky dan´e pozice. Gener´ator tah˚ u bude podrobnˇeji pops´ an v kapitole 2.4. V cyklu zaˇc´ınaj´ıc´ım na ˇr´adku 6 jsou pak dle oˇcek´av´an´ı pomoc´ı rekurzivn´ıho vol´ an´ı funkce minimax prozkoum´av´ani potomci dan´e pozice. ˇ adek 7 si ovˇsem zaslouˇz´ı podrobnˇejˇs´ı vysvˇetlen´ı. Pozorn´ R´ y ˇcten´aˇr si jiˇz jistˇe vˇsiml, ˇze k´od algoritmu obsahuje pouze funkci pro v´ ypoˇcet maxima — funkce pro v´ ypoˇcet minima se v nˇem nikde nevyskytuje, coˇz odporuje tomu, co bylo uv´adˇeno v´ yˇse. Tento rozpor je vˇsak pouze zd´anliv´ y. Algoritmus zde vyuˇz´ıv´a fakt, ˇze ohodnocovac´ı funkce je navrˇzena tak, aby hodnota 0 odpov´ıdala zcela vyrovnan´e pozici, kladn´a ohodnocen´ı pak odpov´ıdaj´ı pozic´ım v´ yhodnˇejˇs´ım pro hr´aˇce na tahu, z´ aporn´ a ohodnocen´ı pak nev´ yhodn´ ym pozic´ım z pohledu hr´aˇce na tahu. Zmˇenou znam´enka ohodnocen´ı tedy m˚ uˇzeme jednoduˇse pˇrej´ıt z pohledu jednoho hr´aˇce do pohledu druh´eho hr´aˇce. Pokud si
2.2.
7
Implementace algoritmu
d´ ale uvˇedom´ıme, ˇze plat´ı rovnost min(a, b) = −max(−a, −b), zjist´ıme, ˇze v´ ypoˇcet t´eto rekurzivn´ı funkce odpov´ıd´a v´ yˇse uveden´emu principu algoritmu s t´ım rozd´ılem, ˇze ohodnocen´ı pozic je nyn´ı vypoˇc´ıt´ ano z pohledu hr´aˇce, kter´ y je v tˇechto pozic´ıch na tahu a ne z pohledu hr´aˇce, kter´ y byl na tahu v koˇrenov´e pozici. Algoritmus 2.1. Zjednoduˇsen´y algoritmus Minimax (pseudok´ od) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:
function minimax(pozice, hloubka) if (pozice je koncov´a or hloubka = 0) then return heuristick´e ohodnocen´ı pozice else ohodnocen´ı ← −∞ for all potomek pozice do ohodnocen´ı ← max(ohodnocen´ı, −minimax(potomek, hloubka − 1)) end for return ohodnocen´ı end if end function
ˇ´ıklad 2.2. Na obr´azku 8. je zn´azornˇen hern´ı strom ohodnocen´ � Pr y zjednoduˇsenou verz´ı reˇ kurzivn´ı funkc´ı minimax. Cervenˇ e zv´ yraznˇen´e uzly byly ohodnoceny heuristicky, u ostatn´ıch uzl˚ u bylo jejich ohodnocen´ı vypoˇcteno jako maximum z opaˇcn´ ych ˇc´ısel k ohodnocen´ım pˇr´ım´ ych potomk˚ u dan´eho uzlu. Pokud tedy jsou o1 , o2 , . . . ohodnocen´ı potomk˚ u, vypoˇc´ıt´ame ohodnocen´ı dan´e pozice jako max(−o1 , −o2 , . . . ). 95 d8-e7
d8-c7
-95 e5-d6 98
12 e5-f6
e5-d6
95 e7-g5
e7-c5 -98
-95
e5-f6
99
-12 c7-b6
c7-e5 -99
c7-d6
15
12
f6-e7
f6-g7
f6-e7
f6-g7
-15
-10
-12
-9
Obr´azek 8. Hern´ı strom ilustruj´ıc´ı v´ ypoˇcty zjednoduˇsen´eho Minimaxu. Pˇredstaven´a zjednoduˇsen´a verze Minimaxu zat´ım neˇreˇs´ı v´ ybˇer nejlepˇs´ıho tahu v koˇrenov´e pozici. D´ ale by tato verze mˇela probl´em s ohodnocov´an´ım pozic, kter´e vedou ke konci hry. Jednoduˇse ˇreˇceno, Minimax zat´ım nerozliˇsuje mezi v´ yhrou (resp. prohrou) prvn´ım tahem a v´ yhrou (resp. prohrou) des´at´ ym tahem, coˇz by mohlo v´est k situaci, kdy poˇc´ıtaˇcov´ y hr´aˇc i na prvn´ı pohled vyhranou partii zbyteˇcnˇe prodluˇzuje. Tyto probl´emy jiˇz ˇreˇs´ı n´asleduj´ıc´ı podrobnˇeji rozpracovan´ y algoritmus Minimax. Jeho rekurˇ ast ˇreˇs´ıc´ı v´ zivn´ı ˇc´ ast je zde uvedena jako algoritmus 2.2. C´ ybˇer tahu v koˇreni hern´ıho stromu pak jako algoritmus 2.3. V t´eto verzi algoritmu Minimax je tak´e explicitnˇe rozeps´ano ohodnocov´an´ı koncov´ ych hern´ıch pozic. Pozici, ve kter´e dan´ y hr´aˇc prohr´al, pˇriˇrad´ıme ohodnocen´ı, kter´e je menˇs´ı neˇz ohodnocen´ı jak´ekoli neprohr´avaj´ıc´ı pozice. Symetricky, pˇriˇrad´ıme vyhr´avaj´ıc´ı pozici, z pohledu v´ıtˇezn´eho
8
Algoritmus Minimax
hr´ aˇce, maxim´aln´ı moˇzn´e ohodnocen´ı. Ohodnocen´ı v´ yhry a prohry by se vˇzdy mˇela liˇsit pouze znam´enkem, v naˇsem pseudok´odu pouˇz´ıv´ame ˇc´ıseln´e konstanty MAX a −MAX. Pokud v dan´e pozici hra skonˇcila rem´ızou, je ohodnocen´ı t´eto pozice rovno nule. U velk´eho mnoˇzstv´ı deskov´ ych her nem˚ uˇze podle pravidel doj´ıt k v´ıtˇezstv´ı hr´aˇce po soupeˇrovˇe tahu, ˇr´adky 5, 6 a 7 je tedy moˇzn´e vˇetˇsinou vynechat. Heuristick´a funkce pˇriˇrazuj´ıc´ı pozici ohodnocen´ı z pohledu hr´aˇce na tahu je tak vol´ana pouze v pˇr´ıpadˇe nekoncov´e pozice a nulov´e hodnoty parametru hloubka (viz ˇr´adky 11 a 12). Na ˇr´adc´ıch 14 aˇz 19 se toho oproti zjednoduˇsen´e variantˇe pˇr´ıliˇs nezmˇenilo, pouze jsme vytv´aˇren´ı potomk˚ u dan´e pozice rozdˇelili do nˇekolika pˇr´ıkaz˚ u (generov´an´ı tah˚ u, zahr´an´ı tahu), coˇz v´ıce odpov´ıd´a praktick´emu ˇreˇsen´ı tohoto d´ılˇc´ıho probl´emu. ˇ adky 20 aˇz 25 algoritmu 2.2. upravuj´ı ohodnocen´ı pozice takov´ R´ ym zp˚ usobem, aby algoritmus preferoval v´ yhru za menˇs´ı poˇcet tahu pˇred vzd´alenˇejˇs´ı v´ yhrou a naopak vzd´alenˇejˇs´ı prohru pˇred rychlejˇs´ı prohrou. Podm´ınky na tˇechto ˇr´adc´ıch vyuˇz´ıvaj´ı konstantu MNOHO pro rozliˇsen´ı ohodnocen´ı bˇeˇzn´ ych pozic od ohodnocen´ı, kter´a pˇr´ısluˇs´ı vyhr´avaj´ıc´ım ˇci prohr´avaj´ıc´ım pozic´ım v horizontu nˇekolika tah˚ u. Pˇri pˇred´av´an´ı ohodnocen´ı vyhr´avaj´ıc´ı ˇci prohr´avaj´ıc´ı pozice od listu smˇerem ke koˇreni stromu se pak absolutn´ı hodnota tohoto ohodnocen´ı s kaˇzd´ ym patrem stromu zmenˇsuje o 1, coˇz vede k v´ yˇse popsan´emu ˇz´adouc´ımu chov´an´ı algoritmu. Algoritmus 2.2. Kompletn´ı pseudok´ od algoritmu Minimax 1:
function minimax(pozice, hloubka)
2: 3: 4:
if je prohra(pozice) then return −MAX end if
5: 6: 7:
if je v´yhra(pozice) then return MAX end if
8: 9: 10:
if je rem´ıza(pozice) then return 0 end if
if hloubka = 0 then return ohodnocovaci funkce(pozice) else tahy ← generuj tahy(pozice) 15: ohodnoceni ← −MAX 11: 12: 13: 14:
18: 19:
for all tah v kolekci tahy do potomek ← zahraj(pozice, tah) ohodnoceni ← max(ohodnoceni, −minimax(potomek, hloubka − 1)) end for
20: 21: 22:
if ohodnoceni > MNOHO then ohodnoceni ← ohodnoceni − 1 end if
23: 24: 25:
if ohodnoceni < −MNOHO then ohodnoceni ← ohodnoceni + 1 end if
16: 17:
26: 27:
return ohodnoceni end if
28:
end function
2.2.
9
Implementace algoritmu
Jak jiˇz bylo uvedeno v´ yˇse, u pozice, kter´a tvoˇr´ı koˇren stromu n´as nezaj´ım´a ani tak jej´ı ohodnocen´ı jako tah, kter´ y vede k nejl´epe ohodnocen´emu potomkovi, coˇz je nejlepˇs´ı moˇzn´ y tah z dan´e pozice. Toto rozhodov´an´ı zajiˇst’uje funkce nej tah popsan´a algoritmem 2.3., kter´a je vol´ana s pozic´ı, z n´ıˇz potˇrebujeme zjistit nejlepˇs´ı moˇzn´ y tah, a hloubkou, do kter´e chceme nechat minimax prohled´ avat hern´ı strom. Od funkce minimax se tato funkce liˇs´ı prakticky jen t´ım, ˇze si kromˇe nejlepˇs´ıho nalezen´eho ohodnocen´ı (uloˇzen´eho v promˇenn´e nejlepsi ohodnoceni ) ukl´ad´a (do promˇenn´e nejlepsi tah) tak´e tah, kter´ y k tomuto ohodnocen´ı vedl. Nejlepˇs´ı nalezen´ y tah funkce tak´e vrac´ı jako svou n´avratovou hodnotu. U koˇrene hern´ıho stromu nen´ı vˇetˇsinou potˇreba testovat, zda nen´ı pˇredan´a pozice koncov´a, ani zda nebyla zadan´a nulov´a hloubka. Tak´e u ´pravy ohodnocen´ı odpov´ıdaj´ıc´ıch v´ yhˇre ˇci prohˇre zde nemaj´ı ˇza´dn´ y v´ yznam. Algoritmus 2.3. Pseudok´ od funkce pro zjiˇstˇen´ı nejlepˇs´ıho tahu 1:
function nej tah(pozice, hloubka)
2:
tahy ← generuj tahy(pozice) nejlepsi ohodnoceni ← −MAX
3:
8: 9: 10: 11:
for all tah v kolekci tahy do potomek ← zahraj(pozice, tah) ohodnoceni ← −minimax(potomek, hloubka − 1) if ohodnoceni > nejlepsi ohodnoceni then nejlepsi ohodnoceni ← ohodnoceni nejlepsi tah ← tah end if end for
12:
return nejlepsi tah
13:
end function
4: 5: 6: 7:
ˇ´ıklad 2.3. Na obr´azku 9. je uk´az´ano ohodnocen´ı hern´ıho stromu odpov´ıdaj´ıc´ımu hern´ı � Pr pozici z obr´azku 6. Pˇri ohodnocov´an´ı byl pouˇzit algoritmus minimax s hloubkou v´ ypoˇctu 4 a konˇ stantami MAX = 99 a MNOHO = 90. Cervenˇ e jsou zv´ yraznˇeny uzly, kter´e byly ohodnoceny heuristicky, a hrana, kter´e odpov´ıd´a vypoˇcten´emu nejlepˇs´ımu tahu.
d8-e7
d8-c7
-97 e5-d6 98
12 e5-f6
e5-d6
98 e7-g5
e7-c5 -99
-99
e5-f6
98
-12 c7-b6
c7-e5 -99
c7-d6
15
12
f6-e7
f6-g7
f6-e7
f6-g7
-15
-10
-12
-9
Obr´azek 9. Hern´ı strom ilustruj´ıc´ı v´ ypoˇcty komplexn´ıho Minimaxu.
10
Algoritmus Minimax
ˇ´ıklad 2.4. Prohl´ednˇete si pozici z obr´azku 10. a hern´ı strom odpov´ıdaj´ıc´ı v´ � Pr ypoˇctu Minimaxu do hloubky 2 pro tuto pozici, kter´ y je zn´azornˇen na obr´azku 11. Nemus´ıte b´ yt pˇreborn´ıci ˇ a d´ama, abyste poznali, ˇze Minimax nezvolil pr´avˇe nejlepˇs´ı tah. Nejvˇetˇs´ı slabinou Mive hˇre Cesk´ nimaxu, kter´a se zde projevila, je jeho omezen´e “vidˇen´ı” do pˇredem urˇcen´e hloubky. V nˇekter´ ych situac´ıch, kdy doch´az´ı k vˇetˇs´ım zmˇen´am v ohodnocen´ı pozic (napˇr. uprostˇred v´ ymˇeny kamen˚ u), nen´ı vhodn´e, aby Minimax ukonˇcil rekurzi. Z tohoto d˚ uvodu se v praxi ˇcasto setk´av´ame s modifikacemi algoritmu Minimax, kter´e v´ ymˇenu kamen˚ u vˇzdy dokonˇc´ı, pˇrestoˇze se jiˇz ocitly v “nulov´e hloubce” a mˇely by tedy prohled´av´an´ı stromu ukonˇcit. 8 7 6 5 4 3 2 1 a
c
b
d
e
f
g
h
ˇ a d´ama, na tahu je ˇcern´ Obr´azek 10. Pozice ze hry Cesk´ y hr´aˇc
e7-d6 15 c5-e7 -15
f8-g7
e7-f6 16
3
g5-e7 -16
-2
c5-b6 c5-d6 1
g5-h6 g5-f6
2
-3
Obr´azek 11. Hern´ı strom ilustruj´ıc´ı v´ ypoˇcet Minimaxu pro pozici z obr´azku 10.
2.3.
Ohodnocovac´ı funkce
Nyn´ı se pod´ıvejme na detaily t´ ykaj´ıc´ı se n´avrhu a implementace ohodnocovac´ı funkce, kter´a byla pouˇzita v k´odu algoritmu 2.2. Jak jiˇz bylo naznaˇceno v´ yˇse, jedn´a se o funkci, jej´ımˇz vstupn´ım parametrem je nekoncov´a hern´ı pozice a v´ ystupem je celoˇc´ıseln´e ohodnocen´ı dan´e pozice z pohledu hr´ aˇce na tahu. Toto ohodnocen´ı je vˇzdy z intervalu �−MNOHO, MNOHO�; ohodnocen´ı, jejichˇz absolutn´ı hodnota je vˇetˇs´ı neˇz MNOHO jsou vyˇclenˇena pro vyhr´avaj´ıc´ı a prohr´avaj´ıc´ı pozice (viz popis algoritmu 2.2. v kapitole 2.2.). Vˇzdy by tak´e mˇelo b´ yt splnˇeno, ˇze ohodnocen´ı jedn´e pozice z pohledu prvn´ıho a druh´eho hr´aˇce se liˇs´ı pouze znam´enkem. V praxi si tedy vystaˇc´ıme s ohodnocovac´ı funkc´ı pro jednoho z hr´aˇc˚ u, ohodnocen´ı z pohledu druh´eho hr´aˇce z´ısk´ame zmˇenou znam´enka. Funkce by d´ale mˇela b´ yt pokud moˇzno jednoduch´a a rychl´a, vesmˇes je mnohem u ´ˇcinnˇejˇs´ı pouˇz´ıt jednoduch´e ohodnocen´ı a prozkoum´avat hern´ı strom do vˇetˇs´ı hloubky neˇz nasadit sloˇzitou ohodnocovac´ı heuristiku.
2.3.
11
Ohodnocovac´ı funkce
Ohodnocovac´ı funkce patˇr´ı samozˇrejmˇe mezi ty ˇc´asti algoritmu, jejichˇz v´ ypoˇcet je silnˇe z´avisl´ y na konkr´etn´ı deskov´e hˇre. Pˇresto se nyn´ı pokus´ıme zformulovat nˇekolik obecn´ ych z´asad, kter´ ych se b´ yv´ a dobr´e drˇzet pˇri n´avrhu ohodnocovac´ıch funkc´ı vˇetˇsiny jednoduch´ ych deskov´ ych her. Pokud je dan´ a hra zaloˇzena na zaj´ım´an´ı kamen˚ u soupeˇre, mˇely by b´ yt poˇcty m´ ych a soupeˇrov´ ych kamen˚ u na desce prim´arn´ım krit´eriem pˇri ohodnocov´an´ı pozice. D´ale lze hodnotit um´ıstˇen´ı jednotliv´ ych kamen˚ u na desce. Toto vˇetˇsinou ˇreˇs´ıme statickou tabulkou bonus˚ u a postih˚ u pro jednotliv´e typy figur (napˇr. d´ama, pˇeˇsec). Bonus ˇci postih se jednoduˇse zapoˇc´ıt´a, pokud dan´a figura stoj´ı na dan´em poli. Pˇr´ıpadnˇe lze tak´e pˇrid´avat bonusy a postihy za r˚ uzn´a seskupen´ı figur na desce, osamˇel´e figury a podobnˇe. Tyto v´ ypoˇcty uˇz ale mohou b´ yt komplikovanˇejˇs´ı a mohou tak negativnˇe ovlivnit rychlost ohodnocovac´ı funkce. 8 7
+2
7
+2
6 5
+2 +2
1
+2 +3 a
b
c
+2
8 7
+3
+3 d
e
+2
+3 f
g
+2
5
3
1
+2 +2 +2 a
b
c
+3 d
e
+3 f
g
-2 -2 -2 c
-3
d
e
-3
f
g
-3
h
-3
-2 -2 -2 -2
4
-2 -2
2 1
h
b
6
3
+3
-2
8
5
+2
+3
-2
a
7
+2
2
-2
2
h
+2
4
-3
1
+2
6
-3
4 3
2
-3
6 5
+2
4 3
-3
8
-2 a
-2 b
c
-2 d
e
-2 f
g
h
Obr´ azek 12. Statick´e “tabulky” pro ohodnocov´an´ı um´ıstˇen´ı b´ıl´eho pˇeˇsce (vlevo nahoˇre), ˇcern´eho pˇeˇsce (vpravo nahoˇre) b´ıl´e d´amy (vlevo dole) a ˇcern´e d´amy (vpravo dole).
ˇ a d´ama. Jak jiˇz ˇ´ıklad 2.5. Zkusme si nyn´ı navrhnout ohodnocovac´ı funkci pro hru Cesk´ � Pr bylo ˇreˇceno v´ yˇse, vystaˇc´ıme si s funkc´ı pro hodnocen´ı pozice z pohledu b´ıl´eho hr´aˇce. Ohodnocen´ı z pohledu ˇcern´eho pak z´ısk´ame zmˇenou znam´enka. N´ıˇze uveden´a ohodnocovac´ı funkce je inspirov´ ana bakal´aˇrskou prac´ı Ladislava Vit´aska [5]. Z´ akladem kaˇzd´eho hodnocen´ı hern´ı pozice je ohodnocen´ı materi´alu. Zde je tˇreba urˇcit hodnotu, kterou budou m´ıt jednotliv´e druhy figur. Pro potˇreby tohoto pˇr´ıkladu budeme za kaˇzd´eho b´ıl´eho pˇeˇsce na desce pˇriˇc´ıtat k aktu´aln´ımu ohodnocen´ı 25 bod˚ u, za kaˇzdou b´ılou d´amu pak 100 bod˚ u. Symetricky za kaˇzd´eho ˇcern´eho pˇeˇsce odeˇcteme 25 a za kaˇzdou ˇcernou d´amu 100 bod˚ u. K ohodnocen´ı materi´aln´ıch sloˇzek pak pˇrid´ame bonusy za um´ıstˇen´ı figur. Toto je moˇzn´e realizovat napˇr´ıklad pˇrid´an´ım bonus˚ u za um´ıstˇen´ı kamen˚ u na konkr´etn´ıch pol´ıch. Pokud si uvˇedom´ıme, ˇze na pol´ıch prvn´ıho a osm´eho sloupce a prvn´ı a osm´e ˇrady nelze k´amen nikdy pˇreskoˇcit, m˚ uˇzeme figur´ am na tˇechto pol´ıch pˇridat za jejich um´ıstˇen´ı bonus v hodnotˇe 2 bod˚ u. B´ıl´e figury v prvn´ı ˇradˇe, stejnˇe jako ˇcern´e figury v osm´e ˇradˇe, nav´ıc br´an´ı soupeˇrov´ ym pˇeˇsc˚ um v promˇenˇe na d´amu. Tˇemto pol´ım tedy pˇrid´ame dalˇs´ı jednobodov´ y bonus. Bonusy jednotliv´ ych pol´ı pro jednotliv´e typy figur ukazuje obr´azek 12.
12
Algoritmus Minimax
8 7 6
?
?
?
?
5 4 3 2 1 a
b
c
d
e
f
g
h
Obr´azek 13. Ilustrace pˇridˇelov´an´ı bonus˚ u za um´ıstˇen´ı v bl´ızkosti jin´ ych figur. Bonusy za um´ıstˇen´ı je moˇzn´e vypoˇc´ıt´avat tak´e principi´alnˇe zcela jin´ ym zp˚ usobem. M˚ uˇzeme napˇr´ıklad pro kaˇzdou figuru urˇcit poˇcet vlastn´ıch figur na sousedn´ıch pol´ıch (viz obr´azek 13.) a za kaˇzdou zjiˇstˇenou sousedn´ı figuru pˇridat k ohodnocen´ı jeden bod. Samozˇrejmˇe je moˇzn´e oba principy libovolnˇe kombinovat. Je ovˇsem potˇreba d´avat pozor na to, aby jedna vˇec nebyla do koneˇcn´eho ohodnocen´ı zapoˇc´ıt´ana v´ıcekr´at! ˇ´ıklad 2.6. Prostudujme si pozici na obr´azku 14. a pokusme se ji ohodnotit funkc´ı zkon� Pr struovanou v pˇr´ıkladu 2.5. Nejprve vypoˇc´ıtejme materi´aln´ı sloˇzku ohodnocen´ı. B´ıl´ y m´a na desce 2 pˇeˇsce a 2 d´amy, ˇcern´ y pak 3 pˇeˇsce a d´amu, ˇcili po zv´aˇzen´ı materi´alu je pozice ohodnocena 2 × 25 + 2 × 100 − 3 × 25 − 100 = 75 bod˚ u. Nyn´ı urˇc´ıme tak´e poziˇcn´ı ˇc´ast ohodnocen´ı. B´ıl´ y pˇeˇsec na poli a7 z´ısk´a nav´ıc 2 body za um´ıstˇen´ı na poli a 1 bod za sousedn´ı b´ılou d´amu. B´ıl´ y pˇeˇsec na c1 obdrˇz´ı 3 body za um´ıstˇen´ı v prvn´ı ˇradˇe. B´ıl´ a d´ ama na b6 z´ısk´a 1 bod za sousedn´ıho pˇeˇsce, b´ıl´a d´ama na a3 pak 2 body za um´ıstˇen´ı na okraji desky. Celkovˇe tedy b´ıl´e figury pˇridaj´ı k ohodnocen´ı 9 bod˚ u. Z ˇcern´ ych figur z´ısk´av´a poziˇcn´ı bonus pouze pˇeˇsec na poli b8 a to konkr´etnˇe 3 body. Poziˇcn´ı sloˇzka ohodnocen´ı tedy ˇcin´ı 9 − 3 = 6 bod˚ u, celkov´e ohodnocen´ı pozice pak 75 + 6 = 81 bod˚ u. 8 7 6 5 4 3 2 1 a
b
c
d
e
f
g
h
Obr´azek 14. Hern´ı pozice pro ilustraci v´ ypoˇctu ohodnocen´ı.
2.4.
2.4.
Gener´ator tah˚ u
13
Gener´ ator tah˚ u
Posledn´ı zat´ım podrobnˇe neokomentovanou souˇc´ast´ı algoritmu 2.2. je gener´ator tah˚ u, kter´emu bude vˇenovan´a tato kapitola. Vstupem gener´atoru je hern´ı pozice, v´ ystup pak tvoˇr´ı kolekce vˇsech tah˚ u, kter´e lze z dan´e pozice podle pravidel dan´e hry prov´est. Pˇri vytv´aˇren´ı t´eto kolekce se pochopitelnˇe vyplat´ı postupovat systematicky. ˇ a d´ama (a mnoh´ U hry Cesk´ ych dalˇs´ıch) napˇr´ıklad pravidla pˇrikazuj´ı prov´est skok, kdykoli je to moˇzn´e. Je tedy nanejv´ yˇs rozumn´e vygenerovat nejprve vˇsechny moˇzn´e skoky a aˇz pokud se zjist´ı, ˇze ˇz´ adn´ y leg´aln´ı skok neexistuje, generovat ostatn´ı tahy. Pˇri samotn´em generov´an´ı tah˚ u obvykle systematicky proch´az´ıme desku (pˇr´ıpadnˇe nˇejak´e pomocn´e kolekce figur) a pro kaˇzdou figuru hr´aˇce na tahu opˇet systematicky hled´ame vˇsechny leg´aln´ı tahy.
14
Algoritmus Minimax
15
3.
Alfa-beta oˇ rez´ av´ an´ı
V t´eto ˇc´asti textu bude uk´az´ano a okomentov´ano jedno z nejˇcastˇeji vyuˇz´ıvan´ ych vylepˇsen´ıch algoritmu Minimax. N´ıˇze prezentovan´ y algoritmus dosahuje stejn´ ych v´ ysledk˚ u jako samotn´ y Minimax. Na druhou stranu je moˇzn´e pouˇzit´ım tohoto algoritmu znaˇcnˇe sn´ıˇzit ˇcasovou n´aroˇcnost v´ ypoˇctu a t´ım umoˇznit v´ ypoˇcet do vˇetˇs´ı hloubky. Princip Alfa-beta oˇrez´av´an´ı spoˇc´ıv´a v neproch´azen´ı tˇech ˇc´ast´ı hern´ıho stromu, kter´e jiˇz zjevnˇe neovlivn´ı pr´avˇe vypoˇc´ıt´avan´ y nejlepˇs´ı tah poˇc´ıtaˇcov´eho hr´aˇce. Algoritmus Alfa-beta oˇrez´av´an´ı je dobˇre pops´an v mnoha publikac´ıch [2, 4, 6].
3.1.
Princip algoritmu
Jak jiˇz bylo ˇreˇceno v´ yˇse, z´akladn´ım principem tohoto vylepˇsen´ı algoritmu Minimax je nevyhodnocov´ an´ı tˇech vˇetv´ı hern´ıho stromu, kter´e jiˇz nemohou ovlivnit ohodnocen´ı uzl˚ u nach´azej´ıc´ıch se nad nimi a tedy ani volbu nejlepˇs´ıho tahu poˇc´ıtaˇcov´eho hr´aˇce z dan´e pozice. Pro snadnˇejˇs´ı objasnˇen´ı tohoto principu se v t´eto podkapitole vr´at´ıme k intuitivn´ı pˇredstavˇe ohodnocov´an´ı hern´ıho stromu, kter´e bylo pouˇzito v kapitole 2.1. Pˇripomeˇ nme, ˇze ˇslo o ohodnocov´ an´ı pozic z pohledu hr´aˇce, kter´ y je na tahu v pozici odpov´ıdaj´ıc´ı koˇreni stromu. V pozic´ıch, kde je na tahu tento hr´aˇc, se vyb´ır´a maximum z ohodnocen´ı n´asledovn´ık˚ u dan´e pozice. V pozici, kde je na tahu soupeˇr, vyb´ır´ame naopak minimum z ohodnocen´ı jej´ıch n´asledovn´ık˚ u. Pˇri zobrazov´an´ı hern´ıch strom˚ u budeme d´ale pˇredpokl´adat, ˇze jsou ohodnocen´ı jednotliv´ ych n´asledovn´ık˚ u kaˇzd´e pozice vypoˇc´ıt´av´ana od nejlevˇejˇs´ıho smˇerem doprava. Principi´alnˇe rozliˇsujeme dva druhy oˇrez´av´an´ı hern´ıho stromu. O alfa-oˇrez´av´an´ı mluv´ıme tehdy, pokud byla mezi ohodnocen´ımi potomk˚ u nalezena velmi mal´a hodnota, kter´a jiˇz zaruˇcuje, ˇze dan´ a vˇetev nebude v ˇz´adn´em pˇr´ıpadˇe zvolena hr´aˇcem na tahu. V t´eto situaci pak jiˇz nem´a smysl zkoumat dalˇs´ı potomky dan´e pozice. U beta-oˇrez´av´an´ı naopak nalezen´ı velmi velk´eho ohodnocen´ı mezi potomky zaruˇc´ı, ˇze zkouman´a vˇetev hern´ıho stromu nebude zvolena soupeˇrem. I zde pak m˚ uˇzeme upustit od zkoum´an´ı dalˇs´ıch potomk˚ u dan´e pozice. Oba typy oˇrez´avan´ı hern´ıho stromu ilustruje n´asleduj´ıc´ı pˇr´ıklad.
≤7
≥9
7
2
7
9 Obr´azek 15. Ilustrace beta-ˇrezu.
ˇ´ıklad 3.1. Uvaˇzujme abstraktn´ı hern´ı strom zn´azornˇen´ � Pr y na obr´azc´ıch 15. a 16. Podobnˇe jako v kapitole 2.1. jsou i zde modˇre oznaˇceny uzly, ve kter´ ych se vyb´ır´a maximum z ohodnocen´ı potomk˚ u, a zelenˇe uzly, ve kter´ ych vyb´ır´ame minimum. Ohodnocen´ı jednotliv´ ych uzl˚ u stromu jsou, jak jiˇz bylo zm´ınˇeno v´ yˇse, vypoˇc´ıt´av´ana postupnˇe a to zleva doprava. V situaci na obr´azku 15. jiˇz byla ˇc´ast ohodnocen´ı vypoˇctena. Ve chv´ıli, kdy je vypoˇctena hodnota 9 jednoho z list˚ u, je zˇrejm´e, ˇze jeho rodiˇc bude m´ıt tak´e hodnotu 9 nebo dokonce jeˇstˇe v´ıce. Tento poznatek je trivi´aln´ım d˚ usledkem faktu, ˇze ohodnocen´ı tohoto rodiˇce je vypoˇc´ıt´av´ano jako maximum ze vˇsech jeho pˇr´ım´ ych potomk˚ u. Podobnˇe je z dˇr´ıve vypoˇcten´ ych hodnot jiˇz k dispozici odhad v´ ysledn´eho ohodnocen´ı zelen´eho uzlu s popiskem “≤ 7”. Zde se opˇet vyuˇzila u ´vaha, ˇze zelen´ y
16
Alfa-beta oˇrez´av´an´ı
≥4
≤3
4
≥9
7
2
7
4
9
4
15
3
15
3
3
1
3
Obr´azek 16. Pˇr´ıklad alfa-oˇrez´an´ı. uzel “≤ 7” bude ohodnocen minimem ze vˇsech ohodnocen´ı jeho pˇr´ım´ ych potomk˚ u. Zˇrejmˇe tedy modr´ y uzel “≥ 9” ani jeho potomci nemohou jiˇz ovlivnit vypoˇc´ıt´avan´e hodnoty uzl˚ u ve vyˇsˇs´ıch patrech stromu a tud´ıˇz je moˇzn´e dalˇs´ı, zat´ım nevyhodnocovan´e, n´asledovn´ıky uzlu “≥ 9” ignorovat. Toto odpov´ıd´a v´ yˇse zm´ınˇen´emu beta-oˇrez´av´an´ı. Uzly dan´eho hern´ıho stromu jsou pak d´ale ohodnocov´any standardn´ım zp˚ usobem. K dalˇs´ımu oˇrezu doch´az´ı aˇz v situaci zn´azornˇen´e na obr´azku 16. Odhad ohodnocen´ı prav´eho potomka koˇrene je aktu´alnˇe 3 nebo m´enˇe (minimum z hodnot 15, 3 a nezn´am´e hodnoty), zat´ımco hodnota koˇrene m˚ uˇze b´ yt odhadnuta na 4 nebo v´ıce. Vzhledem k faktu, ˇze v koˇreni vyb´ır´ame maximum z hodnot jeho potomk˚ u, je tedy jiˇz zˇrejm´e, ˇze druh´ y potomek koˇrene – uzel “≤ 3” v´ ypoˇcet neovlivn´ı a tud´ıˇz jiˇz nen´ı potˇreba ani zkoumat dalˇs´ı jeho potomky, kteˇr´ı jsou na obr´azku oznaˇceni ˇcervenou barvou. V t´eto situaci doˇslo k alfa-oˇrez´an´ı.
3.2.
Implementace algoritmu
V t´eto kapitole se pokus´ıme proniknout do detail˚ u implementace algoritmu Alfa-beta oˇrez´av´an´ı. Podobnˇe jako ˇcist´ y algoritmus Minimax i toto vylepˇsen´ı je realizov´ano pomoc´ı rekurzivn´ı funkce, kter´ a vypoˇc´ıt´av´a ohodnocen´ı pozic do urˇcit´e hloubky hern´ıho stromu. Kromˇe zkouman´e pozice a poˇzadovan´e hloubky je vˇsak nyn´ı potˇreba pˇred´avat pˇri vol´an´ı zm´ınˇen´e funkce tak´e jak´esi hodnoty α a β, kter´e urˇcuj´ı interval �α, β� oˇcek´avan´ ych ohodnocen´ı. Pokud je nalezeno ohodnocen´ı mimo tento interval, doch´az´ı k v´ yˇse zm´ınˇen´emu oˇrez´av´an´ı. Podobnˇe jako u algoritmu Minimax, i nyn´ı se budou ohodnocen´ı pozic “bl´ızk´ ych konci hry” pohybovat v intervalech �−MAX, −MNOHO) a (MNOHO, MAX�. Pˇri rekurzivn´ıch vol´an´ıch (posunu d´ ale od aktu´aln´ı pozice) je pak potˇreba zvˇetˇsovat absolutn´ı hodnotu tˇechto ohodnocen´ı, ˇc´ımˇz se vyjadˇruje fakt, ˇze se dost´av´ame bl´ıˇze k dan´e v´ yhˇre ˇci prohˇre. Toto je v algoritmu realizov´ano pomocnou funkc´ı dal. Naopak pˇri n´avratu z rekurze (pˇribl´ıˇzen´ı se aktu´aln´ı pozici) je potˇreba sn´ıˇzit absolutn´ı hodnoty “ohodnocen´ı bl´ızk´ ych ke konci hry”, coˇz obstar´av´a funkce bliz. Funkce dal a bliz jsou uvedeny v algoritmu 3.1. Algoritmus 3.1. Pseudok´ od funkc´ı pro pˇrepoˇcty ohodnocen´ı bl´ızk´ych konci hry function dal(ohodnoceni) if ohodnoceni > MNOHO then return ohodnoceni + 1 end if if ohodnoceni < −MNOHO then return ohodnoceni − 1 end if return ohodnoceni end function
3.2.
Implementace algoritmu
17
function bliz(ohodnoceni) if ohodnoceni > MNOHO then return ohodnoceni − 1 end if if ohodnoceni < −MNOHO then return ohodnoceni + 1 end if return ohodnoceni end function Stˇeˇzejn´ı ˇc´ast algoritmu Alfa-beta oˇrez´av´an´ı (viz algoritmus 3.2.) je realizov´ana rekurzivn´ı funkc´ı alfabeta, kter´a se do znaˇcn´e m´ıry podob´a v pˇredchoz´ıch kapitol´ach prezentovan´e funkci minimax. Rozd´ıly mezi tˇemito funkcemi jsou patrny pouze v ˇc´asti k´odu realizuj´ıc´ı rekurzivn´ı vol´an´ı na ˇr´adku 17 a d´ ale v ˇc´asti algoritmu zajiˇst’uj´ıc´ı oˇrez´av´an´ı na ˇr´adc´ıch 21–23. Pˇri rekurzivn´ım vol´an´ı funkce alfabeta je pochopitelnˇe nutn´e pˇred´avat tak´e interval oˇcek´avan´ ych ohodnocen´ı pro danou vˇetev v´ ypoˇctu. Podobnˇe jako se pˇri rekurzivn´ım vol´an´ı a n´avratu z rekurze mˇen´ı u vypoˇcten´eho ohodnocen´ı “pohled jednoho hr´aˇce” na “pohled druh´eho hr´aˇce” zmˇenou znam´enka, je potˇreba prov´est tuto zmˇenu i u intervalu oˇcek´avan´ ych hodnot, kde se oˇcek´av´an´ı �α, β� mˇen´ı na �−β, −α�. U pˇr´ıpadn´ ych hodnot bl´ızk´ ych ohodnocen´ı konce hry se nav´ıc prov´ad´ı tak´e zvˇetˇsen´ı jejich absolutn´ıch hodnot o 1. Vˇsimnˇete si tak´e, ˇze aktu´aln´ı maxim´aln´ı nalezen´e ohodnocen´ı se na ˇr´adku 20 ukl´ad´a pˇr´ımo do promˇenn´e alfa, coˇz ihned zpˇresˇ nuje interval oˇcek´avan´ ych ohodnocen´ı pˇri prozkoum´av´an´ı dalˇs´ıch potomk˚ u dan´e pozice. Oˇrez´av´an´ı realizovan´e v algoritmu na ˇr´adc´ıch 21–23 spoˇc´ıv´a v jednoduch´em testu, zda pr´avˇe nalezen´e maxim´aln´ı ohodnocen´ı jiˇz dosahuje ˇci pˇrekraˇcuje maxim´aln´ı oˇcek´avanou hodnotu beta. Pokud ano, je ihned ukonˇceno vyhodnocov´an´ı dalˇs´ıch potomk˚ u dan´e pozice, protoˇze jiˇz nemohou volbu nejlepˇs´ıho tahu nijak ovlivnit. N´avratov´a hodnota beta nijak neovlivˇ nuje v´ ysledn´e ohodnocen´ı rodiˇce dan´e pozice v hern´ım stromu. Algoritmus 3.2. Pseudok´ od stˇeˇzejn´ı ˇc´ asti algoritmu Alfa-beta 1:
function alfabeta(pozice, hloubka, alfa, beta)
if je prohra(pozice) then return −MAX 4: end if 2: 3:
5: 6: 7:
if je v´yhra(pozice) then return MAX end if
8: 9: 10:
if je rem´ıza(pozice) then return 0 end if
11: 12: 13:
if hloubka = 0 then return ohodnocovaci funkce(pozice) end if
14: 15: 16: 17:
tahy ← generuj tahy(pozice) for all tah v kolekci tahy do potomek ← zahraj(pozice, tah) ohodnoceni ← −alfabeta(potomek, hloubka − 1, dal(−beta), dal(−alfa)) ohodnoceni ← bliz(ohodnoceni) if ohodnoceni > alfa then alfa ← ohodnoceni if ohodnoceni � beta then return beta end if
18: 19: 20: 21: 22: 23:
18
Alfa-beta oˇrez´av´an´ı
25: 26:
end if end for return alfa
27:
end function
24:
U aktu´aln´ı pozice (koˇrene hern´ıho stromu) n´as opˇet v´ıce neˇz ohodnocen´ı t´eto pozice zaj´ım´a tah, kter´ y vede k jej´ımu nejl´epe ohodnocen´emu potomkovi, coˇz je pr´avˇe hledan´ y nejlepˇs´ı tah poˇc´ıtaˇcov´eho hr´aˇce z t´eto pozice. V´ ypoˇcet tohoto tahu je realizov´an funkc´ı nej tah, jeˇz je pops´ ana v algoritmu 3.3. Principi´alnˇe se tato funkce shoduje s funkc´ı pro v´ ypoˇcet nejlepˇs´ıho tahu v algoritmu Minimax. Interval oˇcek´avan´ ych ohodnocen´ı je na zaˇc´atku v´ ypoˇctu nastaven na �−MAX, MAX�, na t´eto u ´rovni nedoch´az´ı k ˇz´adn´ ym oˇrez˚ um. Algoritmus 3.3. Pseudok´ od realizuj´ıc´ı v´ypoˇcet nejlepˇs´ıho tahu u koˇrene hern´ıho stromu 1: function nej tah(pozice, hloubka) 2: tahy ← generuj tahy(pozice) 3: alfa ← −MAX 4: for all tah v kolekci tahy do 5: potomek ← zahraj(pozice, tah) 6: ohodnoceni ← −alfabeta(potomek, hloubka − 1, −MAX, dal(−alfa)) 7: ohodnoceni ← bliz(ohodnoceni) 8: if ohodnoceni > alfa then 9: alfa ← ohodnoceni 10: nejlepsi tah ← tah 11: end if 12: end for 13: return nejlepsi tah 14:
end function
ˇ´ıklad 3.2. Uvaˇzujme pozici zn´azornˇenou na obr´azku 17., v n´ıˇz je na tahu b´ıl´ � Pr y hr´aˇc. Nyn´ı se pokusme pomoc´ı algoritmu Alfa-beta oˇrez´av´an´ı s poˇc´ateˇcn´ı hloubkou v´ ypoˇctu nastavenou na 3 tahy vypoˇc´ıtat nejlepˇs´ı tah v t´eto pozici. Interval oˇcek´avan´ ych ohodnocen´ı i nakonec vypoˇc´ıtan´a ohodnocen´ı jednotliv´ ych pozic jsou zn´azornˇena v hern´ım stromu na obr´azku 18. Uzly hern´ıho stromu jsou zde oznaˇceny trojic´ı ˇc´ısel — hodnota vlevo odpov´ıd´a parametru alfa pˇredan´e pˇri rekurzivn´ım vol´an´ı funkce alfabeta pro tuto hern´ı pozici, ˇc´ıslo vpravo pak hodnotˇe parametru beta a ˇc´ıslo uprostˇred ud´av´a vypoˇctenou n´avratovou hodnotu funkce alfabeta. Podobnˇe jako dˇr´ıve budeme i nyn´ı vyhodnocovat jednotliv´e potomky dan´e pozice smˇerem zleva doprava. Vzhledem k tomu, ˇze vypoˇcten´a ohodnocen´ı i intervaly oˇcek´avan´ ych hodnot plnˇe odpov´ıdaj´ı popsan´emu algoritmu, nebudou zde detailnˇe okomentov´ana veˇsker´a vol´an´ı funkce alfabeta, ale pouze nˇekter´e zaj´ımav´e situace. Po prozkoum´an´ı jedin´eho potomka ˇcervenˇe zv´ yraznˇen´e pozice je vr´aceno ohodnocen´ı −85, kter´e po zmˇenˇe znam´enka pˇrekraˇcuje hodnotu beta (70) ve vol´an´ı funkce alfabeta odpov´ıdaj´ıc´ım ˇcervenˇe zv´ yraznˇen´e pozici. Toto zp˚ usob´ı okamˇzit´ y n´avrat z rekurze “do vyˇsˇs´ıho patra hern´ıho stromu”. Protoˇze vˇsak jiˇz byly prozkoum´any vˇsechny moˇzn´e tahy z t´eto pozice, nenast´av´a zde typick´e oˇrez´ an´ı. V zelenˇe zv´ yraznˇen´ ych pozic´ıch prozkoum´av´ame postupnˇe jednotliv´e potomky a z´ısk´av´ame jejich ohodnocen´ı 50 a 60 (resp. −5, 10 a 5), kter´a vˇsak po zmˇenˇe znam´enka nepˇrekraˇcuj´ı ani hodnoty parametr˚ u alfa (v obou pˇr´ıpadech 70) ve vol´an´ıch funkce alfabeta odpov´ıdaj´ıc´ıch tˇemto zelenˇe zv´ yraznˇen´ ym pozic´ım. Z tohoto d˚ uvodu je po prozkoum´an´ı vˇsech potomk˚ u tˇechto pozic vr´ acena hodnota 70 tak´e jako jejich v´ ysledn´e ohodnocen´ı. Po prozkoum´an´ı nejlevˇejˇs´ıho potomka modˇre zv´ yraznˇen´e pozice z´ısk´av´ame jeho ohodnocen´ı 70, coˇz po zmˇenˇe znam´enka dosahuje hodnoty parametru beta vol´an´ı funkce alfabeta, kter´e odpov´ıd´ a modˇre zv´ yraznˇen´e pozici. Toto vede k okamˇzit´emu n´avratu z rekurze “do vyˇsˇs´ıho patra stromu”. Z tohoto d˚ uvodu uˇz nedoch´az´ı k prozkoum´av´an´ı dalˇs´ıch ˇsedˇe vykreslen´ ych potomk˚ u modˇre zv´ yraznˇen´e pozice, coˇz odpov´ıd´a typick´emu oˇrez´an´ı hern´ıho stromu v algoritmu Alfa-beta.
3.2.
19
Implementace algoritmu
Ve vol´an´ı funkce nej tah, kter´a prozkoum´av´a aktu´aln´ı pozici – koˇren zobrazen´eho hern´ıho stromu, m´ame po prozkoum´an´ı vˇsech moˇzn´ ych tah˚ u z t´eto pozice zapamatov´ano maxim´aln´ı ohodnocen´ı 70 a tah, kter´ y jako prvn´ı k tomuto ohodnocen´ı vedl e3-d4. Tento v obr´azku 18. ˇcervenˇe zv´ yraznˇen´ y tah odpov´ıd´a nejlepˇs´ımu tahu vypoˇcten´emu pˇredstavovan´ ym algoritmem. 8 7 6 5 4 3 2 1 a
b
c
d
e
f
g
h
Obr´azek 17. Poˇc´ateˇcn´ı pozice k pˇr´ıkladu 3.2., na tahu je b´ıl´ y hr´aˇc.
Alfa-beta oˇrez´av´an´ı 20
a5-b4
-101 98 100 a3-c5-e7 -101 -99 102
-99 -70 100 d6-c5
d6-e5
70
e3-d4
-101 70
d6-f6
98
d4-b6
-70 -85 102
-101 70
-99 -70 102
a3-b4
e3-f4
-101 60 -70
70 100
a5-c3
-99 -70 -70
70
e3-d4 -101 50 -70
e3-f4
a3-b4
-101 -5
Obr´azek 18. Hern´ı strom z pˇr´ıkladu 3.2.
70
-99 -70 -70
-70
d6-e5
-101 5
f4-g5
a5-b4
-101 10 -70
f4-e5
70 100
d6-c5
-70
Literatura
21
Literatura ˇ a federace d´amy: Ofici´ ˇ e federace d´ [1] Cesk´ aln´ı str´ anky Cesk´ amy, citov´ano 2. 9. 2010. Dostupn´e na adrese http://www.damweb.cz. ˇ [2] Dieter Steinwender, Frederic A. Friedel: Sachy na PC. Unis Publishing, Pˇrerov, 1997. [3] Minimax (algoritmus) – Wikipedie, otevˇren´ a encyklopedie [online], posledn´ı revize 1. 9. 2010 (citov´ano 6. 9. 2010). Dostupn´e na adrese http://cs.wikipedia.org/wiki/Minimax (algoritmus). ˇ [4] Jan Nˇemec: Sachov´ e myˇslen´ı. Linux Software [online], posledn´ı revize 8. 3. 2006 (citov´ano 6. 9. 2010). Dostupn´e na adrese http://www.linuxsoft.cz/article.php?id article=1109. ˇ e [5] Ladislav Vit´asek: Pokroˇcil´ a implementace deskov´e hry D´ ama, bakal´ aˇrsk´ a pr´ ace. Cesk´ vysok´e uˇcen´ı technick´e v Praze, 2006. [6] Alfa-beta oˇrez´ av´ an´ı (ˇcesky, nˇemecky, anglicky) – Wikipedie, otevˇren´ a encyklopedie [online], posledn´ı revize 8. 6. 2011 (citov´ano 27. 10. 2011). Dostupn´e na adrese http://cs.wikipedia.org/wiki/Alfa-beta oˇrez´av´an´ı.
