Artificial intelligence in the game of Quoridor
Master thesis
Permanent lenke
http://hdl.handle.net/11250/2634469Utgivelsesdato
2019Metadata
Vis full innførselSamlinger
Sammendrag
I de siste ti˚arene har brettspill f˚att mye oppmerksomhet innenfor datavitenskapenog kunstig intelligens. Denne masteroppgaven setter søkelys p˚a kunstig intelligensi Quoridor som er et nullsum-spill for to spillere. Quoridor er et forholdsvis ukjentbrettspill og det er for tiden ingen eksisterende kunstig intelligenssystemer somhar blitt testet mot menneskelige spillere.
Først viser vi feil gjort i tidligere analyser av kompleksiteten til Quoridorand gir en ny øvre grense. Deretter foresl˚ar vi nye metoder for ˚a optimaliseregenereringen av legale trekk and kjører eksperimenter som viser en signifikantforbedring i tiden det tar ˚a genererer lovlige trekk. Til slutt implementerer vien minimax-basert agent med alpha-beta pruning. Vi eksperimenterer b˚ade medgenerelle minimax forbedringer og spillspesifike heurustikker. Agenten spilte 30partier 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 motmenneskelige spillere.