Järjestäjä: Antti Laaksonen
Kesäkuussa 2005 Ohjelmointiputkassa pidettiin kilpailu, jossa tehtävänä oli ohjelmoida tekoäly väripeliin. Tässä pelissä ruudukosta poistetaan samanväristen neliöiden muodostamia ryhmiä. Poistojen jälkeen neliökasa tiivistyy niin, että neliöiden väliin ei jää tyhjää tilaa. Kilpailussa oli kaksi sarjaa: yksinpeli ja moninpeli. Yksinpelissä tekoäly poistaa kaikenvärisiä neliöitä, moninpelissä taas jokainen neliö poistaa omanvärisiä neliöitä. Tekoälyn lisäksi kukin kilpailija toimitti oman väripelin aloitustilanteen, jota käytettiin osana testiaineistoa.
Kilpailuun osallistui 14 tekoälyä, joiden toiminta ja toteutus poikkesivat suuresti toisistaan. Osallistujien joukossa oli useita tuttuja nimiä mm. viime vuoden ristinollakilpailusta, mutta moni osallistui myös kilpailuun ensimmäistä kertaa. Tekoälyjen testaus vei oman aikansa, sillä yhteen peliin saattoi helposti kuulua satoja neliöryhmien poistoja. Muutamat tekoälyt hyödynsivät annetun kahden sekunnin aikarajan kokonaan; toiset taas ilmoittivat valintansa sekunnin murto-osassa.
Seuraavassa taulukossa ovat kilpailuun osallistuneet tekoälyt järjestettyinä yksin- ja moninpelin yhteispistemäärän mukaan. Jokaisesta poistetusta neliöstä sai pisteen, ja poistettavien ryhmien koolla ei ollut merkitystä. Paras yksin- ja moninpeli tarkoittaa, kuinka monessa pelissä tekoäly onnistui poistamaan eniten neliöitä. Tyhjennys tarkoittaa, kuinka monessa yksinpelissä tekoäly onnistui poistamaan kaikki neliöt. Poistosuhde on yksinpelissä keskimääräinen poistetun neliöryhmän koko. Keskeytykset johtuivat tekoälyn virheestä tai ajanylityksestä.
| sija | tekoäly | ohjelmoija | kieli | yksinpeli | moninpeli | yhteensä | paras yks. | paras mon. | tyhjennys | poistosuhde | keskeytys |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1. | python | Henrik Huttunen | C++ | 16750 | 4929 | 21679 | 30 | 5 | 21 | 3,71 | 0 |
| 2. | pupilli | Ville Pettersson | C++ | 16732 | 4826 | 21558 | 35 | 2 | 22 | 3,84 | 0 |
| 3. | ogre | Jorma Sainio | C | 16503 | 4902 | 21405 | 16 | 2 | 14 | 4,09 | 0 |
| 4. | illi | Ilja Mäki | C++ | 16463 | 4880 | 21343 | 19 | 0 | 15 | 4,13 | 0 |
| 5. | Fantti | Joonas Mäkinen | C++ | 15937 | 4699 | 20636 | 5 | 0 | 4 | 3,27 | 1 |
| 6. | yritys | Otto Seiskari | C++ | 15827 | 4727 | 20554 | 3 | 0 | 3 | 3,38 | 0 |
| 7. | Naattori | Heikki Lehtosalo | C | 14958 | 4802 | 19760 | 3 | 3 | 4 | 4,64 | 0 |
| 8. | ESKO | Jaakko Puntila | QBasic | 14810 | 4944 | 19754 | 2 | 4 | 1 | 3,53 | 0 |
| 9. | colorado | Marko Rintamäki | C++ | 14542 | 4815 | 19357 | 6 | 2 | 3 | 3,35 | 0 |
| 10. | arpAI | Antti Karhu | C# | 14389 | 4707 | 19096 | 3 | 0 | 2 | 3,72 | 0 |
| 11. | ilepirav | Antti Laaksonen | Python | 14342 | 4753 | 19095 | 2 | 0 | 2 | 3,80 | 0 |
| 12. | bingo | Juhani Åhman | C++ | 14123 | 4763 | 18886 | 1 | 1 | 1 | 4,09 | 7 |
| 13. | iro | Niko Pahajoki | PHP | 13906 | 4971 | 18877 | 1 | 6 | 1 | 3,11 | 1 |
| 14. | TIT | Harry Karvonen | Java | 1410 | 3683 | 5093 | 3 | 2 | 1 | 3,10 | 25 |
Voit kopioida kaikki kilpailuun osallistuneet tekoälyt käännettyinä (520 kt) sekä niiden lähdekoodit (50 kt). Tekoälyjen toiminnasta on lisää tietoa esittelysivulla.
Yksinpelissä pelattiin 546 peliä. Näistä 196 pelissä käytettiin kilpailijoiden omia aloitustilanteita. Loput 350 peliä pelattiin satunnaisilla ruudukoilla, joita oli viisi kutakin kokoa. Ruudukoiden koot ja värimäärät olivat: 10x10 kahdeksalla värillä, 15x15 seitsemällä värillä, 20x20 kuudella värillä, 25x25 viidellä värillä ja 30x30 neljällä värillä. Moninpelissä pelattiin 280 peliä. Näistä 70 pelissä käytettiin viittä erikseen moninpeliin luotua ruudukkoa. Loput 210 moninpeliä käytiin yksinpelin pienimmillä (10x10, 15x15 ja 20x20) satunnaisruudukoilla.
Moninpelit pelattiin niin, että jokainen tekoäly sai vuorollaan olla kussakin asemassa. Jos tietyn värin kerääjän tilanne oli toista parempi, tästä ei siis aiheutunut haittaa. Tekoälyjen järjestys moninpelissä päätettiin yksinpelin tulosten perusteella seuraavasti: python, yritys, ilepirav, pupilli, Naattori, bingo, ogre, ESKO, iro, illi, colorado, TIT, Fantti, arpAI. Oletettavasti vahvimpia tekoälyjä ei näin päästetty vierekkäin. Värien määrästä riippumatta jokaista ruudukkoa pelattiin 14 kertaa.
Tuloksia voi tutkia pelikohtaisesti seuraavilla sivuilla:
Muita tapoja tekoälyihin perehtymiseen:
Yksinpeli osoittautui pelityypeistä kiinnostavammaksi. Monen tekoäly olikin suunniteltu varta vasten yksinpeliä varten, ja moninpelin toteutus oli ajanpuutteen tai muun syyn takia vaatimattomampi. Yksinpeleissä tekoälyjen taidot tulevat myös paremmin esille. Täysin totuudenmukainen kuva moninpeleistä edellyttäisi sitä, että kaikki tekoälyt pelaisivat paitsi jokaista väriä myös kaikilla vastustajayhdistelmillä. Tässä kilpailussa esimerkiksi kuusiväristä ruudukkoa olisi siis pitänyt pelata kaikkiaan 2162160 kertaa, mikä ei kuitenkaan ollut mahdollista rajallisen ajan vuoksi.
Väripelin luonteeseen kuuluu, että sieltä täältä ryhmiä poisteleva yksinkertainen tekoäly voi saada ruudukon lähes tyhjäksi. Kilpailun voittoon asti tällä menetelmällä ei kuitenkaan yltänyt. Heti ensimmäisten testiajojen jälkeen erottui neljän tekoälyn ryhmä – python, pupilli, ogre ja illi –, jotka olivat selvästi edellä muita. Nämä tekoälyt tuntuivat laskevan pelin kulkua varsin pitkälle ja tyhjensivät usein ruudukon viimeistä neliötä myöten. Muut tekoälyt, jotka poistivat ryhmiä vain erilaisten oletusten ja peukalosääntöjen perusteella, eivät menestyneet yhtä hyvin.
Kilpailun tulosten perusteella voidaan todeta, että ruudukon koon kasvattaminen ei aiheuta kovin suuria vaikeuksia tekoälyille. Sitä vastoin värien määrän lisääminen tekee oikean poistojärjestyksen valitsemisesta huomattavasti hankalamman tehtävän. Jos taitavan tekoälyn käytössä olisi ollut enemmän aikaa kuin tässä kilpailussa rajana ollut kaksi sekuntia, tulokset olisivat epäilemättä jonkin verran parantuneet. Mutta etenkin niissä ruudukoissa, joissa värien määrä oli suuri ja neliöiden määrä pieni, paras mahdollinen ratkaisukin jättää usein paljon neliöitä poistamatta.
Lisäväriä kilpailuun toivat kilpailijoiden omat aloitustilanteet, joita laatiessa saattoi myös juonitella oman tekoälyn hyväksi. Yksinpelin voittaja ratkesi juuri tällaisen kamppailun seurauksena. Henrik Huttusen aloitustilanne oli kova pala parhaimmillekin tekoälyille – paitsi pythonille, joka näin sai kymmenien pisteiden etumatkan vastustajiin. Ville Pettersson taas viritti varomattomille tekoälyille kavalan ansan, johon moni kilpailija myös lankesi. Otto Seiskari vuorostaan osoitti, että väripeliruudukon sommitteleminen voi olla myös taidetta. Musta ja valkoinen sekä värikäs tausta loivat sävykkyyttä teokseen.
Ohjelmointiputkan kesäinen algoritmikilpailu alkaa olla jo perinne. Vastaavia kilpailuja järjestetään myös tulevaisuudessa, koska ne selvästi kiinnostavat monia ohjelmoijia. Jos sinulla on tuleviin kilpailuihin liittyviä ehdotuksia, voit lähettää niitä kilpailukeskusteluun tai sähköpostilla. Jos tämän kilpailun järjestelyissä oli puutteita, mainitse myös niistä.
Kiitokset kilpailun osallistujille ja mukavaa loppukesää!
Antti Laaksonen, 10.7.2005