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 x 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í x 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 Ul = 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 =4> zřejmě nenajdeme optimální řešení —>► hledáme lokálně optimální řešení Hry vs. Prohledávání stavového prostoru Hry a Ul - historie Hry a Ul - 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 Ul - aktuální výsledky Hry a Ul - aktuální výsledky ► Reversi/Othello - od 1980 světoví šampióni odmítají hrát s počítači, protože stroje jsou příliš dobré. Reversi pro dva hráče na desce 8x8 -snaží se mezi své dva kameny uzavřít soupeřovy v řadě, která se přebarví. Až se zaplní deska, spočítají se kameny. ( ) ( ) \___,' • • z"-"\ ( ) \___,' • • z"-"\ ( ) ( ) \_/ • • z"-"\ ( ) • ► dáma - 1994 program Chinook porazil světového šampióna Marion Tinsley. Používal úplnou databázi tahů pro < 8 figur (443 748 401247 pozic). Úvod do umělé inteligence 4/12 4/32 Hry vs. Prohledávání stavového prostoru Hry a Ul - aktuální výsledky Hry a Ul - aktuální výsledky ► šachy - 1997 porazil stroj Deep Blue světového šampióna Gary Kašparova V-/2\2y2. 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 šampióna 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. A A A 5 4 3 2 g Úvod do umělé inteligence 4/12 5/32 Hry vs. Prohledávání stavového prostoru Hry a Ul - aktuální výsledky Hry a Ul - 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) 3 2 1 "* N ' /' V- \\ 4» ' /' *■ /■ /; /■ 8 7 6 5 4 3 2 g h Úvod do umělé inteligence 4/12 6/32 Hry vs. Prohledávání stavového prostoru Hry a Ul - aktuální výsledky Hry a Ul - aktuální výsledky ► Go - do roku 2008 světoví šampióni 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 9x9, nižší úroveň i na 19x19). březen 2016 - program AlphaGo porazil lidského velmistra Lee Sedola na normální desce 19x19 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 Ul - aktuální výsledky Hry a Ul - 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 deter m in i st i c ké s náhodou perfektní šachy, dáma, Go, backgammon, znalosti Othello monopoly nepřesné bridge, poker, scrabble znalosti Ú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) a MIN (V) 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: MAX (X) MIN (O) MAX (X) MIN (O) X 0 X X o X X 0 X koncové stavy 0 X 0 0 X X 0 X X 0 X 0 0 utilitární funkce -1 0 +1 Úvod do umělé inteligence 4/12 11 / 32 Algoritmus Minimax Algoritmus Minimax Hráč max (Za) musí prohledat herní strom pro zjištění nejlepšího tahu proti hráči min (V) —>> zjistit nejlepší hodnotu minimax - zajišťuje nejlepší výsledek proti nejlepšímu protivníkovi Hodnota minimax(n) = < utility(ft), pro koncový stav n maxsemoves(n) Hodnota minimax(s), pro max uzel n (n) Hodnota minimax(s), mm se moves 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 util.funkce 3 12 8246 14 52 Ú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 <--oo; newpos <— None foreach pos G 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 Ml Na if TERMINAL-TEST(state) then return UTILITY(state) newval <— oo foreach pos G moves(state) do _, val <(— MAX-VALUE (pos) if val < newval then newval ^— \/a/ 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álni proti optimálnímu oponentovi časová složitost 0(bm) prostorová složitost O(bm), prohledávání do hloubky šachy ... b « 35, m « 100 =4> 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 v Algoritmus Minimax Časové omezení Časové omezení předpokládejme, že máme 100 sekund + prozkoumáme 10 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ů =4> Alfa-Beta procedura je efektivnější variantou minimaxu MAX MIN MAX MIN Algoritmus Alfa-Beta prořezávání Algoritmus Alfa-Beta prořezávání - vlastnosti ► prořezávání neovlivní výsledek =4> 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= 0{bm/2) =4> zdvojí hloubku prohledávání =4> může snadno dosáhnout hloubky 8 v šachu, což už je použitelná úroveň označení a — ß\ ► a... doposud nejlepší hodnota pro MAXe ► ß... doposud nejlepší hodnota pro MINa ► ... interval ohodnocovací funkce v průběhu výpočtu (na začátku <—oo,oo>) ► minimax... V(P) a — ß ... V(P, a, ß) když V(P)ß V{P,a,ß) = ß 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(staře, -oo, oo) return newpos function ALPHA-BETA-MAX- VALUE (state, a, j3) # vrací konfiguraci a ohodnocení pro MAXe if TERMINAL-TEST(sřaře) then return None, UTILITY(sřaře) newval <--oo; newpos <— None foreach pos £ moves(sřaře) do val <- ALPHA-BETA-MIN-VALUE(pos, a, /3) if val > newval then newval ^— val; newpos ^— pos if newval >/3 then break # oříznutí a ^— max(c»i, newval) # zvýšení a return newpos, newval function ALPHA-BETA-MIN-VALUE( state, a, /3) # vrací ohodnocení pro MINa if TERMINAL-TEST(sřaře) then return UTILITY(sřaře) newval <— oo foreach pos £ moves(sřaře) do _, val ► 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 i— hod kostkou, hod mincí, míchání karet příklad - 1 tah s házením mincí: MAX náhoda MIN 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: utility(ft) pro koncový stav n maxsemoves(n) expect_minimax(s) pro MAX uzel n minsGm0ves(n) expect_minimax(s) pro MIN uzel n Esemoves(n) P{s) • expect_minimax(s) pro uzel náhody n expect_minimax(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 0 Ú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 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 x (21 x 20)3 « 1.2 x 109 ► jak se zvyšuje hloubka —>► pravděpodobnost dosažení zvoleného uzlu klesá =4> 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 A 2.1 A 40.9 2 2 3 3 1 1 4 4 20 20 30 30 1 1 400 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 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 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 k. * simulace k. j ŕ < zpětná propagace Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS) Monte Carlo Tree Search (MCTS) 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