Kilpailut: Hippa: tulokset
Järjestäjä: Metabolix
Joulu–tammikuussa 2008–2009 Ohjelmointiputkassa pidettiin kilpailu, jossa tehtävänä oli ohjelmoida tekoäly hippaleikkiin. Tekoälyistä kaksi leikki aina vastakkain, toinen ohjasi hippoja ja toinen pakenijoita. Jokainen hippa ja pakenija sai liikkua peliruudukossa enintään yhden ruudun joka kierroksella, ja jos kierroksen lopuksi pakenija oli hipan ruudussa, se jäi kiinni ja muuttui hipaksi. Pakenijoita ohjannut tekoäly sai yhden pisteen aina kustakin kierroksen alussa vapaana olleesta pakenijastaan, ja sama määrä pisteitä otettiin hippojen tekoälyltä pois. Peli päättyi, kun kaikki pakenijat oli saatu kiinni. Peleillä oli myös tietyt rajoitteet, jottei niistä tulisi aivan kohtuuttoman pitkiä tai jopa päättymättömiä.
Kilpailuun osallistui 15 tekoälyä, jotka juoksentelivat ympäri pelikenttää hyvinkin erilaisten laskelmien ohjaamina. Kilpailuun ei osallistunut yhtäkään strategisesti ylivertaista hippaa, vaan painopiste oli enemmänkin melko yksinkertaisten arvioiden välisessä kamppailussa. Yleensä tekoälyt laskivat siirtonsa sekunnin murto-osissa, mutta muutamalta pääsi toisinaan sekunnin aikaraja ylittymään.
Osallistujat ja tulokset
Seuraavassa taulukossa ovat kaikki kilpailun osallistujat järjestyksessä lopullisen kokonaispistemäärän mukaan. Kaikki älyt pelasivat vastakkain 14 eri alkutilanteesta, ja eri pelikentillä ja pelaajamäärillä pelattujen otteluiden pisteitä suhteutettiin toisiinsa niin, että pienetkin testitapaukset toivat kohtuullisia pistesaaliita suurempiin verrattuna.
| sija | tekoäly | tekijä | nimimerkki | kieli | hippatulos | pakenijatulos | kokonaistulos |
|---|---|---|---|---|---|---|---|
| 1 | tunkki | Otto Seiskari | os | C/C++ | -11931 | 64082 | 52151 |
| 2 | hipake | Lauri Kenttä | Metabolix | C/C++ | -13189 | 62557 | 49368 |
| 3 | u137 | Teemu Valo | User137 | Pascal | -15370 | 38602 | 23231 |
| 4 | HippaZizzo | Petteri Aimonen | jpa | Python | -24109 | 43266 | 19157 |
| 5 | meek | Pekka Karjalainen | Kopeekka | Python | -18171 | 34678 | 16507 |
| 6 | Jeppe | Juho Alho | Juhko | Basic | -17086 | 30555 | 13470 |
| 7 | plussa | pr0l3 | C/C++ | -12651 | 21851 | 9200 | |
| 8 | Hipi1 | Sami Riihelä | Rixa | Basic | -25530 | 32979 | 7448 |
| 9 | MonkeyBot | Lauri Niskanen | Ape | PHP | -14681 | 20655 | 5975 |
| 10 | HIPPAI | Tomi Kokkonen | tkok | C/C++ | -29862 | 20243 | -9619 |
| 11 | hihPah | Toni Huttunen | Seriffi | C/C++ | -42921 | 32071 | -10851 |
| 12 | VehkAly | Lari Vehkalampi | vehkis91 | C/C++ | -51382 | 26884 | -24497 |
| 13 | Luster | Kimmo Parsama | C/C++ | -51696 | 17106 | -34589 | |
| 14 | Hippa2000 | Jere Parikka | JrPr | Java | -58645 | 16990 | -41656 |
| 15 | jpa | Simo Heinonen | Zizzo | Java | -83779 | 8484 | -75296 |
Graafisesta esityksestä nähdään hyvin, että vielä tulosten keskivaiheillakin oli lähes kärjen veroisia hippoja: hippana toiseksi paras äly, plussa, on kokonaistuloksissa vasta seitsemäs. Kärkikaksikon suurin vahvuus olikin pakeneminen: kolmanneksi paras pakenija jäi jo 30 prosenttia vähemmille pisteille. Myös yhteispisteissä ero kärjen ja muiden älyjen välillä on selvä, loput älyt sijoittuivat paljon tasaisemmin välein. Kilpailussa oli monta suunnilleen yhtä hyvää hippaa ja pakenijaa, mutta saman tekoälyn menestys näissä kahdessa roolissa oli joissain tapauksissa hyvinkin erilainen.
Testitapaukset
Tekoälyt kilpailivat kaikki toisiaan vastaan 14 erilaisesta alkutilanteesta. Seuraavasta taulukosta käyvät ilmi älyjen pistesaaliit eri tapauksissa. Otteluiden pisteet skaalattiin ensin niin, että pakopistemäärien keskiarvoksi saatiin aina 100. Tämän jälkeen pisteet vielä kerrottiin painotuskertoimella, joka oli suuremmissa alkutilanteissa suurempi. Skaalaus oli eittämättä tarpeen, koska pienimpien testitapausten raakapistemäärät olivat vain joitakin kymmeniä ja suurimpien jopa kymmeniätuhansia. Yksittäisten otteluiden tulokset on koottu erilliseen tekstitiedostoon, ja otteluiden hippa.txt-tiedostot voi ladata seuraavan taulukon linkeistä. Tiedostojen katselu onnistuu valmiilla HTML-sivulla, jos selain tukee JavaScriptia.
Tekoälyjen keskinäinen järjestys eri testitapauksissa vaihteli jonkin verran, ja lisäksi osa tekoälyistä luotti satunnaislukuihin, joiden takia niiden päätökset vaihtelivat huomattavasti jo eri ajokerroilla. Toisenlainen testitapaussarja olisi siis voinut tuottaa kilpailussa erilaisen lopputuloksen.
| alkutilanne | hihPah | hipake | Hipi1 | H2000 | HIPPAI | HZizzo | Jeppe | jpa | Luster | meek | Monkey | plussa | tunkki | u137 | Vehk |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 8x8-3v1-vk | -742 | 1782 | 290 | -2659 | -911 | 2028 | 1382 | -4358 | 592 | 1094 | 338 | 359 | 1852 | 943 | -1989 |
| 9x9-4v2-rivit-v-PHP | -1845 | 2380 | 427 | -2117 | -1530 | 2307 | 1781 | -4213 | 3 | 1437 | 212 | 127 | 2611 | 644 | -2226 |
| 9x9-4v2-rivit-v-HPH | -1485 | 2070 | -334 | -2795 | -1898 | 2341 | 828 | -3455 | 31 | 1767 | 1336 | 85 | 2323 | 1775 | -2589 |
| 10x10-5v15-rivit-v-PPPH | -19 | 2301 | 348 | -2146 | -2231 | 1570 | 774 | -2633 | -199 | 917 | 124 | -312 | 2703 | 1230 | -2429 |
| 11x11-5v8-kehat-3-4 | -919 | 2557 | -95 | -770 | -1066 | 1831 | 533 | -3700 | -160 | 105 | -352 | 24 | 3122 | -102 | -1006 |
| 13x8-3v5-rivit-p-HP00 | 314 | 1914 | 120 | -3254 | -816 | 1426 | 818 | -2636 | -2506 | 8 | 588 | 422 | 2471 | 874 | 257 |
| 16x8-5v3-rivit-p-HP00 | -579 | 1361 | -58 | -3353 | 477 | 1831 | 826 | -3236 | -3588 | 1161 | 1044 | 765 | 1820 | 996 | 532 |
| 20x11-4v7-kehat-3-5 | -2547 | 4345 | 702 | -4017 | -950 | 3378 | 1457 | -5141 | -5591 | 1499 | 909 | 789 | 4747 | 2087 | -1667 |
| 30x8-8v24-rivit-v-HPPPPH | -525 | 5295 | 1383 | -6668 | 399 | 2416 | 1445 | -5801 | -8013 | 1263 | -20 | 977 | 5218 | 1974 | 657 |
| 18x18-7v21-kehat-0-7 | -76 | 4330 | 776 | -3864 | -786 | 1749 | 460 | -5875 | -1077 | 1345 | -166 | 154 | 5879 | 1601 | -4450 |
| 60x16-6v30-rivit-v-PPHPHPP | -583 | 3850 | 816 | -3701 | -1128 | 1036 | 660 | -4102 | -5261 | 1446 | -303 | 1443 | 4674 | 1795 | -642 |
| 60x16-6v30-rivit-p-PPHPHPP | -395 | 3716 | 879 | -4304 | -271 | 180 | 517 | -4076 | -4564 | 149 | 410 | 1362 | 4686 | 1631 | 81 |
| 33x33-16v4-kehat-16-1 | -2258 | 4465 | 1381 | 1383 | 1221 | 2753 | 1428 | -16678 | -2827 | 1381 | 1162 | 2037 | 4842 | 3306 | -3596 |
| 42x42-8v48-Hku-Pke | 808 | 9002 | 813 | -3390 | -130 | -5689 | 560 | -9390 | -1428 | 2933 | 692 | 968 | 5203 | 4477 | -5430 |
Tekoälyt ja kuvaukset
Tekoälyjen lähdekoodit voi ladata yhtenä pakettina. Osallistujilta pyydettiin tekoälyn saatteeksi myös pientä selostusta sen toimintaperiaatteesta. Näin he kertovat ratkaisuistaan:
| tekoäly & tekijä | kuvaus |
|---|---|
| hihPah Toni Huttunen "Seriffi" | Hippatekoäly jakaa hipat viiden ryhmiksi. Ryhmät asettuvat pystysuoraksi seinämäksi. Ryhmän täyttyessä luodaan uusi ryhmä. Ryhmän keskimmäinen etsii lähimmän pakenijan, jota ei vielä jahdata kenenkään muun ryhmän toimesta. (Poikkeus syntyy kun kaikkia pakenijoita jo jahdataan.) Ryhmän jäsenet seuraavat keskimmäisen liikkeitä. Jokainen laita vetää yhden pakenijan puoleensa, tarkoituksena on houkutella hippoja kulkemaan pitkiä matkoja, saaden näin aikavoittoa. Loput pakenijat tarkistavat lähialueen ja laskevat karkeasti että missä on vähäisin mahdollisuus joutua kiinni. (Tosin maksimissaan vain neljän ruudun päähän) Mikäli uhkaa ei ole, pakenija heiluu oikealle/vasemmalle satunnaisesti, pyrkien sekoittamaan hipan hyökkäyksen. Esimerkiksi: hipat joutuvat päällekkäin, tai jäävät toistamaan samaa liikettä ilman etenemistä |
| hipake Lauri Kenttä "Metabolix" | Tekoälyn pakenemismenetelmä on hyvin yksinkertainen: ensin se laskee pelaajien sijainneista hieman metapalloja muistuttavan kartan, ja sitten jokainen pakenija siirtyy kartan arvojen perusteella "himmeämpään paikkaan" eli kauemmas muista pelaajista. Hippana tekoäly valitsee ensin seuraavat uhrinsa, suunnilleen yhden aina neljää hippaa kohden. Valinta tallennetaan muisti.dat-tiedostoon. Sitten äly toimii suunnilleen samalla tavalla kuin paetessaan, mutta "metapallojen" laskemiseen käytetään vain valittuja pakenijoita ja hieman erilaisia painotuksia. Kun äly saa jonkin pakenijan kiinni, valitaan kaikille hipoille uudet uhrit. |
| Hipi1 Sami Riihelä "Rixa" | Ohjelma lukee mini.txt:tä ja päättelee seuraavan siirron muiden sijaintien mukaan. Ohjelma ei käytä muisti.dat -tiedostoa hyväkseen. Siirto päätellään laskemalla suunnille painotuksia ja valitaan painotuksien perusteella paras suunta siirrolle. Sama toiminta Hipan ja Pinko ohjauksessa. Kirjoitin ohjelman VB .NET:llä, mutta sitä ei voinut tässä käyttää niin porttasin sen VB6:lle. Osaksi tästä syystä ohjelmassa ei ole mitään virheentarkistuksia. Lisäksi olin huolissani nopeudesta, mutta VB6 koodi toimii paljon nopeammin ja F-secure hidasti ohjelmaani melkoisesti ennen kuin tämän keksin. Hippa ohjaus Etsii ensimmäistä (tiedostossa ensimmäinen) hippaa lähinnä olevaa pinkoa. Hippoja ohjataan sen suuntaan. 1. ja 4. hippa liikkuvat mahdollisimman suoraan pinkoa kohti. Muut hipat liikkuvat ensin x tai y suunnassa pinkoa kohden. Kaikki kolme ensimmäistä hippaa ottavat kiinni samaa pinkoa. Muut mahdolliset hipat ottavat kiinni toista pinkoa kiinni. Ellei ole kuin yksi pinko, niin kaikki hipat ajavat sitä takaa. Järjestysnumeroltaan pienempää hippaa ei liikuteta, jos samassa ruudussa on toinenkin hippa. Tällä yritetään estää kaikkien hippojen liikkuminen samassa ruudussa. Pyritään myös siihen, ettei liikuta toisen hipan päälle. Pinko ohjaus Pinko pyrkii aina reunaan ja kiertämään aluetta myötäpäivään. Tiedä sitten onko tämä järkevää. Hipan tullessa iholle, etsitään turvallisin suunta liikkua. Pinko voi myös valita suunnaksi hipan läpi kulkemisen. Ohjelman pelatessa itseään vastaan, näyttää pinko puoli olevan etevämpi. |
| Hippa2000 Jere Parikka "JrPr" | Tekoäly luo 5 pistettä seuraavan kaavion mukaan (X = tyhjä): X 4 X 3 1 5 X 2 X ja valitsee parhaan vaihtoehdon seuraavasti: Hippa liikkuu lähemmäs lähintä pakenijaa, jota ei jo jahtaa hippa. Jos hippoja on enemmän, kuin pakenijoita, hipat jaetaan tasaisesti samoin. Pakenija liikkuu kauimmas kaikista hipoista yhteensä, mutta ei lähimmäs lähintä hippaa. Hyödyntaa javan Point-oliota ja siihen liittyvää distance-funktiota paikan ja sijaintien määrittämiseen. En pitänyt tarpeellisena käyttää muistitiedostoa, koska ohjelma on nopeampi ilman. |
| HIPPAI Tomi Kokkonen "tkok" | Suoraviivainen kiinni juoksija // suoraviivainen karkuun pinkoja. Joululoma sattui liian täydeksi :( |
| HippaZizzo Petteri Aimonen "jpa" | HippaZizzo on kiireessä koodattu tekoäly, joka tallentaa muistiinsa vastustajan eri tilanteissa tekemät siirrot. Tarkoitus on oppia, miten vastustaja reagoi lähitilanteissa, ja hyödyntää tätä tietoa. Käytännössä HippaZizzo ei ole kovinkaan fiksu, mutta muiden kiireiden vuoksi tähän ei ollut käyttää kuin kolmisen tuntia aikaa. |
| Jeppe Juho Alho "Juhko" | Tekoälyn toiminta Hipat: Valitaan 1. hipan lähin pakenija (jotta valinta pysyy varmasti samana koko ajan). Ensimmäinen hippa pyrkii suoraan tätä pakenijaa päin, ja loput rupeavat saartamaan sitä. Pakenijat: Jokainen pakenija pakenee omaa lähintä hippaansa suorinta reittiä, ja joutuessaan jonkun hipan viereen se etsii parhaan mahdollisen pakoreitin. Algoritmit
Muistitiedosto (muisti.dat) Kaikissa muissa paitsi erikoistapauksissa pelaajat liikkuvat vuorotellen x- tai y-suunnassa. Muistitiedostoon on tallennettu joko "0" (x-suunta) tai "1" (y-suunta). Huomautuksia GetHelpForP-aliohjelman tutkimisesta saattaa saada päänsärkyä. |
| jpa Simo Heinonen "Zizzo" | jpa on teko"äly", joka yrittää hämätä vastustajaa liikkumalla täysin päättömästi vailla mitään järkeä. Tavoitteenani olikin lähinnä saada toimiva ohjelma aikaan, sillä ohjelmointitaitoja ei vielä(?) juuri löydy. B) |
| Luster Kimmo Parsama | Erittäin rajoittunut tekoäly joka saatiin kokoon monen tuskaisen tunnin ja ja kymmenien bugien jälkeen. Hipat lähtevät lähimmän pakenijan päälle vaikka kaikki kerralla ja pakenijat liikkuvat jos hippa on yhden ruudun säteellä. Syy rajoittuneeseen älyyn on myöhäinen kilpailun tiedostaminen. Muisti.dat:iin piti alunperin piirtää goatse, mutta aika loppu kesken :/ |
| meek Pekka Karjalainen "Kopeekka" | Ohjelma pisteyttää ruudut sen mukaan, kuinka lähellä ne ovat vastustajia. Takaa-ajaessa etäisyyttä minimoidaan ja samaan ruutuun ei liikuta jos mahdollista. Paettaessa etäisyys pyritää maksimoimaan. |
| MonkeyBot Lauri Niskanen "Ape" | MonkeyBot on PHP:llä tehty Hippa-tekoäly. Se on melko yksinkertainen, eikä käytä kaikkia kilpailun sallimia toimintoja. Hipat tekoäly ohjaa kohti sitä pakenijaa, joka on keskimääräisesti lähinpänä hippoja. Hipat osaavat yksinkertaista yhteistyötä ja pyrkivät aina kaikki ottamaan kiinni samaa pakenijaa. Hipat eivät mene sellaisiin ruutuihin, joissa on jo toinen hippa. Ne myöskin yrittävät edetä eri reittejä: toinen ylhäältä, toinen vasemmalta yms. Pakenijat liikkuvat aina poispäin lähimmästä hipasta. Ne myös välttävät liikkumista sellaiseen paikkaan, jossa on toinen pakenija. |
| plussa "pr0l3" | viisi hippaa menee aina plussaksi ja kohti lähintä pakenijaa mutta ei kaikki plussat samaa kohti ja pakenijat laskevat summan suunnista hipasta tai kulmasta pakenijaan / etäisyyden neliö niin lähemmistä menee kovemmin pois päin |
| tunkki Otto Seiskari "os" | Tekoäly on jaettu kahteen osaan. Pakenevaa pelaajaa ohjaava äly pyrkii hajaantumaan ympäri pelialuetta. Umpikujaan joutunut pakenija yrittää satunnaista paikanvaihtoa. Jahtaava äly valitsee "ahneesti" aina helpoimman kohteen ja määrää vapaista jahtaajista sopivimmiksi katsomansa yksilöt tämän perään, kunnes jahtaajat tai jahdattavat loppuvat. Sopivimman kohteen valinnassa käydään läpi kaikki kohdetta lähimpien jahtaajien mahdolliset järkevät siirtoyhdistelmät. Pattitilanteessa jahtaava äly yrittää satunnaisesti kiinniottoa. Molemmat tekoälyt käyttävät LCG:tä, jonka siemenluku lasketaan pelitilannehistoriasta. Ohjelma ei käytä muistitiedostoa. |
| u137 Teemu Valo "User137" | Lukee vain mini.txt:tä ja kirjoittaa koko tilanteen muisti.dat:n. Hipat ottavat lähimmän kohteekseen ja ajavat sitä takaa, ensisijassa vapaa kohde. Kun etäisyys lähimpään on 1 niin 60% todennäköisyydellä liikkuvat kohteeseen, muutoin pysyvät paikallaan. Eivät kulje enää päällekkäin. Pakenijoilla on joka kierroksella 30% mahdollisuus valita liikesuunta, muulloin ne jatkavat samaan suuntaan kuin edellisellä kierroksella. Eivät kuitenkaan tahallaan liiku hippojen syliin tai seiniä päin. |
| VehkAly Lari Vehkalampi "vehkis91" | HUOM! Koodi on todella sekavaa, koska muutin keskenkaken suunnitelmaa, enkä jaksanut kirjoittaa koko softaa uudelleen. Eli en suosittele koodin tarkempaa tsiigailua. :D Tämä on myös ensimmäinen "kunnon" tekoäly, joten senkään takia "äly" ei ole hirveän monimutkaisesti suunniteltu. Hipan äly on aika alkeellinen, kaikki "hipat" lähtevät ensimmäisen tiedostossa näkyvän pakenijan perään. Kun saadaan pakenija kiini niin taas siirrytään seuraavaan ja niin eespäin... Pakenija laskee erinlaisten ehtojen perusteella jokaisen liikkeen uhkapisteet. Se siirto mikä saa vähiten pisteitä toteutetaan. |
Kiitokset vielä kaikille kilpailuun osallistuneille!