«
Jonathan Sarasua
Software Development
Dominion AI Using Monte Carlo Tree Search
My thesis involved building an Artificial Intelligence ( AI ) to play the deckbuilding card game , Dominion . I chose this project because I have a love of board games , but I had not had a chance to build one in the SMU Guildhall curriculum . I chose Monte Carlo Tree Search ( MCTS ) because it is a general AI strategy that can be used on many types of games and can be combined with other AI strategies to improve them . MCTS tries to intelligently build a tree of all possible moves that can be used to decide what move to make . It generalizes the building process for most kinds of games by using an evaluation function that is playing a game of random moves . Whichever move looks the best to the evaluation function is where MCTS will try to build next .
The project took roughly eight months to complete . I first learned how to use MCTS for a game like Dominion . Pure MCTS was made for games like chess , in which all information is known , but a card game has plenty of hidden information like what cards
your opponent has or what card you will draw next in your deck . I learned quickly that pure MCTS was awful at playing Dominion , so my thesis became how to tweak MCTS so it can play Dominion without being too heavy handed . I learned how MCTS thinks — it looks at a game as a black box with multiple levers . Any lever that is pulled will change the black box , but it does not know the result until the game is finished . I also learned how important making a good user interface is for a game like Dominion . Nobody knew how to use my artifact except for me until I made it more visual and clickable with a mouse . MCTS is an awesome tool that could be applied in many areas . In turn-based games , you can use it as the opposing AI . You could also use it to playtest your game . If you are making a card game and want to see how adding a card will change strategies , MCTS is a great way of quickly testing the effects of the new card . It could also be used to search strategies of what an army should do in a Real-Time Strategy game .
100 SOFTWARE DEVELOPMENT