The Butt Ugly Weblog

Osaako AI pelata Kimbleä?

TL;DR: Ei. Tai no. Osaa. Mutta ei erityisen hyvin, koska kyseessä ei ole strateginen peli.

Pidempi vastaus:

Kimble on Suomessa hyvin tunnettu Trouble/Frustration-pelin variantti, jota Tactic on julkaissut vuosikymmeniä kaikkien kesämökkien iloksi. Sen Pop-O-Matic -noppa on ilahduttanut lapsia, ja erilaisia lauta- ja sääntövariantteja on olemassa Angry Birds -Kimblestä opiskelijoiden suosimaan, lievästi epäilyttävään Norske Kimbleen.

Minulla — ja varmasti kaikilla, jotka ovat pop-o-maticcia koskaan hakanneet — on aina ollut lempistrategia. Ottaako aina kuutosella oma nakkula laudalle? Onko parempi edistää omaa nakkulaa vai syödä kaverin nakkula? Kannattaako siirtää taaimmaisinta vai etumaisinta nakkulaa?

Kun Anthropic antoi muutamaksi viikoksi pääsyn Claude Fable 5 -tekoälymalliin, ja kesälomakin sattui olemaan, niin päätin testailla tämän uuden tekoälymallin kykyjä ja rakentaa sekä pelimoottorin, jolla voi kokeilla erilaisia strategioita, että AlphaZero-tyylisen tekoälyn opetusjärjestelmän, joka oppisi pelin säännöistä lähtien. Hei, se toimi shakille ja go:lle, miksei sitten Kimblen kaltaiselle pelille?

Sellainen pieni huomautus, että tässä tarkoitan tekoälyllä nimenomaan hermoverkkoa, jota on koulutettu koneoppimismenetelmillä. En siis tarkoita sillä viiden rivin Python-algoritmia, jota ihminenkin voisi helposti soveltaa pelitilanteessa.

Ja toinenkin pieni huomautus, että tämä on mun ensimmäinen kosketukseni AlphaZero-tyyppisiin algoritmeihin. Olen kyllä tehnyt hermoverkoilla kaikenlaista muuta, mutta tämmöinen itse itseään opettava algoritmi oli ihan uutta. Joten on ihan mahdollista, että olen mokaillut jotain kovasti perusteellista. Oppia ikä kaikki.

Pelimoottori ja pelaajat

Pelimoottori on kirjoitettu Pythonilla, ja sitä voi käydä kärkkymässä Githubista. Koodi on pitkälti Clauden kirjoittamaa, joten ei siitä sen enempää. Ideana kuitenkin on se, että sille määritellään neljä eri pelaajaa, joista jokainen noudattaa omaa strategiaansa, ja sitten ne pelaavat esimerkiksi 10 000 peliä keskenään. Näin suuressa määrässä pelejä eri strategioiden suhteelliset erot alkavat näkyä.

Testasin muutamaa eri strategiaa, joiden suhteellisia eroja tarkastellaan sitten jutun lopussa.

• random — pelaaja, joka valitsee satunnaisen siirron laillisten siirtojen joukosta, mutta ei pohdi enempää.
• capture — pelaaja, joka pyrkii aggressiivisesti aina syömään muiden nakkuloita, mutta muuten valitsee siirtonsa satunnaisesti.
• runner — pyrkii siirtämään aina pisimmällä olevaa nakkulaansa.
• release — ottaa aina uuden nakkulan laudalle, jos vain voi.
• defensive — pyrkii valitsemaan syömisen, mutta muussa tapauksessa valitsee sen siirron, jolla pääsee pisimmälle (mielellään maalisuoralle).
• rescue — Defensiven muunnos, joka syö jos mahdollista, mutta seuraavaksi pyrkii aina pelastamaan oman nakkulan (siis jos toisen pelaajan nakkula voisi teoriassa syödä sinut omalla vuorollaan, jos toinen heittää hyvin).
• cautious — syö, jos mahdollista; mutta seuraavaksi valitse sellainen siirto, joka ei vie sinua sellaiseen paikkaan, jossa syödyksi tulemisen uhka olisi mahdollinen (eli ei toisen eteen).
• guarded — syö vastustajan nakkula, jos mahdollista; jos joku nakkuloistasi on uhattu, siirrä sitä; vältä siirtoja, jotka vievät sinut toisen eteen; siirrä ensimmäistä nakkulaasi.
• guarded2 — muuten sama kuin Guarded, mutta pyrkii pitämään vähintään kaksi nakkulaa kerrallaan laudalla.
• az-self — Tekoälypelaaja yksi.
• az-vs-guarded — Tekoälypelaaja kaksi.

Voit pysähtyä tähän kohtaan ja miettiä, noudatatko itse jotain näistä strategioista. Jos keksit hyvän, voit poimia lähdekoodin Githubista ja lisätä omasi sinne.

Sivuhuomio nopasta

Törmäsin mielenkiintoiseen sivuhuomioon: Kimblen Pop-O-Matic -noppa ei ole täysin satunnainen, kuten tässä artikkelissa on ansiokkaasti ja ranteita säästelemättä selvitetty. Nopan vastapuoli (eli 1-6, 2-5, 3-4) heitetään peräti 23,9 %:n todennäköisyydellä! Luonnollisesti Kimble-simulaattorini ottaa tämän huomioon ja ajattelin, että tekoäly ehkä oppisi hyödyntämään tietoa jotenkin. Osoittautui kuitenkin, että tällä ei ole hirveästi merkitystä.

Tekoälypelaaja

Kun algoritmiset pelaajat oli valittu ja testattu, seuraavaksi koulutin tekoälypelaajan. Tässä käytettiin AlphaZero-taktiikkaa, eli oleellisesti annettiin tekoälyn vain pelata itseään vastaan niin kauan, että se oppi pelaamaan peliä hyvin.

Kimble on pelinä kuitenkin paljon yksinkertaisempi kuin shakki tai go, joten koulutettava hermoverkkokin oli paljon yksinkertaisempi. Yksinkertaisimmassa versiossa oli noin 85 000 parametria (128 piilotettua neuronia) ja monimutkaisimmassa noin 530 000 parametria (512 piilotettua neuronia). Simulointeja tehtiin 200 tai 800 per siirto, mutta 200 riitti mainiosti. Erot voittoprosenteissa eri kokoisten piilokerrosten välillä eivät kuitenkaan olleet tilastollisesti merkitseviä. Training loss parantui tasaisesti 1.05 → 0.99 → 0.96 mentäessä leveämpiin verkkoihin. Isommat verkot siis oppivat datan paremmin, mutta eivät muuttuneet yhtään vahvemmiksi pelaajiksi.

Koulutin verkot omalla Apple Macbook Air M4 -koneella, mihin meni koosta riippuen muutamasta minuutista muutamaan kymmeneen minuuttiin. Koulutin kaksi pelaajaa: az-self, joka opetteli pelaamaan itseään vastaan, ja az-vs-guarded, jolla oli pelikumppanina vain guarded-pelaaja.

Koulutettujen verkkojen koot ja tulokset

Turnaukset

Tietokonepelaajien keskinäinen paremmuusjärjestys ratkaistiin sitten pelaamalla perinteisiä round-robin -turnauksia, käyttäen Plackett-Luce -pisteytystä. P-L on eräänlainen ELO-pisteiden yleistys useammalle kuin kahdelle pelaajalle. Kaksinpeleissä kun on aina vain voittaja ja häviäjä (tasapelit, juujuu, mutta ne eivät vaikuta pelaajan suhteelliseen vahvuuteen), mutta nelinpeleissä pitää ottaa huomioon se, että toinen sija on parempi kuin kolmas tai neljäs.

Pelit pelattiin siihen asti, että yksi pelaaja voitti. Muut sijat jaettiin niin, että eniten kotiin nakkuloita saanut sai kakkossijan, jne. Toissijaisesti katsottiin sitä, kenellä olivat nakkulat kaikkein pisimmällä.

Kimble-pelejä pelattiin yli sata tuhatta. Mielenkiintoinen tieto muuten oli se, että neljän hengen Kimble-pelin pituus on keskimäärin 250 vuoroa. Kahden hengen peli kestää keskimäärin 107 vuoroa ja kolmen hengen 174 vuoroa.

Kimble ei kuitenkaan oikeasti ole kovin strateginen peli. Kuten allaolevasta taulukosta näkee, noin 80 %:ssa kaikista vuoroista on vain yksi ainoa vaihtoehto: joko istua käsillään tai sitten siirtää sitä ainoaa nakkulaa, jota ylipäätään saa siirtää. Neljän hengen pelissä, joka kestää 250 vuoroa, se tarkoittaa sitä, että jokaisella pelaajalla on vain noin 12 strategista päätöstä tehtävänä pelin aikana. Jokainen pelaaja saa kuitenkin heittää noppaa keskimäärin 63 kertaa, ja kuten tiedämme, sehän Kimblessä oikeasti on tärkeintä.

Laillisten siirtojen määrä	Osuus vuoroista
0 (ei voi siirtää mitään)	31,6 %
1 (pakotettu)	49,1 %
2	18,1 %
3	1,2 %
4	0,04 %

Tämä tarkoittaa sitä, että jos yhteen vuoroon nopan heittoineen, miettimiseen, nälvimiseen, voivotteluun ja itse siirtoon menee kymmenen sekuntia (eli sellainen rauhallinen tahti), ja jokaiseen vuoron skippaamiseen menee kaksi, niin peli kestää keskimäärin 1880 sekuntia, eli noin 31 minuuttia. Kolmen hengen peliin menisi vastaavasti 22 min ja kahden hengen peliin 13 min. Jos pelaajia on vähemmän, myös nakkuloiden syömisiä tapahtuu vähemmän, joten pelit ovat vastaavasti hieman nopeampia.

Turnaustulos

Tässäpä sitten se varsinainen pihvi, ja tunnustus omasta riittämättömyydestä: en saanut tekoälyä pelaamaan paremmin kuin hyvin yksinkertainen, käyntikortin takapuolelle mahtuva algoritmi. Teoriani on se, että Kimblessä satunnaisuus on kuitenkin sen verran iso elementti, että AlphaZeron tyyppinen perushermoverkko ei vain osaa mallintaa sitä. Paras hypoteesini on se, että verkon arvopää (value head) käytännössä yrittää mallintaa kohinaa tilanteessa, jossa käytännössä melkein koko ajan laillisia siirtoja on vain nolla tai yksi. Toivon, että joku, joka oikeasti ymmärtää tämän matematiikan päälle enemmän kuin minä, haluaisi uppoutua asiaan tarkemmin.

Kuten kuvasta näkyy, guarded2 pesi kaikki muut algoritmit mennen tullen turnauksessa, jossa pelattiin yhteensä 102 960 eri peliä. Hermoverkkopohjaiset tekoälyalgoritmit tulivat vasta sijoille 4 ja 5. Oikeassa laidassa ovat lasketut P-L vertailuluvut.

Turnaustulokset, 102 960 peliä

Miksi sitten tuo guarded2 pärjäsi niin hyvin? Se on mielestäni melko tasapainoinen: ensinnäkin toisen pelaajan nakkulan syöminen on aina hyvä asia, koska se saattaa estää toista pelaamasta pitkäänkin. Todennäköisyys heittää kuutonen on kuitenkin pitkällä tähtäimellä vain 1/6.

Toisekseenkin se välttää joutumasta tilanteisiin, joissa voit itse joutua syödyksi.

Kolmanneksi, mitä useampi nakkula sinulla on laudalla, sitä todennäköisempää on, että joku niistä joutuu syödyksi, mutta toisaalta, jos sinulla on vain yksi, niin joudut herkästi tilanteeseen, jossa et voi siirtää mitään.

Mielenkiintoisesti sellainen strategia, jossa aina otetaan nakkula laudalle (release), oli selkeästi huonompi kuin muut, ilmeisesti juuri siksi, että se tarjosi niin paljon syötävää muille.

Lopuksi

Paras löytämäni pelitaktiikka (guarded2) on melko yksinkertainen. Se voittaa noin 31 % neljän hengen peleistä ja on parempi kuin tekoälyalgoritmit. Valitettavasti 31 % ei kuitenkaan ole mikään varma voitto; pelejä tarvitaan satoja (eli kesäsään pitää olla todella, todella huono), että tällä taktiikalla pärjää oikeasti.

Ei siis kannata uhrata tähän enempää aikaa; olkaa vain tyytyväisiä, että minä tuhlasin. Ihan kaikki tavat pelata Kimbleä ovat hyviä — joskin Norske Kimblen kanssa olen hieman epäileväinen.

Joten tässä Jannen Algoritmi, olkaa hyvä:

1. SYÖ: Syö aina toisen nakkula, jos voit. Jos sinulla on useampi mahdollisuus, syö kaikkein pisimmällä oleva.
2. SUOJAA: Älä siirry toisen eteen niin, että hän voi seuraavalla vuorolla syödä sinut.
3. LASKE KAHTEEN: Tuo uusi nakkula laudalle kuutosella, jos sinulla on alle kaksi omaa nakkulaa laudalla JA lähtöruutusi ei ole vaarassa.
4. JUOKSE: Siirrä aina pisimmällä olevaa nakkulaa.

---

(Internet-huomautus: koskapa joku kuitenkin voi pahoin sanasta nakkula ja haluaa ehdoin tahdoin kertoa, että oikeasti se on nappula tai tikku tai joonas tai naapurin skodan ilmanraikastin, niin olkaapa kerrankin kivoja ja jättäkää tämmöiset asiat kertomatta, jooko? Mun blogi, mun sanat.)

(Toinen internet-huomautus: ottakaa tuo Github-repo ja tehkää siitä parempi. Tämä on vain muutaman päivän aivopieruilun tulosta yhdistettynä melko edistyneen tekoälyn tulosteisiin, ja joku joka Oikeasti Tietää Asioista osaa varmaan Tehdä Asiat Paremmin. Ja keksikää lisää algoritmeja ja pelauttakaa niistä vastakkain! Joku varmaan keksii paremman kuin minä…)

---