Kirjautuminen

Haku

Tehtävät

Kilpailu

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

Kilpailut: Poimintapeli: tulokset

Järjestäjä: Metabolix

Vuodenvaihteessa 2018–2019 Ohjelmointiputkassa pidettiin tekoälykilpailu pelistä, jossa pelaajien piti kerätä ruudukosta mahdollisimman suuri summa lukuja.

Kilpailuun osallistui 15 ohjelmaa. Peli osoittautui melko vaikeaksi. Yleisin lähestymistapa oli lyhyt syvyyshaku, mutta myös sopiva ruutujen pisteytys ja satunnaisten reittien kokeileminen sekä pelaamalla opettelu tuottivat hyviä tuloksia. Kokonaisuudessaan kisa oli tasainen, ja luultavasti osallistujien sijoitukset voisivat eri pelilaudoilla olla erilaiset.

Jäljempänä tällä sivulla on ohjelmien kuvauksia, ja tekoälyt voi ladata yhtenä pakettina. Tekoälyjä voi kokeilla myös kisan testaussivulla. Kaikki kilpailussa pelatut ottelut voi ladata testausohjelmalle sopivassa muodossa tästä linkistä (6,6 Mt, purettuna noin 100 Mt).

Osallistujat ja tulokset

Alla ovat kaikki kilpailun osallistujat voittajasta alkaen. Kisassa pelattiin yhteensä 27818 peliä. Jokainen ohjelma pelasi 1456 neljän pelaajan peliä, 6006 kuuden pelaajan peliä, 4004 kymmenen pelaajan peliä ja 1337 kaikkien 15 pelaajan peliä. Jokaisesta pelistä jaettiin häviäjälle 1 piste, seuraavalle 2 pistettä ja niin edelleen, eli voittaja sai pelaajien määrän verran pisteitä. Teoreettinen maksimisuoritus olisi ollut siis 101955 pistettä, ja voittaja saavutti tästä 83 %.

sijatekoälykielitekijänimimerkkipisteet
1osvastusXC++Otto Seiskarios84890
2LokkiC++Aleksi Hartikainenahr80786
3HalfLife3RustSanttu Keskinenskeskinen80429
4pathfindrC++Lari KoponenL2-K272792
5Calgary88C++Jorma SainioFooBat70472
6TaSmanJavaTapani SjömanTapaniS68740
7XRPickerC++Esa LipponenLibo65294
8UppopalloJavaScriptLauri KenttäMetabolix62792
9KumpuinRustTeemu KekkonenTegu57333
10jopeliPythonJoel Honkamaajo12347326
11poimuriC#Sami RiiheläR1xa42914
12ReiskaJavaScriptJohannes Tuomelajohku9042486
13NipsuCJari Saarijsbasic41418
14entropyPythonAntti VainioAnaatti32475
15KetjutinC++Esa LipponenLibo18534

Onnea koko tasaväkiselle kärkijoukolle!

Pistetilastot

Ohjelmien tulokset vaihtelivat melko paljon, osalla enemmän kuin toisilla. Seuraavassa taulukossa esitetään, paljonko pisteitä tekoälyt saivat suhteessa kunkin pelin parhaan ohjelman pisteisiin.

tekoälykeskiarvovaihteluvälikeskihaj.
osvastusX95,9 %(66,8 – 100,0)5,1 %
Lokki94,9 %(53,5 – 100,0)6,2 %
HalfLife395,1 %(43,9 – 100,0)7,1 %
pathfindr92,6 %(65,3 – 100,0)6,2 %
Calgary8891,5 %(66,1 – 100,0)6,1 %
TaSman91,5 %(55,4 – 100,0)7,1 %
XRPicker90,4 %(50,4 – 100,0)7,6 %
Uppopallo89,7 %(54,5 – 100,0)7,8 %
Kumpuin88,1 %(35,8 – 100,0)9,3 %
jopeli84,7 %(46,9 – 100,0)8,3 %
poimuri82,9 %(31,7 – 100,0)10,8 %
Reiska82,3 %(39,9 – 100,0)9,0 %
Nipsu82,6 %(40,4 – 100,0)8,7 %
entropy77,6 %(36,4 – 100,0)9,0 %
Ketjutin69,1 %(34,4 – 100,0)8,8 %

Yllä olevasta taulukosta nähdään, että jokainen tekoäly on onneksi voittanut ainakin yhden pelin. Onneksi olkoon!

Resurssit

Ohjelmien ajankäytössä oli suuria eroja. Aivan salamannopeat tekoälyt jäivät tällä kertaa nuolemaan näppejään, eli menestykseen tarvittiin ainakin ripaus laskentaa. Kilpailun tiukassa aikarajassa pysyttiin hienosti.

tekoälykielipisin aikaaika/otteluaika/siirto
osvastusXC++2650 ms1294 ms11254 µs
LokkiC++840 ms439 ms3784 µs
HalfLife3Rust650 ms297 ms2576 µs
pathfindrC++4380 ms1608 ms13995 µs
Calgary88C++150 ms72 ms622 µs
TaSmanJava2720 ms1334 ms11632 µs
XRPickerC++1520 ms761 ms6599 µs
UppopalloJavaScript840 ms226 ms1960 µs
KumpuinRust50 ms21 ms180 µs
jopeliPython1270 ms689 ms5875 µs
poimuriC#4020 ms1969 ms17103 µs
ReiskaJavaScript1820 ms915 ms7964 µs
NipsuC20 ms4 ms34 µs
entropyPython400 ms192 ms1639 µs
KetjutinC++20 ms6 ms53 µs

Muistinkäyttö puolestaan ei ollut millekään ohjelmalle ongelma, sillä ei muistia ehdi tuossa ajassa edes paljon käyttää. Muistinkäytön kannalta ratkaisevin tekijä oli ohjelmointikieli, koska erilliset ajoympäristöt (C#, Java, JavaScript, Python) veivät paljon enemmän muistia kuin mikään ohjelma muuten.

Ohjelmat

Tekoälyjen lähdekoodit voi ladata yhtenä pakettina. Tekoälyjä voi kokeilla myös kisan testaussivulla. Alla ovat tekijöiden omat kuvaukset ohjelmistaan.

osvastusX
Otto Seiskari
os

Algoritmi 1: Laskee kaikki omat siirrot tiettyyn syvyyteen asti ja valitsee parhaan siirtosarjan sen mukaan, kuinka paljon pisteitä sen varrella on, kuinka aikaisessa vaiheessa ne kerätään, kuinka todennäköisesti jokin vastustaja ehtii missäkin kohtaa väliin ja kuinka hyvä "potentiaali" (heuristiikka) sarjan viimeisellä ruudulla on.

Algoritmi 2: Käytetään loppupelissä, jos jäljellä olevia ei-tyhjiä ruutuja on riittävän vähän. Valitaan N lupaavinta jäljellä olevaa ruutua ja järjestys, jossa ne kannattaa yrittää kerätä.

Lisäksi käytetään kummassakin algoritmissa logiikkaa, joka rajoittaa, milloin suunniteltua reittiä voidaan vaihtaa, mikä estää oman pelaajan jäämisen jumiin kahden tai useamman ruudun sykliin.

Lokki
Aleksi Hartikainen
ahr

Tekoäly laskee jokaiselle vastustajalle K (256) satunnaista polkua (noin 10 siirtoa) ja valitsee näistä M (32) pistearvollisesti parasta. Valituiden polkujen perusteella lasketaan todennäköisyydet eri ruutujen saatavuudelle tulevaisuudessa sillä oletuksella, että jokainen vastustaja valitsee satunnaisesti näistä M:stä polusta. Tämän jälkeen omalle pelaajalle lasketaan polku, joka antaa parhaan odotusarvon pisteille taulukkoon tallennettujen todennäköisyyksien mukaan.

Jos parhaan polun odotusarvo on liian pieni (alle 2), valitaan siirto ns. painovoimataktiikalla. Tässä taktiikassa jokainen laudan numero vaikuttaa pelaajaan painovoimalla etäisyyden ja massan (numeron) mukaan. Siirrot tehdään painovoiman suuntaan. Tällä taktiikkavaihdoksella vältetään jumiin jääminen tilanteissa, joissa pelaajan läheltä ei löydy enää kerättäviä numeroita.

Tekoäly ei osaa muistaa laskelmia siirtojen välillä, eli joka vuorolla kaikki lasketaan uudestaan.

HalfLife3
Santtu Keskinen
skeskinen
Algoritmi antaa jokaiselle ruudulle pistearvon kaavalla ja etsii reitin, joka antaa eniten pisteitä tässä uudessa ruudukossa. Kunkin ruudun arvolla on puoliintumisaika, joka on niin monta vuoroa kuin etäisyys lähimmästä vastustajasta. Toisin sanoen: ruudut ovat arvokkaampia, jos ne ovat kaukana vastustajista ja pelaaja saa ne kerättyä nopeammin itselleen.
pathfindr
Lari Koponen
L2-K2
Nimensä mukaisesti tekoäly pyrkii etsimään vapaasti pelattavissa olevia polkuja pistelaatalta seuraavalle. Polku on vapaasti pelattavissa, jos kukaan vastustajista ei voi ehtiä mihinkään polulla olevaan pistelaattaan ennen tekoälyä (samanaikainen saapuminen on sallittua, koska tällöin molemmat saavat pisteet). Tekoälyn kovuus vastustajana riippuu hyvin voimakkaasti pelaajamäärästä. Kaksinpelissä se on hyvin heikko, mutta samanaikaisten pelaajien määrän kasvaessa se näyttäisi olevan selvästi vahvin ideoistani.
Calgary88
Jorma Sainio
FooBat
Tekee hyvin yksinkertaisen suunnatun haun hakuavaruuteen, johon omalla botilla on lyhyempi matka kuin kilpailijoilla. Jos tällaista kohdetta ei ole tai useampi suunta on yhtä hyvä, liikutaan ensisijaisesti ensisijaisesti kohti painotettua pistekertymää.
TaSman
Tapani Sjöman
TapaniS
Ensin tutkitaan, missä on eniten pisteitä, ja tehdään alkukiihdytys suoraan kyseiselle alueelle. Toisten parhaat jatkot arvioidaan, ja pelikenttä pisteytetään sen mukaisesti. Jos hyvä ruutu on lähempänä vastustajaa, sitä ei huomioida, ja jos itse on 0–2 ruutua lähempänä, ruutu saa lisäarvoa. Jos lähialueella (enintään 5 ruudun päässä) on erittäin hyvä jatko, se noukitaan ilman tilanteen analyysiä. Muutoin laskentasyvyys määräytyy lähialueella olevien pisteiden mukaan. Alussa suurempi tarkkuus, loppupisteistä ei niin väliä. Suuria pisteitä painotetaan bonuspisteiden muodossa.
XRPicker
Esa Lipponen
Libo
Alussa valitaan pelilaudan keskelle kuvitellun ison X:n haaroista mieleisin suunta ja mennään sitä noudatellen hetken matkaa pelilaudan nurkkaa kohti. Sitten etsiskellään parasta siirtoa kahdesta pelisuunnasta neljästä useamman askeleen siirron tuottamien pisteiden perusteella. Vastustajien sijainteja ja mahdollisia pistepoimintoja huomioidaan kevyesti.
Uppopallo
Lauri Kenttä
Metabolix
Uppopallo etsii syvyyshaulla parhaan reitin seitsemän siirron päähän. Vastustajien kohdalle tehdään karttaan pieni läpipääsemätön alue. Ellei haku löydä lähistöltä lukuja, jatketaan entiseen kulkusuuntaan.
Kumpuin
Teemu Kekkonen
Tegu
Kumpuin laskee leveyshaun avulla jokaiselle ruudulle pistekertymän, jos tekoäly etenisi kyseiseen ruutuun lyhyintä reittiä. Ruuduista valitaan suurin, ja tekoäly tekee siirron tätä ruutua kohti. Pisteitä painotetaan hieman mielivaltaisesti kääntäen verrannollisesti etäisyyteen. Painotuksen ideana on yrittää suosia nopeammin saavutettavia suuria pisteitä, sillä tilanne kaukana ehtii luultavasti muuttua ennen kuin sinne pääsee.
jopeli
Joel Honkamaa
jo123
Kyseessä on yksinkertainen Deep Q-learning -toteutus, eli tekoälylle on "opetettu" peli peluuttamalla sitä itsensä kanssa. Käytännössä tämä tarkoittaa sitä, että sovitetaan neuroverkkofunktio dataan pelatuista peleistä. Neuroverkko sovitetaan ennustamaan saatuja pisteitä toiminnon funktiona, mikäli peliä jatkettaisiin optimaalisesti tuon toiminnon jälkeen. Tulevaisuuden pisteille toki annetaan pienempi paino. Toimii tämä vissiin jotenkuten.
poimuri
Sami Riihelä
R1xa
Ohjelma hakee rekursiolla reitin, jolta saa eniten pisteitä. Saman arvoisista reiteistä valitaan se, josta saa suurimman arvon ensimmäisenä. Alussa painotetaan isompia numeroita. Pisteiden vähentyessä haetaan vain lähintä numeroa.
Reiska
Johannes Tuomela
johku90
Yksinkertainen reitinhakualgoritmi, joka valitsee parhaimmat pisteet saaneen reitin painottaen lähempiä ruutuja.
Nipsu
Jari Saari
jsbasic
Tämä kevyt tekoäly suuntaa laudan suurimpiin pisteisiin ja niihin, joihin ehtii ennen muita. Jokaiselta riviltä etsitään sen paras ruutu. Lisäksi tekoäly napsii pisteitä naapuriruuduista, jos ne sattuvat kohdille. Nipsu ei käytä varsinaista reittioptimointia, ja niin säästyy laskenta-aikaa ja muistia.
entropy
Antti Vainio
Anaatti
Tämä on idealtaan yksinkertainen äly, joka pisteyttää mahdolliset siirrot katsomalla, mitä lukuja on siirron läheisyydessä ja kuinka etäällä muut pelaajat ovat. Hieno kikka on siinä, että tekoälyn käyttämät painotukset pisteiden laskentaan on opittu pelaamalla satoja tuhansia pelejä ja katsomalla, millä painotuksilla saa parhaan tuloksen. Käytännössä eri painotuksia on kokeiltu varsin satunnaisesti, joten oppiminen on ollut aikamoista brute forcea eikä kovinkaan tehokasta.
Ketjutin
Esa Lipponen
Libo
Ketjutin on harjoitelma rekursiota käyttävän ohjelman tekemisestä. Kohdatessaan vaelluksellaan pelilaudalta pisteitä sisältävän solun Ketjutin etsii tuosta solusta lähtevän mahdollisimman pitkän pisteketjun. Muuta logiikkaa tai optimointia ketjun sisällä tuossa ei juuri ole.

Lopuksi

Kiitos kaikille osallistujille hyvästä kilpailusta, ja tervetuloa mukaan taas ensi kerralla.

Tietoa sivustosta