Kirjautuminen

Haku

Tehtävät

Kilpailut: Viivapeli

Järjestäjä: Metabolix

Tässä kilpailussa tehtävänä on ohjelmoida tekoäly kahden pelaajan peliin, jossa kumpikin pelaaja ohjaa viivan piirtoa ruudukossa. Joka kierroksella kumpaakin viivaa jatketaan ruutu johonkin suuntaan, ja pelin häviää se, jonka viiva ensiksi törmää jo käytettyyn ruutuun.

Kilpailuaika

Kilpailu alkaa lauantaina 13.3. kello 7 ja päättyy lauantaina 17.4. kello 5. (Nyt kilpailuaika on päättynyt ja tuloksetkin on julkaistu.)

Pelin säännöt

Viivapeliä pelataan suorakulmaisessa ruudukossa, jonka sivujen pituudet ovat parilliset. Pelaaja 1 aloittaa ruudusta (0, 0) ja pelaaja 2 ruudusta (1, 0). Säännöllisin välein kummankin pelaajan viiva kasvaa päästään yhden ruudun ylös, alas, vasemmalle tai oikealle. Jos viiva törmää ruutuun, joka on jo käytetty, pelaaja häviää. Jos kummatkin törmäävät samalla vuorolla, peli päättyy tasan. Viivat kasvavat yhtä aikaa, mutta aloitussijaintiensa vuoksi ne eivät voi päästä samalla hetkellä samaan ruutuun, joten epäselviä tilanteita ei synny.

Viiva voi kasvaa laudan reunan yli ja jatkaa vastakkaiselta reunalta. Tällöin viivan koordinaatit "pyörähtävät ympäri": Jos pelilauta on 12 ruutua leveä ja viiva kasvaa ruudusta (0, 4) vasemmalle, se päätyy ruutuun (11, 4). Vastaava pätee myös y-suunnassa.

Seuraavassa kuvassa on 12×6 ruudun pelilauta, jonka vasemmassa alakulmassa on ruutu (0, 0). Laudalla on kaksi viivaa, jotka ovat liikkuneet sääntöjen mukaisesti. Pelin lopussa sininen (pelaaja 2) törmäsi itseensä ja punainen (pelaaja 1) törmäsi siniseen, eli peli päättyi tasan. (Sininen olisi mahtunut etenemään vielä sivulle, jolloin se olisi voittanut, mutta tällä kertaa se ei kääntynyt ajoissa.)

Tässä kilpailussa pelialue on kooltaan vähintään 4×4 ja enintään 160×120 ruutua, ja siirtojen välissä on vähintään 0,05 sekuntia ja enintään sekunti. Lopulliset pelilaudat ja -nopeudet valitaan myöhemmin osallistujamäärän ja tekoälyjen tason mukaan. Pelejä pelataan usealla eri laudalla ja nopeudella, joten tekoälyn on sopeuduttava erilaisiin tilanteisiin.

Ohjelman toiminta

Tekoäly on komentoriviohjelma, joka lukee kilpailuohjelman syötettä (mm. vastustajan siirtoja) samalla tavalla kuin tavallisesti käyttäjän syötettä (näppäimistöä) ja tulostaa siirtonsa samalla tavalla kuin yleensä ruudullekin. Ohjelman toiminnasta on esimerkkejä joillakin yleisillä kielillä. Huomioitavaa: Jotta tekoälyn lähettämät viestit pääsisivät perille, tulostuksen jälkeen on joissain kielissä tarpeen kutsua flush-funktiota. Kaikki esimerkkiälyt toimivat oikein, joten jos vähänkään epäilyttää, kannattaa ottaa niistä mallia.

Pelaaminen tapahtuu reaaliajassa. Tekoälylle tulostetaan jatkuvasti tietoa pelin kulusta, ja tekoäly saa milloin tahansa ilmoittaa viivansa etenemissuunnan. Viiva kasvaa aina siihen suuntaan, jonka tekoäly on viimeksi ilmoittanut; tekoälyn ei tarvitse vastata ennen jokaista siirtoa, tai toisaalta se saa muuttaa suuntaansa useampaankin kertaan seuraavaa siirtoa odotellessaan. Tekoälyn kuuluu siis jäljitellä ihmistä: seurata pelin kulkua ja yrittää parhaansa mukaan pysytellä mukana.

Kun ohjelma käynnistetään, sille syötetään heti sen oma pelinumero, joka on 1 tai 2. Ohjelman täytyy vastata viiden sekunnin kuluessa tulostamalla oma nimensä.

Kun molemmat pelaajat ovat vastanneet, niille ilmoitetaan pelilaudan koko ja pelin nopeus. Syöterivin alussa on sana PELI, jonka jälkeen tulevat välilyönnein eroteltuina laudan leveys ja korkeus ja siirtojen välinen aika sekunnin tuhannesosina. Esimerkiksi tämä rivi tarkoittaisi aiemmassa kuvassa esitettyä 12×6 ruudun lautaa ja siirtoja 0,23 sekunnin välein:

PELI 12 6 230

Ennen ensimmäistä liikahdusta on sekunnin tauko, jonka aikana tekoälyn on parasta tulostaa aloitussuuntansa; muuten pelaajan 1 viiva etenee vasemmalle ja pelaajan 2 viiva oikealle. Seuraavat siirrot tapahtuvat ilmoitetulla tiheydellä.

Tekoäly ilmoittaa oman liikesuuntansa rivillä +X, -X, +Y tai -Y sen mukaan, haluaako edetä x- vai y-suunnassa ja positiiviseen vai negatiiviseen suuntaan. Esimerkiksi negatiivinen y-suunta (alas) ilmoitetaan näin:

-Y

Tapahtuneet liikkeet ilmoitetaan ohjelmalle riveillä, joiden alussa on sana SIIRTO ja tämän jälkeen välilyönnein eroteltuina siirtyneen pelaajan numero sekä sen ruudun koordinaatit, johon pelaaja eteni. Seuraava rivi kertoo, että pelaaja 1 on edennyt kohtaan (3, 4):

SIIRTO 1 3 4

Ohjelmalle ilmoitetaan kullakin liikekerralla aina ensin pelaajan 1 siirto ja sitten pelaajan 2 siirto.

Kun tekoäly tulostaa viestin PING, sille vastataan heti viestillä PONG. Tällä tavalla tekoäly pystyy tarkistamaan, onko pelissä tapahtunut jotain: ensin se tulostaa viestin PING ja sitten lukee saamiaan viestejä, kunnes löytää PONG-vastauksen. Tekoälyn ei siis tarvitse arvioida itse ajan kulkua, vaan se voi aina sopivan hetken tullen tarkistaa, onko pelissä tapahtunut jotain.

PING
PONG

Kun peli päättyy, tekoälylle tulostetaan rivi LOPPU. Tämän jälkeen ohjelman tulee sulkeutua.

LOPPU

Testaus- ja esimerkkiohjelmat

Oman tekoälyn toimintaa voi testata testausohjelmalla, jossa kaksi pelaajaa (ihmistä tai tekoälyä) voi pelata vastakkain. Testaaminen vaatii Java-tuen. Testausohjelman voi ladata myös JAR-muodossa työpöytäohjelmaksi.

Vinkki: Jos tekoäly ei toimi testausohjelmassa suoraan, voit tehdä Windowsissa bat-tiedoston tai Linuxissa sh-tiedoston, joka käynnistää ohjelman. Bat-tiedosto voisi näyttää tältä:

@echo off
C:
cd "C:\jokin hakemisto\ohjelman sijainti"
ohjelma.exe

Kilpailua varten on tehty myös eri kielillä esimerkkiohjelmia, jotka käyttävät kaikkia yllä mainittuja viestejä. Kannattaa katsoa! Esimerkki lukee viestejä ja lähettää oman liikesuuntansa, mutta sen suurempaa älyä sillä ei ole.

Ohjelman rajoitukset

Ohjelma voi käyttää kokonaisuudessaan reilut 512 megatavua muistia. Suuremman muistimäärän varaaminen epäonnistuu. Jos ohjelma ei käsittele tilannetta, se luultavasti kaatuu. (Kaikissa kielissä tilanteen käsittely ei valitettavasti ole mahdollista, vaan muistinkäyttö tulee arvioida etukäteen.)

Ohjelmalla on käytössään yksi x86-prosessorin ydin, jonka kellotaajuus on 1,73 GHz. Säikeitä saa käyttää ohjelmointiympäristön normaalilla tavalla (C:ssä ja C++:ssa pthreads-kirjastolla), kuitenkin enintään 32.

Kaikenlainen epäilyttävä tai kiero toiminta johtaa hylkäykseen.

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

Kilpailukoneella on kääntäjiä ja tulkkeja monille ohjelmointikielille. Mikäli kuitenkin sopiva kieli puuttuu listalta, lähetä sähköpostia tai osallistu keskusteluun, niin selvitetään, voiko asialle tehdä jotain.

Tuetut ohjelmointikielet versioineen:

Tekoälyjen tulee pitäytyä kielten perusominaisuuksissa; kääntäjästä, kirjastoista tai käyttöjärjestelmästä riippuvaisia ominaisuuksia on parasta välttää. Ohjelman on toimittava yllä mainituilla välineillä GNU/Linux-käyttöjärjestelmässä.

Käännöksissä käytetään kohtuullisia optimointiasetuksia, esimerkiksi GCC:llä ja FPC:llä valitsinta -O2.

Osallistuminen

Ilmoittautumiseen tarvitaan seuraavat tiedot:

Tiedot tulee lähettää osoitteeseen kilpailu@viivapeli.dy.fi. Viestin on oltava perillä viimeistään 17.4. kello 5.00 aamulla. Tiedot julkaistaan kilpailun tulossivulla; jos ehdottomasti ei halua nimeään julki, asiasta voi mainita viestissä.

Osallistumisesta lähetetään vahvistus muutaman päivän kuluessa. Tekoäly myös testataan lyhyesti, ja ilmenneistä virheistä kerrotaan vahvistusviestissä. Kukin kilpailija voi osallistua vain yhdellä tekoälyllä. Ohjelmasta saa lähettää keskeneräisiäkin versioita; viimeinen toimivalta vaikuttava lähetys katsotaan lopulliseksi.

Palkinnot

Jottei pelaamisen tarvitsisi loppua tähän, voittaja saa lunastaa ensi kesän Putkamiitissä sinisen ja punaisen värikynän ja ruutupaperia.

Tarkennuksia

Kysymyksiä ja palautetta kilpailusta voi lähettää sähköpostitse tai keskusteluun.

Tietoa sivustosta