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/33 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 9 kooperativní x soupeřící multiagentní prostředí (MP) Úvod do umělé inteligence 4/12 2/33 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 a 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í Úvod do umělé inteligence 4/12 2/33 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ů o 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í Úvod do umělé inteligence 4/12 3/33 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ů o 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/33 Hry vs. Prohledávání stavového prostoru Hry a Ul - aktuální výsledky Hry a Ul - aktuální výsledky SliDo 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. ( ) ( ) \__y • • /"x ( ) \__y • • ✓™\ ( ) ( ) • • ^™\ ( ) • • 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/33 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ů. abcdefgh 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. abcde f g h Úvod do umělé inteligence 4/12 5/33 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). a b c d e f g h Úvod do umělé inteligence 4/12 6/33 Hry vs. Prohledávání stavového prostoru Hry a Ul - aktuální výsledky Hry a Ul - aktuální výsledky o 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/33 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 3 hodinách učení Úvod do umělé inteligence 4/12 8/33 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 19 hodinách učení Úvod do umělé inteligence 4/12 8/33 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/33 Obsah Q Hry vs. Prohledávání stavového prostoru o Hry a Ul - historie 9 Hry a Ul - aktuálni výsledky • Typy her • Hledání optimálního tahu • Časové omezení • Možnosti vylepšení Minimax/Alpha-Beta • Ohodnocovací funkce • Ohodnocovací funkce - odchylky O Nedeterministické hry • Algoritmus Minimax pro nedeterministické hry 9 Prořezávání v nedeterministických hrách • Nedeterministické hry v praxi • Odchylka v ohodnocení nedeterministických her Úvod do umělé inteligence 4/12 9/33 deter m in isti 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 10 / 33 Hry vs. Prohledávání stavového prostoru Hledání optimálního tahu Hledání optimálního tal 1U 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 11 / 33 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) koncové stavy utilitární funkce X o X X 0 X X o X o X o 0 X X o X X 0 X o 0 -1 0 +1 Úvod do umělé inteligence 4/12 12 / 33 Algoritmus Minimax Algoritmus Minimax Hráč MAX (A) 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(fl), pro koncový stav n maxsemoves(n) Hodnota minimax(s). pro MAX uzel n minsGmoves(n) Hodnota minimax(s), pro MIN uzel n Úvod do umělé inteligence 4/12 13 / 33 Algoritmus Minimax Algoritmus Minimax - pol krač. příklad - hra jen na jedno kolo = 2 tahy (půlkola) Úvod do umělé inteligence 4/12 14 / 33 Algoritmus Minimax Algoritmus Minimax - po krač. příklad - hra jen na jedno kolo = 2 tahy (půlkola) MAX J\ MIN MAX util.funkce Úvod do umělé inteligence 4/12 14 / 33 Algoritmus Minimax Algoritmus Minimax - po krač. příklad - hra jen na jedno kolo = 2 tahy (půlkola) MAX J\ MIN MAX util.funkce Úvod do umělé inteligence 4/12 14 / 33 Algoritmus Minimax Algoritmus Minimax - po krač. příklad - hra jen na jedno kolo = 2 tahy (půlkola) MAX A 3 MIN MAX util.funkce Úvod do umělé inteligence 4/12 14 / 33 Algoritmus Minimax Algoritmus Minimax - po krač. příklad - hra jen na jedno kolo = 2 tahy (půlkola) MAX MIN MAX util.funkce Úvod do umělé inteligence 4/12 14 / 33 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 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 nevwa/ <— \/a/ return nevwa/ Úvod do umělé inteligence 4/12 15 / 33 Algoritmus Minimax Algoritmus Minimax - vlastnosti úplnost optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 4/12 16 / 33 Algoritmus Minimax Algoritmus Minimax - vlastnosti úplnost úplný pouze pro konečné stromy optimálnost časová složitost prostorová složitost Úvod do umělé inteligence 4/12 16 / 33 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 prostorová složitost Úvod do umělé inteligence 4/12 16 / 33 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 0(bm) prostorová složitost Úvod do umělé inteligence 4/12 16 / 33 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 0(bm) prostorová složitost O(bm), prohledávání do hloubky Úvod do umělé inteligence 4/12 16 / 33 Algoritmus Minimax Algoritmus Minimax - vlastnosti úplnost optimálnost časová složitost úplný pouze pro konečné stromy je optimální proti optimálnímu oponentovi 0(bm) prostorová složitost 0{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 Úvod do umělé inteligence 4/12 16 / 33 Časové omezení v Algoritmus Minimax Č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 tesť) - např. hloubka nebo hodnota ohodnocovací f u n kce nahradí koncový test Úvod do umělé inteligence 4/12 17 / 33 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 Úvod do umělé inteligence 4/12 18 / 33 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 Úvod do umělé inteligence 4/12 18 / 33 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 Úvod do umělé inteligence 4/12 18 / 33 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 Úvod do umělé inteligence 4/12 18 / 33 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 Úvod do umělé inteligence 4/12 18 / 33 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 Úvod do umělé inteligence 4/12 18 / 33 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 Úvod do umělé inteligence 4/12 18 / 33 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í 9 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ň SliDo Úvod do umělé inteligence 4/12 19 / 33 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í 9 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ň SliDo označení a — j3\ • a... doposud nejlepší hodnota pro MAXe 9/3... doposud nejlepší hodnota pro MINa • ... interval ohodnocovací funkce v průběhu výpočtu (na začátku <—oo,oo>) • minimax... V(P) a — (3 ... V(P, a, (3) když V(P)/3 V(P,a,f3) = f3 Úvod do umělé inteligence 4/12 19 / 33 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, -oo, oo) return newpos function ALPHA-BETA-MAX- VALUE( state, a, (3) # 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řate) 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(oi, newval) # zvýšení a return newpos, newval function ALPHA-BETA-MIN-VALUE( state, a, (3) # vrací ohodnocení pro MINa if TERMINAL-TEST(state) then return UTILITY(sřaře) newval <— oo foreach pos £ moves(sřate) do _, val <- ALP HA-BETA-MAX-VALUE (pos, a, (3) if val < newval then newval <— val if newval
    ► ohodnocení v deterministické hře funguje jako ordinální funkce Úvod do umělé inteligence 4/12 23 / 33 Nedeterministické hry Nedeterministické hry náhoda <— hod kostkou, hod mincí, míchání karet Úvod do umělé inteligence 4/12 24 / 33 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 2474605 -2 Úvod do umělé inteligence 4/12 24 / 33 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 m3xsGmoves(A?) expect_minimax(s) pro MAX uzel n minsemoves(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 25 / 33 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 Úvod do umělé inteligence 4/12 26 / 33 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 Úvod do umělé inteligence 4/12 26 / 33 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í Úvod do umělé inteligence 4/12 26 / 33 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í Úvod do umělé inteligence 4/12 26 / 33 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 Úvod do umělé inteligence 4/12 26 / 33 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 Úvod do umělé inteligence 4/12 26 / 33 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 Úvod do umělé inteligence 4/12 26 / 33 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 Úvod do umělé inteligence 4/12 26 / 33 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 Úvod do umělé inteligence 4/12 26 / 33 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 Úvod do umělé inteligence 4/12 27 / 33 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 Úvod do umělé inteligence 4/12 27 / 33 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 Úvod do umělé inteligence 4/12 27 / 33 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 Úvod do umělé inteligence 4/12 27 / 33 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 Úvod do umělé inteligence 4/12 27 / 33 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 Úvod do umělé inteligence 4/12 27 / 33 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 Úvod do umělé inteligence 4/12 27 / 33 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 28 / 33 Nedeterministické hry Odchylka v ohodnocení nedeterministických her 2 2 3 3 1 1 4 4 20 20 30 30 1 1 400 400 Úvod do umělé inteligence 4/12 29 / 33 Nedeterministické hry Odchylka v ohodnocení nedeterministických her 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 Úvod do umělé inteligence 4/12 29 / 33 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 Úvod do umělé inteligence 4/12 30 / 33 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 Úvod do umělé inteligence 4/12 30 / 33 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 30 / 33 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ů Úvod do umělé inteligence 4/12 31 / 33 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 31 / 33 Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS) Monte Carlo Tree Search (MCTS) MCTS po 8 simulovaných hrách (4 výhry, 4 prohry) Úvod do umělé inteligence 4/12 32 / 33 Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS) Monte Carlo Tree Search (MCTS) 1. výběr nalezení cesty k listu, který má vysokou pravděpodobnost výhry je vhodné střídat strategie vytěžení (exploitation) a průzkum (exploration) Úvod do umělé inteligence 4/12 32 / 33 Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS) Monte Carlo Tree Search (MCTS) 8 O/i I 3/a ) 0 2. expanze vybraný uzel se expanduje - doplní se možné tahy mezi následníky se opět jeden zvolí Úvod do umělé inteligence 4/12 32 / 33 Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS) Monte Carlo Tree Search (MCTS) 3. simulace z vybraného nového listu se odehraje simulovaná hra až do konce - do výhry nebo prohry tato fáze se dá také nahradit sofistikovaným určením hodnoty pozice -např. výpočtem neuronovou sítí Úvod do umělé inteligence 4/12 32 / 33 Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS) 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 32 / 33 Hry s nepřesnými znalostmi Monte Carlo Tree Search (MCTS) Monte Carlo Tree Search (MCTS) - vlastnosti výhody: nevýhody: Úvod do umělé inteligence 4/12 33 / 33 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: Úvod do umělé inteligence 4/12 33 / 33 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í Úvod do umělé inteligence 4/12 33 / 33 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 33 / 33