´
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 <[email protected]>. 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´
Copyright aˇs K¨
uhr, 2011
Obsah
1. Pr˚
ubˇ
eh hry a jeho
1.1. Z´
akladn´ı pojmy
ˇ a d´
1.2. Cesk´
ama . .
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´
Pozice z hry Cesk´
ama, ˇcern´
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´
Pozice ze hry Cesk´
ama, na tahu je ˇcern´
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´
Cesk´
ama je jednou z mnoha variant svˇetozn´am´e hry D´ama. Jak jiˇz bylo v u
´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
ˇ a
ˇ e federace d´
Cesk´
amy [1], kde je tak´e moˇzn´e snadno dohledat kompletn´ı verzi pravidel hry 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´
. Pr
azku 2. je b´ıl´
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.
Hern´ı strom
3
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´
. Pr
azku 4. je zobrazena ˇc´ast hern´ıho stromu hry Cesk´
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
8
1
a
h
P4
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.
ˇ
R´
adek 7 si ovˇsem zaslouˇz´ı podrobnˇejˇs´ı vysvˇetlen´ı. Pozorn´
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.
Implementace algoritmu
7
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´
y zjednoduˇsenou verz´ı re. Pr
azku 8. je zn´azornˇen hern´ı strom ohodnocen´
ˇ
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´
ym zp˚
usobem, aby algoritR´
mus 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.
Implementace algoritmu
9
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´ı ˇz´
adn´
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´
. Pr
azku 9. je uk´az´ano ohodnocen´ı hern´ıho stromu odpov´ıdaj´ıc´ımu hern´ı
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´
ve hˇre Cesk´
ama, abyste poznali, ˇze Minimax nezvolil pr´avˇe nejlepˇs´ı tah. Nejvˇetˇs´ı slabinou Minimaxu, 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
yˇse, jedn´a se o funkci, jej´ımˇz vstupn´ım
byla pouˇzita v k´
odu algoritmu 2.2. Jak jiˇz bylo naznaˇceno v´
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 h−MNOHO, MNOHOi; 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
yt splnˇeno, ˇze ohodnocen´ı jedn´e
(viz popis algoritmu 2.2. v kapitole 2.2.). Vˇzdy by tak´e mˇelo b´
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.
Ohodnocovac´ı funkce
11
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
7
+2
6
5
+2
+2
+2
+2
1
+3
a
c
+2
8
7
+3
b
+3
d
e
+2
+3
f
g
+2
5
3
1
+2
+2
+2
+2
+3
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
+2
a
-2
8
5
+3
-2
a
7
2
-2
1
+2
4
-3
2
h
+2
6
-3
4
3
2
-3
6
5
4
3
-3
8
+2
-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´
U hry Cesk´
ama (a mnoh´
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
nme, ˇze ˇslo o ohodnoohodnocov´
an´ı hern´ıho stromu, kter´e bylo pouˇzito v kapitole 2.1. Pˇripomeˇ
cov´
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 hα, βi 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 h−MAX, −MNOHO) a (MNOHO, MAXi. 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´ı
hα, βi mˇen´ı na h−β, −αi. 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 h−MAX, MAXi, 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.
Implementace algoritmu
19
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´
ˇ e federace d´
[1] Cesk´
amy: Ofici´
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´ı.
Download

Algoritmy realizující počítačového hráče v jednoduchých deskových