Heisenbot: A Rule-Based Game Agent for Gin Rummy

Matthew Eicholtz, Savanna Moss, Matthew Traino, Christian RobersonAAAI 2021 · DOI

Abstract

Heisenbot is a rule-based artificial intelligence agent designed to tackle the complexities of Gin Rummy, a game defined by imperfect information and chance. By decomposing gameplay into modular policies for drawing, discarding, and knocking—and utilizing a "prognostication" model to estimate the opponent's hand—Heisenbot achieves a nearly 69% average win rate against standard baseline strategies.

Introduction

While AI has famously conquered "perfect information" games like Chess and Go, "imperfect information" games—where players have hidden state—remain a significant challenge. Gin Rummy is a prime example: players must decide which cards to keep or discard without knowing what their opponent holds. Despite its popularity, Gin Rummy has seen relatively little academic AI research compared to Poker. This work develops a competitive agent using empirically driven, rule-based strategies, providing a robust baseline for future research.

Methods

Heisenbot treats Gin Rummy as a series of three independent decision-making policies:

Draw Policy (Future Value)

Instead of just taking a card that completes a "meld" (a set or run), Heisenbot evaluates "Future Value." It prioritizes drawing discards that form a triangle (e.g., two cards of the same rank plus one adjacent card) or low-value cards (Ace or 2) that reduce "deadwood" (unmelded card points).

Discard Policy (Prognostication & Safety)

Heisenbot uses a Prognostication Model—a likelihood score for every card in the deck—to estimate the probability that an opponent holds a specific card based on their previous actions. It also calculates a Safety Count, representing how many potential melds a discarded card could complete for the opponent. Heisenbot prioritizes discarding cards with the lowest safety count.

Knock Policy (Rule-Based)

Rather than knocking as soon as the legal threshold of 10 deadwood points is reached, Heisenbot uses a handcrafted decision tree. It considers the current score, the number of turns elapsed, and the specific number of deadwood cards to avoid risky "undercuts."

Experimental Setup

The authors generated data through massive self-play simulations, running 10,000 to 20,000 games per matchup to statistically determine optimal policy combinations and tune parameters.

Results and Discussion

Heisenbot was tested against four other agents: "Simple," "Greedy," "Always Draw," and "Rule-Based Knocking."

Win rate matrix of Heisenbot versus baseline agents.

Performance Metrics

Heisenbot achieved an average win rate of 68.8% across all matchups. Notably, it won 60.5% of games against the standard "Simple" AI. Beyond win rates, Heisenbot demonstrated superior efficiency in "going Gin" (melding all 10 cards), a result of its "Future Value" draw policy and triangle-prioritization.

Comparison of Gin and Undercut occurrences across different agents.

Strategic Insights

  • The "Triangle" Strategy: Prioritizing triangles offers multiple paths to a meld, making the hand more flexible.
  • The Danger of the Mid-Game: Simulations revealed that knocking immediately is strong in the early or late game, but risky in the "middle game" where opponents have often pruned their hands enough to score an undercut.
  • Modeling the Unknown: The prognostication model demonstrates that simple arithmetic tracking of discards can significantly improve defensive play.

Conclusion

Heisenbot provides a high-performing rule-based baseline for Gin Rummy. While its handcrafted strategies are effective, future work could involve Deep Reinforcement Learning (DRL) to discover even more nuanced strategies, particularly in complex areas like "baiting" discards.

Summary updated

BibTeX
@inproceedings{eicholtz2021heisenbot,
  author = {Matthew Eicholtz and Savanna Moss and Matthew Traino and Christian Roberson},
  title = {{Heisenbot: A Rule-Based Game Agent for Gin Rummy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i17.17823},
}
Figure