Kilpailut: Viivapeli: tulokset

Osallistujat ja tulokset
Ottelut ja tilastot
Tekoälyt

Järjestäjä: Metabolix

Vuoden 2010 alkupuolella Ohjelmointiputkassa pidettiin tekoälykilpailu, jossa ohjelmat piirsivät ruudukkoon viivojaan ja yrittivät ajaa vastustajansa umpikujaan.

Kilpailuun osallistui kaikkiaan kahdeksan tekoälyä, jotka asettuivat tuloksissa varsin selvästi kolmeen ryhmään: kärkikaksikko oli omaa luokkaansa, neljä seuraavaa asettuivat väljästi jonkin verran näistä erilleen, ja perää jäivät pitämään kaksi yksinkertaisinta ohjelmaa, joiden tavoitteena ei itse asiassa ollutkaan menestyä kilpailussa.

Tekoälyt pelasivat seitsemästä eri alkutilanteesta: 8×8, 300 ms; 20×20, 200 ms; 60×10, 100 ms; 40×40, 150 ms; 80×24, 75 ms; 100×80, 150 ms; ja 160×120, 75 ms. Jokainen pari pelasi kunkin tilanteen kahteen kertaan, jotta kumpikin sai olla vuorollaan ykköspelaaja. Tekoälyjen oikeasta järjestyksestä ei jäänyt testien perusteella epäselvyyttä.

Osallistujat ja tulokset

Seuraavassa taulukossa ovat kaikki kilpailun osallistujat järjestyksessä menestyksensä mukaan. Otteluihin ei ole laskettu mukaan tekoälyjen pelejä itseään vastaan. Varsinaisten kilpailijoiden lisäksi kilpailussa oli mukana esimerkkiäly esim.

sija	tekoäly	kieli	koodirivejä	tekijä	nimimerkki	voitot	tasapelit	tappiot	kaatumiset
1.	___	C++	360	Mikko Sysikaski	Sisuaski	94	1	3
2.	Protractor	C++	1550	Niko Nyrhilä	msdos464	86	1	11	(1)
3.	Kvasaari	C++	860	Antti Vainio	Anaatti	59	0	39
4.	Torppo	Haskell	120	Lauri Kenttä	Metabolix	53	3	42
5.	pallo	C	100	Antti Laaksonen	Antti Laaksonen	43	0	55
6.	Tonttu	C++	150	Juho Pinola	JP_94	36	3	59	(6)
7.	BFmato	Brainfuck	210	Eki Lehtimäki	Eki Lehtimäki	15	3	80
8.	esim	(useita)	14×80			0	1	97

Onnea voittajalle!

Ottelut ja tilastot

Seuraavissa taulukoissa ovat otteluiden tulokset. Ensimmäisessä sarakkeessa lukee aina ykköspelaaja ja ylärivillä kakkospelaaja. V merkitsee ykköspelaajan voittoa ja H tämän häviötä, ja viivalla on merkitty tasapelit. Tulos on linkki sivulle, jolla voi katsella koko pelin.

Kuvissa näkyy, millä alueilla tekoälyt ovat parhaiten viihtyneet. Mitä kirkkaampi ruutu on, sitä useampi tekoäly on käynyt juuri siinä. Ykköspelaaja on merkitty punaisella ja kakkospelaaja sinisellä, ja pelin alkupiste on asetettu kuvan keskelle.

— 8×8, 300 ms

	___	Pro	Kva	Tor	pal	Ton	BF	esim
___	–	–	V	V	V	V	V	V
Protractor	V	V	V	V	V	V	V	V
Kvasaari	H	H	–	V	V	V	V	V
Torppo	H	H	H	–	V	V	H	V
pallo	H	H	H	V	–	H	V	V
Tonttu	H	H	H	H	V	–	V	V
BFmato	H	H	H	–	H	H	–	–
esim	H	H	H	H	H	H	H	–

— 20×20, 200 ms

	___	Pro	Kva	Tor	pal	Ton	BF	esim
___	V	H	V	V	V	V	V	V
Protractor	H	H	V	V	V	V	V	V
Kvasaari	H	H	–	H	V	V	V	V
Torppo	H	H	H	H	V	–	V	V
pallo	H	H	H	V	–	H	V	V
Tonttu	H	H	H	H	V	–	H	V
BFmato	H	H	H	H	H	H	–	V
esim	H	H	H	H	H	H	H	–

— 60×10, 100 ms

	___	Pro	Kva	Tor	pal	Ton	BF	esim
___	H	V	V	V	V	V	V	V
Protractor	V	V	V	V	V	V	V	V
Kvasaari	H	V	V	H	H	V	V	V
Torppo	H	H	V	H	V	V	V	V
pallo	H	H	V	H	–	H	V	V
Tonttu	H	H	H	H	V	–	V	V
BFmato	H	H	H	H	H	H	–	V
esim	H	H	H	H	H	H	H	–

— 40×40, 150 ms

	___	Pro	Kva	Tor	pal	Ton	BF	esim
___	H	V	V	V	V	V	V	V
Protractor	H	H	V	V	V	V	V	V
Kvasaari	H	H	–	V	V	H	V	V
Torppo	H	H	V	–	V	V	V	V
pallo	H	H	H	V	–	H	V	V
Tonttu	H	H	V	–	V	–	V	V
BFmato	H	H	H	H	H	H	–	V
esim	H	H	H	H	H	H	H	–

— 80×24, 75 ms

	___	Pro	Kva	Tor	pal	Ton	BF	esim
___	H	V	V	V	V	V	V	V
Protractor	H	V	V	V	V	V	V	V
Kvasaari	H	H	–	V	V	V	V	V
Torppo	H	H	H	–	H	V	V	V
pallo	H	H	H	V	–	V	V	V
Tonttu	H	H	H	H	H	H	V	V
BFmato	H	H	H	H	H	H	–	V
esim	H	H	H	H	H	H	H	–

— 100×80, 150 ms

	___	Pro	Kva	Tor	pal	Ton	BF	esim
___	–	V	V	V	V	V	V	V
Protractor	H	H	V	V	V	V	V	V
Kvasaari	H	H	H	H	V	V	V	V
Torppo	H	H	H	–	V	V	V	V
pallo	H	H	H	H	–	V	V	V
Tonttu	H	H	H	H	H	–	V	V
BFmato	H	H	H	H	H	H	–	V
esim	H	H	H	H	H	H	H	–

— 160×120, 75 ms

	___	Pro	Kva	Tor	pal	Ton	BF	esim
___	–	V	V	V	V	V	V	V
Protractor	H	H	V	V	V	V	V	V
Kvasaari	H	H	–	H	H	V	V	V
Torppo	H	H	H	–	V	V	V	V
pallo	H	H	V	H	–	V	V	V
Tonttu	H	H	H	H	H	V	–	V
BFmato	H	H	H	H	H	H	–	V
esim	H	H	H	H	H	H	H	–

Tekoälyt

Tekoälyjen lähdekoodit voi ladata yhtenä pakettina. Osallistujilta pyydettiin tekoälyn saatteeksi myös pientä selostusta sen toimintaperiaatteesta. Näin he kertovat ratkaisuistaan:

___ Mikko Sysikaski "Sisuaski"	Tavallinen minmax ilman suurempia kikkoja. Hyvyysfunktio laskee, moneenko ruutuun itsellä on lyhyempi matka kuin vastustajalla.
Protractor Niko Nyrhilä "msdos464"	Ohjelmassa hyödynnetään menetelmiä iterative deepening, move ordering ja alpha-beta pruning. Se käyttää pthreads- ja SDL-kirjastoja.
Kvasaari Antti Vainio "Anaatti"	Tekoäly kulkee pääasiassa suoraan ja kääntyy silloin, kun on tarpeen. Se pyrkii välttämään pieniä sumppuja ja umpikujia ja muutenkin valitsee aina pinta-alaltaan suuremman alueen, jos on pakko valita. Tämän lisäksi se yrittää myös aina kääntyä kauemmaksi vastustajan päästä ja välttelemään sitä, jos tämä joutuu liian lähelle vastustajaa. Kun tekoäly joutuu eristetylle alueelle, jolla ei ole vastustajan päätä, se yrittää täyttää jäljellä olevan alueen mahdollisimman tarkasti, pääasiassa tehden spiraalia tai siksakkia. Tällöinkään tekoäly ei mene pieniin sumppuihin tai umpikujiin vaan valitsee aina suuremman alueen. Lisäksi tekoäly yrittää välttää jakamasta jäljellä olevaa aluetta niin, että sieltä jäisi liian suuria alueita täyttämättä. Tekoäly tarkistaa myös pariin kertaan siirron laskemisen aikana, onko jo tapahtunut uusia siirtoja, minkä takia se toimii kohtalaisesti myös erittäin nopeassa pelissä.
Torppo Lauri Kenttä "Metabolix"	Torppo valitsee suunnan, jossa on eniten sellaisia ruutuja, joihin pääsee kääntymällä vain kerran. Ohjelma pärjää hyvin ihmiselle ainakin nopeissa peleissä, mutta tuskinpa siitä on vastukseksi tarkempaa hakua soveltaville tekoälyille.
pallo Antti Laaksonen	Tekoäly matkii pallon pomppimista: viiva liikkuu pelialueella viistosuunnassa, ja jos vastaan tulee este, viiva kimpoaa siitä.
Tonttu Juho Pinola "JP_94"	Tekoäly laskee ennen jokaista siirtoa, missä suunnassa on eniten vapaata tilaa, ja pyrkii kääntymään kannattavimpaan suuntaan.
BFmato Eki Lehtimäki	BFmato on brainfuck-kielellä kirjoitettu erittäin yksinkertainen tekoäly, joka ei paljon vastustajan liikkeistä välitä. BFmato lähtee liikkeelle oletussuunnasta katsoen vasemmalle, etenee pelilaudan korkeuden verran, siirtyy sitten yhden ruudun kulkusuunnassaan katsoen oikealle ja jatkaa alkuperäiseen suuntaan taas pelilaudan korkeuden verran. Hirveää älykkyyttä ei siis ole luvassa. Tavoitteena oli enemmän tutustua mielenkiintoiseen brainfuckiin kuin menestyä kisassa. Vaikka brainfuckilla koodatessa onkin hauskaa kuin anopin hautajaisissa, en aivan jaksanut minmaxia sillä vääntää.
esim	Esimerkkiohjelma valitsee vuorotellen suunnan +Y ja numerostaan riippuen +X tai -X. Ohjelma ei tarkista lainkaan tilannetta pelilaudalta, joten voitosta lienee turha haaveilla.

Onnea voittajalle ja kiitos kaikille kilpailussa tai järjestämisessä osallisina olleille!

Kirjautuminen

Haku

Tehtävät

Kilpailut: Viivapeli: tulokset

Osallistujat ja tulokset

Ottelut ja tilastot

Tekoälyt