Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Aikaa on 6.1. saakka.

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.

sijatekoälytekijänimimerkkikielihippatulospakenijatuloskokonaistulos
1tunkkiOtto SeiskariosC/C++-119316408252151
2hipakeLauri KenttäMetabolixC/C++-131896255749368
3u137Teemu ValoUser137Pascal-153703860223231
4HippaZizzoPetteri AimonenjpaPython-241094326619157
5meekPekka KarjalainenKopeekkaPython-181713467816507
6JeppeJuho AlhoJuhkoBasic-170863055513470
7plussapr0l3C/C++-12651218519200
8Hipi1Sami RiiheläRixaBasic-25530329797448
9MonkeyBotLauri NiskanenApePHP-14681206555975
10HIPPAITomi KokkonentkokC/C++-2986220243-9619
11hihPahToni HuttunenSeriffiC/C++-4292132071-10851
12VehkAlyLari Vehkalampivehkis91C/C++-5138226884-24497
13LusterKimmo ParsamaC/C++-5169617106-34589
14Hippa2000Jere ParikkaJrPrJava-5864516990-41656
15jpaSimo HeinonenZizzoJava-837798484-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.

alkutilannehihPahhipakeHipi1H2000HIPPAIHZizzoJeppejpaLustermeekMonkeyplussatunkkiu137Vehk
8x8-3v1-vk-7421782290-2659-91120281382-435859210943383591852943-1989
9x9-4v2-rivit-v-PHP-18452380427-2117-153023071781-4213314372121272611644-2226
9x9-4v2-rivit-v-HPH-14852070-334-2795-18982341828-345531176713368523231775-2589
10x10-5v15-rivit-v-PPPH-192301348-2146-22311570774-2633-199917124-31227031230-2429
11x11-5v8-kehat-3-4-9192557-95-770-10661831533-3700-160105-352243122-102-1006
13x8-3v5-rivit-p-HP003141914120-3254-8161426818-2636-250685884222471874257
16x8-5v3-rivit-p-HP00-5791361-58-33534771831826-3236-3588116110447651820996532
20x11-4v7-kehat-3-5-25474345702-4017-95033781457-5141-5591149990978947472087-1667
30x8-8v24-rivit-v-HPPPPH-52552951383-666839924161445-5801-80131263-2097752181974657
18x18-7v21-kehat-0-7-764330776-3864-7861749460-5875-10771345-16615458791601-4450
60x16-6v30-rivit-v-PPHPHPP-5833850816-3701-11281036660-4102-52611446-303144346741795-642
60x16-6v30-rivit-p-PPHPHPP-3953716879-4304-271180517-4076-456414941013624686163181
33x33-16v4-kehat-16-1-2258446513811383122127531428-16678-282713811162203748423306-3596
42x42-8v48-Hku-Pke8089002813-3390-130-5689560-9390-1428293369296852034477-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

  • Koko tekoälyn ydin on Nearest-funktiota, joka laskee hippapelaajille sopivan kohteen ja kullekin pakenijalle pisteen, jota paetaan.
  • Hippapelaajat hakeutuvat eri pisteisiin niiden numeron mukaan. Ensimmäinen hippa pyrkii suoraan kohdepakenijaansa kohti ja muut piirittävät sitä ylhäältä, alhaalta, oikealta tai vasemmalta, laskun pelaajan_numero MOD 4 mukaan.
  • Kun pakenijat joutuvat hätätilanteisiin, ne kutsuvat GetHelpForP -aliohjelmaa, joka laskee, minne päin on turvallisinta mennä.
  • Normaalitilanteissa pakenijat pyrkivät pois kentän reunoilta

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!

Tietoa sivustosta