Kirjautuminen

Haku

Tehtävät

Kilpailu

Ohjelmoi tekoäly!
Aikaa on 6.1. saakka.

Kilpailut: Valtapeli: tulokset

Järjestäjä: Metabolix

Vuodenvaihteessa 2012–2013 Ohjelmointiputkassa pidettiin tekoälykilpailu. Aiheena oli Valtapeli, kahden pelattava lautapeli, jossa ensimmäinen pelaaja yrittää valloittaa pelilaudalta mahdollisimman suuria yhtenäisiä alueita ja toinen yrittää estää tämän. Kaikki tekoälyt pelasivat vuorollaan toisiaan vastaan, ja pisteen sai aina se, joka menestyi hyökkäyksessä paremmin.

Kilpailuun osallistui 21 ohjelmaa, joiden taso vaihteli laidasta laitaan. Kiinnostavaa on, että vaikka voittaja käytti runsaasti aikaa pelipuun tutkimiseen, useampi seuraava sija meni heuristiikoille, jotka arvioivat siirtoja vain nykytilan perusteella.

Jäljempänä tällä sivulla on ohjelmien kuvauksia, ja lähdekoodit voi ladata yhtenä pakettina.

Osallistujat ja tulokset

Alla ovat kaikki kilpailun osallistujat voittajasta alkaen. Taulukossa näkyvät myös tekoälyjen keskimääräiset ajat hyökkäyksessä (H) ja puolustuksessa (P).

Varsinaisten kilpailijoiden lisäksi kilpailussa oli mukana esimerkkiäly esim, joka tällä kertaa jopa voitti yhden kilpailijan.

sijatekoälykielitekijänimimerkkivoittojaH-aikaP-aika
1.DrAterC++Mika UrtelaApodus2010,08 s10,88 s
2.FloydCOtto Seiskarios193,82 s3,55 s
3.LightOnC++Lauri KenttäMetabolix180,01 s0,01 s
4.cimplePythonChiman170,19 s0,45 s
5.AeronPythonAntti VainioAnaatti152,18 s10,93 s
6.powerBotCTimo SakariTimmmo150,15 s0,15 s
7.SagaPHPKarl Nystedtqeijo141,40 s1,13 s
8.waltavaGroovyRiku Salkia1310,43 s10,71 s
9.SnipperC++Niko Nyrhilämsdos464120,01 s0,61 s
10.AIkapommiC#Aapo Vuoristoajv108,99 s1,67 s
11.lieroC++Johannes Tuomelajohku90100,19 s0,23 s
12.rxaVB.NetSami RiiheläRixa100,08 s0,07 s
13.talyC++weggo90,25 s0,01 s
14.puruqmiC++pr0l373,71 s7,26 s
15.KuuttiPythonTeemu KekkonenTego60,50 s0,56 s
16.MetapalloCLauri KenttäMetabolix50,01 s0,01 s
17.NaporeinoCEino-Pekka Kantoreino40,35 s0,01 s
18.FU2Fortranjalski30,01 s0,01 s
19.PyPlayerPythonHannes Karppilahfcoder10,14 s0,14 s
20.esim(useita)10,01 s0,01 s
21.jonne8DCAntti LaaksonenAntti Laaksonen10,01 s0,01 s

Onnea voittajalle virheettömästä tuloksesta!

Tilanteissa, joissa kilpailijoilla on yhtä monta voittoa, verrattiin ensin kilpailijoiden pelejä toisiaan vastaan, ja tämän perusteella Aeron voitti powerBotin. Kolmen pelaajan tasapeleissä verrattiin heikoimpia hyökkäyspistemääriä: AIkapommi 948, liero 874, rxa 694; PyPlayer 348, esim 170, jonne8D 128.

Pelit

Tässä taulukossa ovat kaikki pelatut pelit. Aloittaja lukee kunkin rivin alussa ja puolustaja ylärivillä. V-kirjain merkitsee aloittajan voittoa eli sitä, että pelin pistemäärä on suurempi kuin vastapuolen aloittaessa. H-kirjain tarkoittaa vastaavasti häviötä ja T-kirjain tasapeliä, joita tosin ovat vain tekoälyjen pelit itseään vastaan. Tulos on linkki katselusivulle, josta voi katsoa kyseisen pelin. Kaikkien pelien pistemäärät on taulukoitu erilliselle sivulle.

DrFlLiciAepoSawaSnAIlirxatapuKuMeNaFU2Pyesjo
DrAterTVVVVVVVVVVVVVVVVVVVV
FloydHTVVVVVVVVVVVVVVVVVVV
LightOnHHTVVVVVVVVVVVVVVVVVV
cimpleHHHTVVVVVVVVVVVVVVVVV
AeronHHHHTVHVVVVVVVVVVVVVV
powerBotHHHHHTVVVVVVVVVVVVVVV
SagaHHHHVHTHVVVVVVVVVVVVV
waltavaHHHHHHVTHVVVVVVVVVVVV
SnipperHHHHHHHVTHVVVVVVVVVVV
AIkapommiHHHHHHHHVTVHHVVVVVVVV
lieroHHHHHHHHHHTVVVVVVVVVV
rxaHHHHHHHHHVHTVVVVVVVVV
talyHHHHHHHHHVHHTVVVVVVVV
puruqmiHHHHHHHHHHHHHTVVVVVVV
KuuttiHHHHHHHHHHHHHHTVVVVVV
MetapalloHHHHHHHHHHHHHHHTVVVVV
NaporeinoHHHHHHHHHHHHHHHHTVVVV
FU2HHHHHHHHHHHHHHHHHTVVV
PyPlayerHHHHHHHHHHHHHHHHHHTVH
esimHHHHHHHHHHHHHHHHHHHTV
jonne8DHHHHHHHHHHHHHHHHHHVHT

Alueiden määrät

Seuraavassa kuvassa ovat vasemmalla pienet alueet ja oikealla suuret. Palkin koko korkeus on kyseisestä aluekoosta saadun kokonaispistemäärän logaritmi, ja yläpuolella lukee, montako alueita oli. Eri värit merkitsevät eri tavoin sijoittuneita tekoälyjä: vihreät parhaita, siniset keskitasoisia ja punaiset listan viimeisiä. Palkki on jaettu erivärisiin osiin siinä suhteessa, jossa eri tekoälyt ovat samankokoisia alueita muodostaneet.

Kuvasta nähdään, että peleissä on tehty kaikenlaisia alueita, pieniä hyvin paljon ja suuria hyvin vähän. Kaikkein suurimmat alueet ovat enimmäkseen listan paremman puoliskon valtaamia – oletettavasti paljon huonompia vastustajia vastaan. Piikki suurimmassa aluekoossa liittynee esimerkkiälyyn, jota vastaan suuri osa osallistujista osasi hyökätä hyvin tehokkaasti, sekä PyPlayeriin, joka usein kaatui ja siksi pelasi kuten esimerkkiohjelma.

Ohjelmat

Ohjelmien lähdekoodit voi ladata yhtenä pakettina. Alla ovat tekijöiden omat kuvaukset ohjelmistaan.

DrAter
Mika Urtela
Apodus

Tekoälyn menetelmänä on lyhyt minmax, jossa käydään läpi tyypillisimmät fiksut siirrot. Lehtisolmun arvona käytetään Monte Carlo -evaluaatiota, jossa katsotaan tiukemmin ohjattu (naiivi) pelipolku loppuun.

Minmaxissa ei aseteta vakiosyvyyttä vaan ylläpidetään nykytilanteen "leveyttä". Nykyisen tilanteen leveys on edellisen minmax-askeleen leveys kerrottuna nykyisen tilanteen harkittavien siirtojen määrällä. Monimutkaisissa tilanteissa leveys kasvaa nopeasti maksimiarvoon, jolloin palautetaan arvio tilanteesta. Yksinkertaisempia tilanteita taas voidaan laskea hiukan syvemmälle. Ääriesimerkkinä voi ajatella muista peleistä tuttuja pakotettuja jatkoja, jolloin usean siirron ajan peräkkäin harkitaan vain yhtä siirtoa, mikä ei kasvata tilanteen leveyttä lainkaan.

Floyd
Otto Seiskari
os
Hyökkääjän ruutujen naapureita arvioidaan muun muassa sen mukaan, montako ruutua niistä on saavutettavissa tietyllä määrällä askelia. Jos yhtään naapuria ei löydy, valitaan ruutu, joka on mahdollisimman kaukana reunoista ja varatuista ruuduista. Puolustajan tapauksessa arvioidaan myös sitä, montako hyökkääjän ruutujen naapuria jää vapaaksi ja onko näiden kautta jatkuvaa hyökkäystä helppo torjua.
LightOn
Lauri Kenttä
Metabolix

Tekoälyn puolustusalgoritmi koostuu joukosta varsin yksinkertaisia sääntöjä, joiden mukaan ruudut pisteytetään. Ensin lasketaan, miten kaukana lähin hyökkääjän ja puolustajan ruutu on, montako tutkittavan ruudun naapureista ja kulmittaisista ruuduista on hyökkääjän ja puolustajan valtaamia ja ovatko ruudun naapurit vastakkaisilla reunoilla saman pelaajan hallussa. Sitten ajetaan ehtolauseet, jotka määräävät pistemäärän. Menetelmä on alkeellinen ja varmasti täynnä aukkoja ja paranneltavaa, mutta omissa kokeiluissa säännöt tuntuivat toimivan aika hyvin.

Hyökkäyksessä ruudut pisteytetään sen mukaan, kuinka monen ruudun päähän niistä pystyy suoraan etenemään avoimella alueella tai aiempaa omaa aluetta hyödyntäen. Toisin sanoen pisteytysalgoritmi ei mene läpi sellaisista kapeista kohdista, jotka vastustaja pystyisi täysin varmasti sulkemaan.

cimple
Chiman
Hyökkäyksessä aloitetaan isoimman vapaan alueen keskeltä ja laajennetaan omaa yhtenäistä aluetta niin kauan kuin mahdollista. Puolustajana ahdistetaan vastustajaa siirtämällä aina sen laajenemiskykyisen alueen viereen. Sekä hyökätessä että puolustettaessa pelattava ruutu valitaan pisteyttämällä ruudut naapuriruutujen perusteella. Siirtoja ei lasketa eteenpäin.
Aeron
Antti Vainio
Anaatti
Tekoäly pyrkii kasvattamaan isoimpia alueitaan niin, että sille jää edelleen ympärilleen tilaa toimia. Tämän takia tekoäly ei muodosta kovinkaan yhtenäistä aluetta vaan erittäin haarautuneen ja repaleisen alueen. Puolustaessa tekoäly pyrkii myös jakamaan jäljellä olevia alueita pienemmiksi kokonaisuuksiksi, mikäli se on mahdollista yksittäisellä siirrolla.
powerBot
Timo Sakari
Timmmo
Algoritmi on sangen yksinkertainen ja suoraviivainen ilman minkäänlaista rekursiota. Hyökätessään se valitsee tyhjistä ruuduista ne, jotka tuottavat parhaat pisteet. Tästä listasta haetaan sitten ruudut, joilla on eniten tyhjiä naapuriruutuja, ja edelleen ne ruudut, joiden tyhjät naapurialueet ovat isoimmat eli jotka omaavat parhaan kasvupotentiaalin. Näistä valitaan vielä mahdollisimman keskellä pelialuetta oleva ruutu. Puolustaessaan algoritmi valitsee sen siirron, jonka hyökkääjä tekisi äskeistä periaatetta noudattaen.
Saga
Karl Nystedt
qeijo

Saga pisteyttää pelikentän ja siirtyy aina paikkaan, joka tuo hänelle eniten pisteitä. Kaikki vapaat paikat saavat pisteen 0-n, arvo määräytyy paikan ympärillä olevan alueen mukaan. Puolustus toimii samalla tavalla mutta käänteisesti.

Aikaa ohjelman pohtimiseen, tekemiseen ja testaamiseen on käytetty about 4-5 tuntia. Olen erittäin tyytyväinen, jos Saga sijoittuu 50% paremmalle puolelle.

waltava
Riku Salkia
Use the Source, Luke
Snipper
Niko Nyrhilä
msdos464

Hyökkääjä käy kaikki vapaat ruudut läpi ja käyttää simppeliä evaluaatiofunktiota löytääkseen parhaan siirron.

Puolustaja käy läpi kaikki vapaat ruudut, ja kullekin vaihtoehdolle testaa, mitä vapaita ruutuja hyökkääjälle jää käyttöön. Puolustaja valitsee siis sen siirron, joka minimoi hyökkääjän parhaan mahdollisen siirron hyvyyden (minimax).

Koska hyökkääjä ei analysoi mahdollisia puolustajan siirtoja, se tekee siirtoja hyvin lyhyellä tähtäimellä. Puolustaja on vähän vahvempi, koska se katsoo sentään mahdollisia hyökkääjän siirtoja. Kuitenkin sekin on hyvin simppeli, ja se on luultavasti helppo päihittää paremmilla algoritmeilla.

AIkapommi
Aapo Vuoristo
ajv

Ohjelma käyttää parhaan siirron etsimiseen MinMax-algoritmia Alpha-Beta-karsinnalla höystettynä. Hyvyysfunktiossa kenttä pisteytetään kertomalla seuraavat tekijät keskenään sopivilla painoarvoilla: hyökkääjän pistetilanne, hyökkääjän vapaiden naapuriruutujen määrä ja hyökkääjän siirtojen jakauma ruudukossa (keskeltä saa enemmän pisteitä kuin reunoilta).

Lasketut pelitilanteet laitetaan talteen (Zobrist Hash Table), ja lisäksi pidetään muistissa muutamia edellisen haun tuloksia. Lisäksi ohjelma pitää muistissaan parhaita vastasiirtoja, eli jos vastustaja sattuu tekemään siirron, jonka on edellisellä kerralla laskettu, tiedetään, mistä haarasta aikaisemmin on löydetty paras tulos. Tämä auttaa kohtalaisesti, jos vastustaja pelaa, kuten tämä ohjelma olettaa sen pelaavan. :)

Ohjelma saattaa pärjätä muita vastaavalla tavalla pelaavia ohjelmia vastaan, mutta ihmiselle se on helppo vastus. Esim. kauempaa tapahtuvaa ”motitusta” se ei osaa pelätä, kun aika rajoittaa hakusyvyyden ja leveyden vain olemassaolevien hyökkääjän siirtojen välittömään läheisyyteen.

Tarkempi toimintakuvaus löytyy Program.cs-tiedoston alusta.

liero
Johannes Tuomela
johku90
Tekoäly käy läpi kaikki pisteet ja laskee kullekin sijainnille hyvyyden pakoreittien sekä hyökkääjän sijainnin perusteella. Se yrittää selvitä sekä hyökkäyksestä että puolustuksesta samalla tavalla.
rxa
Sami Riihelä
Rixa
Aika vajaa on tämä tekoäly. Valloittajana se etsii vapaita ruutuja omien ruutujen vierestä, jotta yhtenäinen alue olisi mahdollisimman suuri. Estäjänä se etsii vapaita ruutuja vastapuolen ruutujen vierestä.
taly
weggo
Ohjelma laskee optimaalisen siirron parilla itsetehdyllä algoritmilla. Hyökkäysalgoritmiin on panostettu enemmän aikaa ja vaivaa, kun taas puolustus pitäytyy hyvin simppelissä ratkaisussa.
puruqmi
pr0l3
Jokin minmax-viritys, en varmaan osaa.
Kuutti
Teemu Kekkonen
Tego
Kuutti on esimerkin päälle teipattu yksinkertainen tekoälyttömyys. Toiminnan pohjalla on eräänlainen potentiaalikartta, johon hyökkääjän ja puolustajan valtaukset tekevät kumpuja ja kuoppia kiinteän funktion mukaan. Ohjelma valtaa aina korkeimman mahdollisen potentiaalin ruudun joko häiritäkseen tai kasatakseen joukkoa.
Metapallo
Lauri Kenttä
Metabolix

Ohjelma laskee aloittajan ruutujen seutuun positiivisia metapalloja ja puolustajan ruutujen seutuun negatiivisia metapalloja. Vuorolla valitaan ruutu, jossa on suurin positiivinen arvo.

Kunnollisia ohjelmia vastaan ei varmasti ole mitään toivoa, mutta kai tälläkin muutaman amatöörin voittaa.

Naporeino
Eino-Pekka Kanto
reino

Naporeino on tekoälyjen kuolemantähti. Hyvä puolustusalgoritmi ja ovela hyökkäys tekevät siitä aika hienon tekoälyn. Puolustusalgoritmi tekee shakkiruudukon, joka minimoi hyökkääjän pistemahdollisuudet. Hyökkäysalgoritmi on kuin matopeli. Se menee eteenpäin matona ja koettaa minimoida epäyhtenäisyydet. Jos tulee umpikuja tai satunnaislukugeneraattori sanoo toisin, tekoäly hyppää kohtaan, jossa on vieressä oma ruutu. Jos kuitenkaan omien ruutujen viereen ei pääse, tekoäly menee johonkin sattumanvaraisesti.

Jos Naporeino olisi näyttelijä, hän olisi Chuck Norris.

FU2
jalski
Tekoäly käyttää Influence map -pohjaista lähestymistapaa kartoittamaan tilanteen pelilaudalla ja valitsee aina suurimmalla arvolla olevan vapaan ruudun.
PyPlayer
Hannes Karppila
hfcoder
Yksinkertainen, kahdessa tunnissa tehty tekoäly, toimii lähinnä vain yksinkertaisen logiikan varassa.
esimEsimerkkiohjelma valitsee aina ensimmäisen vapaan ruudun.
jonne8D
Antti Laaksonen
Tekoäly toimii muuten kuin esimerkki, mutta se käy läpi vinorivejä ja käy ensin parilliset vinorivit ja sitten parittomat.

Lopuksi

Kiitos kaikille osallistujille kiinnostavasta kilpailusta! Lisää kilpailuja järjestetään varmasti, ja ehdotuksia voi lähettää sähköpostitse.

Tietoa sivustosta