Algoritmus Minimax Tomáš Kühr
Projektový semináˇr 1
Tomáš Kühr
Algoritmus Minimax
Základní pojmy ˇ figury hráˇce na tahu odpovídající Tah = pˇremístení pravidlum ˚ dané hry. Pˇri tahu muže ˚ být manipulováno i s figurami soupeˇre, ˇ pokud to odpovídá pravidlum ˚ hry (napˇr. odstranení ˇ pˇreskoˇcené figury v dáme). ˇ Tah se muže ˚ skládat z nekolika dílˇcích pohybu, ˚ pokud to ˇ odpovídá pravidlum ˚ hry (napˇr. vícenásobný skok v dáme). ˇ Pozor, v nekteré literatuˇre “náš tah” oznaˇcován jako pultah. ˚
Pozice = stav hry v urˇcitém okamžiku. ˇ jednoznaˇcneˇ urˇcena rozmístením ˇ Pozice je vesmes figur na desce a urˇcením hráˇce na tahu. Obˇcas používáme i pojmy vyhrávající pozice, prohrávající pozice, remízová pozice, koncová pozice ˇ ˇ pozice. a pocáte cní
Tomáš Kühr
Algoritmus Minimax
Herní strom Pro zobrazení “všech” možností, jak se muže ˚ hra z dané pozice vyvíjet, používáme tzv. herní strom. ˇ ani poˇcítaˇce zobrazit cˇ i vzít Bohužel není v silách cˇ loveka ˇ eˇ do úvahy celý herní strom. Herní strom tedy bežn zobrazujeme pouze do urˇcité pˇredem dané hloubky (poˇcet zkoumaných po sobeˇ následujících tahu). ˚ Listy herního stromu nemusí být vždy ve stejné hloubce. ˇ ˇ nastal konec Tato situace nastane, pokud v nekteré vetvi hry. P0 d2-c3
d2-e3
P1 c5-b4 P3 c3-a5 P7
P2 c5-d4 P4
c5-d4 P5
c5-b4 P6
c3-e5 P8
Tomáš Kühr
Algoritmus Minimax
Pˇríklad herního stromu
P0
P0 d2-c3
d2-e3
P3 c3-a5 P7
P3 P2
c5-d4 P4
c5-d4 P5
c5-b4 P6
7
6
6
5
5
5
4
4
4
3
3
3
2
2
1
1 b
c
d
e
f
g
P8
P4
1 b
c
d
e
f
g
h
P5
8 7
7
6
6
6
5
5
5
4
4
4
3
3
2
2
b
d
e
f
g
P7
8
d
e
f
g
h
P8
8
7
6
6
6
5
5
5
4
4
4
3
3
2
2
d
e
f
g
h
Algoritmus Minimax
f
g
h
a
b
c
d
e
f
g
h
a
b
c
d
e
f
g
h
3 2
1 c
e
8
7
b
d
1 b
c
7
a
c
2
a
h
b
3
1 c
a
8
7
1
Tomáš Kühr
2
a
h
8
a
P6
8
7
6
1
c3-e5
P2
8
7
a
P1 c5-b4
P1
8
1 a
b
c
d
e
f
g
h
Princip algoritmu Minimax Algoritmus Minimax urˇcuje nejlepší tah na základeˇ prozkoumání herního stromu vycházejícího z aktuální pozice do pˇredem dané hloubky. Minimax nejprve ohodnotí listové pozice pomocí heuristické ohodnocovací funkce. Ohodnocení pozic blíže ke koˇreni herního stromu se pak urˇcí jako maximum z ohodnocení jeho následovníku, ˚ pokud je v dané pozici na tahu aktuální hráˇc nebo jako minimum z ohodnocení následovníku, ˚ pokud je v dané pozici na tahu soupeˇr.
U koˇrenové pozice nás pak nezajímá její ohodnocení, ale tah vedoucí k nejlépe ohodnocenému následovníkovi. Tomáš Kühr
Algoritmus Minimax
Ilustrace principu Minimaxu
95 d8-e7
d8-c7
8
95 e5-d6
7
-12 e5-f6
e5-d6
6
e5-f6
5
98 e7-c5 98
95 e7-g5 95
99
-12 c7-b6
c7-e5 99
4
c7-d6
-15
3 2
-12
f6-e7
f6-g7
f6-e7
f6-g7
-15
-10
-12
-9
1 a
Tomáš Kühr
Algoritmus Minimax
b
c
d
e
f
g
h
Implementace algoritmu Minimax Algoritmus je realizován rekurzivní funkcí, která “prochází” herní strom do urˇcité hloubky. Vstupem funkce je herní pozice a hloubka, do které se má herní strom dále prozkoumávat. Výstupem funkce je vypoˇctené ohodnocení dané pozice. Rozhodování z pohledu obou hráˇcu˚ je realizováno totožným kódem. Využíváme zde toho, že ohodnocení dané pozice z pohledu prvního a druhého hráˇce se liší ˇ pouze znaménkem. Dále je nutné si uvedomit, že platí min(a, b) = −max(−a, −b). Mezní podmínkou rekurze je dosažení požadované hloubky nebo koncové pozice. Tomáš Kühr
Algoritmus Minimax
Zjednodušený pseudokód
function minimax(pozice, hloubka) if (pozice je koncová or hloubka = 0) then return heuristické ohodnocení pozice else ohod ← −∞ for all potomek pozice do ohod ← max(ohod, −minimax(potomek, hloubka − 1)) end for return ohod end if end function
Tomáš Kühr
Algoritmus Minimax
Detailní pseudokód (ošetˇrení výhry/prohry)
function minimax(pozice, hloubka) if je_prohra(pozice) then return −MAX end if if je_výhra(pozice) then return MAX end if if je_remíza(pozice) then return 0 end if ...
Tomáš Kühr
Algoritmus Minimax
Detailní pseudokód (hlavní cˇ ást) ... if hloubka = 0 then return ohodnocovaci_funkce(pozice) else tahy ← generuj_tahy(pozice) ohod ← −MAX for all tah v kolekci tahy do potomek ← zahraj(pozice, tah) ohod ← max(ohod, −minimax(potomek, hloubka − 1)) end for ... return ohod end if end function Tomáš Kühr
Algoritmus Minimax
Detailní pseudokód (pozice blízké konci hry)
... if ohod > MNOHO then ohod ← ohod − 1 end if if ohod < −MNOHO then ohod ← ohod + 1 end if ...
Tomáš Kühr
Algoritmus Minimax
Nalezení nejlepšího tahu function nej_tah(pozice, hloubka) tahy ← generuj_tahy(pozice) nejlepsi_ohodnoceni ← −MAX 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 return nejlepsi_tah end function Tomáš Kühr
Algoritmus Minimax
Pˇríklad Pˇri ohodnocování následujícího herního stromu byl použit algoritmus Minimax s hloubkou výpoˇctu 4 a konstantami ˇ ˇ uzly, které MAX = 99 a MNOHO = 90. Cerven eˇ jsou zvýrazneny byly ohodnoceny heuristicky, a hrana, které odpovídá vypoˇctenému nejlepšímu tahu. d8-e7
d8-c7
-97 e5-d6 98 e7-c5 -99
12 e5-f6
e5-d6
98 e7-g5
e5-f6
98
-12 c7-b6
c7-e5
-99
-99
Tomáš Kühr
c7-d6
15
12
f6-e7
f6-g7
f6-e7
f6-g7
-15
-10
-12
-9
Algoritmus Minimax
Generátor tahu˚ V algoritmu Minimax je potˇreba pro danou herní situaci vytvoˇrit kolekci všech legálních tahu, ˚ které se dají v této pozici zahrát. Tyto tahy jsou pak ve vzájemneˇ jednoznaˇcném vztahu s následovníky dané pozice v herním stromu. Pˇri vytváˇrení kolekce bývá dobré postupovat systematicky ˇ – procházet hrací desku, pˇrípadneˇ nejakou pomocnou kolekci figur a pro každou figuru vygenerovat všechny možné tahy. Algoritmus pro generování tahu˚ je rozumné pˇrizpusobit ˚ pravidlum ˚ dané hry.
Tomáš Kühr
Algoritmus Minimax
Ohodnocovací funkce Vstupem ohodnocovací funkce je ohodnocovaná pozice. Výstupem je celé cˇ íslo v intervalu h−MNOHO, MNOHOi. Ohodnocovací funkci je rozumné vytvoˇrit z pohledu jednoho hráˇce, ohodnocení z pohledu druhého hráˇce pak ˇ získáme zmenou znaménka. Zcela vyrovnaná pozice má tedy ohodnocení rovno nule. Co lze hodnotit? materiální složka (napˇr. rozdíl v poˇctu figur hráˇcu) ˚ ˇ figur statická poziˇcní složka (bonusy a postihy za umístení ˇ na nekterá pole) ˇ figury, . . . ) dynamická poziˇcní složka (bloky figur, osamelé
ˇ být rychlá a jednoduchá. Ohodnocovací funkce by mela ˇ ohodnocení lze „donutit“ poˇcítaˇcového hráˇce Pomocí zmen ˇ agresivite, ˇ aktivite, ˇ ochoteˇ delat ˇ výmeny ˇ a podobne. ˇ k vetší Lze také vytvoˇrit více ohod. funkcí pro ruzné ˚ fáze hry. Tomáš Kühr
Algoritmus Minimax
Princip Alfa-beta oˇrezávání ˇ V nekterých situacích nemusí Minimax zkoumat další herní pozice, protože je již zˇrejmé, že nebudou mít na volbu tahu vliv. Typy oˇrezávání: alfa oˇrezávání – byla nalezena pˇríliš malá hodnota, tuto ˇ vetev hráˇc na tahu nezvolí, beta oˇrezávání – nalezená hodnota je pˇríliš velká, soupeˇr ˇ tuto vetev nezvolí.
V algoritmu použité hodnoty alfa tedy tvoˇrí dolní mez, hodnoty beta pak horní mez pˇri vyhledávání. ˇ z ohodnocení Hodnoty alfa a beta se získají a upˇresnují dˇríve prozkoumaných pozic. ˇ Alfa-beta oˇrezávání je nejúˇcinnejší, pokud se nejprve ˇ tahy. Nekdy ˇ zkoumají nejsilnejší se používá heuristika pro seˇrazení tahu˚ pˇred zkoumáním následovníku˚ dané pozice. Tomáš Kühr
Algoritmus Minimax
Pˇríklad
ˇ Pˇrevzato z Alpha-Beta-Suche (nemecky) – Wikipedie, otevˇrená encyklopedie. Tomáš Kühr
Algoritmus Minimax
Pomocné funkce pro algoritmus Alfa-beta
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
Tomáš Kühr
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
Algoritmus Minimax
Funkce Alfa-beta (ˇcást 1) function alfabeta(pozice, hloubka, alfa, beta) if je_prohra(pozice) then return −MAX end if if je_výhra(pozice) then return MAX end if if je_remíza(pozice) then return 0 end if if hloubka = 0 then return ohodnocovaci_funkce(pozice) end if Tomáš Kühr
Algoritmus Minimax
Funkce Alfa-beta (ˇcást 2) tahy ← generuj_tahy(pozice) for all tah v kolekci tahy do pot ← zahraj(pozice, tah) ohod ← −alfabeta(pot, hloubka − 1, dal(−beta), dal(−alfa)) ohod ← bliz(ohod) if ohod > alfa then alfa ← ohod if ohod = beta then return beta end if end if end for return alfa end function Tomáš Kühr
Algoritmus Minimax
ˇ nejlepšího tahu Zjištení function nej_tah(pozice, hloubka) tahy ← generuj_tahy(pozice) alfa ← −MAX for all tah v kolekci tahy do pot ← zahraj(pozice, tah) ohod ← −alfabeta(pot, hloubka − 1, −MAX, dal(−alfa)) ohod ← bliz(ohod) if ohod > alfa then alfa ← ohod nejlepsi_tah ← tah end if end for return nejlepsi_tah end function Tomáš Kühr
Algoritmus Minimax
Pˇríklad
Pˇrevzato z Alpha-beta pruning (anglicky) – Wikipedie, otevˇrená encyklopedie.
Tomáš Kühr
Algoritmus Minimax
Pˇríklad
Pˇrevzato z knihy Šachy na PC.
Tomáš Kühr
Algoritmus Minimax
Literatura Dieter Steinwender, Frederic A. Friedel: Šachy na PC. Unis Publishing, Pˇrerov, 1997. Minimax (algoritmus) – Wikipedie, otevˇrená encyklopedie [online], poslední revize 1. 9. 2010 (citováno 6. 9. 2010). Dostupné na adrese http://cs.wikipedia.org/wiki/Minimax_(algoritmus). ˇ Alpha-beta pruning (anglicky, nemecky, cˇ esky) – Wikipedie, otevˇrená encyklopedie [online], citováno 19. 10. 2010. Dostupné na adrese http://en.wikipedia.org/wiki/Alpha-beta_pruning. ˇ Jan Nemec: Šachové myšlení. Linux Software [online], poslední revize 8. 3. 2006 (citováno 6. 9. 2010). Dostupné na adrese http://www.linuxsoft.cz/article.php?id_article=1109. Tomáš Kühr
Algoritmus Minimax
