Hry a z´akladn´ı hern´ı strategie Aleˇs Hor´ak E-mail:
[email protected] http://nlp.fi.muni.cz/uui/
Obsah: ◮
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 / 25
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
2 / 25
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 Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
3 / 25 Hry a UI – aktu´ aln´ı v´ ysledky
Hry a UI – aktu´aln´ı v´ysledky – 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). ◮ ˇ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. ◮ Othello – svˇ etov´ı ˇsampioni odm´ıtaj´ı hr´at s poˇc´ıtaˇci, protoˇze stroje jsou pˇr´ıliˇs dobr´e. Othello (t´eˇz Reversi) pro dva hr´aˇce na desce 8×8 – snaˇz´ı se mezi sv´e dva kameny uzavˇr´ıt soupeˇrovy, kter´e se pˇrebarv´ı. Aˇz se zapln´ı deska, spoˇc´ıtaj´ı se kameny. ◮ 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 mohou 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).
◮ d´ ama
´ Uvod do umˇ el´ e inteligence 7/12
4 / 25
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 Hry vs. Prohled´ av´ an´ı stavov´ eho prostoru
5 / 25 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 ◮ utilit´ arn´ı funkce
– urˇcuje, kdy hra konˇc´ı, oznaˇcuje koncov´ e stavy
– numerick´e ohodnocen´ı koncov´ych stav˚ u
´ Uvod do umˇ el´ e inteligence 7/12
6 / 25
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
X
X
7 / 25
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 mins∈moves(n) Hodnota minimax(s), pro MIN uzel n
´ Uvod do umˇ el´ e inteligence 7/12
8 / 25
Algoritmus Minimax
Algoritmus Minimax – pokraˇc. pˇr´ıklad – hra jen na jedno kolo = 2 tahy (p˚ ulkola) MAX
3 a2
a1 MIN
a3 2
3 b1
b2
c1
b3
c2
2 c3
d1
d2
d3
MAX
util.funkce
3
12
8
2
´ Uvod do umˇ el´ e inteligence 7/12
4
6
14
5
9 / 25
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 na tahu v Pos0 max to move( 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
10 / 25
2
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 Algoritmus Minimax
11 / 25 ˇ 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: odhad pˇr´ınosu pozice nahrad´ı utilit´arn´ı funkci
◮ ohodnocovac´ı funkce
◮ 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
12 / 25
Algoritmus Alfa-Beta proˇrez´ av´ an´ı
Algoritmus Alfa-Beta proˇrez´av´an´ı Pˇr´ıklad stromu, kter´y zpracuje predik´at minmax 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
1
13 / 25
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
14 / 25
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). % nejsou dalˇs´ı kandid´ ati goodenough( [], , , Pos, Val, Pos, Val) :- !. goodenough( , Alpha, Beta, Pos, Val, Pos, Val) :MAX dos´ ahl horn´ı hranici min to move( Pos), Val > Beta, ! % ; 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, ! ; max to move( Pos), Val < Val1, !. % Pos je lepˇs´ı neˇz Pos1 jinak je lepˇs´ı Pos1 betterof( , , Pos1, Val1, Pos1, Val1). % ´ Uvod do umˇ el´ e inteligence 7/12 Algoritmus Alfa-Beta proˇrez´ av´ an´ı
15 / 25 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
16 / 25
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
17 / 25
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
18 / 25
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 Nedeterministick´ e hry
6
0
5
-2
19 / 25 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) = mins∈moves(n) expect minimax(s) pro MIN uzel n P s∈moves(n) P(s) · expect minimax(s) pro uzel n´ahody n
´ Uvod do umˇ el´ e inteligence 7/12
20 / 25
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 Nedeterministick´ e hry
/0.5
0
1
[−∞, 1]
1
21 / 25 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
22 / 25
/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
23 / 25
Nedeterministick´ e hry
Odchylka v ohodnocen´ı nedeterministick´ ych her
Odchylka v ohodnocen´ı nedeterministick´ych her MAX
2.1
n´ ahoda
2.1 .9
MIN
2
.9 3
3
21
1.3
.1 2
2
40.9
3
.1 1
1
1
.9 4
4
4
.1 20
20
40.9
20
.9 30
30
30
.1 1
1
1
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´ yUvod ´ nosu do umˇ el´ e inteligence 7/12 24 / 25
400
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:
◮
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
25 / 25
