Improving Determinized Search with Supervised Learning in Trick-Taking Card Games

Abstract

Current state-of-the-art algorithms for trick-taking card games use a process called determinization. Determinization is a technique that allows the application of perfect information state evaluation algorithms to imperfect information games. It involves a two-step process in which a perfect information variant of the game state is sampled from the player’s information set and then solved using an algorithm like minimax search. The majority of recent work related to determinization has focused on addressing some of the theoretical flaws tied to using perfect information techniques to play imperfect information games. However, these works have largely neglected another important part of the equation: inference. Inference involves estimating the state probability distribution of an information set using state information like past opponent actions. It lets players of trick-taking card games predict which cards opponents are holding based on the cards that have been played so far. Inference is crucial for the performance of algorithms that use determinization because it allows states to be sampled according to a better estimate of the true state probability distribution in the information set. This results in improved estimates for action values. In this thesis, I investigate inference in trick-taking card games. In particular, I present a technique that uses past actions to predict hidden state information like the locations of individual cards. I show that deep learning can be useful for handling the larger input feature spaces associated with a richer state representation, and lastly, I explain how to combine these predictions to estimate the probability distribution of states within an information set and improve determinized search techniques — leading to a new state-of-the-art in computer Skat.