Kilpailut: Ristinollakilpailun tulokset
Järjestäjä: Antti Laaksonen
Ohjelmointiputkan kesäkuun 2004 kilpailun tehtävänä oli ohjelmoida ristinollaa pelaava tekoäly. Kaikkien kilpailuun osallistuvien tekoälyjen oli määrä lopuksi pelata toisiaan vastaan, jotta tekoälyjen keskinäinen paremmuusjärjestys selviäisi. Ennen kilpailun alkua moni pelkäsi, että tällaiseen kilpailuun ei ehkä tulisi kovin paljon osallistujia. Huoli oli kuitenkin aiheeton: peräti 33 tekoälyä otti osaa koetukseen. Testiajot kestivät tuntikausia, ja tulokset ovat tässä.
Kilpailutulokset
Kaikki tekoälyt pelasivat toisiaan vastaan kaksi kertaa, kummatkin saivat aloittaa kerran. Jokaisesta voitetusta pelistä tekoäly sai kaksi pistettä ja tasapelistä yhden pisteen. Näin suurin mahdollinen pistemäärä oli 128. Kilpailussa pelattiin kolme kierrosta ruudukoilla 10x10, 15x15 ja 20x20. Jos peli päättyi tasan, siirryttiin seuraavaan ruudukkoon. Loppujen lopuksi tasapelejä tuli vain muutama.
| sija | tekoäly | tekijä | pisteet | voitot | tasat | häviöt | ajany. | virheet | kieli |
|---|---|---|---|---|---|---|---|---|---|
| 1. | Ville | Ville Pettersson | 124 | 62 | 0 | 2 | 0 | 1 | C / C++ |
| 2. | fläbä | Hannu Trey | 116 | 58 | 0 | 6 | 0 | 0 | C / C++ |
| 3. | vekkuli | Ville Mäkynen | 114 | 57 | 0 | 7 | 1 | 3 | C / C++ |
| 4. | wzh2 | Matti Lehtinen | 100 | 50 | 0 | 14 | 3 | 0 | C / C++ |
| 5. | chiman | Chiman | 98 | 49 | 0 | 15 | 1 | 0 | Python |
| 6. | viljo | Teppo Niinimäki | 96 | 48 | 0 | 16 | 0 | 1 | C / C++ |
| 7. | Miranda | Marja Hassinen | 94 | 47 | 0 | 17 | 8 | 0 | Java |
| Konna14 | Ilkka Seppälä | 94 | 47 | 0 | 17 | 0 | 0 | C / C++ | |
| 9. | DelphiXO | Teemu Valo | 90 | 45 | 0 | 19 | 0 | 0 | Pascal |
| 10. | Ristialy | Meitzi | 88 | 44 | 0 | 20 | 0 | 0 | Basic |
| 11. | airn | Sami Kortelainen | 82 | 41 | 0 | 23 | 0 | 0 | C / C++ |
| 12. | SuperX | Samuli Ristaniemi | 78 | 39 | 0 | 25 | 0 | 0 | Basic |
| 13. | tapot | Tuomas Vanhala | 76 | 38 | 0 | 26 | 0 | 0 | C / C++ |
| 14. | sekopaa | Jari-Pekka Ryynänen | 72 | 36 | 0 | 28 | 0 | 0 | C / C++ |
| 15. | kahjo | Tomi Peltola | 69 | 34 | 1 | 29 | 0 | 0 | Python |
| 16. | viritys | Otto Seiskari | 66 | 33 | 0 | 31 | 3 | 17 | C / C++ |
| 17. | PascAivo | Lauri Kenttä | 60 | 30 | 0 | 34 | 0 | 0 | Pascal |
| 18. | taysnull | Henrik Erkkilä ja Pauli Rikula | 58 | 29 | 0 | 35 | 0 | 0 | C / C++ |
| solver | Mika Urtela | 58 | 29 | 0 | 35 | 0 | 0 | C / C++ | |
| bakaXO | Karri Kahelin | 58 | 28 | 2 | 34 | 0 | 0 | Basic | |
| 21. | D_Ahma | Eki Lehtimäki | 56 | 28 | 0 | 36 | 0 | 0 | Pascal |
| 22. | arilu | Ari Luoma | 52 | 26 | 0 | 38 | 0 | 0 | Basic |
| 23. | Habit | Sami Luostarinen | 50 | 25 | 0 | 39 | 0 | 0 | C / C++ |
| 24. | IQ200 | Heikki Lehtosalo | 49 | 24 | 1 | 39 | 0 | 0 | C / C++ |
| 25. | Lurpak | Kustaa Kangas | 48 | 24 | 0 | 40 | 16 | 0 | Basic |
| 26. | pepe | Antti Laaksonen | 44 | 22 | 0 | 42 | 0 | 0 | Python |
| 27. | pottis | Jouko Joensuu | 32 | 16 | 0 | 48 | 0 | 0 | C / C++ |
| 28. | Tikru | Marko Turklin | 26 | 13 | 0 | 51 | 0 | 0 | C / C++ |
| 29. | Magne | Petri Niemelä | 24 | 12 | 0 | 52 | 0 | 0 | Basic |
| plyyr | Niko Nyrhilä | 24 | 12 | 0 | 52 | 0 | 0 | Java | |
| 31. | Neuroman | Toni Okuogume | 7 | 3 | 1 | 60 | 0 | 3 | C / C++ |
| 32. | x0bot | Tomi Kyöstilä | 6 | 3 | 0 | 61 | 1 | 7 | Python |
| 33. | Mopo | Jarno Mäkipää | 3 | 1 | 1 | 62 | 0 | 0 | C / C++ |
Voit kopioida kaikki kilpailuun osallistuneet tekoälyt käännettyinä (1,5 Mt) sekä myös useimpien lähdekoodit (170 kt).
Kaikki pelit
Kaikki 1056 peliä on koottu taulukoksi erilliselle sivulle, jolla voi myös katsella pelien kulkua.
Voit myös kopioida kaikki ottelut (220 kt) tekstimuodossa.
Lisää tekoälyistä
Monet osallistujat liittivät mukaan tarkemman kuvauksen tekoälyn toiminnassa. Seuraavassa ovat nämä kuvaukset.
| nimi | tekijä | kuvaus |
|---|---|---|
| Ville | Ville Pettersson (VilleP) | |
| fläbä | Hannu Trey (devili) | |
| vekkuli | Ville Mäkynen (ville_m) | |
| wzh2 | Matti Lehtinen (Wazah) | MinMax algoritmi + pattern detection pelitilanteen arvioimiseen. |
| chiman | Chiman | Tekoälyn toiminta perustuu kahteen eri menetelmään. Varsinkin pelin alussa käytetään heuristiikkaa, joka yrittää sovittaa valmiita viiden suoria jokaiseen mahdolliseen paikkaan laudalla pisteyttäen tyhjät ruudut. Näitä pistearvoja käytetään, jos toinen menetelmä ei löydä sopivaa siirtoa. Toinen menetelmä etsii laudalta tyhjät ruudut, joihin pelaamalla pakotetaan vastustaja torjumaan seuraavalla siirrolla. Samanlaiset ruudut etsitään myös vastustajalta. Tämän menetelmän täyttä kapasiteettia ei käytetä, sillä en ehtinyt koodata siirtojen laskemista eteenpäin. Tekoäly kuitenkin löytää tyhjät ruudut, jotka aiheuttavat uhan useampaan suuntaan, joten tekoälyn taso on siedettävä, eikä se tee yhtään alkeellista virhettä. |
| viljo | Teppo Niinimäki (tn) | Tekoäly pisteyttää ruutuja viereisten ruutujen mukaisesti, laskee siirtoja eteenpäin kahdesta parhaat pisteet saaneesta ruudusta ja valitsee lopulta mielestään paremman. |
| Miranda | Marja Hassinen (Marja) | Tekoäly käyttää Minmax-algoritmin alfa-beeta-versiota. Kulloisestakin pelitilanteesta lähtien generoidaan pelipuuta, eli lasketaan mahdollisia (omia ja vastustajan) siirtoja eteenpäin. Pelipuun syvyys on ennalta määrätty (aluksi ohjelma muodostaa tyhjien ruutujen määrän perusteella arvion siitä, kuinka syvälle kannattaa laskea). Lehtisolmuille lasketaan hyvyysarvio staattisen evaluointifunktion avulla etsimällä lehtisolmun kuvaamasta tilanteesta omia ja vastustajan suorien osia (antaen enemmän arvoa sellaisille, joilla on jo eniten pelimerkkejä), jolloin omat suorat lisäävät ja vastustajan suorat vähentävät tilan hyvyysarviota. |
| Konna14 | Ilkka Seppänen (iluwatar) | Pisteyttää jokaisen tyhjän paikan pelilaudalla laskemalla sille hyökkäys- ja puolustuspisteet. |
| DelphiXO | Teemu Valo (User137) | Ensimmäiset 2 siirtoa lähtee ruudukon keskustan tienoilta, tai toisen laittaman raksin viereen. Satunnaisuutta on käytössä monessa asiassa. Tästä eteenpäin funktiot lukevat koon puolesta optimoidulle ruudukolle arvokartan, joka kertoo kuinka hyvä tiettyyn ruutuun on raksia/ympyrää laittaa. Parhaista vaihtoehdoista arvotaan valinta. Tekoäly voi toisinaan tuntua melko puolustavalta, mutta voittaa tätä ei voi kuin kuvioimalla. :) |
| Ristialy | Meitzi | Aluksi Ristialy käy kaikki peliauleella olevat merkit läpi ja merkkaa pelattaviksi ruuduiksi kaikki olemassa olevien merkkien viereiset ruudut. (Jossain tilanteessa olisi parempi siirtää 2 ruudun päähän mutta se on tällä tavalla liian hidasta.) Tämän jälkeen Ristialy käy kaikki nämä merkatut ruudut läpi ja testaa, että jos se tekee siirron kyseiseen ruutuun niin minkä mittaisia suoria se saa. Näille kaikille suorille lasketaan pisteet yksinkertaisesti pituuden mukaan. Kun ohjelma on tehnyt tämä ensimmäisen ruudun kuvitellun siirron se merkkaa sen virtuaalilaudalle ja antaa viholliselle vuoron. Vihollisen siirto testataan samalla tavalla kaikki ruudut läpi ja lopuksi vähennetään vihollisen parhaat pisteet oman siiron pisteitä. Ohjelma testaa näin peliä 4 siirron päähän, joka voi tarkoittaa lähes 10 miljoonan siirron testaamista. (Juurikaan enempää ei 10 sekunissa kerkeä.) Ristialy sisältää monia heikkouksia, se antaa mm. 3 merkin mittaisella suoralle samat pisteet oli se sitten estetty tai avoin. Ja aikarajan takia siirrot alkavat olla riittävän isolla pelialueella (paljon merkkejä) epävarmoja. Ristiäly sisältää myös täysin toimivan graafisen ympäristön joka käynnistyy jos ristialy.luk tiedostoa ei löydy. Siellä näkyy mm. tekoälyn antamat pisteet ruuduille pelitilanteessa. |
| airn | Sami Kortelainen (Sami82) | Ohjelma laskee kaikki suorat jokaisesta paikasta ja pisteyttää ne suoran pituuden ja lukumäärän mukaan. Sama homma toistetaan käyttäen vastustajan merkkiä. Löydetyt suorat pisteytetään ja verrataan toisiin suoriin. Eniten pisteitä saanut paikka valitaan ja siihen tökätään oma merkki. Ohjelma ei käytä rekursiivista tarkistusta (vielä ainakaan). |
| SuperX | Samuli Ristaniemi (Professori) | |
| tapot | Tuomas Vanhala (tuoppi) | Koodi perustuu min-max -algoritmiin, jota avustaa staattinen siirtojen arvioija. Jokaisen siirron kohdalla arvioija valitsee MAX_LASKETTAVIEN_MAARA siirtoa, joita se laskee eteenpäin. Jos jostakin kohtaa puuta löytyy siirto, joka johtaa viiden riviin, palautetaan joko INT_MIN (häviö) tai INT_MAX (voitto). Jos saavutetaan maksimilaskentasyvyys eikä voittoa tai häviötä löytynyt, palautetaan siirtojen arvioijan arvio alimman siirron hyvyydestä. |
| sekopää | Jari-Pekka Ryynänen (Dual) | Pelaa muistissaan 4 siirtoa eteenpäin, katsoo tuleeko voittosuoria, jos ei niin otetaan käyttöön alkuperäisestä tilanteesta katsottuna paras siirto. Jos voittosuora löytyy otetaan käyttöön sitä aikaisempi siirto (paitsi jos voittosuora löytyy heti, jolloin otetaan ko. siirto). Jos pelikentälle ei ole muodostunut suoria (2-4 pituisia), arvotaan jonkun oman vierestä paikka (jos ei saada sopivaa ruutua tarpeeksi nopeasti, aletaan käyttää mahdollisina naapurikavereina kaikkia pelattuja ruutuja). Jos eka oma, paikka arvotaan vastustajan aloitusruudun vierestä. Jos pelikenttä tyhjä, ruksataan keskimmäinen ruutu. Sekopaan saa helposti tietynlaisiin ansoihin. Lopuksi haluaisin vielä sanoa: Kreegah bundolo! |
| kahjo | Tomi Peltola (Crimit) | Tekoäly pohjautuu yksinkertaiseen ruutujen pisteytykseen. Esimerkiksi merkkiketjujen päässä olevat tyhjät ruudut saavat lisäpisteitä. Suurimman pistemäärän omaavaan ruutuun laitetaan oma merkki. |
| viritys | Otto Seiskari (otto) | Lopullinen koodi on parsittu kasaan karmealla kiireellä, ja lopputulos on sen näköinen. Tekoäly toimii sekavasti eri tavoin. Pohjana on funktio, joka etsii kaikki jonkin ruudun kautta kulkevat potentiaaliset suorat, ja antaa ruudulle pisteitä sen mukaan, kuinka paljon näitä on ja kuinka valmiita suorat ovat. Tekoälyyn on myöhemmin lisätty rekursiivinen funktio, joka etsii mahdollisia voittostrategioita. |
| PascAivo | Lauri Kenttä (Metabolix) | Hyvin toimii! PascAivo laskee joka ruudulle pistearvon sen perusteella, mitä seuraavissa neljässä ruudussa joka suuntaan on. |
| taysnull | Henrik Erkkilä (Spirits) ja Pauli Rikula | Tekoäly on väsätty lyhyessä ajassa ilman sen kummempaa yritystä ja keskittymistä. Koodi on tästä johtuen epäselvää ja kommentoimatonta. Toiminta perustuu yksinkertaisesti siihen että lasketaan omia ja vastustajan erilaisia suoria eripuolilta ruutua ja tehdään suorakasaumien perusteella siirto. Tekoälyssä on paljon kehiteltävää jos siitä halutaan saada todella haastava. |
| solver | Mika Urtela (Apodus) | Katso lähdekoodi. ^^; Ohjelma on kirjoitettu 23h huomautuksella, ja jälki on sen mukaista. sisältää useita funktioita jotka eivät toimi tai ovat liian hitaita käytettäväksi. Kommentointia on turha odottaa. |
| bakaXO | Karri Kahelin (Blaze) | (readme.txt) |
| D_Ahma | Eki Lehtimäki | |
| arilu | Ari Luoma (arttut02) | |
| Habit | Sami Luostarinen (BadHabit) | Parisen vuotta sitten tein koulun C-ohjelmointikurssilla jätkänshakkipelin, jossa pystyi pelaamaan tietokonetta vastaan. Tämä AI on karsittu versio siitä (GUI siis pois). Toki luku- ja kirjoitusfunktiot täytyi lisätä. Olen hieman yrittänyt optimoida / parannella tekoälyä, mutta vertailukohdan puuttuessa en tiedä onko menty parempaan vai huonompaan suuntaan ;) Koodi on huonosti/surkeasti kommentoitua -- tiedän. Ohjelmointiin on kulunut aikaa n. 1½h (ei siis kirjoitettu tyhjästä) ja optimointiin n. 2h. AI laskee yksinkertaisella kaavalla jokaiselle tyhjälle ruudukolle pistearvon sen mukaan miten sen suhteen on sijoitettu pelimerkkejä. Pelimerkki sijoitetaan parhaan pistemäärän saaneeseen ruutuun. AI ei laske tilannetta yhtään eteenpäin vaan analysoi ainoastaan sen hetkisen tilanteen ja päättää pelimerkin sijoituksen sen mukaan. AI ei siis osaa tehdä ansoja vastustajalle vaan pelailee aika lonkalta :) En odota AI:lta kovin hyvää menestystä, mutta olihan se pakko laittaa kisaan mukaan :P |
| IQ200 | Heikki Lehtosalo (nakkikorva) | |
| Lurpak | Kustaa Kangas (hunajavohveli) | Tekoäly käy silmukalla läpi ruudukon. Jokaisen ruudun kohdalla ajetaan algoritmi, joka tarkistaa millaiset suorat päättyvät tarkistettavaan ruutuun. Ruudun valinta perustuu eräänlaiseen pisteytysmenetelmään. Jos vaikka tarkistettavaan ruutuun päättyy suora, jossa on neljä omaa merkkiä peräkkäin, annetaan sille ruudulle maksimipisteet. Toiseksi eniten pisteitä saa vastustajan neljän suora, kolmanneksi eniten oma kolmen suora jne. Eniten pisteitä saanut ruutu valitaan, ja siihen tekoäly laittaa merkkinsä. Tämä on tekoälyni perusperiaate. |
| pepe | Antti Laaksonen | Ohjelma tutkii kaikkien merkittyjen ruutujen vieressä olevat ruudut, ja pisteyttää ruudut muodostettujen omien rivinalkujen ja estettyjen vastustajan rivien mukaan. Pärjää ihan hyvin ihmiselle, mutta kun hyvä tietokonetekoäly tulee vastaan, pepeä viedään. Lopuksi salaviesti: Allo kudu ural lamm iruu säep epat haka attu ulep eli ekok. |
| pottis | Jouko Joensuu (Jogge) | Pottis laskee jokaiselle ruudulle tärkeysarvon, joista suurimpaan se pistää ristinsä / nollansa. |
| Tikru | Marko Turklin (Marken) | |
| Magne | Petri Niemelä (petrinm) | Tekoäly luo taulukon, johon se asettaa vuoron riippuen onko tiedostosta haetun paikan järjestykseltään parillinen vai ei. Sen jälkeen taulukkoa aletaan käydä ruutu kerrallaan läpi. Löytäessään pienen taikka suuren suoran tekoäly laittaa sen muistiinsa järkevyysnumeron kanssa, joka määräytyy suoran pituudesta. Ruudukon läpi käytyään tekoäly selaa kaikki muistissa olevat järkevyysnumerot ja valitsee järkevimpien seasta tulevan siirron. Mikäli muistissa ei ole yhtään paikkaa, mikä voisi olla edes vähän järkevä, on paikan arpominen parhainta. |
| plyyr | Niko Nyrhilä (msdos464) | Tekoäly etsii, onko peräkkäin jotain ja että saako kerralla useampia esim. neljän suoria. Ei mikään kovin hyvä, kun olin viikon Kreikassa yms. niin ei paljoa aikaa tullut käytettyä. |
| Neuroman | Toni Okuogume (terex) | Tämän tekoälyn motto on "Puolustus on paras hyökkäys" eli sillä ei ole kakea kummempi hyökkäys, mutta se osaa puolustaa. |
| x0bot | Tomi Kyöstilä (dOb) | Tekoäly katsoo, onko toisella pelaajalla vähintään 2 merkkiä pitkä merkkijono. Jos on, tekoäly yrittää estää jonon jatkamisen laittamalla merkin jompaankumpaan jonon päätyyn. Jos ei, tekoäly laittaa merkin jompaankumpaan omaa pisimmän jonon päätyyn. |
| Mopo | Jarno Mäkipää (Isäntä) | Parin tunnin yritelmä, ei mikään vaikea vastus.. no ehkä sokealle =) |
Tilastoja
Keskimääräinen pelin pituus oli 38,6 merkintää.
Kaikki merkinnät ja aloitusmerkinnät. Näissä kuvissa tummin kohta tarkoittaa suurinta merkintöjen määrää.
Lopuksi
Ristinollakilpailun suuri osallistujamäärä viestii siitä, että tämänkaltaiset kilpailut kiinnostavat monia ohjelmoijia. Siksi algoritmeihin ja tekoälyihin liittyviä kilpailuja järjestetään Ohjelmointiputkassa vastaisuudessakin. Jos sinulla on tuleviin kilpailuihin liittyviä ehdotuksia, lähetä ne osoitteeseen kilpailu@ohjelmointiputka.net. Samaan osoitteeseen voit myös lähettää palautetta tämän kilpailun toteutuksesta.
Kiitokset kaikille kilpailuun osallistuneille!