- 186 views
- 353 downloads
Improving Determinized Search with Supervised Learning in Trick-Taking Card Games
-
- Author / Creator
- Solinas, Christopher
-
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.
-
- Subjects / Keywords
-
- Graduation date
- Spring 2019
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.