Tekoälyn rakentaminen vuoropohjaiseen nollasummapeliin

Abstract

Opinnäytetyön tarkoituksena oli tutkia eri toteutustapoja vuoropohjaisen nollasummapelin tekoälylle. Tekoäly tehtiin shakkia muistuttavaan strategiapeliin, joka on osa Friendly Fire Oy:n mobiilipeliprojektia. Tekoäly toimii minimax-algoritmilla, johon on lisätty alpha-beta-karsinta. Työssä esitellään tekoälyn käytännöntoteutus ja sen käyttämät erilaiset heuristiikat. Tekoäly on toteutettu C#-koodikielellä Unity-pelimoottorissa.

Opinnäytetyössä perehdyttiin nollasummapeleissä yleisesti käytettyihin puuhakualgoritmeihin ja niiden toimintaan sekä eroihin. Käsiteltävät algoritmit ovat minimax, alpha-beta-karsinta ja Monte Carlo-haku. Alpha-beta-karsinnan havaittiin olevan puhdasta minimaxia parempi vaihtoehto, koska sillä saadaan sama tulos minimaxia nopeammin. Koneoppimisen todettiin olevan ylimitoitettu vaihtoehto kyseiseen projektiin, mistä syystä työssä keskityttiin käsittelemään aihetta klassisen tekoälyn ja puuhaun näkökulmasta.

Minimaxin todettiin olevan hyvä ratkaisu nollasummapelin tekoälylle, koska se on yksinkertainen toteuttaa ja sen suorituskykyä voidaan parantaa yksinkertaisin keinoin, kuten käyttämällä alpha-beta-karsintaa. Monte Carlo-haun havaittiin myös olevan varteenotettava vaihtoehto, etenkin jos peliin halutaan lisätä enemmän ominaisuuksia, koska Monte Carlo-haku skaalautuu minimaxia ja alpha-beta-karsintaa paremmin pelin monimutkaistuessa.

The purpose of this thesis was to research ways to implement artificial intelligence in a turn-based zero-sum game. The AI was made for a strategy game, which has many similarities with chess. The strategy game is part of a mobile game project developed by Friendly Fire Oy. The AI was made using C#-language on Unity Engine and is based on minimax-algorithm and alpha-beta pruning. The implementation and different heuristics used by the AI are also presented in the thesis.

The thesis covers commonly used tree-search algorithms, which are minimax, alpha-beta pruning and Monte Carlo-search. The goal was to find out how they work and what their differences are. Alpha-beta pruning was found to be a better solution than pure minimax, since it finds the same result faster. Machine learning was found to be too excessive for a project of this scope, so the focus was on classical AI and tree-search algorithms.

Minimax was discovered to be a good solution, since it is simple to implement and it can be easily optimized with alpha-beta pruning. Monte Carlo-search could also be considered, if more features will be added to the game in the future, because Monte Carlo-search is more scalable than minimax and alpha-beta pruning.