Artificial intelligence in the game of Quoridor

Abstract

I de siste ti˚arene har brettspill f˚att mye oppmerksomhet innenfor datavitenskapen og kunstig intelligens. Denne masteroppgaven setter søkelys p˚a kunstig intelligens i Quoridor som er et nullsum-spill for to spillere. Quoridor er et forholdsvis ukjent brettspill og det er for tiden ingen eksisterende kunstig intelligenssystemer som har blitt testet mot menneskelige spillere.

Først viser vi feil gjort i tidligere analyser av kompleksiteten til Quoridor and gir en ny øvre grense. Deretter foresl˚ar vi nye metoder for ˚a optimalisere genereringen av legale trekk and kjører eksperimenter som viser en signifikant forbedring i tiden det tar ˚a genererer lovlige trekk. Til slutt implementerer vi en minimax-basert agent med alpha-beta pruning. Vi eksperimenterer b˚ade med generelle minimax forbedringer og spillspesifike heurustikker. Agenten spilte 30 partier mot menneskelige spillere p˚a Board Game arena og vant 77 % av partiene og oppn˚adde en Elo-rating p˚a 248, noe som indikerer god spillestyrke mot menneskelige spillere.