Kirjautuminen

Haku

Tehtävät

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.

sijatekoälytekijäpisteetvoitottasathäviötajany.virheetkieli
1.VilleVille Pettersson124620201C / C++
2.fläbäHannu Trey116580600C / C++
3.vekkuliVille Mäkynen114570713C / C++
4.wzh2Matti Lehtinen1005001430C / C++
5.chimanChiman984901510Python
6.viljoTeppo Niinimäki964801601C / C++
7.MirandaMarja Hassinen944701780Java
Konna14Ilkka Seppälä944701700C / C++
9.DelphiXOTeemu Valo904501900Pascal
10.RistialyMeitzi884402000Basic
11.airnSami Kortelainen824102300C / C++
12.SuperXSamuli Ristaniemi783902500Basic
13.tapotTuomas Vanhala763802600C / C++
14.sekopaaJari-Pekka Ryynänen723602800C / C++
15.kahjoTomi Peltola693412900Python
16.viritysOtto Seiskari6633031317C / C++
17.PascAivoLauri Kenttä603003400Pascal
18.taysnullHenrik Erkkilä ja Pauli Rikula582903500C / C++
solverMika Urtela582903500C / C++
bakaXOKarri Kahelin582823400Basic
21.D_AhmaEki Lehtimäki562803600Pascal
22.ariluAri Luoma522603800Basic
23.HabitSami Luostarinen502503900C / C++
24.IQ200Heikki Lehtosalo492413900C / C++
25.LurpakKustaa Kangas4824040160Basic
26.pepeAntti Laaksonen442204200Python
27.pottisJouko Joensuu321604800C / C++
28.TikruMarko Turklin261305100C / C++
29.MagnePetri Niemelä241205200Basic
plyyrNiko Nyrhilä241205200Java
31.NeuromanToni Okuogume7316003C / C++
32.x0botTomi Kyöstilä6306117Python
33.MopoJarno Mäkipää3116200C / C++

Voit kopioida kaikki kilpailuun osallistuneet tekoälyt käännettyinä (1,5 Mt) sekä myös useimpien lähdekoodit (170 kt).

Kaikki pelit

Seuraavassa taulukossa on kaikki tekoälyjen pelaamat pelit, joiden yhteismäärä on 1056. Ensimmäisessä sarakkeessa lukee pelin aloittaja ja ylärivillä toinen pelaaja. V merkitsee voittoa, T tasapeliä ja H häviötä. Ruudun väri kertoo viimeisen peliruudukon koon: sininen on 10x10, violetti 15x15 ja keltainen 20x20. Kukin peli tulee näkyviin pelitulosta napsauttamalla.

ai ar ba ch D_ De fl Ha IQ ka Ko Lu Ma Mi Mo Ne Pa pe pl po Ri se so Su tap tay Ti ve vil ViL vir wz x0
airn - V V H H V H V V V H V V H V V V V V V V V V H V V V H V H H V V
arilu V - V H V H H V V H H H V H V V V V V V H H V H H V V H H H H H V
bakaXO H H - H V V H V V H H V V H V V V V V V H H V V V H V H H H V H V
chiman V V V - H H H V V V V V V V V V V V V V H V V V V V V H V H V V V
D_Ahma V H V H - H H V V H H H V H V V V V H V H H H H V V V H V H H H V
DelphiXO V H V V V - H V V V V H V H V V V V V V H V V V V V V V V H V V V
fläbä V V V V V V - V V V V V V V V V V V V H V V V V V V V V V H V V V
Habit H V V H V H H - V V V V H H V V H V V H V H H H H H V H H H H H V
IQ200 H V T H H H H V - H H V V H V V V V V V H H H H H H V H H H V H V
kahjo H V T H V H H H H - H V V H V V V V V V V H V H V H V H H H V H V
Konna14 H V V V V H H V V V - V V V V V V V V V V V V H V V V V H H V H V
Lurpak H V V H V H H V H H H - V H V V H V V V V H H V H H H H H H H H V
Magne H H H H H H H H H H H H - H V V H H H H H H H H H H V H H H H H V
Miranda H V V H V V H V V V V H V - V V V V V V H V V V V V V H H H V V V
Mopo H H H H H H H H H H H H H H - H H H H H H H H H H H H H H H H H V
Neuroman H H H H H H H V H H H H H H T - H H H H H H H H H H H H H H V H H
PascAivo V V V H V H H H V V H V H H V V - H V V H V V V V H V H H H V H V
pepe H V H H V H H H V H H H H H V V V - V V H V V H V H V H V H H H V
plyyr V H H H H H H H H H H H V H V V V H - H H H H H H H V H H H H H V
pottis H H V H H H H H H H H H V H V V H H V - H H H H H H V H H H H H V
Ristialy V V V V V V H H H H V V V H V V V V V V - V V H V V V H V H V V V
sekopaa V V V V H V H V H V H V H H V V H V V V V - V H V H V H H H V H V
solver H V V H H H H V V H H V V H V V V V V V H H - H H V V H V H V H V
SuperX H V H V V V H H V H H V V V V V H V V H V V V - V V V H H H V H V
tapot V V V H V H H V V H V V V V V V V V V V H V V V - V V H V H V H V
taysnull H V V H H V H V V H H V V H V V V H V H H H H V H - V H H H H H V
Tikru H H H H H H H V H H H V H H V V H V V V H H H H H H - H H H V H V
vekkuli V V V H V V V V V V V V V V V V V V V V V V V V V V V - V V V V V
viljo H V V V V V V H V V V V V V V V H V V V V V V V V V V H - H V V V
Ville V V V V V V V V V V H V V V V V V V V V V V V V V V V V V - V V V
viritys V V H H V V H V V V V V V H V V H V V V H H V H H V V V H H - V V
wzh2 V V H V V V V V V V H V V V V V V V V V V V V V V V V V H H V - V
x0bot H H H H H H H H H H H H H H V V H H H H H H H H H H H H H H H H -

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.

nimitekijäkuvaus
VilleVille Pettersson (VilleP)
fläbäHannu Trey (devili)
vekkuliVille Mäkynen (ville_m)
wzh2Matti Lehtinen (Wazah)MinMax algoritmi + pattern detection pelitilanteen arvioimiseen.
chimanChiman

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ä.

viljoTeppo 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.
MirandaMarja 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.
Konna14Ilkka Seppänen (iluwatar)Pisteyttää jokaisen tyhjän paikan pelilaudalla laskemalla sille hyökkäys- ja puolustuspisteet.
DelphiXOTeemu 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. :)
RistialyMeitzi

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.

airnSami 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).
SuperXSamuli Ristaniemi (Professori)
tapotTuomas 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!
kahjoTomi 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.
viritysOtto 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.
PascAivoLauri Kenttä (Metabolix)Hyvin toimii! PascAivo laskee joka ruudulle pistearvon sen perusteella, mitä seuraavissa neljässä ruudussa joka suuntaan on.
taysnullHenrik Erkkilä (Spirits) ja Pauli RikulaTekoä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.
solverMika 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.
bakaXOKarri Kahelin (Blaze)(readme.txt)
D_AhmaEki Lehtimäki
ariluAri Luoma (arttut02)
HabitSami 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

IQ200Heikki Lehtosalo (nakkikorva)
LurpakKustaa 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.

pepeAntti 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.

pottisJouko Joensuu (Jogge)Pottis laskee jokaiselle ruudulle tärkeysarvon, joista suurimpaan se pistää ristinsä / nollansa.
TikruMarko Turklin (Marken)
MagnePetri 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.
plyyrNiko 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ä.
NeuromanToni 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.
x0botTomi 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.
MopoJarno 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!

Tietoa sivustosta