Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Aikaa on 6.1. saakka.

Kilpailut: Pomppis: tulokset

Järjestäjä: Metabolix

Vuodenvaihteessa 2009–2010 Ohjelmointiputkassa pidettiin tekoälykilpailu. Aiheena oli kahden pelattava lautapeli, jossa nappulat pomppivat toistensa yli kohti laudan vastakkaista reunaa. Kaikki tekoälyt pelasivat vuorollaan toisiaan vastaan, ja jokaisesta voitetusta pelistä sai yhden pisteen.

Kilpailuun osallistui kaikkiaan 15 tekoälyä. Aihe oli selvästi hankala näin lyhyessä ajassa ratkaistavaksi: harva kilpailun tekoäly antaa kunnon vastuksen ihmiselle. Useimmat tekoälyt laskevat melko yksinkertaisesti, mikä siirto veisi lyhyellä tähtäimellä mahdollisimman pitkälle, mutta uskalsipa joku osallistua myös ohjelmalla, joka käyttää ensisijaisesti etukäteen kehitettyä taktiikkaa. Tällä kertaa ihmisen valmiiksi viilaama strategia jopa päihitti useimmat tekoälyt, mutta voiton veivät kuitenkin tyypilliset lautapelialgoritmit ja raaka laskenta.

Osallistujat ja tulokset

Seuraavassa taulukossa ovat kaikki kilpailun osallistujat järjestyksessä kokonaispistemäärän mukaan. Varsinaisten kilpailijoiden lisäksi kilpailussa oli mukana esimerkkiäly esim.

sijatekoälykielikoodirivejätekijänimimerkkivoitottappiot
1.KettuC++1090Aleksi Hartikainenahr280
2.pompomLua200Lauri KenttäMetabolix262
3.MijukuC++250Markku VelinenDzarg226
4.AntsPascal270Teemu ValoUser137208
5.KuoviC#660Eki LehtimäkiEki Lehtimäki1810
LiteYearC++360Antti VainioAnaatti1810
silta10C++340Toni HuttunenSeriffi1810
8.KabotC++210Sami KalliomäkiSami3451414
9.P3TOPython280Juho Peltonenaaämdee1216
10.PompperC++100Tomi Kokkonentkok1117
11.AwesomeC++380Michael BorderboroughBorderi919
12.HypsisJava420Tigon721
13.vahajarkiPython120Juho PinolaJP_94523
14.esim*11×80226
15.viikinkiC20Mikko SysikaskiSisuaski028

Onnea voittajalle!

Ottelut

Seuraavassa taulukossa ovat otteluiden tulokset. Ensimmäisessä sarakkeessa lukee pelin aloittaja ja ylärivillä toinen pelaaja. V merkitsee aloittajan voittoa ja H aloittajan häviötä, ja viivalla on merkitty tasapelit. Tulos on linkki sivulle, jolla voi katsella koko pelin. Älyn ottelua itseään vastaan ei laskettu yhteispisteisiin.

KepoMiAnKuLisiKaP3PoAwHyvaesvivoittoja
KettuHVVVVVVVVVVVVVV14
pompomHVVVVVVVVVVVVVV13
MijukuHHVHVVVVVVVVVVV11
AntsHHVHHVHVVVVVVVV10
KuoviHHHVVHVVVVVVVVV10
LiteYearHHHHVVHVVVVVVVV9
silta10HHHVVVVVVVHVVVV10
KabotHHHHHHHHVVVVVVV7
P3TOHHHHHHVHHHVVVVV6
PompperHHHHHHHHHHVVVVV5
AwesomeHHHHVHVHHHHVVV5
HypsisHHHHHHHHHHHHVVV3
vahajarkiHHHHHHHHHHVHVVV3
esimHHHHHHHHHHHHHVV1
viikinkiHHHHHHHHHHHHHH0
voittoja1413111089876644210

Tilastoja ja tarkastelua

Seuraavassa kuvassa tekoälyjen lähtöpaikka on yläreunassa ja maali alareunassa. Kilpailussa hyvin menestyneiden älyjen reitit on väritetty vihertävällä, keskitasoisten sinertävällä ja heikoimmille jääneiden reitit punertavalla. Mitä kirkkaampi alue on, sitä useampi nappula siitä on kulkenut. Laudan keskilinja on ollut hyvin suosittu, mutta osa parhaista älyistä onkin kiertänyt sivummalta.

(kuva)

Tarkastellaan vielä erikseen tuloslistan alku- ja loppuosia. Seuraavassa kuvassa ovat vain viimeiset neljä tekoälyä, ja poikkeamia kuvan reunoille ei juuri näy:

(kuva)

Parhaat neljä tekoälyä taas ovat hajaantuneet selvästi enemmän. Tästä voinee päätellä, että sivukautta on päässyt tehokkaasti huonompien tekoälyjen ohi.

(kuva)

Kuitenkin itse voittaja on pysytellyt erityisesti alkumatkasta lähellä keskilinjaa, eli suorin reitti sittenkin on ollut paras, kunhan on osannut ottaa hyödyn irti vastustajan nappuloista.

(kuva)

Viimeisestä kuvaajasta selviää, kuinka paljon älyt ovat edenneet y-suunnassa yhdellä siirrolla. Jokainen mahdollinen etenemä on kuvattu omalla värillään. Palkkien pituuksia on painotettu hyppyjen pituuksilla, jotta harvemmin sattuneet pitkät hypyt näkyisivät paremmin. Palkin koko kuvastaa siis likimain, kuinka suuren osuuden koko kilpailusta äly on edennyt kyseisellä hyppypituudella.

Kuvaajasta nähdään, että häntäpään älyt eivät ole paljon hyppineet. Toisaalta voittajakaan ei ole kaikkein innokkain hyppijä, eli tässä pelissä on kyse paljon muustakin kuin pitkistä hypyistä.

(kuva)

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:

Kettu
Aleksi Hartikainen
ahr

Ohjelma käyttää parhaan siirron etsimiseen minimax-hakua, jota on tehostettu muutamalla shakkitekoälyistä tutulla tekniikalla:

  • AlphaBeta pruning
  • Negascout
  • Transpositiotaulu (iso hajautustaulu, jossa ovat kaikki tutkitut tilanteet)
  • Historiaheuristiikka (aikaisemmin hyviksi osoittautuneita siirtoja kokeillaan ensin)
pompom
Lauri Kenttä
Metabolix

Taktiikka perustuu ilman vastustajaa tehokkaaksi todettuun menetelmään: Ensin rakennetaan hieman kulmittaista ketjua ja toiseksi suoraa ketjua laudan päähän asti. Sitten vain hypytetään nappuloita ketjua pitkin maaliin, ja lopuksi puretaan ketju alkupäästä lähtien. Muutama ensimmäinen siirto on valittu ennalta, loput lasketaan sen perusteella, kuinka lähellä suunniteltua ketjua tai maalia kohderuutu on.

Tekoäly ei ennakoi omia tai vastustajan siirtoja mitenkään; siirrot tehdään vain nykyisen tilanteen perusteella ja vain oman etenemisen näkökulmasta. Menestys riippuu täysin siitä, tukkiiko vastustaja tien ja osaako ehkä jopa hyödyntää valmiiksi tarjottua hyppyreittiä. Ihmispelaajalle tekoälystä ei ole juuri vastusta.

Mijuku
Markku Velinen
Dzarg

Tekoäly siirtää ensin neljä vakiosiirtoa ja sen jälkeen aloittaa siirtojen arvioinnin tutkimalla kaikki omat siirtomahdollisuudet, kaikki niiden jälkeiset vastustajan siirrot ja vielä niiden jälkeiset omat siirrot. Siirroksi valitaan se siirto, joka tuottaa isoimman hyödyn (tai pienimmän haitan) y-koordinaatin suhteen. Samantasoisista siirroista valitaan se, jossa siirrettävä nappula on kauimpana maalista.

Aika oli vähän tiukassa, joten ei tullut mitään omaperäistä toteutettua ja tekoäly on suoraan jatkettu C++-esimerkkitoteutuksesta.

Ants
Teemu Valo
User137
Neljäs kehitysversio kokeilee hyppyjä ja yksittäisiä siirtoja, jolla liikkuu eniten kullakin vuorolla. Joka vuorolla käydään myös läpi ja pisteytetään kaikki omat ja vastustajan siirtovaihtoehdot, jotka seuraavat niitä. Antaa hieman enemmän painoarvoa nappuloille, jotka ovat kauimpana maalista.
Kuovi
Eki Lehtimäki

Kuovi arvioi pelitilanteita MSPV-pisteytyksen avulla (MSPV = "monenko siirron päässä voitosta?"). Yhden nappulan MSPV-arvo on pienin laillisten siirtojen lukumäärä, jolla nappula pääsisi maaliin, jos laudan muut nappulat eivät liikkuisi. (Ei siis todellakaan absoluuttinen siirtojen määrä varmasta voitosta, vaan tunnusluku, joka kertoo, onko nappulan asema hyvä vai huono.) Pelivuorollaan Kuovi kokeilee eri siirtoja, laskee kutakin siirtoa vastaavan kaikkien nappuloiden yhteenlasketun MSPV-pistemäärän ja valitsee (yleensä) pienimmän tuloksen antavan siirron. Koskaan ei siis lasketa enempää kuin yksi siirto eteenpäin.

Taktiikan haittapuoli on se, että siirto, joka parantaisi asemia parin siirron päästä mutta huonontaa MSPV-pisteitä tilapäisesti "pomppureittien" tukkeutumisen takia, on tällä logiikalla aina huono. Ongelman kiertämiseksi Kuovi yrittää tunnistaa, milloin sen oma peli on muuttumassa passiiviseksi, ja käyttää silloin "aggressiivista avaussiirtoa", joka ei ole mitenkään riippuvainen MSPV-pisteistä. Myös kuusi ensimmäistä siirtoa tehdään MSPV-pisteistä riippumatta aina samalla tavalla, jotta alkusommitelma saataisiin mahdollisimman hyväksi. Aluksi Kuovi laski myös vastustajan MSPV-pisteitä ja yritti mahdollisuuksien mukaan haitata vastustajan peliä. Testeissä estotaktiikkaa käyttävä Kuovi kuitenkin yleensä hävisi pelinsä, joten lopullinen Kuovi ei yritä estämistä lainkaan.

LiteYear
Antti Vainio
Anaatti
Jokaisella vuorollaan ohjelma etsii aluksi kaikki siirrot, jotka pystyisi tekemään. Tämän jäkeen se pisteyttää jokaisen siirron, ja lopulta se siirto, joka sai eniten pisteitä, tehdään. Tekoäly keskittyy pääasiassa omaan peliin eikä niinkään välitä vastustajasta. Siirtojen pisteytyksessä käytetään joitakin yksinkertaisia asioita kuten etenemistä y-akselilla, mutta myös monimutkaisempia asioita kuten omien nappuloiden x-koordinaattien keskiarvoa. Muutama tilanne on myös etukäteen pisteytetty, ja tietyin väliajoin käytetään vähän erilaisia pisteytysmenetelmiä.
silta10
Toni Huttunen
Seriffi
Seuraa asetettua reittiä vastustajaa huomioimatta. Luottaa muiden tekoälyjen sokeuteen.
Kabot
Sami Kalliomäki
Sami345
Tekoäly laskee pisteet kaikille mahdollisille siirroille ja valitsee niistä parhaan. Pisteet lasketaan oman, vihollisen ja oman seuraavan siirron perusteella.
P3TO
Juho Peltonen
aaämdee
Python 3 Teko-Olento pyrkii etenemään aina ensisijaisesti hyppimällä. Yrittää hankaloittaa muodostelmalla vastustajan kulkua.
Pompper
Tomi Kokkonen
tkok
Esimerkin kevyesti paranneltu versio.
Awesome
Michael Borderborough
Borderi
Minimaxia höystettynä hupaisilla heuristiikoilla.
Hypsis
Tigon

Tämä on oikeasti yhden viikonlopun väsäys, mutta kiinnostaa, miten pärjää. Omalla vuorolla peli käy läpi mahdolliset siirrot ja laskee sitten syntyville pelitilanteille jonkin arvosanan. Siirroista valitaan se, joka johtaa parhaaseen pelitilanteeseen. Varsin perinteinen menetelmä, olettaisin.

Itse tekoäly on siis pelilaudan tilanteen pisteiden laskemisessa. Tämä on pilkottu osiin, jotka vaikuttavat pisteisiin eri painoarvoilla. Ajoin ohjelmaa pari tuntia niin, että eri painoarvoilla pelaavat tekoälyt pelasivat toisiaan vastaan, ja poimin sieltä sitten parhaan tänne kisaan.

Jatkokehittäminen olisi helppoa lisäämällä uusia sääntöjä pelitilanteen pisteytykseen ja muuttamalla ohjelmaa niin, että pelitilannetta katsotaan enemmän kuin tämän yhden siirron verran eteenpäin.

vahajarki
Juho Pinola
JP_94
Tekoäly yrittää siirtää nappuloita mahdollisimman nopeasti maalia kohti tarvittaessa vastustajan nappuloita kiertämällä. Äly osaa myös hyppiä nappuloiden yli ja voi tehdä pitkiäkin hyppysarjoja sen ollessa mahdollista ja kannattavaa maalia kohti pääsemisen kannalta.
esimEsimerkkiohjelma liikuttaa nappuloita askeleen kerrallaan maalia kohti tai positiiviseen x-suuntaan, jos tie on tukittu. Jos kumpikaan ei onnistu, ohjelma pysyy paikallaan.
viikinki
Mikko Sysikaski
Sisuaski
Rintamapuolustus.

Kiitokset vielä niin osallistujille kuin yleisöllekin onnistuneesta kilpailusta!

Tietoa sivustosta