Kilpailut: Valtapeli: tulokset

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.

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.

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.

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.

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.

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 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.