Kilpailut: Valtapeli

Valtapeli on kahden pelaajan lautapeli, jossa ensimmäinen pelaaja yrittää valloittaa pelilaudalta mahdollisimman suuria yhtenäisiä alueita ja toinen yrittää estää tämän. Tässä kilpailussa on tehtävänä ohjelmoida tekoäly Valtapeliin.

Kilpailuaika

Kilpailu alkaa maanantaina 17.12.2012 kello 15.00 ja päättyy sunnuntaina 13.1.2013 kello 18.00.

(Nyt kilpailu on ohi ja tulokset on julkaistu.)

Pelin säännöt

Pelilauta on kooltaan 16×16 ruutua. Pelaajat saavat vuorotellen vallata yhden vapaan ruudun mistä tahansa pelilaudalta, kunnes lauta on täynnä. Aloittaja saa kustakin valtaamastaan yhtenäisestä alueesta A×A pistettä, missä A on alueen ruutujen määrä. Toinen pelaaja ei saa pisteitä vaan pyrkii pelkästään häiritsemään ensimmäistä.

Seuraavassa kuvassa on eräs mahdollinen Valtapelin lopputilanne. Oransseista ruuduista muodostuvat 63 ja 65 ruudun alueet ja violeteista 1, 2, 12 ja 113 ruudun alueet. Jos oranssi on aloittaja, hän saa 63² + 65² = 8194 pistettä. Jos taas violetti on aloittaja, hän saa 1² + 2² + 12² + 113² = 12918 pistettä. Kummassakaan tapauksessa toinen pelaaja ei saa pisteitä.

Kilpailun pistelasku

Kokonaiskilpailussa tekoäly saa pisteen jokaisesta vastustajasta, jota vastaan saa suuremman pistemäärän kuin vastapuoli itse aloittaessaan. Jos tuloksiin jää vielä tasatilanteita, vertaillaan tasoissa olevien tuloksia toisiaan vastaan tai tarvittaessa yksittäisten otteluiden pistemääriä pienimmästä alkaen.

Ohjelman toiminta

Tekoäly on käynnissä yhden pelin alusta loppuun. Se on komentoriviohjelma, joka lukee kilpailuohjelman syötettä (vastustajan siirtoja) kuten käyttäjän syötettä (näppäimistöä) ja tulostaa joka kierroksella vastauksensa kuten ruudullekin. Ohjelman toiminnasta on esimerkkejä joillakin yleisillä kielillä. Huomio! Joissain kielissä pitää tulostuksen jälkeen kutsua flush-funktiota, kuten esimerkkiohjelmissa tarvittaessa tehdään.

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. Siirto muodostuu kahdesta kokonaisluvusta, koordinaateista, jonka pelaaja valtaa. Esimerkiksi seuraavat rivit tarkoittavat pelilaudan kulmia:

1 1
1 16
16 1
16 16

Jos ohjelma kaatuu, ylittää aikarajan tai tekee virheen, se sammutetaan ja sen loput vuorot pelataan esimerkkiohjelman tapaan eli siirto tehdään ensimmäiseen vapaaseen ruutuun.

Ohjelman rajoitukset

Ohjelma saa käyttää kokonaisuudessaan enintään 512 megatavua muistia ja 30 sekuntia laskenta-aikaa kussakin ottelussa. Ohjelman ajankäyttö pitää mitoittaa sen mukaan, että testikoneen x86-64-prosessorin kellotaajuus on 1,73 GHz. Kilpailussa mitataan aikaa, jonka ohjelma itse käyttää, eli jos ohjelma joutuu odottamaan vastustajan siirtoa, kello ei käy.

Ohjelman pitää toimia joka ajokerralla samalla tavalla. Satunnaislukuja ei saa käyttää. Kellonaika ja tietokoneen nopeus eivät saa vaikuttaa tekoälyn toimintaan.

Ohjelman pitää keskittyä pelaamaan pelejä kunnolla. Kaikenlainen vilppi johtaa hylkäykseen.

Testausohjelma

Oman tekoälyn toimintaa voi testata testausohjelmalla, jossa kaksi pelaajaa (ihmistä tai tekoälyä) voi pelata vastakkain. Testaaminen vaatii Java-tuen. Testausohjelma ei sisällä ajanottoa, muistirajaa eikä muitakaan erityisiä tarkistuksia.

Ohjelman nimi

Jokaisella ohjelmalla on oltava nimi, jonka pituus on 3–9 merkkiä ja joka muodostuu pelkästään kirjaimista a–z ja A–Z ja numeroista 0–9.

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:

• Bash (4.2.39)
• C++ (GCC 4.7.2, -std=c++11)
• C (GCC 4.7.2, -std=c1x)
• C# (Mono 2.10.8, dmcs, C# 4.0)
• FreeBASIC (0.24.0)
• Haskell (GHC 7.6.1)
• Java (OpenJDK 1.7.0)
• JavaScript (SpiderMonkey 1.8.5)
• Lua (5.2.1)
• Pascal (Free Pascal 2.6.0)
• Perl (5.16.2)
• PHP (5.4.9)
• Python (2.7.3 ja 3.3.0)
• Ruby (1.9.3)
• VB.NET (Mono 2.10.8, VB.NET-kääntäjä 0.0.0.5943)

Tekoälyjen tulee pitäytyä kielten perusominaisuuksissa; kääntäjästä, kirjastoista, käyttöjärjestelmästä tai prosessorin tyypistä riippuvaisia ominaisuuksia ei pidä käyttää. Ohjelman on toimittava yllä mainituilla välineillä 64-bittisessä 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:

• osallistujan nimi ja nimimerkki Ohjelmointiputkassa, jos on
• tekoälyn nimi (katso rajoitukset!)
• käytetty ohjelmointikieli (katso vaihtoehdot!)
• tiivis kuvaus tekoälyn toimintaperiaatteesta
• liite: tekoälyn lähdekoodi (enintään 1 Mt)
• liite: tekoälyn datatiedostot (jos tarpeen; enintään 1 Mt)

Tiedot tulee lähettää sähköpostitse osoitteeseen kilpailu@ohjelmointiputka.net. Viestin on oltava perillä kilpailuajan puitteissa. Tiedot julkaistaan kilpailun tulossivulla; jos ehdottomasti ei halua nimeään tai nimimerkkiää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ä. Uusia versioita saa lähettää kilpailuajan loppuun asti; viimeinen toimiva versio katsotaan lopulliseksi.

Kilpailuun saa halutessaan osallistua myös usealla eri ohjelmalla, kunhan niiden toimintaperiaatteet ovat selvästi erilaiset.

Tarkennuksia

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