Hry a základní herní strategie
Aleš Horák
E-mail: hales@fi.muni.cz
http://nlp.fi.muni.cz/uui/
Obsah:
▶ Hry vs. Prohledávání stavového prostoru
▶ Algoritmus Minimax
▶ Algoritmus Alfa-Beta prořezávání
▶ Nedeterministické hry
▶ Hry s nepřesnými znalostmi
Úvod do umělé inteligence 4/12 1 / 32
Hry vs. Prohledávání stavového prostoru
Hry × Prohledávání stavového prostoru
Multiagentní prostředí:
▶ agent musí brát v úvahu akce jiných agentů → jak ovlivní jeho vlastní
prospěch
▶ vliv ostatních agentů – prvek náhody
▶ kooperativní × soupeřící multiagentní prostředí (MP)
Hry:
▶ matematická teorie her (odvětví ekonomie) – kooperativní i soupeřící MP,
kde vliv všech agentů je významný
▶ hra v UI = obv. deterministické MP, 2 střídající se agenti, výsledek hry je
vzájemně opačný nebo shoda
Algoritmy soupeřícího prohledávání (adversarial search):
▶ oponent dělá dopředu neurčitelné tahy → řešením je strategie, která
počítá se všemi možnými tahy protivníka
▶ časový limit ⇒ zřejmě nenajdeme optimální řešení → hledáme lokálně
optimální řešení
Úvod do umělé inteligence 4/12 2 / 32
Hry vs. Prohledávání stavového prostoru Hry a UI – historie
Hry a UI – historie
▶ Babbage, 1846 – počítač porovnává přínos
různých herních tahů
▶ von Neumann, 1944 – algoritmy perfektní hry
▶ Zuse, Wiener, Shannon, 1945–50 – přibližné
vyhodnocování
▶ Turing, 1951 – první šachový program (jen na papíře)
▶ Samuel, 1952–57 – strojové učení pro zpřesnění vyhodnocování
▶ McCarthy, 1956 – prořezávání pro možnost hlubšího prohledávání
řešení her je zajímavým předmětem studia ← je obtížné:
průměrný faktor větvení v šachách b = 35
pro 50 tahů 2 hráčů . . .
prohledávací strom ≈ 35100 ≈ 10154 uzlů (≈ 1040 stavů)
Úvod do umělé inteligence 4/12 3 / 32
Hry vs. Prohledávání stavového prostoru Hry a UI – aktuální výsledky
Hry a UI – aktuální výsledky
▶ Reversi/Othello – od 1980 světoví šampioni
odmítají hrát s počítači, protože stroje jsou příliš
dobré. Reversi pro dva hráče na desce 8×8 –
snaží se mezi své dva kameny uzavřít soupeřovy
v řadě, která se přebarví. Až se zaplní deska,
spočítají se kameny.
▶ dáma – 1994 program Chinook porazil světového
šampiona Marion Tinsley. Používal úplnou
databázi tahů pro ≤ 8 figur (443 748 401 247
pozic).
Úvod do umělé inteligence 4/12 4 / 32
Hry vs. Prohledávání stavového prostoru Hry a UI – aktuální výsledky
Hry a UI – aktuální výsledky
▶ šachy – 1997 porazil stroj Deep Blue světového šampiona Gary
Kasparova 31/2 : 21/2. Stroj počítal 200 mil. pozic/s, používal
sofistikované vyhodnocování a nezveřejněné metody pro prozkoumávání
některých tahů až do hloubky 40 tahů.
2006 porazil program
Deep Fritz na PC světového
šampiona Vladimíra Kramnika 2:4.
V současnosti vyhrávají
turnaje i programy na slabším hardware
mobilních telefonů s 20 tis. pozic/s.
Úvod do umělé inteligence 4/12 5 / 32
Hry vs. Prohledávání stavového prostoru Hry a UI – aktuální výsledky
Hry a UI – aktuální výsledky
▶ Arimaa – hra na šachovnici se standardníma figurama, speciálně
navržená v roce 2003 tak, aby vyžadovala lidskou inteligenci (variabilní
počet tahů, figury se tlačí nebo táhnou, pasti...). Člověk překonán
počítačem 18. dubna 2015 3 : 0 (v rámci každoroční Arimaa Challenge).
Úvod do umělé inteligence 4/12 6 / 32
Hry vs. Prohledávání stavového prostoru Hry a UI – aktuální výsledky
Hry a UI – aktuální výsledky
▶ Go – do roku 2008 světoví šampioni odmítali hrát s počítači, protože
stroje jsou příliš slabé. V Go je b > 300, takže počítače mohly používat
téměř pouze znalostní bázi vzorových her.
od 2009
– první programy dosahují pokročilejší
amatérské úrovně (zejména na
desce 9×9, nižší úroveň i na 19×19).
březen 2016
– program AlphaGo porazil lidského
velmistra Lee Sedola na normální
desce 19×19 4 : 1. AlphaGo využívá
učící se hodnotící funkce založené
na hlubokých neuronových sítích.
Úvod do umělé inteligence 4/12 7 / 32
Hry vs. Prohledávání stavového prostoru Hry a UI – aktuální výsledky
Hry a UI – aktuální výsledky
▶ Go . . .
květen 2017 – program AlphaGo
porazil Ke Jie, který byl po 2 roky
nejlepší hráč světa, 3 : 0.
říjen 2017 – nová verze AlphaGo
Zero postavená na posílením
učení hluboké neuronové sítě
s reziduálními bloky, která se učí
pouze hrou sama se sebou.
Tato verze poráží předchozí
AlphaGo 100 : 0. Program při
samoučení nalezl známé i
neznámé strategie hry Go.
po 70 hodinách učení
Úvod do umělé inteligence 4/12 8 / 32
Hry vs. Prohledávání stavového prostoru Typy her
Typy her
deterministické s náhodou
perfektní
znalosti
šachy, dáma, Go,
Othello
backgammon,
monopoly
nepřesné
znalosti
bridge, poker, scrabble
Úvod do umělé inteligence 4/12 9 / 32
Hry vs. Prohledávání stavového prostoru Hledání optimálního tahu
Hledání optimálního tahu
2 hráči – MAX ( ) a MIN ( )
MAX je první na tahu a pak se střídají až do konce hry
hra = prohledávací problém:
▶ počáteční stav – počáteční herní situace + kdo je na tahu
▶ přechodová funkce – vrací dvojice (legální tah, výsledný stav)
▶ ukončovací podmínka – určuje, kdy hra končí, označuje koncové stavy
▶ utilitární funkce – numerické ohodnocení koncových stavů
Úvod do umělé inteligence 4/12 10 / 32
Hry vs. Prohledávání stavového prostoru Hledání optimálního tahu
Hledání optimálního tahu – pokrač.
počáteční stav a přechodová funkce definují herní strom:
Úvod do umělé inteligence 4/12 11 / 32
Algoritmus Minimax
Algoritmus Minimax
Hráč MAX ( ) musí prohledat herní strom pro zjištění nejlepšího tahu
proti hráči MIN ( )
→ zjistit nejlepší hodnotu minimax – zajišťuje nejlepší výsledek proti
nejlepšímu protivníkovi
Hodnota minimax(n) =



utility(n),
pro koncový stav n
maxs∈moves(n) Hodnota minimax(s),
pro MAX uzel n
mins∈moves(n) Hodnota minimax(s),
pro MIN uzel n
Úvod do umělé inteligence 4/12 12 / 32
Algoritmus Minimax
Algoritmus Minimax – pokrač.
příklad – hra jen na jedno kolo = 2 tahy (půlkola)
MAX
MIN
MAX
a1
b1 b2 b3
a2
c1 c2 c3
a3
d1 d2 d3
util.funkce
3
3
3 12 8
2
2 4 6
2
14 5 2
Úvod do umělé inteligence 4/12 13 / 32
Algoritmus Minimax
Algoritmus Minimax – pokrač.
function MINIMAX(state) # vrací novou konfiguraci
newpos, _ ← MAX-VALUE(state)
return newpos
function MAX-VALUE(state) # vrací konfiguraci a ohodnocení pro MAXe
if TERMINAL-TEST(state) then return None, UTILITY(state)
newval ← −∞; newpos ← None
foreach pos ∈ moves(state) do
val ← MIN-VALUE(pos)
if val > newval then
newval ← val; newpos ← pos
return newpos, newval
function MIN-VALUE(state) # vrací ohodnocení pro MINa
if TERMINAL-TEST(state) then return UTILITY(state)
newval ← ∞
foreach pos ∈ moves(state) do
_, val ← MAX-VALUE(pos)
if val < newval then
newval ← val
return newval
Úvod do umělé inteligence 4/12 14 / 32
Algoritmus Minimax
Algoritmus Minimax – vlastnosti
úplnost úplný pouze pro konečné stromy
optimálnost je optimální proti optimálnímu oponentovi
časová složitost O(bm)
prostorová složitost O(bm), prohledávání do hloubky
šachy . . . b ≈ 35, m ≈ 100 ⇒ přesné řešení není možné
např. bm = 106, b = 35 ⇒ m ≈ 4
4-tahy ≈ člověk-nováček
8-tahů ≈ člověk-mistr, typické PC
12-tahů ≈ Deep Blue, Kasparov
Úvod do umělé inteligence 4/12 15 / 32
Algoritmus Minimax Časové omezení
Časové omezení
předpokládejme, že máme 100 sekund + prozkoumáme 104 uzlů/s
⇒ 106 uzlů na 1 tah
řešení minimax_cutoff:
▶ ohodnocovací funkce odhad přínosu pozice
nahradí utilitární funkci
▶ ořezávací test (cutoff test) – např. hloubka nebo hodnota
ohodnocovací funkce
nahradí koncový test
Úvod do umělé inteligence 4/12 16 / 32
Algoritmus Alfa-Beta prořezávání
Algoritmus Alfa-Beta prořezávání
Příklad stromu, který zpracuje algoritmus minimax
Alfa-Beta odřízne expanzi některý uzlů ⇒ Alfa-Beta procedura je
efektivnější variantou minimaxu
MAX
MIN
MAX
MIN
4
4
4
1 4
≥ 5
5
≤ 2
2
2 1
Úvod do umělé inteligence 4/12 17 / 32
Algoritmus Alfa-Beta prořezávání
Algoritmus Alfa-Beta prořezávání – vlastnosti
▶ prořezávání neovlivní výsledek ⇒ je stejný jako u minimaxu
▶ dobré uspořádání přechodů (možných tahů) ovlivní efektivitu prořezávání
▶ v případě “nejlepšího” uspořádání časová složitost= O(bm/2)
⇒ zdvojí hloubku prohledávání
⇒ může snadno dosáhnout hloubky 8 v šachu, což už je použitelná
úroveň
označení α − β:
▶ α . . . doposud nejlepší hodnota pro MAXe
▶ β . . . doposud nejlepší hodnota pro MINa
▶ <α, β> . . . interval ohodnocovací funkce v průběhu výpočtu (na
začátku <−∞, ∞>)
▶ minimax . . . V (P) α − β . . . V (P, α, β)
když V (P) ≤ α V (P, α, β) = α
když α < V (P) < β V (P, α, β) = V (P)
když V (P) ≥ β V (P, α, β) = β
Úvod do umělé inteligence 4/12 18 / 32
Algoritmus Alfa-Beta prořezávání
Algoritmus Alfa-Beta prořezávání
function ALPHA-BETA(state) # vrací novou konfiguraci
newpos, _ ← ALPHA-BETA-MAX-VALUE(state, −∞, ∞)
return newpos
function ALPHA-BETA-MAX-VALUE(state , α, β) # vrací konfiguraci a ohodnocení pro MAXe
if TERMINAL-TEST(state) then return None, UTILITY(state)
newval ← −∞; newpos ← None
foreach pos ∈ moves(state) do
val ← ALPHA-BETA-MIN-VALUE(pos, α, β)
if val > newval then
newval ← val; newpos ← pos
if newval ≥β then break # oříznutí
α ← max(α, newval) # zvýšení α
return newpos, newval
function ALPHA-BETA-MIN-VALUE(state , α, β) # vrací ohodnocení pro MINa
if TERMINAL-TEST(state) then return UTILITY(state)
newval ← ∞
foreach pos ∈ moves(state) do
_, val ← ALPHA-BETA-MAX-VALUE(pos, α, β)
if val < newval then
newval ← val
if newval ≤α then break # oříznutí
β ← min(β, newval) # snížení β
return newval
Úvod do umělé inteligence 4/12 19 / 32
Algoritmus Alfa-Beta prořezávání Možnosti vylepšení Minimax/Alpha-Beta
Možnosti vylepšení Minimax/Alpha-Beta
▶ vyhodnocovat pouze klidné stavy (quiescent search)
▶ při vyhodnocování počítat s efektem horizontu – zvraty mimo
prohledanou oblast
▶ dopředné ořezávání – některé stavy se ihned zahazují
bezpečné např. pro symetrické tahy nebo pro tahy hluboko ve stromu
Úvod do umělé inteligence 4/12 20 / 32
Algoritmus Alfa-Beta prořezávání Ohodnocovací funkce
Ohodnocovací funkce
Černý na tahu Bílý na tahu
Bílý ma o něco lepší pozici Černý vítězí
Pro šachy typicky lineární vážený součet rysů
Eval(s) = w1f1(s) + w2f2(s) + . . . + wnfn(s) = n
i=1 wi fi (s)
např. w1 = 9
f1(s) = (počet bílých královen) − (počet černých královen)
. . .
Úvod do umělé inteligence 4/12 21 / 32
Algoritmus Alfa-Beta prořezávání Ohodnocovací funkce – odchylky
Ohodnocovací funkce – odchylky
MAX
MIN
MAX
2
1
1 2
2
2 4
20
1
1 20
20
20 400
chová se stejně pro libovolnou monotónní transformaci funkce Eval
záleží pouze na uspořádání → ohodnocení v deterministické hře funguje
jako ordinální funkce
Úvod do umělé inteligence 4/12 22 / 32
Nedeterministické hry
Nedeterministické hry
náhoda ←− hod kostkou, hod mincí, míchání karet
příklad – 1 tah s házením mincí:
MAX
náhoda
MIN
2 4 7 4 6 0 5 -2
/0.5 /0.5 /0.5 /0.5
3
3
2 4
-1
0 -2
Úvod do umělé inteligence 4/12 23 / 32
Nedeterministické hry Algoritmus Minimax pro nedeterministické hry
Algoritmus Minimax pro nedeterministické hry
expect_minimax . . . počítá perfektní hru s přihlédnutím k náhodě
rozdíl je pouze v započítání uzlů náhoda:
expect_minimax(n) =



utility(n)
pro koncový stav n
maxs∈moves(n) expect_minimax(s)
pro MAX uzel n
mins∈moves(n) expect_minimax(s)
pro MIN uzel n
s∈moves(n) P(s) · expect_minimax(s)
pro uzel náhody n
Úvod do umělé inteligence 4/12 24 / 32
Nedeterministické hry Prořezávání v nedeterministických hrách
Prořezávání v nedeterministických hrách
je možné použít upravené Alfa-Beta prořezávání
MAX
náhoda
MIN
2 2 2 1 0 1 1
/0.5 /0.5 /0.5 /0.5
1.5
[1.5, 1.5]
[2, 2] [1, 1]
[−∞, 0.5]
[0, 0] [−∞, 1]
Úvod do umělé inteligence 4/12 25 / 32
Nedeterministické hry Prořezávání v nedeterministických hrách
Prořezávání v nedeterministických hrách – pokrač.
pokud je možno dopředu stanovit limity na ohodnocení listů →
ořezávání je větší
MAX
náhoda
MIN
2 2 2 1 0
/0.5 /0.5 /0.5 /0.5
1.5
[1.5, 1.5]
[2, 2] [1, 1]
[−2, 1]
[−2, 0] [−2, 2]
Úvod do umělé inteligence 4/12 26 / 32
Nedeterministické hry Nedeterministické hry v praxi
Nedeterministické hry v praxi
▶ hody kostkou zvyšují b → se dvěma kostkami 21 možných výsledků
▶ backgammon – 20 legálních tahů:
hloubka 4 = 20 × (21 × 20)3
≈ 1.2 × 109
▶ jak se zvyšuje hloubka →
pravděpodobnost dosažení zvoleného uzlu klesá
⇒ význam prohledávání se snižuje
▶ alfa-beta prořezávání je mnohem méně efektivní
▶ program TDGammon používá prohledávání do hloubky 2 + velice
dobrou Eval funkci
≈ dosahuje úrovně světového šampionátu
Úvod do umělé inteligence 4/12 27 / 32
Nedeterministické hry Odchylka v ohodnocení nedeterministických her
Odchylka v ohodnocení nedeterministických her
MAX
náhoda
MIN
2 2 3 3 1 1 4 4 20 20 30 30 1 1 400 400
.9 .1 .9 .1 .9 .1 .9 .1
2.1
2.1
2 3
1.3
1 4
40.9
21
20 30
40.9
1 400
chování je zachováno pouze pro pozitivní lineární transformaci funkce Eval
Eval u nedeterministických her by tedy měla proporcionálně odpovídat
očekávanému výnosu
Úvod do umělé inteligence 4/12 28 / 32
Hry s nepřesnými znalostmi Monte Carlo prohledávání
Monte Carlo prohledávání
▶ např. karetní hry → neznáme počáteční namíchání karet oponenta
▶ obvykle můžeme spočítat pravděpodobnost každého možného rozdání
▶ zjednodušeně – jako jeden velký hod kostkou na začátku
▶ prohledáváme ovšem ne reálný stavový prostor, ale domnělý stavový
prostor
▶ program Jack, nejčastější vítěz počítačových šampionátů v bridgi
používá metodu Monte Carlo:
1. generuje 100 rozdání karet konzistentních s daným podáním
2. vybírá akci, která je v průměru nejlepší
V roce 2006 porazil program Jack na soutěži 3 ze 7 top holandských
hráčských párů.
Úvod do umělé inteligence 4/12 29 / 32
Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS)
Monte Carlo Tree Search (MCTS)
kombinace stromového prohledávání a Monte Carlo pro ohodnocení
tahů
opakuj X-krát
výběr expanze simulace zpětná propagace
Úvod do umělé inteligence 4/12 30 / 32
Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS)
Monte Carlo Tree Search (MCTS)
5/9
4/6
0/1 4/5
1/2 3/3
1/1
0/1 1/2
0/1 1/1
4. zpětná propagace
aktualizuje skóre od
nového uzlu směrem
nahoru ke kořeni stromu
Úvod do umělé inteligence 4/12 31 / 32
Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS)
Monte Carlo Tree Search (MCTS) – vlastnosti
výhody:
▶ obecnost – nepotřebuje heuristiku
▶ přizpůsobení – expanduje strom podle simulovaných her
▶ zlepšování – kdykoliv poskytne současný nejlepší odhad
▶ jednoduchost
nevýhody:
▶ přesnost – někdy nenajde nejlepší tahy
▶ rychlost – může potřebovat hodně simulací
v současnosti používána v nejlepších herních strategiích
Úvod do umělé inteligence 4/12 32 / 32