6533b871fe1ef96bd12d1da8

RESEARCH PRODUCT

An AI for dominion based on Monte-Carlo methods

subject

description

Masteroppgave i Informasjons- og kommunikasjonsteknologi IKT590 Universitetet i Agder 2014 To the best of our knowledge there exists no Arti_cial Intelligence (AI)for Dominion which uses Monte Carlo methods, that is competitive on ahuman level. This thesis presents such an AI, and tests it against someof the top Dominion strategies available. Although in a limited testingenvironment, the results show that our AI is capable of competing withhuman players, while keeping processing time per move at an acceptablelevel for human players. Although the approach for our AI is built onprevious knowledge about Upper Con_dence Bounds (UCB) and UCBapplied to Trees (UCT), an approach for handling the stochastic elementof drawing cards is presented, as well as an approach for handling in-teraction between players. Our best solutions win 87.5% games againstmoderately experienced human players, and outperforms the successful,rule-based, Dominion strategies SingleWitch and DoubleWitch both witha win percentage of 68.5%.Keywords: Dominion, UCT, UCB, AI, Multi-Armed Bandit Problem,Monte-Carlo, Tree Search