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