Kirjautuminen

Haku

Tehtävät

Kilpailut: Pomppis

Järjestäjä: Metabolix

Tässä kilpailussa on tehtävänä ohjelmoida tekoäly kahden pelaajan lautapeliin, jossa nappulat pomppivat toistensa yli kohti laudan vastakkaista reunaa. Kaikki tekoälyt pelaavat vuorollaan toisiaan vastaan, ja jokaisesta voitetusta pelistä saa yhden pisteen. Kilpailun voittaa suurimman kokonaispistemäärän saavuttanut tekoäly.

Kilpailuaika

Kilpailu alkaa lauantaina 26.12.2009 ja päättyy sunnuntaina 17.1.2010. Ohjelmia saa lähettää sunnuntai-iltana keskiyöhön saakka.

(Nyt kilpailu on jo päättynyt ja tulokset on julkaistu.)

Pelin säännöt

Pomppista pelataan 16×16 ruudun kokoisella pelilaudalla. Siinä on kaksi pelaajaa, joilla on kummallakin alussa 16 pelinappulaa. Pelaajat aloittavat laudan vastakkaisilta reunoilta, ja tavoitteena on siirtää kaikki pelinappulat vastustajan päätyyn.

Aluksi kummankin pelaajan nappulat ovat neliössä keskellä laudan sivua.

Pelaajat pelaavat vuorotellen. Pelaajalla on kolme vaihtoehtoa:

Seuraavaan kuvaan on piirretty vasemmassa alakulmassa olevan nappulan ainoa mahdollinen hyppyreitti oikeaan yläkulmaan. Jokainen hyppy kulkee yhden sinisen nappulan puolelta toiselle. Koko hyppysarjan saa kulkea samalla vuorolla.

Seuraavassa kuvassa on eräs mahdollinen pelitilanne. Yksi nappula on merkitty valkoisella täplällä, ja mustat täplät merkitsevät ruutuja, joihin nappula voisi siirtyä seuraavalla vuorolla. Nappula pääsee liikkumaan askeleen vasemmalle tai alas tai hyppimään useita ruutuja lähtemällä ylöspäin.

Kun nappula pääsee pelilaudan viimeiselle riville, se poistetaan pelistä. Voittaja on se, joka ensin saa kaikki nappulansa pois pelistä. Seuraavassa kuvassa sininen pelaaja lähestyy maalialuetta. Oikeanpuoleisin nappula hyppää maalialueelle ja katoaa.

Jos peli ei pääty aiemmin, 1000 pelikierroksen eli yhteensä 2000 vuoron jälkeen lähempänä maalia oleva pelaaja voittaa. Mukaan lasketaan jokaisen nappulan etäisyys maalirivistä, eli esimerkiksi rivillä 13 olevan nappulan matka maaliriville 16 olisi 3.

Ohjelman toiminta

Tekoäly on käynnissä yhden pelin alusta loppuun. Se on komentoriviohjelma, joka lukee kilpailuohjelman syötettä (vastustajan siirtoja) samalla tavalla kuin käyttäjän syötettä (näppäimistöä) ja tulostaa joka kierroksella vastauksensa samalla tavalla kuin ruudullekin. Ohjelman toiminnasta on esimerkkejä joillakin yleisillä kielillä.

Kun ohjelma käynnistetään, sille syötetään vuoronumero, joka on 1 tai 2. Ohjelman täytyy vastata rivillä, jolla on sen oma nimi. Tämän jälkeen pelaaja 1 aloittaa pelin.

Tekoälyn täytyy omalla vuorollaan tulostaa siirtonsa ja vastustajan vuorolla lukea vastustajan siirto. Pelilaudan rivit ja sarakkeet on numeroitu luvuin 1–16. Tekoäly aloittaa pelin aina pelilaudan siltä reunalta, jolla y-koordinaatti on 1, ja maali on aina reunalla, jolla y-koordinaatti on 16.

Nappulan siirtäminen ilmaistaan kahdella rivillä, joista ensimmäinen sisältää kirjaimen S ja toinen lähtö- ja maaliruutujen koordinaatit välilyönnein eroteltuina. Seuraavat rivit tarkoittavat siirtoa ruudusta (7, 3) ruutuun (6, 5):

S
7 3 6 5

Rivi T tarkoittaa, että tekoäly jättää vuoronsa väliin.

T

Kun peli päättyy, tekoälylle tulostetaan rivi L. Tällöin ohjelman pitää sulkeutua.

L

Omalla vuorollaan ohjelman tulee tulostaa joko S-komento koordinaatteineen tai T-komento. Jos komento on viallinen eikä testiohjelma ymmärrä sitä, peli päättyy ja virheen tehnyt tekoäly häviää. Samoin käy, jos tekoälyn ehdottama siirto on sääntöjen vastainen.

Vastustajan vuorolla tekoälylle ilmoitetaan vastustajan valinta täsmälleen yllä kuvatussa muodossa. Tekoälyn täytyy itse tunnistaa, milloin jokin nappula siirtyy maalialueelle ja katoaa; tästä ei ilmoiteta erikseen, vaan kyseessä on aivan tavallinen siirto.

Esimerkki

Seuraavassa on esimerkki tekoälyn toiminnasta. Rivin alussa > tarkoittaa, että rivi on syötetty ohjelmalle; muut rivit ovat ohjelman tulostamia. Oikeasti rivit eivät sisällä tätä merkkiä eivätkä ylimääräisiä välilyöntejä, vaan ne ovat edellisen osion mukaisia.

> 1
  Alypomppu
  S
  7 4 6 4
> S
> 10 13 10 12
  T
> S
> 8 13 10 11
  S
  7 3 5 5
> L
  1. Ohjelma lukee pelinumeronsa, 1.
  2. Ohjelma vastaa tulostamalla nimensä, Alypomppu.
  3. Ohjelma aloittaa pelin siirrolla (7, 4) => (6, 4).
  4. Ohjelma lukee vastustajan siirron (10, 13) => (10, 12).
  5. Ohjelma jättää vuoron väliin.
  6. Ohjelma lukee vastustajan toisen siirron ((8, 13) => (10, 11)). Nappula siis hyppää kahdesti.
  7. Ohjelma tulostaa siirron (7, 3) => (5, 5). Siirto on laiton, joten tekoäly häviää.
  8. Ohjelma lukee rivin L, joka kertoo, että peli on päättynyt. Ohjelma sulkeutuu.

Seuraavassa on sama peli toisen tekoälyn näkökulmasta. Tekoäly saa eri pelinumeron, ja kaikki koordinaatit on peilattu toisin päin.

> 2
  Janojussi
> S
> 10 13 11 13
  S
  7 4 7 5
> T
  S
  9 4 7 6
> L
  1. Ohjelma lukee pelinumeronsa, 2. Vastustaja aloittaa pelin.
  2. Ohjelma vastaa tulostamalla nimensä, Janojussi.
  3. Ohjelma lukee vastustajan siirron (10, 13) => (11, 13).
  4. Ohjelma tulostaa siirron (7, 4) => (7, 5).
  5. Ohjelma lukee vastapuolen siirron; vastapuoli jätti vuoronsa käyttämättä.
  6. Ohjelma tulostaa siirron (9, 4) => (7, 6). Nappula siis hyppää kahdesti.
  7. Ohjelma lukee vastapuolen valinnan. L kertoo, että vastapuoli teki virheen ja hävisi.
  8. Peli päättyi, joten ohjelma sulkeutuu.

Kilpailua varten on tehty eri kielillä esimerkkiohjelmia, jotka pyrkivät melko päättömästi kohti toista päätä.

Testausohjelma

Oman tekoälyn toimintaa voi testata testausohjelmalla, jossa kaksi pelaajaa (ihmistä tai tekoälyä) voi pelata vastakkain. Testaaminen vaatii Java- ja JavaScript-tuen. Jotta tekoäly toimisi testauksessa, voi olla tarpeen kutsua tulostuksen jälkeen erikseen flush-funktiota; esimerkkiälyissä on tarvittaessa tehty näin. Itse kilpailussa tätä lisävaatimusta ei ole.

Ohjelman rajoitukset

Ohjelma saa käyttää kokonaisuudessaan enintään 512 megatavua muistia ja 60 sekuntia prosessointiaikaa kussakin ottelussa. Ohjelman ajankäyttö pitää mitoittaa sen mukaan, että testikoneen x86-prosessorin kellotaajuus on 1,73 GHz. Kilpailussa mitataan ohjelman itse käyttämää aikaa, eli jos ohjelma joutuu odottamaan vastustajan siirtoa, kello ei käy. Rajojen ylittämisestä seuraa häviö.

Satunnaisuus

Ohjelman on toimittava joka ajokerralla samalla tavalla. Siirtoja ei saa arpoa millään sellaisella perusteella, että lopputulos voisi vaihdella eri ajokerroilla. Ohjelman lopputulos ei myöskään saa riippua siitä, miten nopeasti vastustaja tekee siirtonsa, vaan siirtojen täytyy perustua pelkästään pelitilanteeseen. Kun siis kaksi älyä laitetaan ottelemaan keskenään, ottelun on joka kerta kuljettava täsmälleen samalla tavalla riippumatta kellonajasta, tietokoneesta tai säätilasta!

Itse kehitettyjä pseudosatunnaislukuja saa käyttää, kunhan ne täyttävät tässä mainitut ehdot. Standardikirjastojen satunnaislukugeneraattorien käyttö ei ole sallittua, koska nekin saattavat eri tietokoneilla olla erilaisia.

Ohjelman nimi

Jokaisella ohjelmalla on oltava nimi. Sopiva pituus on 3–9 merkkiä; kohtuuttoman pitkät nimet pyydetään muuttamaan. Sallitut merkit ovat isot ja pienet aakkoset ilman skandinaavisia merkkejä, numerot, viiva ja alaviiva, tiiviimmin -, _, A–Z, a–z ja 0–9. Tarkista nimen kelpoisuus!

Ohjelmointikieli

Testikoneessa on Java-kehitysympäristö, GCC:n C-, C++-, Objective-C- ja Fortran-kääntäjät, Haskell-kääntäjä (GHC), Brainfuck-kääntäjä, Free Pascal ja FreeBASIC sekä Python-, Ruby-, Perl-, PHP- ja Lua-tulkit ja Mono-ympäristö, jossa voi kääntää VB.Net ja C#-ohjelmia, sekä Inferno-virtuaalikone Limbo-kääntäjän kera.

Basicin käyttäjien kannattaa käyttää FreeBASICia, koska se toimii testiympäristössä varmimmin. .Net-kielten käyttäjien on syytä varmistaa, että ohjelma toimii Mono-ympäristössä, ja pitäytyä varmuuden vuoksi .Net Framework 2.0:n tavallisissa ominaisuuksissa.

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, jotta toiminta voidaan varmistaa.

Käännöksissä käytetään kohtuullisia optimointiasetuksia (esimerkiksi GCC:llä ja FPC:llä -O2). Lisäpyyntöjä ohjelmien kääntämisen ja ajamisen suhteen voi esittää ilmoittautumisen yhteydessä.

Kilpailukoneen tiedot

Osallistuminen

Ohjelmien lähdekoodit ja muut tiedostot sekä tarvittaessa myös käännetyt ohjelmat tulee lähettää ennen kilpailuajan päättymistä osoitteeseen kilpailu@pomppis.dy.fi. Viestiin kuuluvat seuraavat asiat:

Mainitut tiedot julkaistaan kilpailun tulossivulla. Mikäli jostain syystä ei halua nimensä tulevan julki, asiasta voi mainita ilmoittautumisviestissä. Ohjelmasta voi lähettää myös useamman eri version, jolloin näistä viimeinen toimiva osallistuu kilpailuun. Myös selostukset julkaistaan tulosten yhteydessä, ja tarvittaessa niiden ulkoasua muokataan sen mukaan.

Jos käytetty ohjelmointikieli ei ole listalla, myös käännetty ohjelmatiedosto täytyy toimittaa. Muussa tapauksessa pelkkä lähdekoodi riittää osallistumiseen.

Kukin kilpailija voi osallistua kilpailuun vain yhdellä tekoälyllä. Osallistumisesta lähetetään vahvistus muutaman päivän kuluessa.

Palkinnot

Voittaja voi lunastaa ensi kesän Putkamiitissä muodikkaan superpallon.

Tarkennuksia

Kysymyksiä ja palautetta kilpailusta voi lähettää keskusteluun.

Tietoa sivustosta