Střední hra v go na 9x9
Zápočtový projekt z
Neuronových sítí
Tomáš Kozelek & Dominik Franěk
Co je go?
Nejstarší a nejsložitější desková hra Pochází z Číny, cca 4000 let stará Hraje se na desce 19x19, tj. 361 polí Stupeň komplexnosti 36 ( šachy 20 ) Populárnější než šachy
Zatím naprosto mimo možnosti počítačů Obrovský stavový prostor – nejde propočítat Vyžaduje velkou kreativitu – v tom se AI člověku
zdaleka nevyrovná Nejlepší program cca stupeň 12 (8. kyu)
Pravidla go Jednoduchá pravidla Efektivita vs. riziko
Ukázka partie
Rozehraná hra Konec
Jak může hrát počítač go? Hru je nutné rozložit na části a každou
řešit jiným přístupem Konvenčně
Joseki (zahajovací sekvence v rozích) Databáze tvarů Život skupin
AI Rozeznání tvarů Propojení skupin Určení vlivu a směru hry Rozeznání kritických oblastí
Vliv v programu TurboGo
Co jsme zavrhli
Síť se bude učit jen pozice->tah Ukáže x nejlepších tahů
Složitá chybová funkce
Ohodnotí každé pole „zajímavostí“ pro tah Šlo by to taky
S předzpracováním vstupu Bude umět odůvodnit své tahy
Vyžaduje ruční zpracování
Co jsme zvolili a proč
Učení sítě na některou z podůloh by vyžadovalo velmi složité předzpracování dat
Vyzkoušeli jsme nejjednodušší přístup - pozice -> tah v rozmezí 8.-12. tahu (pozice je dostatečně jednoduchá)
První úvahy
Výhody NN je ideální na rozeznávání tvarů Měla by být schopná hrát zajímavé tahy i
bez znalosti pravidel
Nevýhody Síť netuší co je živá skupina V partii je víc dobrých tahů, uvidí jen jeden
Co jsme očekávali
Pozitivní Dobré navrhované tahy Poměrně snadné hodnocení
Obavy Bude hrát pořád do středu – průměr tahů
Stalo se při malém počtu skrytých neuronů (30-30)
Příliš velká síť – 9x9 vstupů + skryté n. Síť navrhne dobrý tah, ale jiný než byl v partii, což
se pozná jen ručně
Vstupní partie
partie ve formátu SGF ( zápis partie ) přibližně 1600 partií pokročilých hráčů ( věnují se
hře několik let ) ze serveru Little Golem problém s ,,ortogonalitou“ partií - ve velmi
podobných ( příp. stejných pozicích ) hráli různí hráči ( strategicky ) různé tahy
příklad partie ve formátu sgf: (;FF[4]PB[tasuki]PW[Xaver]KM[5.5]SZ[9]B[ee];W[ff
];B[ef];W[fe];B[fd];W[gd];B[gc];W[ed];B[fc];W[dd];B[fg];W[gg];B[eg])
Preprocesing
Bash script/awk simulace jednotlivých tahů dle pravidel Go zmenšení pozice z 9x9 na 7x7 odstraněním 1. linky
( v zahájení a střední hře nepodstatná ) transformace pozice do řetězce 0, 1, -1 odstranění redundantních a neplatných pozic výstup: matice pozic a odp. matice správných tahů
výsledek preprocesingu pro 1 partii: 3 7;0 0 0 0 0 0 0 0 1 0 0 0 0 -1 1 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 -1 -1 0 0 0 1 -1 0 0 1 0 0 -1 0 0 0 0 0
Algoritmus
Rozdělení vstupů asi 7000 pozic rozděleno na učící (7/10) a testovací
množinu Učení na různých architekturách vrstevnatých sítí
varianty algoritmu Back Propagation výstup sítě je souřadnice doporučeného tahu
Testování definované ohodnocení výstupu sítě ( ,,pošťácká metrika“ )
umožňuje statistické určení úspěšnost rychlé ohodnocení, ale vůči ,,lidskému posouzení“ nepřesné
( dobré tahy v jiné části desky nežli tah v partii jsou ohodnoceny špatně )
Ohodnocení doporučeného tahu
neplatné tahy mimo desku, na obsazenou pozici ~ 0 b.
ohodnocení platných tahů pošťáckou metrikou správný tah ~ 5 b., vzdálenost 1 ~ 4 b., …
vzdálenost >= 5 ~ 0 b.
úspěšnost sítě získaných bodů / možných bodů ( vyjádřeno v procentech )
Architektury použité VNS
Vyzkoušeno 6 různých architektur algoritmy učení: trainlm (mnoho paměti), trainrp
(rychlý ale potřebuje stovky epoch) dvou až čtyř vrstevné sítě různé parametry učení, různé cíle příklady:
[50,40,2], {tansig, tansig, purelin}, trainlm, l=0.05, g=0.07 [30,30,15,2], {tansig, tansig, tansig, purelin}, trainrp,
l=0.03, g=0.05
Statistické výsledky I
Úspěšnost velmi podobné výsledky všech architektur díky použití učícího algoritmu trainrp ( pomalejší
konvergence, ale menší paměťové nároky než trainlm ) dosažení horších hodnot MSE (okolo 0.5) než byly požadované hodnoty (okolo 0.01 – 0.05)
95% úspěšnost na známých datech při učení na menší množině ( okolo 2000 pozic )
55% úspěšnost na známých datech při učení na velké množině ( 4500 pozic ) ( neortogonalita )
30% úspěšnost dle definovaného ohodnocení na testovacích (neznámých) datech při 4500 pozic na učení a 1800 na testování
Statistické výsledky II
Výsledky na arch. [30,30,15,2] trainrp 4500 učících pozic, 1888 neznámých test. pozic >>distance 0 --> 73 results >>distance 1 --> 146 results >>distance 2 --> 218 results >>distance 3 --> 283 results >>distance 4 --> 207 results >>distance >=5 --> 961 results >>>Out of bounds 131 >>>Stone already there 577 >>>Efficiency: 30%:
Myšlenky do budoucna
Zamezit nekorektním tahům znatelné procento neúspěchu tvoří kameny hrané
na obsazené pozice/na pozice mimo desku vylepšit operátor porovnání s požadovaným
výstupem při učení aby zohledňoval nekorektní tahy Lépe připravit vstupní množinu
pokusit se vynutit ortogonalitu vstupních pozic případně ručně předzpracovat partie ( označit
živé/mrtvé skupinky, oblasti vlivu, více možných tahů – náročné, ale síť má více informací o pozici => může lépe simulovat tahy