Determinization with Monte Carlo Tree Search for the card game Hearts

Abstract

Monte Carlo Tree Search (MCTS) is a popular algorithm used in AI for games. It is most famous for its implementation in the game Go. Determinization is a technique used to extend an algorithm for a game of perfect information to a game of imperfect information. It does this by determinizing the lacking information and calculating the average best move over all the instances with the perfect information algorithm. This paper provides an implementation of MCTS for the card game Hearts and it uses determinization to extend MCTS to games of imperfect information. We analysed the influence of better sampling in the determinization process on the performance of the player. We found that an improvement in the quality of the samples improves the performance of the player. We also show that inference methods could further increase the performance.