Študent Žilinskej univerzity Matej Isteník vyhral medzinárodný turnaj StarCraft

223

Matej IstenikZačiatkom roka sa na Katedre Aplikovanej Informatiky FMFI, Univerzity Komenského konalo finále druhého ročníka medzinárodného turnaja umelých inteligencií v strategickej hre StarCraft pod názvom SSCAI.

Myšlienka je jednoduchá: Súťažiaci naprogramujú svojich UI agentov (botov) v Jave alebo C++ a nechajú ich hrať proti sebe o body. Všetky zápasy sa pri tom dajú sledovať naživo na webe turnaja (www.sscaitournament.com).

Podľa zakladateľa turnaja, Dr. Michala Čertického, je StarCraft ideálnou doménou pre štúdium a implementáciu rôznych techník umelej inteligencie (UI) od pathfindingu a CSP, cez evolučné algoritmy, plánovanie a reinforcement learning, až po neurónové siete.

Spomedzi súťažiacich zo svetových univerzít ako UC Berkeley (US), University of Alberta (CAN), Ritsumeikan University (JAP) a podobne, vyšiel tento krát víťazne študent Žilinskej univerzity, Matej Isteník. Prinášame vám rozhovor s ním.

Ako si sa dostal k StarCraftu a programovaniu UI?

StarCraft bola a stále je jedna z mojich najobľúbenejších hier. Prvýkrát som ju spoznal na konci prvého ročníka základnej školy. Spolu s bratom nám ju ukázal jeden kolega v práci, kde vtedy pracoval otec. Dodnes si pamätám ako som prvý krát hral príbehovú kampaň.

K programovaniu UI som sa dostal vďaka bakalárskej téme. Jej úlohou bolo spoznať a popísať BWAPI a BWSAL (API a knižnice používané pri tvorbe botov). Keďže som si chcel aj zaprogramovať, dohodol som sa s vedúcim, že práca bude mať aj praktickú časť s vytvorím kompletného bota. Po úspešnej obhajobe práce som sa zapojil do projektovej výučby, ktorej cieľom je práve vývoj StarCraftového bota.

Ako si sa dostal k turnaju SSCAI?

Odpoveď súvisí práve s mojou účasťou na projektovej výučbe. Keďže sme sa iba rozbiehavali, padol návrh, že by som svojho bakalárskeho bota trochu vylepšil a zaslal do súťaže, aby sme získali skúsenosti.

Bot totižto dokázal postaviť bázu a produkovať jednotky, ale útok prebiehal tak, že v určitý čas jednoducho všetko poslal proti protivníkovej hlavnej báze. Primárne používal Vultures (rýchla útočná jednotka), ktoré ovládal pomocou Potential Field Control algoritmov, ale to bolo tak všetko.

Ako si bota pripravil na súťaž?

V tom čase som mal plné ruky práce s povinnými predmetmi, takže som si vyhradil jeden víkend na vylepšenie zásadných vecí a zvyšok som nechal tak.

Vultures boli doplnené tankami, pre ktoré sa naprogramovali vlastné kontrolné mechanizmy. Vylepšil sa prieskum, aby vedel rozumne prehľadať celú mapu. A nakoniec plánovač útoku, ktorý postupne zameriaval všetky protivníkove budovy. Bota som prvýkrát uploadol práve po týchto zmenách.

Ako sa mu darilo?

Bola to hrôza. Prvé hry prehrával. Ukázalo sa, že niektoré veci sú navrhnuté veľmi zle a bolo ich treba vylepšovať. Problém bol hlavne s tankmi. Ich chovanie bolo nastavené príliš defenzívne, a viac utekali ako bojovali. Postupne som ich priority totálne obrátil; akonáhle mali po čom útočiť, útočili, kým mohli. Ich obranu mali zabezpečovať ostatné jednotky. Občas som vtipkoval, že som z tankov vyhodil francúzov a zamestnal som rusákov 🙂

Tvoj bot sa neskôr začal objavovať na predných miestach. Bolo to týmito úpravami, alebo si pokračoval ešte ďalej?

Bot sa zlepšil, a začal už ako tak rozumne fungovať. Videl som ale pár oblastí, ktoré by sa dali zlepšiť, tak som pokračoval. Tlačil ma čas, ale chcel som bota pripraviť čo najlepšie. Niekedy totiž robil úplne hlúposti.

Napríklad bol schopný zablokovať si východ zo základne armádou a potom nemohla vyjsť prieskumná jednotka. Vďaka tomu nikdy nenašiel nepriateľa a teda nikdy blokujúcu armádu nepohol. Časť problémov bola aj s knižnicou BWSAL, ktorá sa občas vedela dobre zosypať, napríklad zastavila produkciu jednotiek aj keď surovín mal bot dostatok. V tom čase vzniklo botove meno, Dementor. Znie to trochu pejoratívne, ale ten bot je naozaj istým spôsobom hlupák. A dobre sa to vyslovuje 🙂

Zaujímavé bolo sledovať naživo taktiky ostatných hráčov a upravovať tak chovanie bota. Jeden z protossov, už si asi nespomeniem na meno, ale bol to bot jedného študenta z Univerzity Komenského, mal záľubu v dark templaroch, trvalo neviditeľných jednotkách. Raz s nimi nabehol do základne môjho bota, zničil všetky detektory a vyhral. Po tom, čo som to videl, som upravil stratégiu tak aby bot staval viac detektorov. Súperovi tak nevyšiel prvotný útok, a hra sa zvrhla na veľkú bitku o stred mapy. Môj bot postupne získaval prevahu a nakoniec vyhral.


Pozrite si video, komentovaný zápas víťazstvo Dementora proti Skynetu (Skynet v posledných rokoch vyhráva všetky ostatné turnaje na vedeckých konferenciách).


Kedy si si uvedomil, že s tvojím botom máš šancu biť sa o prvé miesta?

Prvé znamenie bolo asi vtedy, keď mi zasvietil achievement, že bot počas posledných 48 hodín dosiahol 80% úspešnosť. Vtedy som si povedal, že možno sa dostanem do prvej desiatky. Nastali dokonca obdobia, keď sa dostal na prvé miesto v tabuľke; považoval som to ale skôr za kuriozitu, lebo som čakal, že množstvo botov sa ešte zvýši, keď sa priblíži termín uzávierky.

Samozrejme, dúfal som v čo najlepšie umiestnenie, ale bol som realista a vedel som, že to moje stvorenie je veľká hŕba rýchlo písaného kódu s pár sofistikovanejšími riešeniami.

Celkovo, vnútri to bol čistý hnus. Celá logika, ktorá riešila build order, obranu a útok, bola jedna metóda s hŕbou podmienok. Celý bot fungoval na ručne vyladených stavových automatoch. Niektoré jednotky boli ovládané špecializovanými agentami, a mal som tam niečo ako reprezentáciu stavu sveta pre útok a prieskum, ale to bolo tak všetko.

Napriek tomu sa mu ale darilo. Ako je to možné?

Nad botom som strávil veľmi veľa času, ktorý som venoval ladeniu. Oproti pôvodnému plánu, jeden víkend, sa pracovný čas roztiahol na dva a pol týždňa. A to bol naozaj “pracovný” týždeň. Ráno vstať, pracovať na botovi a večer spať. Jeden týžden som ani nechodil do školy. Počas vývoja mi stále bežal StarCraft a na druhom počítači stream zo SSCAI. Bota som testoval v rôznych podmienkach, napr. v hre proti dvom protivníkom alebo vo free-for-all hrách. Bot vtedy používal iba jednu taktiku, ale vedel ju použiť dostatočne dobre.

Počas vývoja som prišiel na veľa praktických zlepšení; napríklad som začal útočiť nie smerom na najskôr objavené budovy, ale najneskôr. Bot tak začal ničiť protivníkove expandy (predsunuté bázy pre získavanie surovín), a ich ničením získaval ekonomickú prevahu.

Turnaj na konci dopadol nerozhodne. Tvoj bot proti botovi Poliaka menom Marcin Bartnicki. Prečo vyhral práve tvoj bot?

Marcin mal veľmi “drzého”, ale úspešného Zergského bota (Zergovia sú jedna z rás dostupných v StarCrafte). Agresívne robil prieskum, a hneď ako mohol, zaútočil. To bolo v čase, keď drvivá väčšina botov ešte len budovala ekonomiku a nemala sa ako brániť.

Nakoniec mi ale pomohla trochu náhoda a trochu šťastie. Ako rozhodujúca mapa sa vybral Electric Circuit. Táto mapa má na niektorých miestach neutrálne budovy, ktoré blokujú cestu. StarCraftový pathfinding s týmto neráta, a jednotky sa dokážu na takejto budove zaseknúť. Ja som to nakoniec po niekoľkých pokusoch vyriešil tak, že bot tieto budovy aktívne hľadal a ničil. V poslednom súboji boti dostali práve také štartovné pozície, že útok zerga sa zasekol o neutrálnu budovu. Môj bot tak dostal čas postaviť dostačujúcu armádu. Keď som sa toto dozvedel, bola to pre mňa úžasná satisfakcia za to, že som sa rozhodol riešiť problém, ktorý drvivá väčšina botov zanedbala.

Čo ti turnaj okrem výhry priniesol?

Hlavne poznanie, že sofistikovaný bot nemusí byť vždy lepší. V turnaji sa objavilo veľa botov, ktorí používali rôzne pokročilejšie AI techniky, bayesovské siete, predikčné algoritmy, učenie sa z hier, atď. Napriek tomu ich porazili boti, ktorí boli úrovňou niekde dosť nižšie. Dôležité totiž je, že v botovi sa nemôže dobre spraviť jedna časť a druhá zanedbať. Je síce fajn, že bot vie odhadnúť, s akou kompozíciou armády na neho protivník zaútočí, ale ak sa nevie ubrániť, je mu to nanič. Našťastie si ale myslím, že je len otázkou času, kým sa ostatní boti dostanú na lepšiu úroveň a taktiky, ktoré by napr. proti človekovi nemali šancu, sa stanú nepoužiteľnými.

SSCAI ma tiež veľmi inšpirovala. V rámci fakulty sme asi mesiac po súťaži zorganizovali malý BWAPI turnaj zameraný hlavne na zložku mikromanažmentu. Akcia mala veľmi dobrý ohlas a na začiatku júla bude druhé kolo, tentoraz prístupné každému. Ak máte záujem, navštívte nás na scmai.hackcraft.sk.

Zúčastníš sa aj SSCAI 2013?

Určite. A nielen ja, zo Žiliny by mala prísť celá delegácia. Pravdepodobne tentoraz už nevyhrám, ale určite sa posnažím skončiť aspoň v prvej tretine. Predtým ale budem musieť veľmi zapracovať na botovi, lebo konkurencia sa zase výrazne zlepšila. A popravde, chcelo by to už zmeniť meno bota 🙂


Ako začať?

Turnaja SSCAI sa môže zúčastniť každý. Stačí naprogramovať bota buď v Jave (návod)  alebo v C++ (návod) a zaregistrovať ho na webe SSCAI súťaže.

Uzávierka tohoto ročníka je síce až v decembri 2013, ale oplatí sa registrovať čo najskôr a postupne nahrávať novšie verzie. Zápasy totiž prebiehajú už teraz – zatiaľ síce nejde o skóre, ale môžete naživo sledovať svoj výtvor v akcii a opravovať chyby čo robí. A ako bonus váš bot odomyká rôzne achievementy a portréty pre svoj profil na turnajovom webe.

Dobrý článok? Chceš dostávať ďalšie?

Už viac ako 4 200 z vás dostáva správy e-mailom. Nemusíš sa báť, nie každé ráno. Len občasne.

I agree to have my personal information transfered to MailChimp ( more information )

Tvoj email neposkytneme 3tím stranám. Posielame naňho len informácie z robime.it. Kedykoľvek sa môžete odhlásiť.