The Monte Carlo tree search-algorithm (MCTS) has been proven successful when applied to combinatorial games, a term applied to sequential games with perfect information. As the focus for MCTS has tended to lean towards combinatorial games, general MCTS-strategies for other types of board games are hard to find. On another front, board games under the name of “Eurogames” have become increasingly popular in the last decade. These games introduce yet another set of challenges for game-playing agents on top of what combinatorial games already offer. Since its initial conception, a large number of enhancements to the MCTS-algorithm has been proposed. Seeing that eurogames share much of the same game-mechanics with each other, MCTS-enhancements proving effective for one game could potentially be aimed towards eurogames in general. In this paper, alterations to the expansion phase, the playout phase and the backpropagation phase are made to the standard MCTS-algorithm for agents playing the game of Carcassonne. To detect how enhancements are affected by chance events, both a deterministic and a stochastic version of the game is examined. It can be concluded that a reward policy relying solely on in-game score outperforms the conventional wins-against-losses policy. Concerning playouts, the Early Playout Termination enhancement only yields better results when the number of MCTS-iterations are somewhat restricted. Lastly, delayed node expansion is shown to be preferable over that of conventional node expansion. None of the enhancements showed any increasing or declining performance with regard to chance events. Additional experiments on other eurogames are needed to reaffirm any findings. Moreover, subsequent studies which introduce modifications to the examined enhancements is proposed as a measure to further increase agent performance. / Monte Carlo tree search-algoritmen (MCTS) har visat sig framgångsrik när den tillämpats på "combinatorial games", en term som används för sekventiella spel med perfekt information. Eftersom fokusområdet för MCTS har tenderat att luta mot "combinatorial games", är det svårt att hitta allmänna MCTS-strategier för andra typer av brädspel. På en annan front har brädspel under namnet "Eurogames" blivit allt populärare under det senaste decenniet. Dessa spel introducerar ännu en uppsättning utmaningar för agenter utöver vad "combinatorial games" redan erbjuder. Sedan dess begynnande så har ett stort antal förbättringar av MCTS-algoritmen föreslagits. Med tanke på att eurogames delar mycket av samma spelmekanik med varandra kan MCTS-förbättringar som visar sig vara effektiva för ett spel potentiellt riktas mot eurogames i allmänhet. I denna studie görs förändringar av expansionsfasen, playout-fasen och backpropagation-fasen i standard MCTS-algoritmen för agenter som spelar spelet Carcassonne. För att upptäcka hur förbättringar påverkas av slumpmässiga händelser undersöks både en deterministisk och en stokastisk version av spelet. Man kan dra slutsatsen att en belöningspolicy som enbart förlitar sig på poäng i spelet överträffar konventionell vinst-mot-förlust-policy. När det gäller "playouts" så bidrar Early Playout Termination-tillägget endast med bättre resultat när antalet MCTS-iterationer är något begränsat. Slutligen kan det visas att fördröjd expansion av noder att föredra framför konventionell expansion. Ingen av förbättringarna visade någon ökande eller minskande prestanda med avseende på slumpmässiga händelser. Ytterligare experiment på andra eurogames behövs för att bekräfta eventuella fynd. Dessutom föreslås efterföljande studier som introducerar modifieringar av de undersökta förbättringarna som ett mått för att ytterligare öka agentens prestanda.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:miun-41251 |
| Date | January 2020 |
| Creators | Bergh, Peter |
| Publisher | Mittuniversitetet, Institutionen för data- och systemvetenskap |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds