Shakkitietokoneiden keskeiset algoritmit ja niiden optimointi

Abstract

Tässä kandidaatintutkielmassa tarkastellaan shakkitietokoneiden keskeisiä algoritmeja, niiden suorituskykyä parantavia optimointimenetelmiä sekä moderneja koneoppimiseen perustuvia lähestymistapoja. Tutkielman tutkimuskysymykset ovat: mitkä ovat shakkitietokoneiden keskeiset algoritmit, millaisia optimointitekniikoita niiden tehostamiseen on esitetty kirjallisuudessa sekä miten modernit koneoppimiseen perustuvat menetelmät vaikuttavat shakkitietokoneiden kehitykseen.

Tutkielma toteutettiin kirjallisuuskatsauksena hyödyntämällä vertaisarvioituja tieteellisiä artikkeleita ja konferenssijulkaisuja. Tarkastelun kohteena olivat erityisesti pelipuun hakualgoritmit, evaluointifunktiot sekä modernit neuroverkkoihin perustuvat menetelmät.

Työssä havaittiin, että shakkitietokoneiden toiminta perustuu ennen kaikkea pelipuun tehokkaaseen tutkimiseen. Keskeisiä algoritmeja ovat minimax-algoritmi ja sitä tehostava alfa-beeta-karsinta. Lisäksi iteratiivinen syvennys ja transpositiotaulut ovat merkittäviä optimointimenetelmiä, joiden avulla hakuprosessia voidaan nopeuttaa ja laskennallista kuormaa vähentää. Evaluointifunktioiden avulla shakkitietokone pystyy vertailemaan peliasemia tilanteissa, joissa koko pelipuuta ei voida käydä läpi.

Kirjallisuuden perusteella modernit koneoppimiseen perustuvat menetelmät ovat muuttaneet merkittävästi shakkitietokoneiden kehitystä. Neuroverkkoihin perustuvat evaluointifunktiot ja Monte Carlo -puuhaku mahdollistavat aiempaa tarkemman aseman arvioinnin ja tehokkaamman hakuprosessin. Erityisesti itseoppivat järjestelmät, kuten AlphaZero, ovat osoittaneet, että korkea pelitaso voidaan saavuttaa ilman perinteisiä käsin suunniteltuja evaluointifunktioita.

Tutkielman perusteella voidaan todeta, että nykyiset shakkimoottorit perustuvat yhä useammin hybridimalleihin, joissa yhdistyvät perinteisten hakualgoritmien tehokkuus ja koneoppimiseen perustuvien menetelmien tarkempi asemanarviointi. Shakkitietokoneiden kehitys näyttääkin painottuvan tulevaisuudessa yhä enemmän oppivien menetelmien ja perinteisten algoritmien yhdistämiseen.