Vertaisarviointi

[TopiasHarjunpaa]

Viikko 5 vertaisarviointi

Ohjelma ladattu to 18.8.2022 noin klo 19.20

Hyvin toimiva ja selkeällä käyttöliittymällä varusteltu peli. Hyvin vaikuttaisi pystyvän vielä kasvattamaan default -laskentasyvyyttä ilman mahdottomia odotusaikoja. Ainakin seiskalla palauttaa vastauksen todella nopeasti ja kasillakin malttaa hetken odottamaan. Myös dokumentaatio on mielestäni esimerkillinen.

Ohjelman toiminta

Ohjelma vaikuttaa toimivan kuten pitääkin ja itse en ainakaan onnistunut löytämään selkeitä virheitä toteutuksen suhteen. Koodi on helposti luettavissa ja luulen saaneeni kohtuullisen käsityksen siitä, kuinka ohjelma toimii. Itse toimintalogiikan suhteen lähystymistapa on hieman erilainen kuin itselläni ja itseasiassa luulin jo löytäneeni toiminnallisuudesta virheen josta kirjoitin pitkästi, kunnes huomasin olleeni väärässä.

Pohjustan alkuun hieman kuinka tulkitsin ohjelman ja etenkin Minimax algoritmisi toimintaa. Tekoälyn siirtovuorolla algoritmi alustetaan MIN pelaajaksi, eli se pyrkii omalla vuorollaan saavuttamaan mahdollisimman pienen arvon. Tästä syystä myös tekoäly saa heuristiikan avulla (omasta näkökulmastaan) hyvillä siirroilla enemmän negatiivisia pisteitä. Vastaavasti voiton tarkistuksessa tekoäly saa voitosta negatiivisia pisteitä ja vastustaja (ihminen) positiivisia pisteitä. Päädyin itse toteuttamaan Minimaxin päinvastaisesti, eli tekoäly on maksimoiva ja vastustaja on minimoiva. Tässä ei nähdäkseni ole mitään eroa, kunhan pisteytyskin toteutetaan päinvastaisesti. Tästä syystä erehdyin luulemaan, että vastustajan voiton blokkaaminen ei toimi odotetulla tavalla.

Testasin asettamalla laskentasyvyyden arvoksi 1 ja simuloin alla olevan mukaisen pelin. Tässä minulla oli keskirivillä kolmen suora ja Minimax valitsi blokkaamisen sijasta sarakkeen 5 pisteytyksellä -28. Pitkän koodin tutkimisen jälkeen tulin kuitenkin siihen johtopäätökseen, että vika ei ole voitontarkistuksessa vaan heuristiikka ohjaa valintaa sarakkeella 5, koska sieltä taitaa saada 12 lisäpistettä blokkaamiseen verrattuna. Jo pykälää suuremmalla laskentasyvyydellähän blokkaaminen toimii kuten halutaankin.

Minimax valitsi sarakkeen 5 pisteytyksellä -28
Pelipuun solmuja käsitelty: 8 kpl
Minimax-algoritmin suoritusaika: 0.0045032501220703125 sekuntia

[[1 2 3 4 5 6 7]] 

[[0 0 0 0 0 0 0]
 [0 0 0 1 0 0 0]
 [0 0 0 1 0 0 0]
 [0 0 0 1 2 0 0]
 [0 0 0 2 2 0 0]
 [0 0 0 1 2 0 0]]

Ehkä juurikin tähän negatiiviseen pisteytykseen liittyen voisi yhtenä epäoleellisena huomiona mainita, että nykyinen pisteytysfunktio evaluate_board voisi palauttaa suoraan pisteytyksen käänteisluvun, koska ainoastaan tekoälyhän käyttää kyseistä funktio, ei sen vastustaja.

Toisena huomiona (kuten taisit dokumentaatiossakin mainita) sovelluslogiikkaa voisi hieman uudelleen järjestellä. Lähinnä mietin, että pelilaudan voiton tarkastukset sekä tekoälyn pisteytysfunktion tarkistukset voisi hoitaa käyttämällä yhteisiä apufunktioita. Nythän tekoälyn puolella tarkastetaan 2 ja 3 suorat, kun taas voittotarkastelussa täytyy tarkastaa 4 suorat. Ehkä tämän kaltaisille operaatioille voisi tehdä oman luokan, jolloin GameBoard -luokan vastuulle jäisi pelitilanteen ylläpitäminen, AI -luokalle seuraavan siirron laskeminen ja omalle luokalle pisteytys / pelitilanteen arvottaminen.

Kolmantena huomiona testeihin voisi lisätä ainakin voiton blokkaavia siirtoja. Luulisi helpottavan siinä vaiheessa, kun testataan uusien optimointien toimivuutta.

Kehitysehdotuksia

Olet varmaan tässä vaiheessa jo aika hyvin perillä siitä, millä tavalla tekoälyalgoritmin toimintaa voisi optimoida, mutta listaan alle muutamia huomioita omasta kokemuksesta:

1. Yksi helppo nopeasti tehtävissä oleva toteutus hakupuun karsimiseen voisi olla tarkastella onko vastustajan mahdollista voittaa seuraavalla omalla kierroksella. Ja jos on, niin tutkia ainoastaan voittosiirron blokkaava sarake ja jättää muut sarakkeet tarkastamatta. Nämähän vääjäämättä päättyvät tappioon ellei itse satu voittamaan omalla vuorollaan. Tämä toki lisää laskenta-aikaa, mutta ainakin itse pääsin yhden pykälän syvemmälle vastaavassa ajassa.
2. Isoimman parannuksen sain aikaan korvaamalla matriisityylisen pelilaudan bittitaululla ja tekemällä tarkistukset binäärioperaatioiden avulla. Se tosin oli ainakin itselleni melkoisen työläs ja toki edellyttää isoa remonttia kaikille tarkastusfunktioille. Välimallin ratkaisu voisi olla tehdä ainoastaan voiton tarkastukset binäärioperaatioilla (koska nämähän tehdään jokaisessa funktiokutsussa). Tästä ei ehkä saa ihan niin paljon hyötyä, koska matriisi pitäisi kuitenkin aina muuttaa bittitauluksi ennen operaation suorittamista.
3. Iteratiivinen syveneminen on melko nopea toteuttaa. Sen avulla ei tosin taida pelkästään saada laskentasyvyyttä kasvatettua (pl. loppupelissä, jossa hakupuu väistämättä kapenee sarakkeiden täyttyessä). Sen avulla tosin pystyy tekemään muita optimointeja, kuten esimerkiksi sarakkeiden tarkistusjärjestyksen muuttaminen aiemman iteraation tuloksen perusteella.

Loppukommentit

Oikein mainio toteutus! Olisin toivonut pystyväni antamaan hieman hyödyllisempää palautetta, mutta homma ohjelma vaikuttaa olevan sen verran hyvällä mallilla, että joutui kaivelemaan enemmänkin toissijaisia huomioita. Tsemppiä projektin loppuun viemisessä ja hyvää loppukesää!

-Topias

[rheikkinen]

Kiitos palautteesta, kyllä tästä hyötyä oli. Oikeastaan vasta tällä viikolla olen näitä tehostusvaihtoehtoja algoritmille alkanut tutkailla enemmän, joten tässä oli hyviä kehitysideoita ja muutenkin hyviä ajatuksia. Bittitaulut tuli tosin itse heivattua hyvinkin alkuvaiheessa juuri siksi, että vaikuttivat liian työläältä, ja on tässä kyllä työtä hyvin riittänyt ilman niitäkin. :smile:

Hyvää loppukurssia ja loppukesää sinnekin!