Xobot: umělá inteligence na herně

Xobot: umělá inteligence na herně

Byl jsem požádán Specsem v diskuzi na herně www.piskvorky.net, jestli bych nemohl napsat krátké populárně naučné povídání o Xobotovi. Výsledek ne úplně krátký je níže. Budu se snažit vynechat technické detaily, protože to je téma na samostatný článek nebo seriál.

Možná někteří z vás zaregistrovali, že na serveru piškvorky.net se pravidelně a vytrvale objevuje hráč Xobot. Jak název napovídá, jedná se o složeninu z piškvorkových symbolů XO a slova bot. Xobot propojuje uživatelské prostředí v herně s existujícím herním brainem Embryo. Má na starosti komunikaci s hráčem a hracím stolem na straně jedné, a zároveň, když potřebuje hráči odpovědět na tah, zeptá se připojené umělé inteligence, který tah má zahrát, na straně druhé.

Za možnost zahrát si s robotem i v době, kdy v herně nejsou soupeři, poděkujte Olšavě, která odvedla veliký kus práce při programování webu.

Nyní přejdu k té části Xobota, která má na starosti vymýšlení tahů, kde se cítím povolanější k povídání.

Gomocup intro

Můj první piškvorkový program byl napsaný kdysi dávno ještě nádherně naivně v Basicu. Pak dlouhou dobu nic a asi až před dvěma lety jsem se dostal přes svého synovce ke Gomocupu. Tento turnaj má za sebou již 19 ročníků a podle mých vědomostí se jedná o nejprestižnější piškvorkový turnaj počítačových programů (brainů) na světě.

Co takový brain musí umět? Vlastně skoro nic: rozumět několika povinným povelům, nespotřebovat víc času a paměti, než je povoleno, a pokud chce vyhrávat, tak i vracet co nejlepší tah.

A co naopak umět nemusí? Nepotřebuje žádná zahájení, protože se hraje tak, že špičkoví hráči připraví vyrovnaná zahájení a brainy hrají stejnou pozici dvakrát s otočenými barvami. Zde je největší odchýlení od herní praxe, brain je snadno porazitelný, když nezná žádnou teorii. Pokud má dostatek času, tak je schopen tento handicap částečně kompenzovat. Xobot používá pro zahájení přednastavená schémata od Peroxida. Embryo o nich nemá tušení.

Zrod Embrya

Rozhodl jsem se, že se turnaje zúčastním a idealisticky jsem si představoval, jak to všem nandám, jak jsem dobrej programátor. Zbrusu nový projekt začal v jazyce C, později v C++, a pracovní název Embryo pro první prototyp už programu zůstal. Série výher se neustále ne a ne dostavit, dostával „kanára“ od všech brainů, které jsem zkoušel. To byl okamžik, kdy jsem se na Emryo chtěl vykašlat, ale pak jsem si řekl: "živíš se přece programováním a nedokážeš napsat ani blbý piškvorky?". Hledal jsem někde inspiraci, jenže piškvorkových podkladů bylo málo a ty, na které jsem narazil, mě zavedly špatným směrem. Naštěstí jsem narazil na open source šachový program Stockfish, kde jsem našel systém, jak testovat a vůbec jak se dělá úspěšný program. Stockfish přitom vede všechny šachové žebříčky. Části kódu jsem použil jako ideový vzor (čti opsal jsem je) v úpravě pro piškvorky. Po malých krůčcích se hra zlepšovala, podařilo se dokonce občas něco vyhrát. Po vylepšení postupu při hledání chyb, kdy bylo důležité si sám sobě připustit, že bych vůbec nějakou mohl udělat, se výkonnost dostala na úroveň, která už dávala šanci neudělat ostudu.

Jak Embryo uvažuje?

Z nadhledu je činnost programu prostá: dostane pozici na desce a v daném čase má vyplivnout nejlepší možný tah. Realizace je nepatrně složitější, ačkoliv odpověď na otázku z nadpisu je snadná. Embryo totiž neuvažuje vůbec, takže nečekejte žádnou převratnou myšlenku, umělou inteligenci či umělý mozek. Program pro slušnou herní úroveň musí akorát co nejlépe zajišťovat v tomto pořadí tyto tři požadavky: 1) nemít logické chyby, 2) fungovat efektivně, 3) tušit, jakou hru to hraje. Tím dávám současně i odpověď na dotaz, jak je možné, že nepišvorkář vytvoří slušně hrající program. Stačilo mi pouze vědět, co je pětka, čtyřka, vidlička a že se hráči střídají, což jsem ale věděl už ze školy.

Program dělá neustále dokola tři věci: nejprve vyrobí seznam tahů, které postupně provádí a pozici následně ohodnotí.

Seznam tahů vypadá jako nejjednodušší část programu. Stačí přece udělat jen seznam všech možných tahů. V mém případě je to však největší zásobárna chyb. Pokud by nějaký tah chyběl, program bude „slepý“, tedy buď přehlédne svoji dobrou možnost a nenajde nejsilnější pokračování, nebo neuvidí nějaký tah soupeře, nebude s ním počítat a vyrobí těžko pochopitelný blundr. Pokud vygeneruje naopak více tahů, než je nutné, nevede to sice přímo k prohře, program však zabije zbytečně čas na zkoumání tahu, kterým se vůbec zabývat neměl.

Provádění tahů a jejich kombinací je druhá činnost programu. V ideálním případě nekonečného výkonu CPU by v každé pozici mělo být možné propočítat všechny možnosti a dát odpověď výhra, prohra nebo remíza. V reálném světě, kde je omezený výkon a čas na hledání, není možné většinu pozic dopočítat až do konce a je nutné volit určité kompromisy při prohledávání všech možností. Tady vzniká výkonnost a charakter programu, protože se dá ladit spousta parametrů hledání: kolik tahů v každé úrovni prohledává, jak agresivně zvyšuje hloubku hledání ve vynucených variantách atd. Jde o to najít kompromis, který bude mít statisticky nejlepší výsledky. To, že v nějaké konkrétní pozici nenajde v omezeném čase lepší řešení, než soupeř, je běžné. Neřeším však jednotlivé partie. Důležité je mít pravdu častěji než ostatní.

Hodnotící funkce je taková Popelka, která není na očích. Vezme počty hrozeb, pronásobí je magickými koeficienty a přičte skóre za konstelaci kamenů na desce (kolik je možné vytvořit pětic procházejících políčkem, jak je políčko daleko od okraje atd.).

Současný vývoj už je spíše jen vylepšování a zrychlování současného kódu. Poslední větší přírůstek kódu byla Renju varianta Embrya a ještě předtím gomocupová Standard verze nebo chcete-li právě pět podle českých pravidel. Verzi Standard vyprovokoval Specs ve svém (o)slavném článku a verzi Renju má touha zvládnout naprogramovat tu asymetrickou šílenost s divnými pravidly. Hráči renju prominou, jsou li tu nějací. Pokud by byl zájem a volná kapacita serveru piškvorky.net, mohl by vzniknout i renju-xobot.

Gomocup turnaj

První účast Embrya na Gomocupu se odehrála v roce 2017, kde jako nové a nenasazené začínalo v poslední třetí skupině, aby se přes druhou dostalo do první skupiny mezi velké kluky. Jedenácté místo ze 16 ve finále nebyla žádná sláva. Myslím si, že bylo z bojů ve skupinách i dost unavené. Větší radost jsem měl, že jsem od Yixina, který uhrál výsledek 351:9, nedostal kanára a uhrál jsem jeden bodík z 24 v partií na dlouhý čas (300s/tah, 1000s/partie). V bleskovce bylo skóre „výrazně“ lepší 2:22, stejně jako pořadí bylo o jeden nebo dvě místa lepší. Přibližný odstup od Yixina byl nekonečných 500-600 Elo bodů. Co jsou Elo body? Wikipedie dá přesnější popis, pro naše účely stačí, že se jedná o pravděpodobnost výhry. Několik přibližných hodnot zmiňovaných v tomto článku: 200 Elo odpovídá výsledku zápasu 75:25, 60 Elo 59:41, 500 Elo 97:3.

Ironie osudu byla, že jsem týden po Gomocupu našel v programu chybu, která srážela výkon nejméně o 200 Elo bodů. Příprava na ročník 2018 byla vedena s jasným cílem přiblížit se výkonnostně co nejvíc k Yixinovi. Zpočátku bylo Embryo s bídou schopné poškrábat Yixina zespodu na podrážce, postupem času se přes okopávání kotníků dostalo až k důstojné prohře.

Gomocup 2018 byl již popsán Specsem. Ve stručnosti: Embryo bralo první místo v bleskovce a druhé v královské kategorii. K tomu není mnoho co dodat. Snad jen, že je příjemné být chvíli slavný i třeba jen v malé komunitě nadšenců. Výsledek opět měřený Elo odstupem od Yixina -60 na dlouhý čas a +190 v bleskovce.

Do očí bijící rozdíl 250 bodů je vysvětlitelný jen chybou v Yixinovi či Embryu. Programy na této úrovni by měly držet přibližný poměr výsledků nezávisle na rychlosti hry. Vsadil jsem na chybu v Embryu a začalo pátrání. Po pár dnech jsem objevil podezřelou logickou podmínku, která byla v programu od začátku, tisíckrát jsem ji viděl a celou dobu jsem ji bral jako naprosto správnou. Nebyla správná. Po opravě okamžitě přibylo 70 Elo, a tak zbývalo najít další část rozdílu. I ta souvisela s touto chybou. Postupem času se povedlo laděním parametrů chybu částečně korigovat a bylo nutné ladění zopakovat od začátku pro opravený program. Dvouměsíční ladění a povedlo se vydolovat dalších sto Elo bodů. Jubilejní 20. Gomocup příští rok je výzva a plán je jasně daný – zúčastnit se ve všech 4 kategoriích a …

Úloha

Něco k zamýšlení na závěr ;-)

Tato pozice se objevila kdysi v partii s Yixinem, kdy Embryo několik tahů (tři nebo čtyři čtyřky) před touto pozicí nahlásilo výhru a když mělo udělat klíčový tah celé kombinace, díky chybě v generátoru tahů ji nezvládlo.

Černý vyhraje nejpozději svým 8. tahem. Nápověda: první klíčový tah se zrovna nenabízí.

úloha


—Míra Fontán, Radomyšl



Diskuze k článku

 
1