Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Tulokset on julkaistu.
Onnea voittajalle!

Kilpailut: Viivapeli: tulokset

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.

sijatekoälykielikoodirivejätekijänimimerkkivoitottasapelittappiotkaatumiset
1.___C++360Mikko SysikaskiSisuaski9413
2.ProtractorC++1550Niko Nyrhilämsdos46486111(1)
3.KvasaariC++860Antti VainioAnaatti59039
4.TorppoHaskell120Lauri KenttäMetabolix53342
5.palloC100Antti LaaksonenAntti Laaksonen43055
6.TonttuC++150Juho PinolaJP_9436359(6)
7.BFmatoBrainfuck210Eki LehtimäkiEki Lehtimäki15380
8.esim(useita)14×800197

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

___ProKvaTorpalTonBFesim
___VVVVVV
ProtractorVVVVVVVV
KvasaariHHVVVVV
TorppoHHHVVHV
palloHHHVHVV
TonttuHHHHVVV
BFmatoHHHHH
esimHHHHHHH

— 20×20, 200 ms

___ProKvaTorpalTonBFesim
___VHVVVVVV
ProtractorHHVVVVVV
KvasaariHHHVVVV
TorppoHHHHVVV
palloHHHVHVV
TonttuHHHHVHV
BFmatoHHHHHHV
esimHHHHHHH

— 60×10, 100 ms

___ProKvaTorpalTonBFesim
___HVVVVVVV
ProtractorVVVVVVVV
KvasaariHVVHHVVV
TorppoHHVHVVVV
palloHHVHHVV
TonttuHHHHVVV
BFmatoHHHHHHV
esimHHHHHHH

— 40×40, 150 ms

___ProKvaTorpalTonBFesim
___HVVVVVVV
ProtractorHHVVVVVV
KvasaariHHVVHVV
TorppoHHVVVVV
palloHHHVHVV
TonttuHHVVVV
BFmatoHHHHHHV
esimHHHHHHH

— 80×24, 75 ms

___ProKvaTorpalTonBFesim
___HVVVVVVV
ProtractorHVVVVVVV
KvasaariHHVVVVV
TorppoHHHHVVV
palloHHHVVVV
TonttuHHHHHHVV
BFmatoHHHHHHV
esimHHHHHHH

— 100×80, 150 ms

___ProKvaTorpalTonBFesim
___VVVVVVV
ProtractorHHVVVVVV
KvasaariHHHHVVVV
TorppoHHHVVVV
palloHHHHVVV
TonttuHHHHHVV
BFmatoHHHHHHV
esimHHHHHHH

— 160×120, 75 ms

___ProKvaTorpalTonBFesim
___VVVVVVV
ProtractorHHVVVVVV
KvasaariHHHHVVV
TorppoHHHVVVV
palloHHVHVVV
TonttuHHHHHVV
BFmatoHHHHHHV
esimHHHHHHH

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!

Tietoa sivustosta