A Highly-Parameterized Ensemble to Play Gin Rummy

Masayuki Nagai, Kavya Shrivastava, Kien Ta, Steven Bogaerts, Chad ByersAAAI 2021 · DOI

Abstract

Gin Rummy is a classic imperfect information card game that presents significant challenges for automated agents due to its hidden states and conflicting strategic goals. This paper details the development of a sophisticated Gin Rummy player using a modular, highly-parameterized ensemble approach. By decomposing decision-making into specialized "deciders" for drawing, discarding, and knocking, and optimizing these components through genetic algorithms and grid searches, we developed an agent that achieves a ~74% win rate against a standard baseline. Our results highlight the importance of adjacency-based state tracking and a dynamic two-stage knocking strategy.

Introduction

Unlike games of perfect information like Chess, Gin Rummy requires players to manage uncertainty regarding the opponent's hand and the remaining stock pile. Success in Gin Rummy involves balancing meld building, deadwood management, and risk assessment. While Nash equilibrium strategies have revolutionized AI in games like Poker, Gin Rummy remains relatively under-explored. This research bridges the gap by employing a structured, heuristic-based ensemble approach to create a high-level automated player.

Methods

The agent's architecture is divided into three primary decision modules and a state-tracking engine.

State Tracking and Adjacency Updates

The system estimates the probability $p(c)$ of unknown cards being in the stock pile versus the opponent's hand. A key innovation is the use of "adjacency updates": if an opponent draws a specific card, the AI increases the estimated probability that the opponent holds numerically adjacent cards or cards of the same rank. These parameters were optimized using a Genetic Algorithm (GA).

Fitness values over turns for different adjacency update configurations.

Decision Modules

  1. Draw Decider: Employs a two-stage logic, prioritizing meld completion early in the game and deadwood reduction in later stages.
  2. Discard Decider (Ensemble): The core of the agent, utilizing a weighted sum of six policies: Meldability, Deadwood Reduction, Turn-based Deadwood Penalization, Knowledge-based Deadwood Penalization, Aces/Twos Bonus, and Adjacency Seeking.
  3. Knock Decider: Uses a two-stage threshold to determine when to end the round.

Optimization

The agent's nine state-tracking parameters were tuned via GA, while ensemble weights and knocking thresholds were optimized through exhaustive grid searches. Training involved millions of simulated rounds to ensure robust parameter selection.

Results and Discussion

The fully tuned agent achieved a win rate of 0.739 against a "Simple Player" baseline.

The "Two-Stage" Knocking Strategy

Grid search analysis revealed that the most effective knocking strategy involves aggressive early knocking (up to 10 deadwood points) in the first five turns, followed by a shift to "Gin-only" (0 points) for the remainder of the round. This approach outperformed a pure Gin-only strategy by a margin of 57% to 43%.

Grid search results for knocking threshold parameters, showing the performance of various threshold combinations.

Key Insights

  • Deadwood Management: Policies related to deadwood reduction accounted for 60% of the total decision weight in the ensemble, confirming that minimizing point loss is the primary driver of success.
  • Meld Preferences: Optimal parameters favored "run" melds over "rank" melds, as runs offer more flexible combination potential.
  • Adjacency Effectiveness: As shown in Figure 1, incorporating adjacency updates significantly improves fitness values as the game progresses compared to baseline updates alone.

Conclusion

This research demonstrates that a modular, heuristic-based ensemble can achieve high-level performance in Gin Rummy. The success of adjacency-based state tracking and dynamic knocking thresholds provides a blueprint for future work, which may include deep reinforcement learning to discover non-obvious features or more advanced opponent modeling to predict specific hand compositions.

Summary updated

BibTeX
@inproceedings{nagai2021highly,
  author = {Masayuki Nagai and Kavya Shrivastava and Kien Ta and Steven Bogaerts and Chad Byers},
  title = {{A Highly-Parameterized Ensemble to Play Gin Rummy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i17.17839},
}
Figure