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).
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 %.
| sija | tekoäly | kieli | tekijä | nimimerkki | pisteet |
|---|---|---|---|---|---|
| 1 | osvastusX | C++ | Otto Seiskari | os | 84890 |
| 2 | Lokki | C++ | Aleksi Hartikainen | ahr | 80786 |
| 3 | HalfLife3 | Rust | Santtu Keskinen | skeskinen | 80429 |
| 4 | pathfindr | C++ | Lari Koponen | L2-K2 | 72792 |
| 5 | Calgary88 | C++ | Jorma Sainio | FooBat | 70472 |
| 6 | TaSman | Java | Tapani Sjöman | TapaniS | 68740 |
| 7 | XRPicker | C++ | Esa Lipponen | Libo | 65294 |
| 8 | Uppopallo | JavaScript | Lauri Kenttä | Metabolix | 62792 |
| 9 | Kumpuin | Rust | Teemu Kekkonen | Tegu | 57333 |
| 10 | jopeli | Python | Joel Honkamaa | jo123 | 47326 |
| 11 | poimuri | C# | Sami Riihelä | R1xa | 42914 |
| 12 | Reiska | JavaScript | Johannes Tuomela | johku90 | 42486 |
| 13 | Nipsu | C | Jari Saari | jsbasic | 41418 |
| 14 | entropy | Python | Antti Vainio | Anaatti | 32475 |
| 15 | Ketjutin | C++ | Esa Lipponen | Libo | 18534 |
Onnea koko tasaväkiselle kärkijoukolle!
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äly | keskiarvo | vaihteluväli | keskihaj. |
|---|---|---|---|
| osvastusX | 95,9 % | (66,8 – 100,0) | 5,1 % |
| Lokki | 94,9 % | (53,5 – 100,0) | 6,2 % |
| HalfLife3 | 95,1 % | (43,9 – 100,0) | 7,1 % |
| pathfindr | 92,6 % | (65,3 – 100,0) | 6,2 % |
| Calgary88 | 91,5 % | (66,1 – 100,0) | 6,1 % |
| TaSman | 91,5 % | (55,4 – 100,0) | 7,1 % |
| XRPicker | 90,4 % | (50,4 – 100,0) | 7,6 % |
| Uppopallo | 89,7 % | (54,5 – 100,0) | 7,8 % |
| Kumpuin | 88,1 % | (35,8 – 100,0) | 9,3 % |
| jopeli | 84,7 % | (46,9 – 100,0) | 8,3 % |
| poimuri | 82,9 % | (31,7 – 100,0) | 10,8 % |
| Reiska | 82,3 % | (39,9 – 100,0) | 9,0 % |
| Nipsu | 82,6 % | (40,4 – 100,0) | 8,7 % |
| entropy | 77,6 % | (36,4 – 100,0) | 9,0 % |
| Ketjutin | 69,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!
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äly | kieli | pisin aika | aika/ottelu | aika/siirto |
|---|---|---|---|---|
| osvastusX | C++ | 2650 ms | 1294 ms | 11254 µs |
| Lokki | C++ | 840 ms | 439 ms | 3784 µs |
| HalfLife3 | Rust | 650 ms | 297 ms | 2576 µs |
| pathfindr | C++ | 4380 ms | 1608 ms | 13995 µs |
| Calgary88 | C++ | 150 ms | 72 ms | 622 µs |
| TaSman | Java | 2720 ms | 1334 ms | 11632 µs |
| XRPicker | C++ | 1520 ms | 761 ms | 6599 µs |
| Uppopallo | JavaScript | 840 ms | 226 ms | 1960 µs |
| Kumpuin | Rust | 50 ms | 21 ms | 180 µs |
| jopeli | Python | 1270 ms | 689 ms | 5875 µs |
| poimuri | C# | 4020 ms | 1969 ms | 17103 µs |
| Reiska | JavaScript | 1820 ms | 915 ms | 7964 µs |
| Nipsu | C | 20 ms | 4 ms | 34 µs |
| entropy | Python | 400 ms | 192 ms | 1639 µs |
| Ketjutin | C++ | 20 ms | 6 ms | 53 µ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.
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. |
Kiitos kaikille osallistujille hyvästä kilpailusta, ja tervetuloa mukaan taas ensi kerralla.