Introduction
Gin Rummy is a classic imperfect-information game where players must make strategic decisions based on hidden variables—specifically, the ten cards held by their opponent. Unlike games with perfect information like Chess, optimal play in Gin Rummy requires "opponent modeling": the ability to infer hidden cards based on observable actions, such as discards and pickups from the face-up pile.
This research introduces an AI agent that replaces traditional complex game-tree searches or rigid heuristics with a statistical model for Opponent Hand Estimation (OHE). By training a multi-output Random Forest on millions of game states, the researchers developed an agent capable of achieving a 61% win rate against a standard heuristic baseline, demonstrating that non-parametric machine learning can effectively substitute for explicit logical reasoning in high-uncertainty environments.
Methodology
Input Encoding and Model Architecture
The authors employed a Multi-Output Random Forest to perform OHE. The game state was converted into a 156-dimensional vector (3 x 52), utilizing one-hot encodings for:
- Cards currently in the agent's hand.
- Cards discarded by either player.
- Cards picked up from the discard pile by the opponent.
While standard Random Forests typically predict a single scalar, this architecture predicts a 52-dimensional vector simultaneously. Each output represents the probability that a specific card in the deck is currently in the opponent's hand.
Integration into Gameplay
The agent utilizes these probabilities to calculate a "usefulness score" ($w$) for its own cards. It decides which card to discard by balancing two factors: Deadwood ($d$), the point value of cards not in a meld, and Meld Potential ($w$), the likelihood that keeping a card will eventually lead to a meld based on OHE predictions. The decision formula is defined as:
$$v = w \times \alpha + d \times (1 - \alpha)$$
where $\alpha$ is a tunable parameter representing the weight given to opponent modeling.
Data Generation
The dataset was generated through self-play using a baseline heuristic agent. The training set comprised 20,000 games (approximately 2.57 million individual plays), while a separate set of 10,000 games was reserved for evaluation.
Key Results and Analysis
The Random Forest model significantly outperformed linear alternatives, suggesting that the relationship between observed card movements and the opponent's hand is highly non-linear. As shown in the performance comparison below, the Random Forest achieved superior accuracy and precision compared to K-Nearest Neighbors (KNN) and Logistic Regression.
Emergent Logic and Calibration
The model successfully "learned" the underlying logic of Gin Rummy without explicit programming. For instance, it correctly predicted that if an opponent picks up a 5, they are statistically more likely to hold other 5s or adjacent cards (4s and 6s) to form melds.
However, a "calibration gap" was observed: the model's probabilities rarely reached 0 or 1, even in the endgame when card locations should be certain. This is likely because the training data is dominated by "foggy" middle-game states rather than clear-cut endgames.
Impact on Win Rate
The integration of OHE scores into the decision-making process led to a substantial performance boost. Interestingly, the highest win rates were achieved with relatively low values of $\alpha$, indicating that even a small amount of statistical "hunch" regarding the opponent's hand is significantly better than no modeling at all.
Discussion and Future Work
While the OHE-informed agent won 61% of its games against the baseline, several limitations remain. The model was trained on a specific heuristic agent and may struggle against human players or AI with different strategies, such as "baiting" discards. Furthermore, the current model lacks temporal awareness, treating a card discarded on turn 1 with the same weight as one discarded on turn 15.
Future research could involve weighting recent events more heavily or developing a "defensive" version of the agent that uses OHE to avoid discarding cards the opponent is likely waiting for. Additionally, addressing overfitting to suit-agnostic patterns by averaging probabilities across suit permutations could further refine the model's accuracy.
Summary updated