Improving Search with Supervised Learning in Trick-Based Card Games

Christopher Solinas, Douglas Rebstock, Michael Buro

TL;DR

This paper introduces a novel approach to improve AI performance in trick-taking card games by using deep neural networks to predict individual card locations, leading to more realistic state sampling during search. This method significantly boosts the playing strength of a PIMC-based Skat AI, outperforming existing state-of-the-art methods.

What Problem Does This Paper Address?

Artificial intelligence in games often relies on evaluating possible future states to make optimal decisions. In imperfect information games like trick-taking card games (e.g., Skat, Bridge), players don't know all the cards held by their opponents. This uncertainty makes decision-making challenging. Traditional AI approaches for these games often use a two-step process: sampling possible future states and then evaluating those states. While state evaluation has seen much progress, the accuracy of the sampled states (inference) has been a bottleneck. Poor sampling can lead to catastrophic errors, even with a perfect evaluator. This paper addresses the gap in improving the sampling of realistic states by leveraging supervised learning to infer hidden information.

Methods

The core innovation is a supervised learning approach using a deep neural network to predict the locations of individual cards. Instead of directly predicting the entire game state (which is too complex), the network learns to estimate the probability of each card being in a specific player's hand or in the "skat" (a common pool of cards in Skat). This prediction is based on the game's move history.

The paper then integrates these predictions into a Perfect Information Monte Carlo (PIMC) search algorithm. PIMC typically samples states uniformly from the information set. The proposed method, termed BDCI (Bidding-Declaration-Cardplay Inference), uses the neural network's card location probabilities to create a biased sampling distribution. This distribution favors states that are more likely given the observed move history, making the sampled states more realistic. The network is trained on human gameplay data.

Datasets

The neural networks were trained on data from 20 million games played by humans on a popular Skat server (DOSKV). The evaluation was performed using holdout sets of games previously played by humans.

Key Insights and Ideas

  • Sampling is as Crucial as Evaluation: The paper strongly emphasizes that the quality of state sampling (inference) is as vital as state evaluation for strong play in imperfect information games.
  • Individual Card Inference is Powerful: Predicting the location of individual cards, rather than the entire game state, is a tractable and effective way to infer hidden information.
  • Move History is Key: Incorporating the sequence of moves (cardplay history) into the inference process significantly improves the accuracy of state sampling compared to methods that only consider bidding and declarations.
  • Human Data is Valuable: Training on a large dataset of human gameplay provides the neural network with the nuanced understanding of card play needed for effective inference.
  • Defender Advantage in Inference: The paper observes that inference is generally easier for defenders than for the soloist, as the soloist has more initial information (e.g., knowing the skat).

Key Results

  • Improved Inference Performance: The BDCI method achieved a significantly higher True State Sampling Ratio (TSSR) compared to baseline methods (NI - No Inference, BDI - Bidding-Declaration Inference, KI - Kermit's Inference). TSSR measures how much more likely the true state is to be sampled compared to uniform random sampling. BDCI consistently outperformed other methods, especially in the mid-game.
  • Substantial Cardplay Strength Increase: In Skat tournaments, the BDCI-enhanced PIMC player achieved a statistically significant increase in tournament points per game, outperforming the state-of-the-art KI player by over 4 points per game in suit and null games.
  • Efficiency Trade-off: While BDCI is more effective, it is slower than KI, taking approximately 3.1 times longer per move (0.286 seconds vs. 0.093 seconds) when evaluating 320 states per move. However, it remains feasible for human-level play.

Limitations and Future Work

  • Generalizability: While the paper demonstrates success in Skat, the authors suggest that the core technique of individual card inference with neural networks can be adapted to other trick-taking card games by adjusting the network's input features and output size.
  • Opponent Modeling: The current inference is general and does not adapt to individual opponents. Future work could involve improving inference to adjust to specific opponent tendencies or to smooth state probabilities to account for opponents who make mistakes or play deceptive moves.
  • Recursive Search: The authors propose incorporating their inference technique into more advanced search algorithms like recursive PIMC (IIMC) and Information Set Monte Carlo Tree Search (ISMCTS) to further enhance playing strength.
  • Computational Cost: While BDCI is faster than a brute-force approach, its computational cost is still a factor, especially in early game stages with large information sets. Further optimization or parallelization could be beneficial.

Summary updated

Abstract

In trick-taking card games, a two-step process of state sampling and evaluation is widely used to approximate move values. While the evaluation component is vital, the accuracy of move value estimates is also fundamentally linked to how well the sampling distribution corresponds the true distribution. Despite this, recent work in trick-taking card game AI has mainly focused on improving evaluation algorithms with limited work on improving sampling. In this paper, we focus on the effect of sampling on the strength of a player and propose a novel method of sampling more realistic states given move history. In particular, we use predictions about locations of individual cards made by a deep neural network --- trained on data from human gameplay - in order to sample likely worlds for evaluation. This technique, used in conjunction with Perfect Information Monte Carlo (PIMC) search, provides a substantial increase in cardplay strength in the popular trick-taking card game of Skat.
BibTeX
@inproceedings{solinas2019improving,
  author = {Christopher Solinas and Douglas Rebstock and Michael Buro},
  title = {{Improving Search with Supervised Learning in Trick-Based Card Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=vesAYILOeH},
}
Figure