Hry a z´akladn´ı hern´ı strategie Aleˇs Hor´ak E-mail:
[email protected] http://nlp.fi.muni.cz/uui/
Obsah: Statistick´e v´ysledky pr˚ ubˇeˇzn´e p´ısemky Hry vs. Prohled´av´an´ı stavov´eho prostoru Algoritmus Minimax Algoritmus Alfa-Beta proˇrez´av´an´ı Nedeterministick´e hry Hry s nepˇresn´ymi znalostmi ´ Uvod do umˇ el´ e inteligence 7/12
1 / 29
Statistick´ e v´ ysledky pr˚ ubˇ eˇzn´ e p´ısemky
Statistick´e v´ysledky pr˚ ubˇeˇzn´e p´ısemky pr˚ ubˇeˇzn´a p´ısemka PB016 49 student˚ u Body 32 24 21 16 13 10 8 5 2 0
Poˇcet student˚ u 4 3 9 2 7 10 2 4 2 6
Pr˚ umˇer: 13.31
´ Uvod do umˇ el´ e inteligence 7/12
2 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hry × Prohled´av´an´ı stavov´eho prostoru Multiagentn´ı prostˇred´ı: agent mus´ı br´at v u ´vahu akce jin´ych agent˚ u → jak ovlivn´ı jeho vlastn´ı prospˇech vliv ostatn´ıch agent˚ u – prvek n´ahody kooperativn´ı × soupeˇr´ıc´ı multiagentn´ı prostˇred´ı (MP) Hry: matematick´a teorie her (odvˇetv´ı ekonomie) – kooperativn´ı i soupeˇr´ıc´ı MP, kde vliv vˇsech agent˚ u je v´yznamn´y hra v UI = obv. deterministick´e MP, 2 stˇr´ıdaj´ıc´ı se agenti, v´ysledek hry je vz´ajemnˇe opaˇcn´y nebo shoda Algoritmy soupeˇr´ıc´ıho prohled´av´an´ı (adversarial search): oponent dˇel´a dopˇredu neurˇciteln´e tahy → ˇreˇsen´ım je strategie, kter´a poˇc´ıt´a se vˇsemi moˇzn´ymi tahy protivn´ıka ˇcasov´y limit ⇒ zˇrejmˇe nenajdeme optim´aln´ı ˇreˇsen´ı → hled´ame lok´alnˇe optim´aln´ı ˇreˇsen´ı ´ Uvod do umˇ el´ e inteligence 7/12
3 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hry a UI – historie
Hry a UI – historie
Babbage, 1846 – poˇc´ıtaˇc porovn´av´a pˇr´ınos r˚ uzn´ych hern´ıch tah˚ u von Neumann, 1944 – algoritmy perfektn´ı hry Zuse, Wiener, Shannon, 1945–50 – pˇribliˇzn´e vyhodnocov´an´ı Turing, 1951 – prvn´ı ˇsachov´y program (jen na pap´ıˇre) Samuel, 1952–57 – strojov´e uˇcen´ı pro zpˇresnˇen´ı vyhodnocov´an´ı McCarthy, 1956 – proˇrez´av´an´ı pro moˇznost hlubˇs´ıho prohled´av´an´ı
´ Uvod do umˇ el´ e inteligence 7/12
4 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hry a UI – historie
Hry a UI – historie
Babbage, 1846 – poˇc´ıtaˇc porovn´av´a pˇr´ınos r˚ uzn´ych hern´ıch tah˚ u von Neumann, 1944 – algoritmy perfektn´ı hry Zuse, Wiener, Shannon, 1945–50 – pˇribliˇzn´e vyhodnocov´an´ı Turing, 1951 – prvn´ı ˇsachov´y program (jen na pap´ıˇre) Samuel, 1952–57 – strojov´e uˇcen´ı pro zpˇresnˇen´ı vyhodnocov´an´ı McCarthy, 1956 – proˇrez´av´an´ı pro moˇznost hlubˇs´ıho prohled´av´an´ı ˇreˇsen´ı her je zaj´ımav´ym pˇredmˇetem studia ← je obt´ıˇzn´e: pr˚ umˇern´y faktor vˇetven´ı v ˇsach´ach b = 35 pro 50 tah˚ u 2 hr´aˇc˚ u ... prohled´avac´ı strom ≈ 35100 ≈ 10154 uzl˚ u (≈ 1040 stav˚ u) ´ Uvod do umˇ el´ e inteligence 7/12
4 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hry a UI – aktu´ aln´ı v´ ysledky
Hry a UI – aktu´aln´ı v´ysledky Reversi/Othello – od 1980 svˇetov´ı ˇsampioni odm´ıtaj´ı hr´at s poˇc´ıtaˇci, protoˇze stroje jsou pˇr´ıliˇs dobr´e. Reversi pro dva hr´aˇce na desce 8×8 – snaˇz´ı se mezi sv´e dva kameny uzavˇr´ıt soupeˇrovy v ˇradˇe, kter´a se pˇrebarv´ı. Aˇz se zapln´ı deska, spoˇc´ıtaj´ı se kameny.
d´ama – 1994 program Chinook porazil svˇetovou ˇsampionku Marion Tinsley. Pouˇz´ıv´a u ´plnou datab´azi tah˚ u pro ≤ 8 figur (443 748 401 247 pozic).
´ Uvod do umˇ el´ e inteligence 7/12
5 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hry a UI – aktu´ aln´ı v´ ysledky
Hry a UI – aktu´aln´ı v´ysledky
ˇsachy – 1997 porazil stroj Deep Blue svˇetov´eho ˇsampiona Gary Kasparova 31/2 : 21/2. Stroj poˇc´ıt´a 200 mil. pozic/s, sofistikovan´e vyhodnocov´an´ı a nezveˇrejnˇen´e metody pro prozkoum´av´an´ı nˇekter´ych tah˚ u aˇz do hloubky 40 tah˚ u. 2006 porazil program Deep Fritz na PC svˇetov´eho ˇsampiona Vladim´ıra Kramnika 2:4. V souˇcasnosti vyhr´avaj´ı turnaje i programy na slabˇs´ım hardware mobiln´ıch telefon˚ u s 20 tis. pozic/s.
´ Uvod do umˇ el´ e inteligence 7/12
6 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hry a UI – aktu´ aln´ı v´ ysledky
Hry a UI – aktu´aln´ı v´ysledky Arimaa – hra na ˇsachovnici se standardn´ıma figurama, speci´alnˇe navrˇzen´a v roce 2003 tak, aby vyˇzadovala lidskou inteligenci (variabiln´ı ˇ ek pˇrekon´an poˇcet tah˚ u, figury se tlaˇc´ı nebo t´ahnou, pasti...). Clovˇ poˇc´ıtaˇcem 18. dubna 2015 3 : 0 (v r´amci kaˇzdoroˇcn´ı Arimaa Challenge).
´ Uvod do umˇ el´ e inteligence 7/12
7 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hry a UI – aktu´ aln´ı v´ ysledky
Hry a UI – aktu´aln´ı v´ysledky Go – do roku 2008 svˇetov´ı ˇsampioni odm´ıtali hr´at s poˇc´ıtaˇci, protoˇze stroje jsou pˇr´ıliˇs slab´e. V Go je b > 300, takˇze poˇc´ıtaˇce mohly pouˇz´ıvat t´emˇeˇr pouze znalostn´ı b´azi vzorov´ych her. od 2009 – prvn´ı programy dosahuj´ı pokroˇcilejˇs´ı amat´ersk´e u ´rovnˇe (zejm´ena na desce 9 × 9, niˇzˇs´ı u ´roveˇ n i na 19 × 19). bˇrezen 2016 – program AlphaGo porazil lidsk´eho velmistra Lee Sedola na norm´aln´ı desce 19 × 19 4 : 1. AlphaGo vyuˇz´ıv´a uˇc´ıc´ı se hodnot´ıc´ı funkce zaloˇzen´e na hlubok´ych neuronov´ych s´ıt´ıch. ´ Uvod do umˇ el´ e inteligence 7/12
8 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Typy her
Typy her
perfektn´ı znalosti
deterministick´e
s n´ahodou
ˇsachy, d´ama, Go, Othello
backgammon, monopoly bridge, poker, scrabble
nepˇresn´e znalosti
´ Uvod do umˇ el´ e inteligence 7/12
9 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hled´ an´ı optim´ aln´ıho tahu
Hled´an´ı optim´aln´ıho tahu
2 hr´aˇci – MAX ( ) a MIN ( ) MAX je prvn´ı na tahu a pak se stˇr´ıdaj´ı aˇz do konce hry hra = prohled´avac´ı probl´em: poˇc´ateˇcn´ı stav – poˇc´ateˇcn´ı hern´ı situace + kdo je na tahu pˇrechodov´a funkce – vrac´ı dvojice (leg´aln´ı tah, v´ysledn´y stav) ukonˇcovac´ı podm´ınka – urˇcuje, kdy hra konˇc´ı, oznaˇcuje koncov´e stavy utilit´arn´ı funkce – numerick´e ohodnocen´ı koncov´ych stav˚ u
´ Uvod do umˇ el´ e inteligence 7/12
10 / 29
Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
Hled´ an´ı optim´ aln´ıho tahu
Hled´an´ı optim´aln´ıho tahu – pokraˇc. poˇc´ateˇcn´ı stav a pˇrechodov´a funkce definuj´ı hern´ı strom: MAX (X)
X
X
X
MIN (O)
X
X
X X
X O
X
O
X O X
X O X
MAX (X)
MIN (O)
X O
...
X O X
...
...
...
...
...
X O X O X O
X O X O O X X X O
X O X X X O O
...
koncové stavy utilitární funkce
−1
0
+1
´ Uvod do umˇ el´ e inteligence 7/12
11 / 29
X
X
Algoritmus Minimax
Algoritmus Minimax
Hr´aˇc MAX ( ) mus´ı prohledat hern´ı strom pro zjiˇstˇen´ı nejlepˇs´ıho tahu proti hr´aˇci MIN ( ) → zjistit nejlepˇs´ı hodnotu minimax – zajiˇst’uje nejlepˇs´ı v´ysledek proti nejlepˇs´ımu protivn´ıkovi
Hodnota minimax(n) =
utility(n), pro koncov´y stav n maxs∈moves(n) Hodnota minimax(s), pro MAX uzel n min s∈ moves(n) Hodnota minimax(s), pro MIN uzel n
´ Uvod do umˇ el´ e inteligence 7/12
12 / 29
Algoritmus Minimax
Algoritmus Minimax – pokraˇc. pˇr´ıklad – hra jen na jedno kolo = 2 tahy (p˚ ulkola)
´ Uvod do umˇ el´ e inteligence 7/12
13 / 29
Algoritmus Minimax
Algoritmus Minimax – pokraˇc. pˇr´ıklad – hra jen na jedno kolo = 2 tahy (p˚ ulkola) MAX a1
a2
a3
MIN b1
b2
c1
b3
c2
c3
d1
d3
d2
MAX
util.funkce
3
12
8
´ Uvod do umˇ el´ e inteligence 7/12
2
4
13 / 29
6
14
5
2
Algoritmus Minimax
Algoritmus Minimax – pokraˇc. pˇr´ıklad – hra jen na jedno kolo = 2 tahy (p˚ ulkola) MAX a1 MIN
a2
a3
3 b1
b2
2 c1
b3
c2
2 c3
d1
d3
d2
MAX
util.funkce
3
12
8
´ Uvod do umˇ el´ e inteligence 7/12
4
2
13 / 29
6
14
5
2
Algoritmus Minimax
Algoritmus Minimax – pokraˇc. pˇr´ıklad – hra jen na jedno kolo = 2 tahy (p˚ ulkola) MAX
3 a1
MIN
a2
a3 2
3 b1
b2
c1
b3
c2
2 c3
d1
d3
d2
MAX
util.funkce
3
12
8
´ Uvod do umˇ el´ e inteligence 7/12
2
4
13 / 29
6
14
5
2
Algoritmus Minimax
Algoritmus Minimax – pokraˇc. pˇr´ıklad – hra jen na jedno kolo = 2 tahy (p˚ ulkola) MAX
3 a1
MIN
a2
a3 2
3 b1
b2
c1
b3
c2
2 c3
d1
d3
d2
MAX
util.funkce
3
12
8
´ Uvod do umˇ el´ e inteligence 7/12
2
4
13 / 29
6
14
5
2
Algoritmus Minimax
Algoritmus Minimax – pokraˇc. % minimax( +Pos, −BestSucc, −Val): % Pos je rozloˇzen´ı figur, Val je minimaxov´ a hodnota tohoto rozloˇzen´ı; % nejlepˇs´ı tah z Pos vede do rozloˇzen´ı BestSucc minimax( Pos, BestSucc, Val) :moves( Pos, PosList), !, % PosList je seznam leg´ aln´ıch tah˚ u z Pos best( PosList, BestSucc, Val) ; staticval( Pos, Val). % Pos nem´ a n´ asledn´ıky: ohodnot´ıme staticky best( [Pos], Pos, Val) :- minimax( Pos, , Val), !. best( [Pos1 | PosList], BestPos, BestVal) :minimax( Pos1, , Val1), best( PosList, Pos2, Val2), betterof( Pos1, Val1, Pos2, Val2, BestPos, BestVal). betterof( Pos0, Val0, Pos1, Val1, Pos0, Val0) :- % Pos0 je lepˇs´ı neˇz Pos1 min to move( Pos0), % MIN na tahu v Pos0 Val0 > Val1, ! % MAX chce nejvyˇsˇs´ı hodnotu ; max to move( Pos0), % MAX na tahu v Pos0 Val0 < Val1, !. % MIN chce nejmenˇs´ı hodnotu betterof( Pos0, Val0, Pos1, Val1, Pos1, Val1). % jinak je Pos1 lepˇs´ı neˇz Pos0 ´ Uvod do umˇ el´ e inteligence 7/12
14 / 29
Algoritmus Minimax
Algoritmus Minimax – vlastnosti
u ´plnost optim´alnost ˇcasov´a sloˇzitost prostorov´a sloˇzitost
´ Uvod do umˇ el´ e inteligence 7/12
15 / 29
Algoritmus Minimax
Algoritmus Minimax – vlastnosti
u ´plnost optim´alnost ˇcasov´a sloˇzitost prostorov´a sloˇzitost
u ´pln´y pouze pro koneˇcn´e stromy
´ Uvod do umˇ el´ e inteligence 7/12
15 / 29
Algoritmus Minimax
Algoritmus Minimax – vlastnosti
u ´plnost optim´alnost ˇcasov´a sloˇzitost prostorov´a sloˇzitost
u ´pln´y pouze pro koneˇcn´e stromy je optim´aln´ı proti optim´aln´ımu oponentovi
´ Uvod do umˇ el´ e inteligence 7/12
15 / 29
Algoritmus Minimax
Algoritmus Minimax – vlastnosti
u ´plnost optim´alnost ˇcasov´a sloˇzitost prostorov´a sloˇzitost
u ´pln´y pouze pro koneˇcn´e stromy je optim´aln´ı proti optim´aln´ımu oponentovi O(b m )
´ Uvod do umˇ el´ e inteligence 7/12
15 / 29
Algoritmus Minimax
Algoritmus Minimax – vlastnosti
u ´plnost optim´alnost ˇcasov´a sloˇzitost prostorov´a sloˇzitost
u ´pln´y pouze pro koneˇcn´e stromy je optim´aln´ı proti optim´aln´ımu oponentovi O(b m ) O(bm), prohled´av´an´ı do hloubky
´ Uvod do umˇ el´ e inteligence 7/12
15 / 29
Algoritmus Minimax
Algoritmus Minimax – vlastnosti
u ´plnost optim´alnost ˇcasov´a sloˇzitost prostorov´a sloˇzitost
u ´pln´y pouze pro koneˇcn´e stromy je optim´aln´ı proti optim´aln´ımu oponentovi O(b m ) O(bm), prohled´av´an´ı do hloubky
ˇsachy . . . b ≈ 35, m ≈ 100 ⇒ pˇresn´e ˇreˇsen´ı nen´ı moˇzn´e napˇr. b m = 106 , b = 35 ⇒ m ≈ 4 4-tahy ≈ ˇclovˇek-nov´aˇcek 8-tah˚ u ≈ ˇclovˇek-mistr, typick´e PC 12-tah˚ u ≈ Deep Blue, Kasparov
´ Uvod do umˇ el´ e inteligence 7/12
15 / 29
Algoritmus Minimax
ˇ Casov´ e omezen´ı
ˇ Casov´ e omezen´ı
pˇredpokl´adejme, ˇze m´ame 100 sekund + prozkoum´ame 104 uzl˚ u/s ⇒ 106 uzl˚ u na 1 tah ˇreˇsen´ı minimax cutoff: ohodnocovac´ı funkce odhad pˇr´ınosu pozice nahrad´ı utilit´arn´ı funkci oˇrez´avac´ı test (cutoff test) – napˇr. hloubka nebo hodnota ohodnocovac´ı funkce nahrad´ı koncov´y test
´ Uvod do umˇ el´ e inteligence 7/12
16 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minimax Alfa-Beta odˇr´ızne expanzi nˇekter´y uzl˚ u ⇒ Alfa-Beta procedura je efektivnˇejˇs´ı variantou minimaxu MAX
MIN
MAX
MIN
´ Uvod do umˇ el´ e inteligence 7/12
17 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minimax Alfa-Beta odˇr´ızne expanzi nˇekter´y uzl˚ u ⇒ Alfa-Beta procedura je efektivnˇejˇs´ı variantou minimaxu MAX
MIN
≤4
MAX
MIN
4
1
4
´ Uvod do umˇ el´ e inteligence 7/12
17 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minimax Alfa-Beta odˇr´ızne expanzi nˇekter´y uzl˚ u ⇒ Alfa-Beta procedura je efektivnˇejˇs´ı variantou minimaxu MAX
MIN
≤4
MAX
MIN
4
1
≥5
4
5
´ Uvod do umˇ el´ e inteligence 7/12
17 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minimax Alfa-Beta odˇr´ızne expanzi nˇekter´y uzl˚ u ⇒ Alfa-Beta procedura je efektivnˇejˇs´ı variantou minimaxu MAX
MIN
4
MAX
MIN
4
1
≥5
4
5
´ Uvod do umˇ el´ e inteligence 7/12
17 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minimax Alfa-Beta odˇr´ızne expanzi nˇekter´y uzl˚ u ⇒ Alfa-Beta procedura je efektivnˇejˇs´ı variantou minimaxu MAX
≥4
MIN
4
MAX
MIN
4
1
≥5
4
5
´ Uvod do umˇ el´ e inteligence 7/12
17 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minimax Alfa-Beta odˇr´ızne expanzi nˇekter´y uzl˚ u ⇒ Alfa-Beta procedura je efektivnˇejˇs´ı variantou minimaxu MAX
≥4
MIN
4
MAX
MIN
≤2
4
1
≥5
4
2
5
´ Uvod do umˇ el´ e inteligence 7/12
2
17 / 29
1
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minimax Alfa-Beta odˇr´ızne expanzi nˇekter´y uzl˚ u ⇒ Alfa-Beta procedura je efektivnˇejˇs´ı variantou minimaxu MAX
4
MIN
4
MAX
MIN
≤2
4
1
≥5
4
2
5
´ Uvod do umˇ el´ e inteligence 7/12
2
17 / 29
1
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı – vlastnosti proˇrez´av´an´ı neovlivn´ı v´ysledek ⇒ je stejn´y jako u minimaxu dobr´e uspoˇr´ad´an´ı pˇrechod˚ u (moˇzn´ych tah˚ u) ovlivn´ı efektivitu proˇrez´av´an´ı v pˇr´ıpadˇe “nejlepˇs´ıho” uspoˇr´ad´an´ı ˇcasov´a sloˇzitost= O(b m/2 ) ⇒ zdvoj´ı hloubku prohled´av´an´ı ⇒ m˚ uˇze snadno dos´ahnout hloubky 8 v ˇsachu, coˇz uˇz je pouˇziteln´a u ´roveˇ n
´ Uvod do umˇ el´ e inteligence 7/12
18 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı – vlastnosti proˇrez´av´an´ı neovlivn´ı v´ysledek ⇒ je stejn´y jako u minimaxu dobr´e uspoˇr´ad´an´ı pˇrechod˚ u (moˇzn´ych tah˚ u) ovlivn´ı efektivitu proˇrez´av´an´ı v pˇr´ıpadˇe “nejlepˇs´ıho” uspoˇr´ad´an´ı ˇcasov´a sloˇzitost= O(b m/2 ) ⇒ zdvoj´ı hloubku prohled´av´an´ı ⇒ m˚ uˇze snadno dos´ahnout hloubky 8 v ˇsachu, coˇz uˇz je pouˇziteln´a u ´roveˇ n oznaˇcen´ı α − β: α . . . doposud nejlepˇs´ı hodnota pro MAXe β . . . doposud nejlepˇs´ı hodnota pro MINa <α, β> . . . interval ohodnocovac´ı funkce v pr˚ ubˇehu v´ypoˇctu (na zaˇc´atku <−∞, ∞>) minimax . . . V (P) kdyˇz V (P) ≤ α kdyˇz α < V (P) < β kdyˇz V (P) ≥ β
α − β . . . V (P, α, β) V (P, α, β) = α V (P, α, β) = V (P) V (P, α, β) = β
´ Uvod do umˇ el´ e inteligence 7/12
18 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı alphabeta( Pos, Alpha, Beta, GoodPos, Val) :- moves( Pos, PosList), !, boundedbest( PosList, Alpha, Beta, GoodPos, Val) ; staticval( Pos, Val). % statick´ e ohodnocen´ı Pos boundedbest( [Pos | PosList], Alpha, Beta, GoodPos, GoodVal) :alphabeta( Pos, Alpha, Beta, , Val), goodenough( PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal). goodenough( [], , , Pos, Val, Pos, Val) :- !. % nejsou dalˇs´ı kandid´ ati goodenough( , Alpha, Beta, Pos, Val, Pos, Val) :min to move( Pos), Val > Beta, ! % MAX dos´ ahl horn´ı hranici ; max to move( Pos), Val < Alpha, !. % MIN dos´ ahl doln´ı hranici goodenough( PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal) :newbounds( Alpha, Beta, Pos, Val, NewAlpha, NewBeta), % uprav hranice boundedbest( PosList, NewAlpha, NewBeta, Pos1, Val1), betterof( Pos, Val, Pos1, Val1, GoodPos, GoodVal). newbounds( Alpha, Beta, Pos, Val, Val, Beta) :min to move( Pos), Val > Alpha, !. % newbounds( Alpha, Beta, Pos, Val, Alpha, Val) :max to move( Pos), Val < Beta, !. % newbounds( Alpha, Beta, , , Alpha, Beta). %
MAX zv´ yˇsil doln´ı hranici MIN sn´ıˇzil horn´ı hranici jinak hranice nezmˇ enˇ eny
betterof( Pos, Val, Pos1, Val1, Pos, Val) :- min to move( Pos), Val > Val1, ! Pos je lepˇs´ı neˇz Pos1 ; max to move( Pos), Val < Val1, !. % betterof( , , Pos1, Val1, Pos1, Val1). % jinak je lepˇs´ı Pos1 ´ Uvod do umˇ el´ e inteligence 7/12
19 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Moˇznosti vylepˇsen´ı Minimax/Alpha-Beta
Moˇznosti vylepˇsen´ı Minimax/Alpha-Beta
vyhodnocovat pouze klidn´e stavy (quiescent search) pˇri vyhodnocov´an´ı poˇc´ıtat s efektem horizontu – zvraty mimo prohledanou oblast dopˇredn´e oˇrez´av´an´ı – nˇekter´e stavy se ihned zahazuj´ı bezpeˇcn´e napˇr. pro symetrick´e tahy nebo pro tahy hluboko ve stromu
´ Uvod do umˇ el´ e inteligence 7/12
20 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Ohodnocovac´ı funkce
Ohodnocovac´ı funkce
ˇ y na tahu Cern´ B´ıl´y ma o nˇeco lepˇs´ı pozici
´ Uvod do umˇ el´ e inteligence 7/12
B´ıl´y na tahu ˇ y v´ıtˇez´ı Cern´
21 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Ohodnocovac´ı funkce
Ohodnocovac´ı funkce
ˇ y na tahu Cern´ B´ıl´y ma o nˇeco lepˇs´ı pozici
B´ıl´y na tahu ˇ y v´ıtˇez´ı Cern´
Pro ˇsachy typicky line´arn´ı v´aˇzen´y souˇcet rys˚ u P Eval(s) = w1 f1 (s) + w2 f2 (s) + . . . + wn fn (s) = ni=1 wi fi (s) napˇr. w1 = 9 f1 (s) = (poˇcet b´ıl´ych kr´aloven) − (poˇcet ˇcern´ych kr´aloven) ... ´ Uvod do umˇ el´ e inteligence 7/12
21 / 29
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Ohodnocovac´ı funkce – odchylky
Ohodnocovac´ı funkce – odchylky MAX
2
MIN
MAX
20
1
1
2
2
2
´ Uvod do umˇ el´ e inteligence 7/12
1
4
1
22 / 29
20
20
20
400
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Ohodnocovac´ı funkce – odchylky
Ohodnocovac´ı funkce – odchylky MAX
2
MIN
MAX
20
1
1
2
2
2
1
4
1
20
20
20
400
chov´a se stejnˇe pro libovolnou monot´onn´ı transformaci funkce Eval z´aleˇz´ı pouze na uspoˇr´ad´an´ı → ohodnocen´ı v deterministick´e hˇre funguje jako ordin´aln´ı funkce ´ Uvod do umˇ el´ e inteligence 7/12
22 / 29
Nedeterministick´ e hry
Nedeterministick´e hry n´ahoda ←− hod kostkou, hod minc´ı, m´ıch´an´ı karet
´ Uvod do umˇ el´ e inteligence 7/12
23 / 29
Nedeterministick´ e hry
Nedeterministick´e hry n´ahoda ←− hod kostkou, hod minc´ı, m´ıch´an´ı karet pˇr´ıklad – 1 tah s h´azen´ım minc´ı: MAX
3
n´ ahoda
3
MIN
2
-1
/0.5
/0.5
/0.5
/0.5
2
4
0
-2
4
7
4
´ Uvod do umˇ el´ e inteligence 7/12
6 23 / 29
0
5
-2
Nedeterministick´ e hry
Algoritmus Minimax pro nedeterministick´ e hry
Algoritmus Minimax pro nedeterministick´e hry
expect minimax . . . poˇc´ıt´a perfektn´ı hru s pˇrihl´ednut´ım k n´ahodˇe rozd´ıl je pouze v zapoˇc´ıt´an´ı uzl˚ u n´ahoda: utility(n) pro koncov´y stav n maxs∈moves(n) expect minimax(s) pro MAX uzel n expect minimax(n) = min s∈moves(n) expect minimax(s) P pro MIN uzel n s∈moves(n) P(s) · expect minimax(s) pro uzel n´ahody n
´ Uvod do umˇ el´ e inteligence 7/12
24 / 29
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[−∞, ∞]
n´ ahoda
[−∞, ∞] /0.5
MIN
[−∞, ∞] /0.5
/0.5
[−∞, ∞]
[−∞, ∞]
´ Uvod do umˇ el´ e inteligence 7/12
[−∞, ∞]
25 / 29
/0.5 [−∞, ∞]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[−∞, ∞]
n´ ahoda
[−∞, ∞] /0.5
MIN
[−∞, ∞] /0.5
/0.5
[−∞, 2]
[−∞, ∞]
[−∞, ∞]
2
´ Uvod do umˇ el´ e inteligence 7/12
25 / 29
/0.5 [−∞, ∞]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[−∞, ∞]
n´ ahoda
[−∞, ∞] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−∞, ∞]
[−∞, ∞]
2
´ Uvod do umˇ el´ e inteligence 7/12
25 / 29
[−∞, ∞]
/0.5 [−∞, ∞]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[−∞, ∞]
n´ ahoda
[−∞, 2] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−∞, ∞]
2
[−∞, 2]
2
´ Uvod do umˇ el´ e inteligence 7/12
25 / 29
[−∞, ∞]
/0.5 [−∞, ∞]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[1.5, ∞]
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−∞, ∞]
2
[1, 1]
2
[−∞, ∞]
1
´ Uvod do umˇ el´ e inteligence 7/12
25 / 29
/0.5 [−∞, ∞]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[1.5, ∞]
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−∞, ∞]
2
[1, 1]
2
[−∞, 0]
1
´ Uvod do umˇ el´ e inteligence 7/12
0
25 / 29
/0.5 [−∞, ∞]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[1.5, ∞]
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−∞, ∞]
2
[1, 1]
2
[0, 0]
1
´ Uvod do umˇ el´ e inteligence 7/12
/0.5
0
25 / 29
1
[−∞, ∞]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
[1.5, 1.5]
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−∞, 0.5]
2
[1, 1]
2
[0, 0]
1
´ Uvod do umˇ el´ e inteligence 7/12
/0.5
0
25 / 29
1
[−∞, 1]
1
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach je moˇzn´e pouˇz´ıt upraven´e Alfa-Beta proˇrez´av´an´ı MAX
1.5
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−∞, 0.5]
2
[1, 1]
2
[0, 0]
1
´ Uvod do umˇ el´ e inteligence 7/12
/0.5
0
25 / 29
1
[−∞, 1]
1
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach – pokraˇc. pokud je moˇzno dopˇredu stanovit limity na ohodnocen´ı list˚ u→ oˇrez´av´an´ı je vˇetˇs´ı MAX
[−2, 2]
n´ ahoda
[−2, 2] /0.5
MIN
[−2, 2] /0.5
/0.5
[−2, 2]
[−2, 2]
´ Uvod do umˇ el´ e inteligence 7/12
[−2, 2]
26 / 29
/0.5 [−2, 2]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach – pokraˇc. pokud je moˇzno dopˇredu stanovit limity na ohodnocen´ı list˚ u→ oˇrez´av´an´ı je vˇetˇs´ı MAX
[−2, 2]
n´ ahoda
[−2, 2] /0.5
MIN
[−2, 2] /0.5
/0.5
[−2, 2]
[−2, 2]
[−2, 2]
2
´ Uvod do umˇ el´ e inteligence 7/12
26 / 29
/0.5 [−2, 2]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach – pokraˇc. pokud je moˇzno dopˇredu stanovit limity na ohodnocen´ı list˚ u→ oˇrez´av´an´ı je vˇetˇs´ı MAX
[0, 2]
n´ ahoda
[0, 2] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−2, 2]
[−2, 2]
[−2, 2]
2
´ Uvod do umˇ el´ e inteligence 7/12
26 / 29
/0.5 [−2, 2]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach – pokraˇc. pokud je moˇzno dopˇredu stanovit limity na ohodnocen´ı list˚ u→ oˇrez´av´an´ı je vˇetˇs´ı MAX
[0, 2]
n´ ahoda
[0, 2] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−2, 2]
2
[−2, 2]
[−2, 2]
2
´ Uvod do umˇ el´ e inteligence 7/12
26 / 29
/0.5 [−2, 2]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach – pokraˇc. pokud je moˇzno dopˇredu stanovit limity na ohodnocen´ı list˚ u→ oˇrez´av´an´ı je vˇetˇs´ı MAX
[1.5, 2]
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−2, 2]
2
[1, 1]
2
[−2, 2]
1
´ Uvod do umˇ el´ e inteligence 7/12
26 / 29
/0.5 [−2, 2]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach – pokraˇc. pokud je moˇzno dopˇredu stanovit limity na ohodnocen´ı list˚ u→ oˇrez´av´an´ı je vˇetˇs´ı MAX
[1.5, 1.5]
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−2, 1]
2
[1, 1]
2
[−2, 0]
1
´ Uvod do umˇ el´ e inteligence 7/12
0
26 / 29
/0.5 [−2, 2]
Nedeterministick´ e hry
Proˇrez´ av´ an´ı v nedeterministick´ ych hr´ ach
Proˇrez´av´an´ı v nedeterministick´ych hr´ach – pokraˇc. pokud je moˇzno dopˇredu stanovit limity na ohodnocen´ı list˚ u→ oˇrez´av´an´ı je vˇetˇs´ı MAX
1.5
n´ ahoda
[1.5, 1.5] /0.5
MIN
/0.5
/0.5
[2, 2]
2
[−2, 1]
2
[1, 1]
2
[−2, 0]
1
´ Uvod do umˇ el´ e inteligence 7/12
0
26 / 29
/0.5 [−2, 2]
Nedeterministick´ e hry
Nedeterministick´ e hry v praxi
Nedeterministick´e hry v praxi
hody kostkou zvyˇsuj´ı b → se dvˇema kostkami 21 moˇzn´ych v´ysledk˚ u backgammon – 20 leg´aln´ıch tah˚ u: hloubka 4 = 20 × (21 × 20)3 ≈ 1.2 × 109 jak se zvyˇsuje hloubka → pravdˇepodobnost dosaˇzen´ı zvolen´eho uzlu kles´a ⇒ v´yznam prohled´av´an´ı se sniˇzuje alfa-beta proˇrez´av´an´ı je mnohem m´enˇe efektivn´ı program TDGammon pouˇz´ıv´a prohled´av´an´ı do hloubky 2 + velice dobrou Eval funkci ≈ dosahuje u ´rovnˇe svˇetov´eho ˇsampion´atu
´ Uvod do umˇ el´ e inteligence 7/12
27 / 29
Nedeterministick´ e hry
Odchylka v ohodnocen´ı nedeterministick´ ych her
Odchylka v ohodnocen´ı nedeterministick´ych her MAX
2.1
n´ ahoda
2.1 .9
MIN
1.3
.1 2
2
40.9
2
.9 3
3
3
.1 1
1
21
1
.9 4
4
´ Uvod do umˇ el´ e inteligence 7/12
.1 20
4
20
28 / 29
40.9
20
.9 30
30
30
.1 1
1
1
400
400
400
Nedeterministick´ e hry
Odchylka v ohodnocen´ı nedeterministick´ ych her
Odchylka v ohodnocen´ı nedeterministick´ych her MAX
2.1
n´ ahoda
2.1 .9
MIN
1.3
.1 2
2
40.9
2
.9 3
3
3
.1 1
1
21
1
.9 4
4
.1 20
4
20
40.9
20
.9 30
30
30
.1 1
1
1
400
400
400
chov´an´ı je zachov´ano pouze pro pozitivn´ı line´arn´ı transformaci funkce Eval Eval u nedeterministick´ych her by tedy mˇela proporcion´alnˇe odpov´ıdat oˇcek´avan´emu v´ynosu ´ Uvod do umˇ el´ e inteligence 7/12
28 / 29
Hry s nepˇresn´ ymi znalostmi
Hry s nepˇresn´ymi znalostmi
napˇr. karetn´ı hry → nezn´ame poˇc´ateˇcn´ı nam´ıch´an´ı karet oponenta obvykle m˚ uˇzeme spoˇc´ıtat pravdˇepodobnost kaˇzd´eho moˇzn´eho rozd´an´ı zjednoduˇsenˇe – jako jeden velk´y hod kostkou na zaˇc´atku prohled´av´ame ovˇsem ne re´aln´y stavov´y prostor, ale domnˇel´y stavov´y prostor program Jack, nejˇcastˇejˇs´ı v´ıtˇez poˇc´ıtaˇcov´ych ˇsampion´at˚ u v bridgi pouˇz´ıv´a metodu Monte Carlo: 1. generuje 100 rozd´an´ı karet konzistentn´ıch s dan´ym pod´an´ım 2. vyb´ır´a akci, kter´a je v pr˚ umˇeru nejlepˇs´ı
V roce 2006 porazil Jack na soutˇeˇzi 3 ze 7 top holandsk´ych hr´aˇcsk´ych p´ar˚ u.
´ Uvod do umˇ el´ e inteligence 7/12
29 / 29
