Ristinollan matematiikka ja peliteoria: Kokeile voittaa tekoäly
⏱️ TIIVISTELMÄ (PELITEORIA)
- Nollasummapeli: Ristinolla on matemaattinen ”täydellisen informaation” peli. Jos molemmat pelaavat optimaalisesti, peli päättyy aina algoritmiseen tasapeliin.
- Ratkaistu peli: Tietojenkäsittelytieteessä ristinolla luokitellaan kategoriaan ”ratkaistu” (Solved Game). Sen mahdollinen tilapuun koko on vain $3^9 = 19,683$, mikä tekee siitä triviaalin tekoälylle.
- Kokeile itse: Haasta alla oleva Tietoviisaan Kognitiivinen Minimax-algoritmi. Teoreettisesti et voi voittaa sitä, jos se pelaa optimaalisesti.
Ristinolla (Tic-Tac-Toe) on monelle tuttu yksinkertainen ajanviete lapsuudesta tai Googlen hakukoneeseen piilotettuna Easter Egginä. Peliteorian ja ohjelmoinnin näkökulmasta sen taustalta löytyy kuitenkin kiehtova koneoppimisen ja puuhakualgoritmien maailma. Unohdetaan hetkeksi perinteiset ”miten piirrän ristin” -ohjeet ja tutustutaan siihen, miten tekoäly on jo vuosikymmeniä sitten ”tuhonnut” tämän pelin viihdearvon ratkaisemalla sen täydellisesti.
Testaa aivojasi Minimax-algoritmia vastaan
Alla on Tietoviisaan koodaama tekoälyllä varustettu ristinolla. Tekoäly peluuttaa ohjelman taustalla jokaista mahdollista tulevaisuuden skenaariota (tilapuu) ennen jokaista siirtoaan. Olemme kuitenkin jättäneet tekoälyyn 15 % todennäköisyyden laiskaan ”satunnaissiirtoon”, jotta ihmispelaajalla olisi edes teoreettinen mahdollisuus voittaa. Kokeile kykyjäsi!
Tietoviisas AI-Ristinolla
Kognitiivinen harjoitus: Testaa lyhytkestoista työmuistiasi algoritmia vastaan. (Olet Risti X)
Miksi ristinolla päättyy aina tasapeliin ammattilaisilla?
Peliteoriassa ristinolla on klassinen esimerkki nollasummapelistä. Tämä tarkoittaa sitä, että toisen pelaajan voitto on matemaattisesti eksaktisti yhtä suuri tappio toiselle pelaajalle. Koska pelissä ei ole noppaa eikä korttipakkaa – eli sattuman osuus on pyöreä nolla – puhutaan täydellisen informaation pelistä. Jokainen pelin tila on molempien pelaajien tiedossa.
Matemaattisesti ristinollassa on $3^9$ eli tasan 19 683 erilaista merkkien sijoitteluyhdistelmää, joista vain pienehkö luku muodostaa loogisesti pelattavan laillisen pelin. Koska tilapuu on tällä tavoin uskomattoman pieni, tietokone pystyy käytännössä parissa millisekunnissa laskemaan pelin jokaisen haaran mahdolliseen lopputulokseen asti.
Algoritmin aivot: mikä on Minimax?
Yllä näkemäsi Tietoviisaan tekoäly (ja myös Googlen oma ”Vaikea”-tason Ristinolla) perustuu todennäköisesti Minimax-nimiseen pelialgoritmiin. Tekoälyn toimintaperiaate on kiehtova mutta raaka:
- Kun on tekoälyn vuoro, se tutkii pelilaudan ja listaa jokaisen mahdollisen tyhjän ruudun, johon se voisi asettaa merkkinsä.
- Algoritmi pelaa omassa simulaatiossaan jokaisen noista tulevaisuuksista loppuun asti (tuhansien skenaarioiden päähän), olettaen, että ihminen tekee omalla vuorollaan itselleen parhaan mahdollisen siirron.
- Jokaiselle mahdolliselle tulevaisuudelle annetaan matemaattinen arvosana: +10 pistettä jos tekoäly voittaa, -10 pistettä jos ihminen voittaa, ja 0 pistettä jos peli päättyy tasapeliin.
- Lopulta: Tekoäly valitsee sen tämän hetken siirron, joka takaa korkeimman mahdollisen minimipisteen, riippumatta siitä, mitä ihminen tekee tulevaisuudessa. Tämä on ”Minimax”-säännön ydin.
Strategisia siirtoja ihmisaivojen hämäämiseksi
Koska tekoälyn voittaminen on lähtökohtaisesti mahdotonta, jos koodissa ei ole ”satunnaisuuden” tuomaa heikkoutta, monien pelaajien todelliseksi vastustajaksi muodostuu toinen ihminen. Ihmisiä vastaan pelatessa puhdas matematiikka jää toiseksi, ja tilalle nousee kognitiivinen psykologia.
- Keskustan hallinta ei ole kaikki kaikessa: Useimmat aloittelijat pyrkivät valtaamaan keskimmäisen ruudun heti ensimmäisenä. Vaikka se avaa geometrisesti eniten voittolinjoja (pysty, vaaka ja kaksi vinoa), se tekee pelistä nopeasti puolustustaistelun ja johtaa lähes väistämättä tasapeliin.
- Kaksinkertainen ansa (The Fork): Peliteoreettisesti optimaalisin strategia ihmistä vastaan on aloittaa kulmaruudusta. Tähtäimenä on asettaa seuraavat kaksi merkkiä reagoimalla siten, että muodostuu niin sanottu ”haarukka”. Tällöin uhkaat voittoa samanaikaisesti kahdella eri linjalla. Vastustaja voi puolustaa vain toista, jolloin otat voiton toisella linjalla.
Viihdearvo ja muistin kapasiteetti
Vaikka ristinolla on koodareille triviaali harjoitus, sen asema ihmisen vapaa-aikana kognitiivisena leikkinä ja stressin purkajana on pysyvä. Lyhytkestoinen pelisilmukka vaatii juuri sopivasti työmuistin allokaatiota huijatakseen aivot irti raskaista analyyttisista asioista, mutta ei liikaa niin, että siitä tulisi itsessään työtaakka.
Jos kaipaat vaativampaa geometrista pähkinää, voit aina kokeilla esimerkiksi Google Miinaharavaa, missä matemaattiset riskit yhdistyvät puhtaaseen tuuriin, luoden monimutkaisemman dopamiinivasteen hermostossa.
