Modeling Expert Knowledge in a Heuristic-Based Gin Rummy Agent

Sarah Larkin, William Collicott, Jason HiebelAAAI 2021 · DOI

Introduction

Gin Rummy is a sequential, imperfect information game characterized by a hidden deck and unknown opponent hand. While games like Poker have been successfully addressed using Counterfactual Regret Minimization (CFR), Gin Rummy's vast game tree makes such approaches computationally prohibitive for real-time play on standard hardware. Researchers at Michigan Technological University developed Tonic, an agent that translates fuzzy expert intuition into precise, parameterized heuristics to bridge this gap.

Decision-Making Architecture

Tonic's logic is divided into three core modules: drawing/discarding filters, dynamic knocking, and opponent hand estimation. Unlike simpler greedy agents, Tonic employs a hierarchical filtering process for discards. It prioritizes keeping "narrow pairs" (cards with multiple paths to forming a meld) and avoids discarding cards that its internal estimator suggests the opponent might need.

Figure 1: The discard filtering process, highlighting the logic shift based on hand depth.

A key insight modeled by the researchers is the "Two-Turn Rule." Through grid search optimization, they discovered that holding high-value pairs (such as Kings) is statistically beneficial only during the first two turns. Beyond this point, the risk of being caught with high "deadwood" points outweighs the probability of completing the meld, as illustrated in the decision flow in Figure 1.

Opponent Modeling and Dynamic Knocking

To estimate the opponent's hand, Tonic uses a logistic function to track the likelihood of every card in the deck. This likelihood is updated dynamically: drawing a face-up card sets its likelihood to 1.0 and increases the likelihood of related cards, while passing on a card decreases the likelihood of surrounding cards.

Furthermore, Tonic implements a variable knocking threshold. In Gin Rummy, "knocking" ends the hand if a player's deadwood is below a certain limit (typically 10). However, knocking late in the game with 10 points often leads to being "undercut" by an opponent who has had time to refine their hand. Tonic mitigates this by automatically lowering its threshold to 6 or 4 points as the hand depth increases.

Key Results

Tonic was evaluated against the SimpleAI baseline from the EAAI-2021 Undergraduate Research Challenge. In large-scale simulations of 100,000 games, Tonic achieved a win rate of 68% against the baseline.

Figure 4: Comparison of win rates across different knocking strategies, demonstrating the superiority of the variable threshold.

As shown in Figure 4, the variable threshold strategy performs comparably to a highly aggressive fixed threshold (4 points), but with the added benefit of being undercut much less frequently. The researchers also demonstrated that the "Two-Turn Rule" is a mathematical "sweet spot"; extending the pair-holding threshold beyond two turns resulted in a performance drop of over 10%.

Conclusion

Tonic demonstrates that expert intuition can be quantified into a high-performing heuristic agent without the need for massive computational resources. Future work will focus on refining fallback logic for discards and exploring hybrid models that use these heuristics to prune game trees for more efficient CFR integration.

Summary updated

BibTeX
@inproceedings{larkin2021modeling,
  author = {Sarah Larkin and William Collicott and Jason Hiebel},
  title = {{Modeling Expert Knowledge in a Heuristic-Based Gin Rummy Agent}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i17.17834},
}
Figure