´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Hernı´ algoritmy, prˇedn. 4 Proof number search Lambda search Jan Hric, Petr Baudisˇ NAIL103, ZS
20. listopadu 2013
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
1 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Obsah 1
´ vod U ´ vod U
2
PNS alg. Idea
3
PNS varianty Varianty
4
Depth first PNS DF-PNS
5
Dalsˇ´ı PNS
6
Lambda search Lambda search
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
2 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Proof number search, u´vod • Pouzˇ´ıva´ se typicky pro hleda´nı´ (u´plne´) u´tocˇne´ nebo obranne´ strategie, tj. dokazova´nı´, zda je pozice vyhrana´ • Idea: neˇktere´ veˇtve majı´ mnohem lehcˇı´ (tj. mensˇ´ı) du˚kaz • Hodı´ se usporˇa´danı´ tahu˚ • Uniformnı´ prohleda´va´nı´ do stejne´ hloubky (jako alfabeta) ma´ nevy´hody. Hluboke´, ale veˇtsˇinou vynucene´ veˇtve lze doka´zat snadneˇji. • V mnoha hra´ch, veˇtvı´cı´ faktor nenı´ uniformnı´: • sˇachy: kra´l musı´ uniknout z sˇachu, jinak prohra • da´ma: ska´kat se musı´ (v pravidlech). Taky to zjednodusˇuje pozici. • go: u kamenu˚ ”blı´zko” zˇivota stacˇı´ spocˇı´tat ma´lo u´tocˇny´ch tahu˚,
ostatnı´ jsou neu´cˇinne´ • du˚sledek: omezeny´ veˇtvı´cı´ faktor, zvysˇuje se hloubka prohleda´nı´ Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
3 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS
• PNS: Victor Allis 1994; prˇedtı´m McAllester: conspiracy numbers, min. pocˇet vrcholu˚, ktere´ ”zmeˇnı´” hodnotu korˇene • najde du˚kaz anebo vyvra´cenı´ pro pozici • konstruuje oba stromy soucˇasneˇ (proof, disproof), rozvı´jı´ vzˇdy jeden (nejprˇ´ınosneˇjsˇ´ı) uzel • alg. v pru˚beˇhu vy´pocˇtu neˇktere´ uzly doka´zˇe anebo vyvra´tı´, ale veˇtsˇina uzlu˚ je ve stavu nezna´my´ (...) • alg. koncˇı´, azˇ je korˇen zna´my´, tj. doka´zany´ nebo vyvra´ceny´ • v principu: informovane´ prohleda´va´nı´ do sˇ´ırˇky, nemusı´ najı´t nejmensˇ´ı strom
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
4 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS (2)
• Meˇjme pru˚beˇzˇny´ neu´plny´ strom: jak daleko jsme od doka´za´nı´/vyvra´cenı´? (Vy´sledek nevı´me doprˇedu.) • Najdeme minima´lnı´ (proti-)du˚kazovou mnozˇinu ((dis-)proof set): mnozˇina vrcholu˚, ktere´ musı´ by´t doka´za´ny/vyvr., aby jsme dok./vyvr. korˇen • Princip: optimizmus prˇi neurcˇitosti (bude i v MCTS) • Prˇedpokla´dejme cenu nezna´meho uzlu 1 - to je dolnı´ mez • Du˚kaz ma´me, kdyzˇ ma´ du˚kazova´ mnozˇina velikost 0. (analogicky pro vyvra´cenı´) • Idea: expandujeme vrchol z min. du˚kazove´ a min. vyvracecı´ mnozˇiny (analogie PV)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
5 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Nejslibneˇjsˇ´ı uzel
• Klı´cˇova´ vlastnost PNS: vzˇdy existuje ve stromeˇ nejslibneˇjsˇ´ı uzel (Most-Promising Node, MPN) • MPN je v pru˚niku minima´lnı´ du˚kazove´ a minima´lnı´ vyvracecı´ mnozˇiny • Vyrˇesˇenı´ MPN pomu˚zˇe prˇi du˚kaze nebo vyvracenı´, protozˇe zmensˇ´ı velikost prˇ´ıslusˇne´ minima´lnı´ mnozˇiny pro korˇen • V pru˚beˇhu alg. po rozvinutı´ jednoho MPN velikosti min. mnozˇin typicky vzrostou (kromeˇ koncovy´ch pozic). • Pozn: MPN nenı´ jednoznacˇny´, cozˇ nevadı´.
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
6 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS algoritmus
• Proof number vrcholu n: velikost minima´lnı´ du˚kazove´ mnozˇiny pro n. Optimisticky´ odhad nejkratsˇ´ıho du˚kazu n. • Disproof number: velikost minima´lnı´ vyvracecı´ mnozˇiny pro n. Optimisticky´ odhad nejkratsˇ´ıho vyvra´cenı´ n. • PNS alg.: najdi MPN a expanduj. Prˇepocˇı´tej hodnoty PN a DN. Cykli, dokud nenı´ korˇen doka´zany´ nebo vyvra´ceny´ (a jsou zdroje). • (MPN ska´cˇe mezi podstromy; podobneˇ jako expandovany´ uzel v MCTS)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
7 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Proof a Disproof numbers v listech
• Znacˇenı´: n.pn = proof number vrcholu n • Znacˇenı´: n.dn = disproof number vrcholu n • List, vy´hra: n.pn = 0, n.dn = ∞ • List, prohra: n.pn = ∞, n.dn = 0 • List, nezna´my´: n.pn = n.dn = 1 • Vy´hra a prohra: podle pravidel hry
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
8 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Proof a Disproof numbers ve vnitrˇnı´ch vrcholech
• prˇipomenutı´: pro du˚kaz korˇene potrˇebujeme doka´zat jednoho syna v OR-uzlu a vsˇechny syny v AND-uzlu (OR=MAX) • pocˇı´ta´nı´ cˇı´sel zdola; kdyzˇ ma´me hodnoty v synech, pak • pro OR-uzel je PN minimum z PN-hodnot synu˚ a DN je soucˇet DN-hodnot vsˇech synu˚ • pro AND-uzel dua´lneˇ: PN je soucˇet a DN je minimum • prˇedpoklad: podstromy se rˇesˇ´ı neza´visle (neplatı´ vzˇdy (tj. pouzˇitelne´ na DAG/DCG); zpu˚sobı´ neoptimalitu (azˇ prˇetecˇenı´), ale ne chybny´ vy´sledek)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
9 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Vzorce
Backup fa´ze (terminologie: prˇepocˇı´ta´nı´?), zdola • OR-uzel: n.pn = mins∈synove(n) s.pn P • OR-uzel: n.dn = s∈synove(n) s.dn P • AND-uzel: n.pn = s∈synove(n) s.pn • AND-uzel: n.dn = mins∈synove(n) s.dn • operace s ∞: ∞ + ∞ = ∞ + c = ∞, min(c, ∞) = c...
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
10 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Doka´zane´ a vyvra´cene´ vrcholy
• Doka´zany´ vrchol n: n.pn = 0, n.dn = ∞ • Vyvra´ceny´ vrchol n: n.pn = ∞, n.dn = 0 • Vy´hry a prohry se propagujı´ podle ocˇeka´va´nı´: • Pro OR-uzel syn si je vy´hra: • n.pn = min(s1 .pn, ...si .pn, ...) = min(..., 0, ...) = 0 P P • n.dn = (s1 .dn, ...si .dn, ...) = (..., ∞, ...) = ∞
• Pro AND-uzly dua´lneˇ, tj. prohodı´me .pn a .dn
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
11 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS impl.
• za´kladnı´ impl.: informovaneˇ do sˇ´ırˇky, uzly v pameˇti • pro OR-uzly podle min PN • pro AND-uzly podle min DN
• optimizace: prˇi prˇepocˇı´ta´va´nı´ zdola mu˚zˇeme zastavit, pokud se hodnoty pn a dn nemeˇnı´ (nasta´va´, kdyzˇ vı´c synu˚ meˇlo stejne´ pn, resp. dn). Vy´beˇr MPN spustı´me odtud.
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
12 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Analy´za
• pro jedno rozvinutı´ MPN: (bez optimalizacı´) • Vy´beˇr MPN: hloubka MPN × pru˚m. faktor veˇtvenı´ ´ prava PNs: stejne´ • U • Expanze MPN: pocˇet synu˚ × cena vytvorˇenı´ a inicializace uzlu • Pameˇt’ na iteraci: pocˇet synu˚ × velikost uzlu • Pokud je strom vyva´zˇeny´ a faktor veˇtvenı´ omezeny´ konstantou: hloubka je O(log n) pro n uzlu˚, cˇas O(log n), O(1) pameˇti za iteraci • Celkovy´ cˇas pro strom s n uzly, omezene´ veˇtvenı´: Θ(n log n) pro vyva´zˇeny´ strom, Θ(n2 ) pro degenerovany´ (male´ veˇtvenı´, hluboke´ veˇtve)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
13 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS, komenta´rˇe • Best-first, vhodny´ pro nevyva´zˇene´ stromy • Adaptuje se na hluboke´, ale u´zke´ du˚kazy • Nezarucˇuje kra´tkou vy´hru a maly´ strom du˚kazu - ignoruje cenu dosud vygenerovane´ cˇa´sti • Chova´ se spı´sˇ jako (loka´lnı´) ”cˇisteˇ heuristicke´ prohleda´va´nı´” z jedno-agentove´ho prohleda´va´nı´ stavove´ho prostoru nezˇ jako optima´lnı´ A* (naprˇ. nejlepsˇ´ı rˇesˇenı´ mu˚zˇe by´t ”schovane´” za jednı´m nevynuceny´m, prˇ´ıpravny´m tahem) • Existuje alg. AO*, ekvivalent k A*, pro hleda´nı´ nejlepsˇ´ıch rˇesˇenı´ v AND/OR stromech. (Ale v obecnosti chceme hledat v grafech, typicky acyklicky´ch)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
14 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS, komenta´rˇe 2
• na´rocˇny´ na pameˇt’, vsˇechny uzly jsou v pameˇti (depth first PNS to odstranˇuje) • doka´zane´ a vyvr. stromy lze vypousˇteˇt z pameˇti (pokud si je nechci uschovat/prohlı´zˇet; mu˚zˇu vypsat do logu) • lze vypousˇteˇt nekriticke´ veˇtve • kompromis: pro u´cˇely znovuprohleda´nı´ si pamatuju PN a DN korˇene vypousˇteˇne´ veˇtve • lı´ne´ vypousˇteˇnı´, kdyzˇ docha´zı´ pameˇt’ • (viz alg. SMA*, analogie k A*, ale s omezenou pameˇtı´)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
15 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Pouzˇitı´
• na vyrˇesˇenı´ her: ..., pisˇkvorky • na koncovky; ... naprˇ. shogi (japonske´ sˇachy na 9x9) • pro prakticke´ pouzˇitı´ potrˇeba prˇeformulovat do depth first varianty • neza´visly´ na hrˇe: nepotrˇebuje heuristiku (rˇ´ıdı´ se stromem), ale nepodporuje prˇ´ımou integraci heuristiky (viz) • neˇktere´ hry (naprˇ. Arimaa) nemajı´ vy´znamneˇ ru˚zny´ pocˇet tahu˚ pro
dobre´ a sˇpatne´ pozice
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
16 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS na DAG
vı´c realisticka´ varianta • je dobrˇe definovany´, pocˇı´ta´nı´ hodnot zdola • Proble´m 1: vrchol ma´ vı´c nezˇ jednoho rodicˇe • Proble´m 2: nadhodnocenı´ PN a DN
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
17 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
na DAG, vı´c rodicˇu˚
Proble´m 1: vrchol ma´ vı´c rodicˇu˚ • Prˇepocˇı´ta´nı´ vsˇech? Cena se zvy´sˇ´ı, nejhu˚rˇ z Θ(log n) na Θ(n) na iteraci • Prˇepocˇı´ta´nı´ pouze jednoho? Hodnoty se rozsynchronizujı´ a MPN bude neprˇesneˇ pocˇı´ta´n • Obvykle: prˇepocˇı´ta´nı´ jednoho rodicˇe, ostatnı´ azˇ/pokud jsou zpracova´ny • Otevrˇeny´ proble´m: jde to le´pe?
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
18 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
na DAG, nadhodnocenı´
Proble´m 2: nadhodnocenı´ PN a DN • prˇipomenutı´: PN a DN odhadujı´ min. pocˇet listu˚, ktere´ se musı´ vyrˇesˇit • v DAG se stejny´ list mu˚zˇe zapocˇı´tat po neˇkolika cesta´ch • toto nadhodnocenı´ mu˚zˇe by´t exponencia´lneˇ horsˇ´ı • du˚sledek: lehky´ vrchol vypada´ (velmi) teˇzˇce; na´sledneˇ vrcholy mimo dis/proof set musı´me rozpracovat o (hodneˇ) vı´c nezˇ prˇi teˇsneˇjsˇ´ıch mezı´ch • vyskytuje se v praxi: tsume shogi (u´lohy, (dlouhe´) koncovky), go • mozˇnosti: Proof-set search (Nagai), u´pravy df-pns
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
19 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Heuristicka´ inicializace
• Heuristicka´ inicializace pn a dn (stejneˇ nepocˇı´ta´ nejmensˇ´ı stromy) • Prˇipomenutı´: pn a dn jsou dolnı´ meze pro cenu vyrˇesˇenı´ uzlu • Inicializace hodnotou 1 je naivnı´ • Lze najı´t lepsˇ´ı odhad? Za´visı´ na pozici. Lze pouzˇ´ıt dome´novou znalost, naprˇ. bezpecˇnost kra´le, go: ”vzda´lenost k zˇivotu” • Jsou pn a dn neprˇ´ımo u´meˇrne´? Ne zcela. • Vy´znamne´ zlepsˇenı´ v praxi • Pouze cˇa´stecˇna´ a neprˇ´ıma´ heuristika, nety´ka´ se stromu • Otevrˇena´ ota´zka: lze pouzˇ´ıt strojove´ ucˇenı´? A jak?
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
20 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Vylepsˇenı´: vy´hled jednoho tahu
• Jak dopadne expanze jednoho uzlu? V prˇ´ıpadeˇ, zˇe se ho nepodarˇ´ı vyrˇesˇit. • OR uzel: pn = 1 prˇed a po, dn = 1 prˇed a pocˇtu deˇtı´ po • AND uzel: dn = 1 prˇed a po, pn = 1 prˇed a pocˇtu deˇtı´ po
• v mnoha hra´ch je lacine´ spocˇı´tat nebo odhadnout(!) pocˇet na´slednı´ku˚; go: pocˇet volny´ch pru˚secˇı´ku˚ je dobry´ odhad • inicializujme dn v OR- a pn v AND-uzlu odhadem pocˇtu deˇtı´ • v podstateˇ to znamena´, ma´me vy´hled o 1 tah da´l • Jak tato inicializace interaguje s jiny´mi (naprˇ. dome´novy´mi) metodami?
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
21 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Vyhodnocenı´ listu
okamzˇite´ vs. odlozˇene´ ohodnocenı´; immediate resp. delayed evaluation • Okamzˇite´ ohodnocenı´ : rozvinu list a nove´ syny hned ohodnotı´m • ma´m vı´c informacı´, tj. rˇ´ızenı´ je lepsˇ´ı • Odlozˇene´ ohodnocenı´ : list se ohodnotı´, azˇ je vybra´n jako MPN • za specia´lnı´ch okolnostı´, viz prˇ. • - mu˚zˇe by´t neˇkolik ”u´rovnı´” vyhodnocenı´: 1. rychle´, neprˇesne´; 2. prˇesne´ • Prˇ, v PN2 : PN2 ma´ okamzˇite´ ohodnocenı´, PN1 odlozˇene´ (ale pamatuju si dolnı´ odhady PN a DN)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
22 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Rozsˇ´ırˇenı´ na vı´cehodnotovy´ prˇ´ıpad
naprˇ. vy´hra - remı´za - prohra; go: zˇivot, seki a (ru˚zne´ druhy) ko, prˇesne´ pocˇı´ta´nı´ koncovek • Se´rie boolovsky´ch hleda´nı´; naprˇ. bina´rnı´ nebo sekvencˇnı´ hleda´nı´ • Kazˇde´ hleda´nı´ (pru˚chod) pouzˇ´ıva´ mez pro listy, podobneˇ jako hleda´nı´ s nulovy´m oknem • Otevrˇeny´ proble´m: Jak vyuzˇ´ıt stromy du˚kazu z minuly´ch pru˚chodu˚? • Lehky´ prˇ´ıpad: minule´ hleda´nı´ bylo s prˇ´ısneˇjsˇ´ımi mezemi nezˇ
aktua´lnı´ • Teˇzˇky´ prˇ´ıpad: novy´ cı´l je teˇzˇsˇ´ı
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
23 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Prˇ´ıpadova´ studie: Da´ma/Checkers
ˇ esˇenı´ da´my, Schaffer a kol. • R • Pouzˇitı´ ja´dra (seed) pro generova´nı´ stromu: nejlepsˇ´ı varianty jsou navrzˇeny lidsky´mi experty • Pseudo-du˚kaz: prˇedpokla´dejme, zˇe vsˇechno se (staticky´m) ohodnocenı´m > 150 je vy´hra, < −150 je prohra. Vytvorˇ´ı se strom. • Azˇ se strom s mezı´ ±150 vybuduje, zvy´sˇ´ı se mez na ±200, atd. Azˇ mez dosa´hne ±∞, ma´me u´plny´ du˚kaz.
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
24 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Prˇ´ıpadova´ studie: Da´ma/Checkers (2)
• Pro rozsˇirˇova´nı´ stromu lze pouzˇ´ıt simulace uzˇ hotovy´ch stromu˚ - stejny´ tah/podstrom zkousˇ´ıme u bratra. Navı´c nejlepsˇ´ı tahy uzˇ typicky ma´me: ja´dro, eval. okolo 0. • Listy v pseudodu˚kazu: v koncovka´ch je strom maly´ (resp. pouzˇijeme endgame tabulky) • Listy uvnitrˇ: ma´me proble´m, pokud pseudolist n je ”vy´hra”, ale pozice je rea´lneˇ prohra - pak musı´me najı´t jiny´ du˚kaz otce (nebo vzda´leneˇjsˇ´ıho prˇedchu˚dce) n. Ma´lo cˇaste´, pouze kdyzˇ heur. fce je neprˇesna´ • Specia´lneˇ: v dobry´ch pozicı´ch mu˚zˇu udeˇlat horsˇ´ı tah, abych se dostal do jizˇ doka´zane´ cˇa´sti stromu, resp. na polozˇky TT (kde je eval. okolo 0).
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
25 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Prˇedchu˚dce PNS: Konspiracˇnı´ cˇı´sla pro AB
• navrzˇeno McAllister 1985, 1988 • Kolik vrcholu˚ v Alfabeteˇ se musı´ dohodnout, aby zmeˇnili minimaxovou hodnotu korˇene? • Prˇipomenutı´: PV nenı´ jedinecˇna´, musı´ se zmeˇnit vrcholy ve ”vsˇech” PV (v nichzˇ platı´ val = PV .val) • Zjednodusˇenı´, omezenı´ na boolovsky´ prˇ´ıpad vedlo V. Allise k PNS
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
26 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS: dodatky
• dobre´ a sˇpatne´ prˇ´ıklady pro PNS • spra´va pameˇti a garbage collection • dvoju´rovnˇovy´ PNS - PN 2 (jedno z prvnı´ch vylepsˇenı´) • negamax formulace PNS • u´prava na (iterovane´) prohleda´va´nı´ do hloubky - df-pns • prohleda´va´nı´ s omezenou sˇ´ırˇkou: case study: hex; pouzˇitelne´ obecneˇ, hodı´ se usporˇa´da´nı´ tahu˚ (tj. integrace heur./dome´nove´ info) • (dalsˇ´ı: PN∗ , PDS, λPNS, EF-PN (evaluation function-based) )
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
27 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Chova´nı´ Dobre´ prˇ´ıpady • nerovnomeˇrne´ veˇtvenı´ • rychle´ du˚kazy/vyvra´cenı´ pro neˇktere´ veˇtve (chybu souperˇe rychle potresta´me, ma´me ja´dro pro simulace) • pocˇet tahu˚ koreluje s pravdeˇpodobnostı´ vy´hry; sˇachy: ma´lo obranny´ch tahu˚ (prˇi sˇachu) mu˚zˇe znamenat kra´l v proble´mech Sˇpatne´ prˇ´ıpady • ”vsˇude to vypada´ stejneˇ” • uniformnı´ veˇtvenı´, bez rychly´ch vy´her/proher; prˇ´ıpravne´ tahy • v podstateˇ: drahy´ zpu˚sob pro neinformovane´ prohleda´va´nı´
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
28 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
PNS :-(
Velmi sˇpatne´ prˇ´ıpady • Kdyzˇ PNS aktivneˇ ”zava´dı´ na scestı´” • Prˇ: kra´tky´ du˚kaz potrˇebuje 3 uzly, ale existuje velky´ strom s pn ≤ 2 • Mnoho vynucovacı´ch tahu˚, ktere´ nefungujı´. Funguje pouze ”tichy´” tah. • Go: veˇtvı´cı´ se schody, vsˇechny veˇtve selzˇou, ale ”gheta” (sı´t’) funguje • prˇ. Arimaa: zmrazenı´ nebo branı´ (nepodstatny´ch) figur souperˇe (nejcˇasteˇji je cı´l dosazˇen vlastnı´ volnostı´ (goal) a ne omezenı´m souperˇe (swarm a bez tahu; bez kra´lı´ku˚)) • Q: vztah k proble´mu horizontu?
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
29 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Dvoju´rovnˇovy´ PNS - PN 2 • Prvnı´ PNS beˇzˇ´ı v korˇeni • V listech beˇzˇ´ı druhy´ PNS, omezeny´ (prahem, pameˇtı´): jeho informace se propagujı´ nahoru • Strom druhe´ho PNS se zahazuje - sˇetrˇ´ı to pameˇt’, ale prˇ´ıpadneˇ ply´tva´ zdroji. Naprˇ. se necha´vanı´ synove´ druhotne´ho korˇene v prvnı´m stromu • Nevy´hoda: Korˇenovy´ PNS je cely´ v pameˇti • impl.: pro M = velikost pameˇti a x = # uzlu˚ v hlavnı´m stromeˇ, druhotny´ x−a strom rozvine min(M, 1 + e b ), vhodne´ a, b (b urcˇuje kvocient, a ba´zi) • → druhotne´ stromy rostou zhruba geometrickou rˇadou (”kapita´nsky´ krok”), dı´ky prˇeskakova´nı´ MPN prozkouma´va´me ru˚zne´ veˇtve se zvysˇujı´cı´m se u´silı´m
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
30 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Negamax formulace PNS
• n.φ = n.pn v OR-uzlu, n.dn v AND-uzlu • n.δ = n.dn v OR-uzlu, n.pn v AND-uzlu • Vzorec pro vy´pocˇet: n.φ = min(s1 .δ, ..., sk .δ) P • Vzorec pro vy´pocˇet: n.δ = (s1 .φ, ..., sk .φ) • Du˚sledek: z hlediska vy´pocˇtu nerozlisˇuju OR a AND uzly
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
31 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
´ prava na prohleda´va´nı´ do hloubky U • Depth-first verze PNS: df-pn (na´sledneˇ neˇkolik variant alg.) • Nagai, 2002 • df-pn se chova´ jako PNS, expanduje MPN • pro u´plnost: obecneˇ je vı´c MPN, vy´beˇr z nich se mu˚zˇe lisˇit • za´kladnı´ verze df-pn: pouze iterace v korˇeni
• Snizˇuje opakovane´ expanze vnitrˇnı´ch vrcholu˚ • Pouzˇ´ıva´ TT, chova´ se dobrˇe i s maly´mi tabulkami • df-pn(r): Kishimoto, Mu¨ller: u´prava df-pn pro hry s opakova´nı´m (da´ma, ko v go), tj. DCG, nejen DAG (impl. pocˇı´ta´ min. vzda´lenost od korˇene) • prˇedchu˚dci: PDS: iterativnı´ prohlubova´nı´ (pouze) v korˇeni, tj. zvysˇova´nı´ prahu˚; PN*: zvysˇova´nı´ pouze pro pn; ...
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
32 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Prˇ´ınosy Df-pn
• Efektivita • Pameˇt’ • Opakovane´ iterativnı´ prohlubova´nı´ ve vnitrˇnı´ch vrcholech • Rozsˇ´ırˇenı´ pro vyhnutı´ se dvojite´mu pocˇı´ta´nı´ v DAG • Rozsˇ´ırˇenı´ v df-pn+ umozˇnı´ ocenit hrany, najde optima´lnı´ rˇesˇenı´ v And/Or grafech (jako AO*)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
33 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Df-pn: Idea pro vy´pocˇet Min
• v PNS, hleda´nı´ cˇasto ”uvı´zne” v jednom podstromeˇ na dlouhou dobu • pokud vı´me urcˇit MPN (most proving node), nezajı´majı´ na´s konkre´tnı´ pn a dn cˇı´sla - lze odlozˇit backup • prˇ: n.pn = min(80,70,20,65,50) = 20 • loka´lneˇ, zu˚staneme v podstromeˇ s pn = 20, dokud jeho pn (ostrˇe) neprˇevy´sˇ´ı druhe´ nejmensˇ´ı pn2 mezi syny, tj. 50 v prˇ. • globa´lneˇ, musı´me kontrolovat zda se volba veˇtve nezmeˇnı´ neˇkde vy´sˇ ve stromeˇ. To lze poslat z rodicˇe dolu˚ jako pra´h. • Vzorec pro novy´ pra´h pn: min(parent.pn,pn2 + 1)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
34 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Df-pn: Idea pro vy´pocˇet Sum
• n.pn =
P (s1 .pn,...sk .pn)
• Ma´me pra´h pro vrchol n, n.mezpn • Q: Jak dlouho budeme pracovat v si ? • A: Dokud n.pn ≥ n.mezpn anebo zvy´sˇenı´ v si neprˇevy´sˇ´ı rozdı´l n.mezpn − n.pn. • Vzorec: si .mezpn = si .pn + (n.mezpn − n.pn) • tj. vycˇerpali jsme rezervu, je jedno, kde (z hlediska du˚kazu)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
35 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Opakovane´ iterativnı´ prohlubova´nı´
Multiple Iterative Deepening (MID) • Iterativnı´ ”prohlubova´nı´” v kazˇde´m vrcholu, nejen v korˇeni • Prohloubenı´ znamena´ zvy´sˇenı´ prahu, nikoli hloubky • Vhled: pn a dn se mu˚zˇou i snı´zˇit, nejen zvy´sˇit (kdyzˇ se doka´zˇe syn neˇjake´ho sum-uzlu) • df-pn vola´ z korˇene MID s prahy ±∞ • pouzˇ´ıva´ TT
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
36 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
df-pn+
Mysˇlenky: • Heuristicka´ inicializace v listech: urcˇuje obtı´zˇnost du˚kazu/vyvra´cenı´ pro list • Ohodnocenı´ hran • Meˇrˇ´ı ”dychtivost” zkouma´nı´ tohoto tahu • vysoka´ cena hrany: preferuj plytke´ stromy, vı´c do sˇ´ırˇky • nı´zka´ cena: preferuj tuto veˇtev
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
37 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Sˇetrˇenı´ pameˇtı´
• Beˇzˇ´ı s malou spotrˇebou pameˇti • Prorˇeza´va´nı´ (Nagai): SmallTreeGC, SmallTreeReplacement • SmallTreeGC: GC se prˇedajı´ vrcholy s maly´mi podstromy • SmallTreeReplacement: Hasˇova´nı´ pomocı´ otevrˇene´ adresace, vyzkousˇej pa´r (naprˇ. 10) polozˇek a nahrad’ tu s nejmensˇ´ım stromem • Jina´ mozˇnost: Hasˇova´nı´ se zrˇeteˇzenı´m - ukla´da´ se vı´c nezˇ 1 polozˇka na 1 adresu (i zde potrˇebuje uvolnˇovat) • DC impl.: jak uvolnˇovat globa´lneˇ nejmensˇ´ı? Chceme on-line, jako side-efekt (plovoucı´ mez)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
38 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Weak PNS
• Pokud pracujeme na DAG, PNS nadhodnocuje pn a dn, protozˇe jeden vrchol je zapocˇı´ta´n po neˇkolika cesta´ch • Weak PNS odstranˇuje tuto nevy´hodu: mı´sto sumy pro dn v OR- (a analogicky pn v AND-uzlu) pocˇı´ta´ • dn(n) = max dn(s) + n.nevyresenySyn − 1
pro OR-uzel
• tj. dalsˇ´ı deˇti, kromeˇ nejteˇzˇsˇ´ıho, zapocˇı´ta´ pouze hodnotou 1
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
39 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Focused DFPNS, FDFPNS • PNS prohleda´va´ vsˇechny uzly, neprorˇeza´va´ jako Alfabeta • Kdyzˇ hra neposkytuje vodı´tko, prohleda´va´m i zbytecˇne´ veˇtve (ktere´ nejsou ve vy´sledne´m stromeˇ; typicky na zacˇa´tku) • Prˇ: Hex: ve stejne´ hloubce stejne´ veˇtvenı´; Arimaa: velke´ veˇtvenı´ rˇa´du 104 (protozˇe v tahu ma´m azˇ 4 kroky za sebou) • Idea: omezit sˇ´ırˇku, tj. pocˇet aktivnı´ch synu˚ jednoho uzlu. • Pokud se neˇktere´ho syna podarˇ´ı doka´zat, dalsˇ´ı jesˇteˇ nezpracovany´ syn se stane aktivnı´ • Vyuzˇ´ıva´ usporˇa´da´nı´, preferuje nejlepsˇ´ı uzly (!za oba, tj. nejteˇzˇsˇ´ı, neju´cˇinneˇjsˇ´ı obranu). (Ostatnı´ chci prˇeskocˇit, ne (projı´t a) vyvra´tit) • Q: Integrace s jiny´mi technikami
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
40 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Dalsˇ´ı • PNS ska´cˇe mezi veˇtvemi, to nenı´ kompatibilnı´ s inkrementa´lnı´ u´pravou d.s./stavovy´ch informacı´. Naprˇ. pro Hex se engine bez inkrementa´lnı´ho pocˇı´ta´nı´ 2x spomalil • Lambda DFPN, LDFPN - kombinace PNS a lambda stromu˚: pomocı´ PNS rˇesˇ´ı λi -strom pro nejmensˇ´ı i • 1 + trick, Lew Lukasz 2006: prahy v DFPNS zveˇtsˇuju geometrickou rˇadou, to zmensˇuje pocˇet prˇeskoku˚ mezi podstromy, ktere´ se prˇ´ıpadneˇ nevejdou do TT • (pouzˇitelne´ i v MCTS: spocˇı´tat pevnou cˇa´st (naprˇ. 1/10) pocˇtu
na´vsˇteˇv v akt. uzlu a neopousˇteˇt uzel, dokud se nevykona´ asponˇ tolik playoutu˚ v podstromeˇ) • Q: srovna´nı´ s SMA* (Simplified Memory-Bounded A*) - explicitneˇ zahazuje nejme´neˇ slibne´ vrcholy a pamatuje si dolnı´ odhady uvolneˇny´ch vrcholu˚ Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
41 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Lambda Search • Allis a kol. 1996, Thomsen 2000, Cazenave 2002 • Idea: pouzˇ´ıvame hrozby ru˚zne´ho rˇa´du n ˇ a´d hrozby neforma´lneˇ: kolikra´t mu˚zˇe souperˇ vynechat tah (tj. null • R move/pas) nezˇ prohraje • V λn -stromeˇ se prohleda´vajı´ pouze hrozby rˇa´du n, bez ohledu na hloubku stromu. • Pokud ve vrcholu nenı´ λn -tah, vrchol je listem, prohrany´m (pro hra´cˇe na tahu) • Rozlisˇujeme u´tocˇnı´ka, ktery´ hraje v korˇeni a snazˇ´ı se o splneˇnı´ cı´le, a obra´nce (attacker, defender) - nesymetricke´ role • prˇ´ıklad pro prˇedstavu: pisˇkvorky
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
42 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Lambda Strom • Znacˇenı´: λn =1, pokud u´tocˇnı´k mu˚zˇe vyhra´t v dane´ pozici pomocı´ hrozby rˇa´du n, jinak λn =0 • Rekurzivnı´ definice λn -stromu, podle hloubky: ´ speˇsˇny´ λ0 -strom pro u´tocˇnı´ka: obsahuje jeden λ0 -tah, ktery´ splnı´ cı´l • U • λn -strom obsahuje λn -tahy, listy jsou prohrane´ pro hra´cˇe na tahu (tj. nema´ λn -tah) • λna -tah pro u´tocˇnı´ka je tah, zˇe pokud obra´nce pasuje, existuje λi -strom s λi =1 pro 0 ≤ i ≤ n − 1. Tj. u´tocˇnı´k hrozı´ vyhra´t hrozbou nizˇsˇ´ıho rˇa´du • λnd -tah pro obra´nce je tah, zˇe po neˇm neexistuje zˇa´dny´ λi -strom s λi =1 pro 0 ≤ i ≤ n − 1. Tj. obra´nce odvra´til vsˇechny hrozby nizˇsˇ´ıho rˇa´du • Prˇ: Go: schody: λ1a - a λ1d -tahy; prˇi neu´speˇsˇny´ch schodech v listeˇ neex. dalsˇ´ı λ1a -tah Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
43 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Lambda Search
• Du˚sledek: λn tahy jsou urcˇeny λn−1 -prohleda´va´nı´m. • Obvykle je λn−1 strom mnohem mensˇ´ı nezˇ λn -strom • Na´sledneˇ λ-prohleda´va´nı´ prorˇezˇe tahy podle λ u´rovneˇ u´cˇinneˇ, s maly´m u´sily´m
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
44 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Pouzˇitelnost
• λ-search je nesymetricky´, cı´l je pro u´tocˇnı´ka • pouzˇitelne´ na globa´lnı´ i loka´lnı´ cı´le • integrovatelne´ se znalostmi pro konkre´tnı´ hru: Hex, Havannah, Pisˇkvorky, Go • • • •
(vsˇe jsou nepohyblive´, ”spojovacı´” hry) ˇra´d hrozby se da´ odhadnout z pozice (pisˇkvorky, svobody v go) i (ne-)relevantnı´ u´tocˇne´ a obranne´ tahy (nejen ”nepohybliva´”) hra dovoluje hledat mı´sta, ktere´ jsou relevantnı´ (prˇ: tahy dvojı´ho u´cˇelu) ´ /O potrˇebujeme opacˇne´ meze odhadu) • (impl: pro vyloucˇenı´ tahu˚ U
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
45 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Vlastnosti
• Vlastnosti, vztahy: • Pokud λn =1, pak λk =1 pro n ≤ k • Pokud λn =0, pak λi =0 pro 0 ≤ i ≤ n • Korektnost: • Vy´sledek λn =1 je korektnı´, pokud hra ma´ tah pas nebo zugzwang nenı´ cı´lem hry/u´lohy (!, neforma´lneˇ) • λn =0 znamena´, zˇe rˇesˇenı´ neexistuje anebo je na vysˇsˇ´ı u´rovni hrozby n0 > n
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
46 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Lambda Search, Doplnˇky
• Zobecneˇne´ hrozby: Cazenave 2002 - pocˇı´ta´ uzly na jednotlivy´ch u´rovnı´ch • Simulace: Kawano 1996 (PNS search) - vyuzˇ´ıva´nı´ informacı´ z prohledany´ch cˇa´stı´ stromu (!) • (α − β jako driver pro PNS)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
47 / 48
´ vod U
PNS alg.
PNS varianty
Depth first PNS
Dalsˇ´ı PNS
Lambda search
Dual Lambda Search
• Dual lambda search: Soeda 2005 (µ-search): (tsume shogi) • motivace: pu˚vodnı´ λ-search je nesymetricky´. Souperˇ ma´ taky cı´l • Idea: Vyhra´va´ ten, kdo ma´ hrozbu nizˇsˇ´ıho rˇa´du - hrozby souperˇe musı´m nejdrˇ´ıv odvra´tit • λn -stromy u´tocˇnı´ka nesmı´ obsahovat u´speˇsˇny´ strom (ostrˇe) nizˇsˇ´ıho rˇa´du pro souperˇe • Prˇi prohleda´vanı´ musı´m odvracet hrozby souperˇe: sˇirsˇ´ı strom • Prˇi rovnosti rˇa´du hrozeb vy´hoda tempa. Prˇ: pisˇkvorky; go: semeai (boj)
Jan Hric, Petr Baudisˇ ( NAIL103, ZS )
Hernı´ algoritmy, prˇedn. 4
20. listopadu 2013
48 / 48
