Kirjautuminen

Haku

Tehtävät

Kilpailu

Algoritmikisa
Putka Open 2020 -kisan
Finalistit julkaistaan pian...

Kilpailut: Väripelikilpailu

Järjestäjä: Antti Laaksonen

Kilpailutehtävä

Kilpailutehtävänä on ohjelmoida tekoäly väripeliin. Pelissä on tarkoituksena tyhjentää mahdollisimman täydellisesti eriväristen neliöiden muodostama pelikenttä. Kilpailussa on kaksi pelityyppiä: yksinpeli, jossa tekoäly koettaa tyhjentää koko kentän yksin, sekä moninpeli, jossa kukin tekoäly poistaa kentältä omaa väriään. Tekoälyn lisäksi jokainen osallistuja toimittaa kilpailuun yhden oman väripelin aloitustilanteen.

Kilpailuaika

1. kesäkuuta 2005 – 30. kesäkuuta 2005

Väripelin säännöt

Pelikenttä on aluksi täynnä erivärisiä neliöitä.

Pelikentältä saa poistaa neliöitä, jotka muodostavat ryhmän. Ryhmään kuuluvat neliöt muodostavat yhtenäisen samanvärisen alueen. Ryhmässä täytyy olla ainakin kaksi neliötä. Jos poistetun ryhmän yläpuolella on neliöitä, ne putoavat alemmas. Esimerkkipelissä suurin ryhmä on neljän punaisen neliön muodostama L-kirjaimen muotoinen alue. Jos tämä ryhmä poistetaan, pelikenttä näyttää tältä:

Jos neliökasojen välille uhkaa jäädä tyhjää tilaa, kasat yhdistyvät. Seuraavassa kuvassa pelikentältä on poistettu ensin kolmen sinisen neliön muodostama ryhmä ja sen jälkeen muodostunut neljän vihreän neliön ryhmä. Nyt pelikentällä on kaksi erillistä neliökasaa, jotka yhdistyvät.

Pelissä pyritään poistamaan neliöitä sellaisessa järjestyksessä, että lopulta jäljelle jäävien neliöiden määrä on mahdollisimman pieni. Kaikkien neliöiden poistaminen ei ole aina mitenkään mahdollista. Moninpelissä poistetaan ainoastaan omanvärisiä neliöitä.

Tekoälyn nimi

Keksi tekoälylle omaperäinen nimi, jonka pituus on 3 – 8 kirjainta. Tätä nimeä käytetään tekoälyyn liittyvissä tiedostoissa ja myöhemmin tuloslistoissa.

Yksinpeli

Tekoäly lukee pelitilanteen samassa hakemistossa olevasta tiedostosta [nimi].luk, jossa [nimi] on tekoälyn nimi. Jos tekoälyn nimi on kake, tiedoston nimi on siis kake.luk. Tiedoston ensimmäisellä rivillä on neljä lukua: pelikentän leveys ja korkeus, värien määrä sekä pelitapa. Pelikentän leveys ja korkeus ovat 5 – 30 neliötä. Värien määrä on 2 – 8. Yksinpelissä pelitapa on 0.

Tiedoston seuraavat rivit vastaavat pelikentän rivejä. Värinumero 0 tarkoittaa tyhjää tilaa. Muut värinumerot (1, 2, 3, ...) kuvaavat erivärisiä neliöitä. Rivin numeroiden määrä on sama kuin pelikentän leveys. Seuraava tiedosto vastaa esimerkkikuvan aloitustilannetta.

6 5 5 0
1 2 1 3 1 2
4 3 5 5 4 3
4 5 4 4 4 5
5 2 2 3 3 5
4 3 5 3 4 2

Tekoäly kirjoittaa tiedostoon yhden poistettavaan alueeseen kuuluvan neliön koordinaatit. Samassa hakemistossa olevan tiedoston nimi on [nimi].kir, jossa [nimi] on tekoälyn nimi. Jos tekoälyn nimi on kake, tiedoston nimi on siis kake.kir. Pelikentän vasemman yläkulman koordinaatit ovat (1, 1), ja numerot kasvavat vasemmalta oikealle ja ylhäältä alas. Koordinaateista ensimmäinen kuvaa saraketta ja toinen riviä.

Esimerkissä punaisen L-kirjaimen muotoisen ryhmän poistamisen voi ilmoittaa neljällä tavalla. Seuraava merkintä osoittaa ryhmän yläkärkeen, toisen rivin viidenteen sarakkeeseen.

5 2

Tähän päättyy ohjelman suoritus yhden pelivuoron osalta. Ohjelman ei siis pidä tulostaa mitään tekstiä näytölle eikä avata näkyviin ikkunaa. Sen ainoa tehtävä on luoda samaan hakemistoon [nimi].kir-tiedosto, jossa on tieto ohjelman poistamasta alueesta. Muita tiedostoja ohjelma ei saa luoda.

Tekoälyn täytyy suoriutua poistettavan ryhmän valinnasta kahdessa sekunnissa. Jos valinta venyy tätä pidemmäksi tai tekoäly ei kirjoita tiedostoon mitään, peli keskeytyy ja senhetkinen tilanne tulkitaan lopulliseksi. Peli päättyy myös, jos tekoäly osoittaa yksinäiseen neliöön, jota ei pysty poistamaan, tai neliökasojen ulkopuolelle. Peli päättyy viimeistään, kun pelikentällä ei ole yhtään poistettavaa ryhmää.

Moninpeli

Moninpelissä 2 – 8 tekoälyä kamppailee keskenään niin, että jokainen poistaa pelikentältä ainoastaan tietynvärisiä neliöitä. Moninpeli vastaa yksinpeliä seuraavin muutoksin.

Tiedostossa [nimi].luk ensimmäisen rivin neljäs numero kuvaa sitä väriä, jota tekoäly pyrkii poistamaan. Lisäksi tiedoston lopussa on kutakin värinumeroa koskeva rivi, jossa on kaksi numeroa. Numeroista ensimmäinen on 1, jos tätä väriä keräävä tekoäly on mukana pelissä, ja muussa tapauksessa 0. Toinen numero kertoo, kuinka paljon tätä väriä oli aloitustilanteessa pelikentällä. Rivien järjestys on sama kuin värinumeroiden järjestys.

Seuraavassa tiedostossa on moninpelin aloitustilanne. Kun ensimmäisen rivin viimeinen numero on jokin muu kuin 0, se kuvaa kerättävän värin numeroa ja ilmaisee, että meneillään on moninpeli. Tässä pelissä jokaisella pelikentän värillä on ainakin aluksi oma kerääjänsä, sillä kaikki lisärivit alkavat luvulla 1. Pelikentältä ei ole poistettu vielä mitään, minkä vuoksi värien aloitusmäärät vastaavat pelikentän värien määriä.

6 5 5 1
1 2 1 3 1 2
4 3 5 5 4 3
4 5 4 4 4 5
5 2 2 3 3 5
4 3 5 3 4 2
1 3
1 5
1 7
1 8
1 7

Moninpelin pelivuorot kulkevat värijärjestyksessä. Ensin neliöitä poistaa siis väriä 1 keräävä tekoäly, sen jälkeen väriä 2 keräävä tekoäly jne., kunnes pelikierroksen päättää viimeistä väriä keräävä tekoäly. Moninpelistä aikarajan ylittänyt tai virheellisen poiston tehnyt tekoäly suljetaan pois muiden jatkaessa. Tekoälyn on pakko poistaa omanvärinen neliöryhmä. Jos pelikentältä ei pysty poistamaan tiettyä väriä, tekoälyn vuoro jää välistä.

Ympäristö

Ohjelmat ajetaan tietokoneella, jossa on 3 GHz prosessori, 1 Gt muistia ja Windows XP -käyttöjärjestelmä.

Ohjelmointikieli on vapaa. Kilpailuun lähetetään sekä ohjelman lähdekoodi että käännetty Windowsissa toimiva ohjelma. Kilpailukoneelle on asennettuna Java-, PHP- ja Python-tulkit, joiden kautta ohjelma voidaan myös ajaa.

Oma aloitustilanne

Jokainen kilpailija toimittaa tekoälyn lisäksi yhden väripelin aloitustilanteen. Nämä aloitustilanteet ovat osana tekoälyjen testiaineistoa. Aloitustilanne tallennetaan tiedostoon, jonka nimi on [nimi].alk. Jos siis tekoälyn nimi on kake, tiedoston nimi on kake.alk. Tiedosto vastaa muuten tekoälyn lukemaa tiedostoa, paitsi että pelitapaa ei ilmoiteta. Tiedoston ensimmäisellä rivillä on siis ainoastaan kolme lukua.

Kilpailuun osallistuminen

Lähetä kesäkuun loppuun mennessä sähköpostilla osoitteeseen kilpailu@ohjelmointiputka.net viesti, jossa on ainakin seuraavat tiedot:

Laita viestin liitteeksi kolme tiedostoa: tekoälyn lähdekoodi, ajettava ohjelmatiedosto ja oma aloitustilanne. Tiedostojen nimien alkuosan täytyy olla sama kuin tekoälyn nimi. Jos esimerkiksi tekoälysi nimi on kake ja olet ohjelmoinut sen C-kielellä, tiedostojen nimet ovat kake.c, kake.exe ja kake.alk.

Viestin saapumisesta perille tulee varmistus.

Ohjelmien arvostelu

Kaikille tekoälyille tulee sama tehtäväsarja. Tehtävien määrää ja laatua ei ole päätetty etukäteen. Jokainen poistettu omanvärinen ruutu kartuttaa tekoälyn pistemäärää. Jos useampi tekoäly saavuttaa tarkalleen saman kokonaispistemäärän, vähemmän poistoja tehnyt katsotaan paremmaksi.

Kysymykset

Kilpailuun liittyviä kysymyksiä voi lähettää osoitteeseen kilpailu@ohjelmointiputka.net tai kilpailukeskusteluun.

Menestystä tekoälyn ohjelmointiin!

Uutisia 5.6.

Lukutiedoston rakenne moninpeleissä on nyt alkuperäistä laajempi. Tiedoston jatkeena aloitusrivin ja pelikentän jälkeen on kutakin värinumeroa vastaava rivi, jolla on kaksi numeroa. Ensimmäinen numero on 1, jos pelissä on mukana tätä väriä keräävä tekoäly, ja muuten 0. Toinen numero kertoo kyseisen värin määrän aloitustilanteessa eli silloin, kun pelikenttä oli vielä koskematon. Tekoäly voi halutessaan hyödyntää näitä tietoja pelatessaan.

Moninpelin sääntöihin on tullut lisäksi pari tarkennusta. Aluksi jokaisella pelikentän värillä on oma kerääjänsä. Aikarajan ylitykset karsivat pelaajajoukkoa. Tekoälyt poistavat neliöitä värien numerojärjestyksessä. Pelikierroksen aloittaa siis se tekoäly, joka kerää väriä 1 ja lopettaa se tekoäly, joka kerää viimeistä väriä. Kaikki muut tekoälyt poistavat omia neliöitään näiden välillä numerojärjestyksessä.

Jos tekoäly käyttää aikaa enemmän kuin kaksi sekuntia tai ei kirjoita tiedostoon minkään neliön koordinaatteja, peli päättyy. Moninpelissä muut tekoälyt jatkavat vielä tämän jälkeen ja keskeyttäneen tekoälyn väri merkitään keräämättömäksi.

Uutisia 14.6.

Vielä kerran kilpailun sääntöjä joudutaan muuttamaan. Tekoälyn täytyy joka tilanteessa poistaa neliöryhmä kentältä. Yksinpelissä kaikenväriset ryhmät kelpaavat, moninpelissä tekoäly saa poistaa ainoastaan omanvärisiä neliöitä. Jos kentällä ei ole yhtään poistettavaa (moninpelissä oikeanväristä) ryhmää, tekoälyä ei myöskään kutsuta. Aikaisemmin säännöissä oli sallittu sekä poistamatta jättäminen että moninpelissä toisenvärisen ryhmän poistaminen.

Uutisia 10.7.

Kaikki testipelit on nyt pelattu, ja tulossivulla on kilpailuun osallistuneet tekoälyt, niiden saamat pisteet yksin- ja moninpelissä sekä mahdollisuus katsella jälkeenpäin pelejä. Kaikki tekoälyt ja niiden lähdekoodit pystyy myös kopioimaan. Näin päättyi tämä kilpailu – kiitos osallistujille!

Tietoa sivustosta