A Monte-Carlo Hearts Engine

Abstract

The card game Hearts is a stochastic, sequential, non-zero sum, 4-player, partial information game. Such qualities of the game prevent standard game algorithms from finding optimal play in reasonable time. The Monte-Carlo tree search partially addresses this issue by offering an approximation of the payoff resulting from optimal play, so that every potential move in the game does not have to be searched for an action’s value to be evaluated. However, a standard Monte-Carlo tree search does not address imperfect information, stochastic, or N-Player games. My approach aims to close this gap by integrating other algorithms such as maxn [2] and Monte-Carlo sampling [3] to address these aspects of the game that Monte-Carlo tree search does not. The combination of these techniques results in a Hearts engine that is able to beat many base-level algorithms, existing Hearts engines, and advanced human Hearts players.