Hry dvou hr´acˇ u˚ (napˇr. sˇ achy) • Uvaˇzujeme jen hry s nulovym ´ souˇctem, tj. zisk jednoho znamen´a ztr´atu druh´eho hr´acˇ e. ˚ zisk, s tahem • Stˇr´ıd´a se n´asˇ tah, kde maximalizujeme svuj soupeˇre, ktery´ se snaˇz´ı n´asˇ zisk minimalizovat, neboˇt to je jeho ztr´ata. ˚ MAX a MIN. • N´asˇ graf prohled´av´an´ı bude m´ıt dva typy uzlu:
8
MAX
A 7
8
B
7
9
C
MIN
8
8
11
D 7
9
1
8
8
E 2
2
5
5
MAX
G
9
F
8 1
8
9
9
11 MIN
4
9
1
4
11
8
8
listy
Algoritmus Minimax function MINIMAX–DECISION(game) returns an operator for each op in Operators(game) do Value[op]=MINIMAX–VALUE(Apply(op, game), game) end return the op with the highest Value[op] function MINIMAX–VALUE(state, game)returns a utility value if TERMINAL–TEST[game](state) then return Utility[game](state) else if MAX is to move in state then return the hightest MINIMAX–VALUE of Successors(state) else return the lowest MINIMAX–VALUE of Successors(state)
Proˇrez´av´an´ı v dan´e hloubce (Cutoff) Potˇrebujeme ohodnocovac´ı funkci na stavech, napˇr. • sˇ achy, d´ama, mlynek: materi´al jednoho hr´acˇ e m´ınus materi´al ´ protivn´ıka • piˇskvorky: ohodnocen´ı pozice – voln´e trojice, cˇ teˇrice, apod. v pˇredem dan´e hloubce nevol´ame MINIMAX, ale odhadneme ohodnocen´ı pozice. ˚ ze protivn´ık br´at, je odhad nestabiln´ı – Uklidnˇen´ı: pokud zrovna muˇ je vhodn´e j´ıt jeˇstˇe p´ar tahu˚ dopˇredu, neˇz se situace uklidn´ı. Probl´em horizontu: mohu sebr´an´ı d´amy odkl´adat za horizont, ale ne navˇeky – nen´ı univerz´aln´ı rˇ eˇsen´ı.
8
MAX
A 7
8
alpha=7
B
7
9
C
MIN
8
8
11
D 7
9
MAX
G 8
8 E 2
2
5
5
9
F
8 1
8
9
9
11 MIN
4
9
1
4
11
8
8
listy
α–β proˇrez´av´an´ı • α je nejlepˇs´ı skore MAX uzlu na cestˇe od koˇrene do stavu u MAX uzlu pˇr´ıpadnˇe zvˇetˇsen´a prohledanymi dˇetmi ´ • β je nejniˇzsˇ´ı skore MIN uzlu na cestˇe od koˇrene do stavu u MIN uzlu pˇr´ıpadnˇe zmenˇsen´a prohledanymi dˇetmi ´ tj. pokud MAX uzel pˇrekroˇc´ı β nebo MIN uzel pˇrekroˇc´ı α, nˇekdo z pˇredku˚ pˇretoˇc´ı smˇer hry do jin´eho podstromu, neˇz pr´avˇe jsem.
α–β proˇrez´av´an´ı
max −I
<−I,I> A
alpha
if alpha > beta then prune
<−I,I> min
I
B
beta
min
beta C
D 7
9
max
alpha G
8 min
2
E
beta
min
5
1
8
beta F 4
9
9
8
11
α–β proˇrez´av´an´ı
<−I,I>
alpha max −I 7 7 <−I,I>
min
A
B beta I 7 9 8 7
9
if alpha > beta then prune
<7,I>
min
beta C
8 D
7
9
max
alpha G
8 min
2
E
beta
min
5
1
8
beta F 4
9
9
8
11
α–β proˇrez´av´an´ı
<−I,I>
alpha max −I 7 7 <−I,I>
min
B beta I 7 9 8 7
9
A 8
min <7,I> 8
alpha max 7 79 <7,I>
8
if alpha > beta then prune
<7,I> beta C I 8
D <7,I>
E
beta min I 2
min
2<7
I
beta F
5
1
8
4
9
2
2
alpha G max 7 9>8
9
8
11
α–β proˇrez´av´an´ı
<−I,I>
alpha max −I 7 7 <−I,I>
min
B beta I 7 9 8 7
9
8
A
8
<7,I>
min <7,I>
beta C I 8
<7,8> 8
8
8
alpha max 7 79 <7,I>
8
D <7,I> 8
E
beta min I 2
beta F I8 9 8
min
2<7
2
2
8 5
alpha G max 7 9 9>8
1
8
9 9
9 4
9 8 8
11
Algoritmus alfa–beta proˇrez´av´an´ı function MAX–VALUE(state, game, α, β) returns the minimax value of state if CUTOFF–TEST(state) then return Eval (state) for each s in SUCCESSORS(state) do α = MAX(α, MIN–VALUE(s, game, α, β)) if α ≥ β then return β end return α function MIN–VALUE(state, game, α, β) returns the minimax value of state if CUTOFF–TEST(state) then return Eval (state) for each s in SUCCESSORS(state) do β = MIN(β, MAX–VALUE(s, game, α, β)) if β ≤ α then return α end return β
Transpoziˇcn´ı tabulky
Pamatuji si stavy, neboˇt se cˇ asto opakuj´ı v jinych ´ vˇetv´ıch.
Transpoziˇcn´ı tabulky
Lasker position – Sigma Chess – b´ıly´ na tahu
• Vyhr´avaj´ıc´ı tah je Ka1-b1!! • Ka1-b2 vede k rem´ıze • je tˇreba prohledat asponˇ 20 tahu˚ dopˇredu • bez pamˇeti hodiny cˇ i dny, s pamˇet´ı m´enˇe neˇz sekundu • d´ıky tomu, zˇ e pˇesˇ i jsou blokovan´ı, je stavovy´ prostor maly´ Za chv´ıli bude α–β proˇrez´av´an´ı s pamˇet´ı.
Nulov´e okno – Test • Pokud α − β pust´ıme m´ısto h−∞, ∞i s oknem hk − , k + i, pt´ame se, zda m´a MAX hr´acˇ zaruˇcenu vyhru k. ´ • Pˇri takov´emto testu proˇrez´av´am v´ıc, neˇz h−∞, ∞i, proto se cˇ asto vyplat´ı zavolat nˇekolik testu˚ m´ısto h−∞, ∞i. • Plat´ım za to t´ım, zˇ e dostanu jen doln´ı cˇ i horn´ı mez, nikoli pˇresnou hodnotu – aˇz se meze rovnaj´ı, m´am pˇresnou hodnotu.
Nulov´e okno – Test <1.5,1.6> 7 A alpha max −I 7 7 > 1.6 7 <1.5,1.6>
min
B beta I 7 9 8 7
7
9 9
dolní odhad if alpha > beta then prune
min 8
beta C
D
max
alpha G
8 min
2
E
beta
min
5
1
8
beta F 4
9
9
8
11
Memory-enhanced Test Driver
function MTDF(root : node_type; f : integer; d : integer) : integer; g := f; upperbound := +INFINITY; lowerbound := -INFINITY; repeat if g == lowerbound then beta := g + 1 else beta := g; g := AlphaBetaWithMemory(root, beta - 1, beta, d); if g < beta then upperbound := g else lowerbound := g; until lowerbound >= upperbound; return g;
Prvn´ı odhad pomuˇ ˚ ze ˚ Pokud se tref´ım, tak jen dva pruchody. function iterative_deepening(root : node_type) : integer; firstguess := 0; for d = 1 to MAX_SEARCH_DEPTH do firstguess := MTDF(root, firstguess, d); if times_up() then break; return firstguess;
α–β proˇrez´av´an´ı s pamˇet´ı function AlphaBetaWithMemory(n : node_type; alpha , beta , \\ depth : integer) : integer; if retrieve(n) == OK then /* Transposition table lookup */ if n.lowerbound >= beta then return n.lowerbound; if n.upperbound <= alpha then return n.upperbound; alpha := max(alpha, n.lowerbound); beta := min(beta, n.upperbound); if depth == 0 then g := evaluate(n); /* leaf node */
else if n == MAXNODE then g := -INFINITY; c := firstchild(n); while (g < beta) and (c != NOCHILD) do g := max(g, AlphaBetaWithMemory(c, alpha, beta, d - 1)); alpha := max(alpha, g); c := nextbrother(c); else /* n is a MINNODE */ g := +INFINITY; c := firstchild(n); while (g > alpha) and (c != NOCHILD) do g := min(g, AlphaBetaWithMemory(c, alpha, beta, d - 1)); beta := min(beta, g); c := nextbrother(c);
/* Traditional transposition table storing of bounds */ /* Fail low result implies an upper bound */ if g <= alpha then n.upperbound := g; store n.upperbound; /* Found an accurate minimax value will not occur if called with zero window */ if g > alpha and g < beta then n.lowerbound := g; n.upperbound := g; store n.lowerbound, n.upperbound; /* Fail high result implies a lower bound */ if g >= beta then n.lowerbound := g; store n.lowerbound; return g;
Z´ajem UI o hry • uk´azat schopnosti inteligence poˇc´ıtaˇcu˚ • stanovit hodnotu (game–theoretic value) hry prvn´ı hr´acˇ vyhraje, prohraje, remizuje pokud vˇsichni hr´acˇ i hraj´ı optim´alnˇe My: hry s plnou informac´ı a s nulovym ´ souˇctem.
Stupnˇe vyˇreˇsen´ı hry • Silnˇe vyˇreˇsen´a – je zn´am´a optim´aln´ı strategie pro vˇsechny pozice • Slavˇe vyˇreˇsen´a – je zn´am´a optim´aln´ı strategie pro poˇca´ teˇcn´ı pozici • Ultra slabˇe vyˇreˇsen´a – je zn´am´a hodnota poˇca´ teˇcn´ı pozice, ale ne strategie, jak j´ı dos´ahnout
Sloˇzitost her • Velikost stavov´eho prostoru • velikost hern´ıho stromu (pro MINIMAX atd.)
Mlynek (Nine men’s morris) ´
Mlynek (Nine men’s morris) ´ • Vyˇreˇsil Gasser 1995 • Poˇcet stavu˚ hry je: 7,673,759,269 (vylouˇcen´e symetrie) • vytvoˇril datab´azi vˇsech pozic pro stˇredn´ı a koncovou hru (od okamˇziku, kdy je poloˇzen posledn´ı k´amen), tj. 28 w–b datab´az´ı, kde w a b jsou poˇcty b´ılych ´ a cˇ ernych ´ kamenu˚ • za pouˇzit´ı t´eto datab´aze prohledal strom pro 18 tahu˚ od poˇca´ tku • hodnota hry je rem´ıza
Checkers (D´ama, trochu jin´a) • CHINOOK se stal prvn´ım mistrem svˇeta v hern´ı soutˇezˇ i lid´ı a poˇc´ıtaˇcu˚ 1994 • jeˇstˇe nebyla (r. 2002) slabˇe vyˇreˇsen´a ˚ tj. 443,748,401,247 • datab´aze koncovek pro osm a m´enˇe kamenu, pozic, zkomprimovanych ´ na 6GB • datab´aze stˇredn´ı hry – jakmile se podaˇr´ı urˇcit hodnotu pozice ve stˇredn´ı hˇre, uloˇz´ı se do datab´aze v praxi umoˇznilo urˇcit hodnotu mnoha pozic s 22 kameny • do datab´aze stˇredn´ı hry pˇridan´e pozice, z´ıskan´e pokusem rˇ eˇsit poˇca´ teˇcn´ı postupy popsan´e v literatuˇre do hloubky
Stalet´a pozice (197 let´a) • 1800–1900 diskuse o hodnotˇe pozice, z´avˇer b´ıly´ v´ıtˇez´ı • CHINOOK 1997: bˇehem sekundy odpovˇedˇel, zˇ e je to rem´ıza
ˇ Sachy ... budou pˇr´ısˇ t´ı tyden na Semin´arˇ i UI ´
Hex
Hex Ultra–slabˇe vyˇreˇseno 1. rem´ıza nen´ı moˇzn´a z tvaru hrac´ı plochy 2. tah nikdy nen´ı na sˇ kodu 3. kdyby existovala vyhr´avac´ı stragetie pro druh´eho, pak prvn´ı poloˇz´ı prvn´ı k´amen n´ahodnˇe a pokraˇcuje podle druh´eho strategie.
Connect four, Kokosov´e oˇrechy, ...
AND–OR graf ´ • pˇr. rozklad ulohy na nˇekolik d´ılˇc´ıch c´ılu˚ • nebo ”boj s n´ahodnym akce” – pak mus´ıme vˇetve ´ vysledkem ´ AND uzlu v´azˇ it pravdˇepodobnost´ı vysledk u˚ ´ • Podobnˇe jako v MIN–MAX grafu se v AND–OR grafu stˇr´ıdaj´ı ˚ uzly dvou druhu. • Nechˇt m´ame heuristiku h(n), kter´a je doln´ı odhad ceny ˚ optim´aln´ıho rˇ eˇs´ıc´ıho grafu z uzlu n do c´ılovych ´ uzlu.
MAX
Chance 1/3
2/3
MAX
Chance
MAX
Chance
MAX
AO* Algorithm ˇ s´ıc´ı graf G’ z n do N: Prohled´av´an´ı AND–OR grafu Reˇ • je–li n ∈ N, je G’ tvoˇren pouze n • jinak pokud vych´az´ı z n konektor K do mnoˇziny {n1 , . . . , nk }, zˇ e existuje rˇ eˇs´ıc´ı graf z kaˇzd´eho ni do N, pak se G’ skl´ad´a z n, K, n1 , . . . , nk a rˇ eˇs´ıc´ıch grafu˚ z ni do N • jinak rˇ eˇs´ıc´ı graf z n do N neexistuje. C´ılem je naj´ıt optim´aln´ı rˇ eˇs´ıc´ı graf. Cena k(n, N ) rˇ eˇs´ıc´ıho grafu z n do N • je–li n ∈ N, je k(n, N ) = 0 • jinak z n vych´az´ı konektor K do mnoˇziny {n1 , . . . , nk }, je-li jeho cena c(K ), je k(n, N ) = c(K ) + w1K · k(n1 , N ) + . . . + wnK · k(nk , N ).
1. G ← {s0 }; q(s0 ) ← h(s0 ), je–li s0 c´ılovy, ´ oznaˇcme ho SOLVED 2. while s0 not SOLVED do 3. begin 4. G’ ← currently best solution subgraph from s0 5. n ← unsolvedLeaf(G’) 6. EXPAND(n); add successors to G, assign q(n) = h(n) to new nodes, assign SOLVED to terminal nodes; if n has no successors, set q(n) = ∞. 7.
7. S ← {n} (a) while S not empty do (b) begin (c) m ← takeAndRemoveNodeWithoutSuccessorsInS(S) (d) for each connector Ki set qi (m) ← c(Ki ) + w1K · q(n1 ) + . . . + wnK · q(nki ) (e) q(m) ← mini qi (m); mark appropriate connector, remove the old mark (f) if all nodes in the marked connector solved, mark m SOLVED (g) if m marked SOLVED or q changed then add all parents of m to S where m is a child via a marked connector
Negamax Pokud se V´am nechce poˇra´ d stˇr´ıdat MIN a MAX, zkuste Negamax!
8
MAX
A 7
8
B
7
9
C
MIN
8
8
8
D 7
9
1
8
2
2
8
E
min(2,5,1)=−max(−2,−5,−1)
5
5
MAX
G
9
F
8 1
8
9
9
11 MIN
4
9
1
4
11
8
8
listy
max(7,8)
8
MAX
A
−7
−8
max(−7,−9,−8)B
7
7
9
9
C
max(−8,−11)
MAX
8
8
max(1,8)
D
−1
8
2
5
5
MAX
G
max(9,4,11)
−8
max(−2,−5,−1) E
2
11
max(−8,−9,−8)
9
8 1
8
9
9
11
F
MAX 4
9
1
4
11
8
8
listy
