Kirjautuminen

Haku

Tehtävät

Kilpailut: Hippa

Järjestäjä: Metabolix

Kumpi meist' on vikkelin, sitä pitäis koettaa,
emo lupas rinkelin sille, joka voittaa.

Kenellä onkaan Ohjelmointiputkan vikkelin äly? Se selviää tällä kertaa hipan merkeissä. Tässä kilpailussa on nimittäin tarkoitus ohjelmoida tekoäly, joka saa toiset nopeasti kiinni mutta pääsee itse ketterästi karkuun.

Kilpailuaika

Kilpailu pidetään 12.12. klo 12.12 – 12.1. klo 21.21. Ilmoittautumisia otetaan vastaan mainitun minuutin loppuun asti. (Kilpailuaika on nyt jo päättynyt ja tulokset on julkaistu.)

Kilpailun säännöt

Tässä nimenomaisessa hippaleikissä yksi tekoäly ohjaa hippoja ja toinen pakenijoita. Kun hippa saa pakenijan kiinni, pakenija muuttuu hipaksi. Peli päättyy, kun kaikki pakenijat on saatu kiinni tai kun ketään ei saada kiinni määrätyn ajan kuluessa.

Pelialue on suorakulmainen ruudukko, jonka sivut ovat L ja K ruutua pitkät (8 ≤ K ≤ L ≤ 100). Pelaajat on numeroitu numeroin 1–N (4 ≤ N ≤ 100). Kaikki pelaajat, sekä hipat että pakenijat, liikkuvat yhtä aikaa. Joka kierroksella saa pysyä paikallaan tai liikkua johonkin viereisistä ruuduista eli ylös, alas, vasemmalle tai oikealle. Samassa ruudussa voi olla myös useampi pelaaja. Hipan kanssa samaan ruutuun joutuneet pakenijat jäävät kiinni ja ovat siis seuraavalla kierroksella hippoja. Peli päätetään kesken, jos hipat eivät saa peräkkäisten 10L + 10K pelikierroksen aikana enempää pakenijoita kiinni.

Pakenevan tekoälyn pistemäärä on sen tekemien siirtojen summa, eli mitä pitempään ja mitä useammalla pelaajalla sen onnistuu paeta, sitä enemmän pisteitä kertyy. Hippaäly vastaavasti menettää saman määrän pisteitä. Jos siis pakeneva tekoäly saa ottelun aikana kokoon 13 pistettä, hippaälyn pistesaalis on tämän vastaluku, -13.

Jos hippa ei saa yhtään pakenijaa kiinni, pelistä kertyy (10L + 10K) * P pistettä, missä P on pakenijoiden määrä. Tämä on turnauksessa myös ottelun maksimipistemäärä; tämän yli menevää osaa pisteistä ei huomioida.

Jotta kilpailu olisi tasapuolisempi erilaisissa olosuhteissa menestyville tekoälyille, pyritään turnauksia pelaamaan ainakin kaksi. Lopullisiin tuloksiin eri turnausten pistemääriä painotetaan niin, että myös pienistä pelitilanteista saa kohtuullisesti pisteitä suhteessa isompiin.

Lopussa on vielä joitakin tarkennuksia sääntöihin.

Ohjelman toiminta

Ohjelma käynnistetään uudestaan jokaista siirtoa varten, ja sillä on joka kerta käytössään yksi sekunti prosessoriaikaa (ks. testiympäristö) ja enintään gigatavu muistia. Se saa lukea tiedostoja hippa.txt ja mini.txt ja kirjoittaa tiedostoon liike.txt. Lisäksi tiedosto nimeltä muisti.dat on vapaasti käytettävissä oman datan tallentamiseen. Muistitiedoston maksimikoko kuitenkin on 16 megatavua, ja se tyhjennetään aina otteluiden välillä eli silloin, kun vastustaja vaihtuu. Jos kokoraja ylittyy, tiedostoa lyhennetään väkisin. Muihin kuin mainittuihin tiedostoihin ei saa koskea, ja ohjelma hylätään, jos sen havaitaan yrittävän jotain epäilyttävää tai laitonta.

Tiedostossa hippa.txt on kaikki otteluun liittyvä data, ja näitä tiedostoja julkaistaankin kilpailun jälkeen. Tiedoston ensimmäisellä rivillä on hippaohjelman nimi ja toisella rivillä pakenevan ohjelman nimi. Kolmannella rivillä on neljä toisistaan välilyönnillä erotettua kokonaislukua, L, K, N ja M. Näistä L ja K ovat pelikentän leveys ja korkeus, eli ruutujen koordinaateille (x, y) pätevät 1 ≤ x ≤ L ja 1 ≤ y ≤ K. Luku N on pelaajien kokonaismäärä ja luku M pelattujen kierrosten lukumäärä. Tämän jälkeen toistuu M+1 kertaa seuraava sarja: Ensimmäisellä rivillä on luku E, edeltävien kierrosten määrä. Seuraavilla N rivillä ovat pelaajien tiedot: tyyppi (H, hippa, tai P, pakenija) ja kokonaislukukoordinaatit (x, y) eroteltuina välilyönnein. Tiedot ovat pelaajien numeroiden mukaisessa järjestyksessä (1–N).

Niille, jotka eivät kaipaa tietoa pelin aiemmasta kulusta, on tarjolla tiedosto mini.txt, joka sisältää tiedon vain uusimmasta pelitilanteesta. Ensimmäisellä rivillä on ensiksi kirjain H, jos tekoäly ohjaa hippoja, ja P, jos se ohjaa pakenijoita. Tämän jälkeen on vielä neljä kokonaislukua (L, K, N ja M), jotka ovat samat kuin hippa.txt-tiedoston kolmannella rivillä. Seuraavat N riviä kertovat pelaajien viimeisimmät tiedot samassa muodossa kuin hippa.txt-tiedostossa. Nämä ovat siis samat kuin hippa.txt-tiedoston lopussa.

Ohjelman liikemääräys tiedostossa liike.txt sisältää rivejä, joista jokaisella on pelaajan numero ja tämän liikesuunta (+x, -x, +y, -y tai 0). Mikäli sama pelaaja esiintyy tiedostossa monta kertaa, viimeisimmän rivin katsotaan olevan lopullinen päätös. Vialliset rivit jätetään huomiotta, ja ne pelaajat, joille ei ilmoiteta suuntaa tai jotka törmäisivät alueen reunaan, pysyvät paikoillaan.

Lopussa on vielä joitakin tarkennuksia tässä esitettyihin asioihin.

Esimerkki

Pelin alussa tiedostot voisivat näyttää tältä:
hippa.txt:

hipake
pinko
9 9 4 0
0
H 3 6
H 5 8
P 9 9
P 4 7

mini.txt, jota hipake lukee:

H 9 9 4 0
H 3 6
H 5 8
P 9 9
P 4 7

mini.txt, jota pinko lukee:

P 9 9 4 0
H 3 6
H 5 8
P 9 9
P 4 7

Tekoälyt voisivat tulostaa esimerkiksi tällaiset päätökset:
liike.txt, jonka hipake tulostaa:

1 +x
2 -y

liike.txt, jonka pinko tulostaa:

3 -x
4 -y
3 0

Seuraavassa kuvassa on esitetty tämä alkutilanne, ja kolme pientä nuolta kuvaavat liikkuvien pelaajien (1, 2 ja 4) liikesuuntia. Pelaaja 3 ei liiku, koska viimeinen sitä koskeva rivi oli "3 0".

Pelaajat 1 (hippa) ja 4 (pakenija) siirtyvät samaan ruutuun, jolloin pakenija muuttuu hipaksi:

Seuraavan kierroksen alussa tiedostot näyttäisivät siis tältä:
hippa.txt:

hipake
pinko
9 9 4 1
0
H 3 6
H 5 8
P 9 9
P 4 7
1
H 4 6
H 5 7
P 9 9
H 4 6

mini.txt, jota hipake lukee:

H 9 9 4 1
H 4 6
H 5 7
P 9 9
H 4 6

mini.txt, jota pinko lukee:

P 9 9 4 1
H 4 6
H 5 7
P 9 9
H 4 6

Oman tekoälyn testaaminen

Tässä paketissa on oman tekoälyn testaamiseen tarkoitetun, pelkistetyn testiohjelman C-kielinen lähdekoodi ja Windows-binaari (exe) sekä esimerkki testiohjelman tarvitsemasta hippa.in-tiedostosta. Lisäksi paketissa on JavaScriptin voimin toimiva html-sivu, jonka avulla voi tutkia pelin lopputulosta selaimessa. Tiedostot on luotu Linuxissa, joten tekstien rivinvaihdot eivät välttämättä näy oikein esimerkiksi Notepadilla!

Tämä testiohjelma ei ole sama kuin lopullinen turnausohjelma eikä esimerkiksi mittaa tekoälyn käyttämää muistia ja aikaa eikä huolehdi muisti.dat-tiedoston tuhoamisesta. Ohjelma pyytää tekoälyjen ajamiseen käytettävät komennot, kopioi tiedoston hippa.in tiedostoon hippa.txt ja jatkaa turnausta tästä kohti, kunnes kaikki pakenijat on saatu kiinni.

Ohjelman nimi

Jokaisella ohjelmalla on oltava nimi. Nimen maksimipituus on noin kahdeksan merkkiä, ja sallitut merkit ovat isot ja pienet aakkoset ilman skandinaavisia merkkejä, numerot, viiva ja alaviiva, tiiviimmin -_A-Za-z0-9.

Ohjelmointikieli

Ohjelmointikielen suhteen ei ole varsinaisia rajoituksia. Testiympäristössä toimiva käännetty ohjelma riittää, ja myös yleisimmät skriptikielet (PHP, Python, Ruby, Perl) kelpaavat ilman muuta. Koneeseen on asennettu myös Java-kehitysympäristö. Muista kääntäjistä käytössä ovat ainakin GCC:n C-, C++-, Objective-C- ja Fortran-kääntäjät, Haskell-kääntäjä (GHC) sekä Free Pascal ja FreeBASIC. Muista kielitoiveista on syytä ilmoittaa ajoissa, jotta mahdolliset ongelmat selviävät jo ennen lopullista turnausta. Tällöin on hyvä lähettää myös pieni esimerkkiohjelma, joka lukee yhtä tiedostoa ja kirjoittaa toiseen, jotta nämä tärkeät toiminnot voidaan todeta toimiviksi.

GCC:llä ja FPC:llä käännökset tehdään -O2-lipun kanssa ja GHC:llä -O-lipun kanssa. Muuten käytetään kääntäjien ja tulkkien oletusasetuksia. Lisäpyyntöjä ohjelmien kääntämisen ja ajamisen suhteen voi esittää ilmoittautumisen yhteydessä, jos jokin yksinkertainen asetus vaikuttaa olennaisesti ohjelman toimintaan.

Lopussa on vielä joitakin tarkennuksia kielikysymyksiin liittyen.

Kilpailukoneen tiedot

Ohjelmia päivitetään, jos uusia versioita ilmestyy.

Osallistuminen

Ohjelmat ja niiden lähdekoodit tulee lähettää ennen kilpailuajan päättymistä osoitteeseen hippakilpailuun@kyt.key.dy.fi. Jos testijärjestelmässä on sopiva kääntäjä tai tulkki, käännettyä ohjelmaa ei luonnollisestikaan tarvita. Viestiin kuuluvat seuraavat asiat:

Mainitut tiedot julkaistaan kilpailun tulossivulla. Mikäli jostain syystä ei halua nimensä tulevan julki, asiasta on syytä mainita ilmoittautumisviestissä. Ohjelmasta voi lähettää myös useamman eri version, jolloin näistä viimeinen osallistuu kilpailuun.

Sanallisten selitysten tarkoitus on kertoa muille kilpailijoille, millaisia ratkaisuideoita ongelmaan on löytynyt. Selostuksessa kannattaa siis paneutua erityisesti tekoälyn strategiaan, jos sillä on sellainen, mutta myös käytetyistä algoritmeista ja menetelmistä voi kertoa lyhyesti. Tulevia kilpailuja ajatellen olisi mukava tietää lisäksi, millaista käyttöä on keksitty tekoälyn muistitiedostolle (muisti.dat), jota ei ole ennen sallittu.

Viestin saapumisesta lähetetään vahvistus muutaman päivän kuluessa.

Palkinnot

Voittaja voi halutessaan lunastaa runossa luvatun rinkelin seuraavassa Putkamiitissä.

Tarkennuksia

Säännöt:

Ohjelmat:

Kielet:

Tulokset on nyt julkaistu.

Jos jokin vielä askarruttaa, kysymyksiä voi esittää keskustelussa tai lähettää sähköpostilla.

Tietoa sivustosta