Algoritmit shakkitietokoneissa

Abstract

Shakkitietokone on laitteisto tai ohjelmisto, joka kykenee pelaamaan shakkia itsenäisesti. Shakkitietokoneita voi käyttää esimerkiksi pelien analysoimiseen ja harjoitteluun, ja niistä saatavat hyödyt ovat merkittäviä shakin pelaajille. Olennainen osa niiden toimintaa ovat erilaiset algoritmit, joiden avulla shakkitietokone pyrkii löytämään optimaalisen siirron kussakin pelitilanteessa. Tämän työn tavoite on tutkia, millaisia erilaisia algoritmeja shakkitietokoneissa käytetään ja miten niitä käytetään tunnetuissa shakkitietokoneissa. Tarkasteltaviksi shakkitietokoneiksi on valittu Deep Blue, Stockfish, AlphaZero ja Leela Chess Zero.

Tutkielma on toteutettu kirjallisuuskatsauksena, jossa esitellään ensin shakki ja shakkitietokoneet yleisesti. Tämän jälkeen esitellään minimax-algoritmi ja Monte Carlo -puuhaku muunnelmineen ja tutustutaan tarkasteltavaksi valittujen shakkitietokoneiden toimintaan.

Tutkielmassa havaittiin, että shakkitietokoneiden huipulla paikkansa vakiinnuttaneet algoritmit ovat minimax-algoritmin ja Monte Carlo -puuhaun muunnelmat, jotka eroavat toiminnaltaan huomattavasti toisistaan. Moderneissa shakkitietokoneissa algoritmeja käytetään yhdessä neuroverkkojen kanssa, jotka auttavat niitä parhaan siirron löytämisessä. Alfa-beta-karsinnalla tehostettu minimax on ollut vuosikymmeniä käytössä shakkitietokoneissa ja se on edelleen suosittu menetelmä, jota käytetään esimerkiksi huipputason Stockfish-shakkitietokoneessa. Muunneltu Monte Carlo -puuhaku on puolestaan uudempi menetelmä, joka nousi todelliseksi haastajaksi AlphaZero-shakkitietokoneen saavutuksien myötä. Algoritmia käytetään nykyisin esimerkiksi huipputason Leela Chess Zero -shakkitietokoneessa.