gin_rummy_engine/
heuristic.rs

1//! [`HeuristicBot`]: a deterministic knowledge-based player
2//!
3//! The knowledge-free greedy core in this module — draw only on strict
4//! deadwood improvement, shed the least useful card, knock as soon as
5//! allowed — is the policy the sibling crate's `simulate` example proved
6//! out, and it doubles as the rollout policy of the Monte Carlo bot.  The
7//! bot itself layers opponent knowledge on top: discards are penalized by
8//! how much they could help the opponent's melds.
9
10use crate::{DrawAction, Layoff, Strategy, TurnAction, UpcardAction, View};
11use gin_rummy::{Card, Hand, Meld, Rank, Suit, best_melds, deadwood};
12
13/// The discard leaving the least deadwood, skipping the just-taken card
14///
15/// Ties prefer shedding higher pip values, then the lowest card in hand
16/// order.  This is the knowledge-free greedy shed shared with the Monte
17/// Carlo rollout policy.
18pub(crate) fn best_shed(hand: Hand, taken: Option<Card>) -> (Card, u8) {
19    hand.iter()
20        .filter(|&card| Some(card) != taken)
21        .map(|card| (card, deadwood(hand - card.into())))
22        .min_by_key(|&(card, rest)| (rest, u8::MAX - card.rank.deadwood()))
23        .expect("a hand with a draw always has a legal discard")
24}
25
26/// Whether taking `top` strictly lowers deadwood after the best legal shed
27/// (which may not be `top` itself)
28pub(crate) fn improves(hand: Hand, top: Card) -> bool {
29    let with = hand | top.into();
30    let (_, rest) = best_shed(with, Some(top));
31    rest < deadwood(hand)
32}
33
34/// The greedy layoff: the highest-pip own deadwood card that extends a
35/// spread meld, with the target meld's index
36///
37/// Restricted to deadwood cards of an optimal arrangement — laying off a
38/// melded card could *increase* final deadwood, since the defender's
39/// remainder is melded optimally at settlement.  Shared with the Monte
40/// Carlo rollout policy.
41pub(crate) fn greedy_layoff(
42    hand: Hand,
43    spread: impl Iterator<Item = Meld>,
44) -> Option<(Card, usize)> {
45    let dead = best_melds(hand).deadwood_cards();
46    spread
47        .enumerate()
48        .flat_map(|(index, meld)| {
49            dead.iter()
50                .filter(move |&card| meld.extended(card).is_some())
51                .map(move |card| (card, index))
52        })
53        .max_by_key(|&(card, _)| card.rank.deadwood())
54}
55
56/// Tuning knobs for [`HeuristicBot`]
57///
58/// Like [`gin_rummy::Rules`], the struct is non-exhaustive: start from
59/// [`HeuristicConfig::default`] and adjust fields.
60#[derive(Debug, Clone, Copy, PartialEq, Eq)]
61#[non_exhaustive]
62pub struct HeuristicConfig {
63    /// Knock whenever the residual deadwood is at most
64    /// `min(knock_limit, knock_threshold)`
65    ///
66    /// The default of 4 holds out past the first legal knock — banking a
67    /// small knock every hand loses a game to the gin and undercut bonuses.
68    /// Raise it toward the knock limit to knock as soon as the rules allow,
69    /// or lower it to hunt gin.  [`score_awareness`](Self::score_awareness)
70    /// bends this threshold by the game score at play time.
71    pub knock_threshold: u8,
72    /// Weight of discard safety against the opponent's revealed cards
73    ///
74    /// Zero ignores the opponent entirely, reproducing the pure greedy
75    /// player.  The default is 1.
76    pub safety_weight: u8,
77    /// How strongly the game score shifts the knock threshold
78    ///
79    /// Points of threshold shift per unit of `margin / (game_target −
80    /// leader_score)`, where `margin` is this seat's game-score lead and
81    /// `leader_score` the higher of the two running totals.  Ahead the
82    /// effective threshold rises toward the
83    /// legal limit (bank the lead by knocking early); behind it falls
84    /// toward zero (hold out for a gin that swings the deficit).  The
85    /// denominator is the leader's distance to the winning line, not the
86    /// full target, so the same lead bends the threshold ever harder as
87    /// the game nears its end: a modest early-game nudge becomes a knock
88    /// at any deadwood once the front-runner is a hand from winning.  Zero
89    /// ignores the score, so a round played outside a game is unaffected.
90    pub score_awareness: u8,
91}
92
93impl Default for HeuristicConfig {
94    fn default() -> Self {
95        // Tuned by whole-game self-play (see `examples/tune.rs`): holding
96        // past the first legal knock and shifting the knock threshold by
97        // the leader's distance to the winning line lift the heuristic's
98        // game-win rate to ~50% against the Monte Carlo bot, up from ~42%
99        // for score-blind play.
100        Self {
101            knock_threshold: 4,
102            safety_weight: 1,
103            score_awareness: 40,
104        }
105    }
106}
107
108/// A deterministic knowledge-based player
109///
110/// Fast enough for tournaments at any scale: every decision costs a few
111/// deadwood-solver calls, each microseconds.
112#[derive(Debug, Clone, Copy, Default)]
113pub struct HeuristicBot {
114    config: HeuristicConfig,
115}
116
117impl HeuristicBot {
118    /// A bot with the default configuration
119    #[must_use]
120    pub fn new() -> Self {
121        Self::default()
122    }
123
124    /// A bot with custom tuning
125    #[must_use]
126    pub const fn with_config(config: HeuristicConfig) -> Self {
127        Self { config }
128    }
129
130    /// The cards that could meld with `card`: its rank in the other suits,
131    /// and its suit within two ranks
132    fn adjoiners(card: Card) -> Hand {
133        let mut mask = Hand::EMPTY;
134        for suit in Suit::ASC {
135            if suit != card.suit {
136                mask.insert(Card {
137                    suit,
138                    rank: card.rank,
139                });
140            }
141        }
142        let pivot = card.rank.get();
143        for rank in pivot.saturating_sub(2).max(1)..=(pivot + 2).min(13) {
144            if rank != pivot {
145                mask.insert(Card {
146                    suit: card.suit,
147                    rank: Rank::new(rank),
148                });
149            }
150        }
151        mask
152    }
153
154    /// How much discarding `card` could help the opponent
155    ///
156    /// Adjoining cards the opponent is known to hold weigh double, unseen
157    /// adjoiners weigh single, and adjoiners the opponent shed or declined
158    /// count against — they signal disinterest, and shed adjoiners are
159    /// physically unavailable.
160    fn danger(view: &View<'_>, card: Card) -> i32 {
161        let mask = Self::adjoiners(card);
162        let known = (mask & view.opponent_known()).len() as i32;
163        let unseen = (mask & view.unseen()).len() as i32;
164        let cold = (mask & (view.opponent_shed() | view.opponent_passed())).len() as i32;
165        2 * known + unseen - 2 * cold
166    }
167
168    /// The knock threshold in effect, shifted by the game score
169    ///
170    /// The neutral base is `knock_threshold`; `score_awareness` scales the
171    /// shift by `(mine − theirs) / (game_target − leader_score)`.  Ahead the
172    /// threshold rises (knock sooner), behind it falls toward zero (hold
173    /// out for gin); dividing by the leader's distance to the line, not
174    /// the full target, makes the same lead matter more late in the game.
175    fn knock_threshold(&self, view: &View<'_>) -> u8 {
176        let base = i32::from(self.config.knock_threshold);
177        let [mine, theirs] = view.game_scores().map(i32::from);
178        // The leader's distance to the winning line: the score bias grows
179        // as the game nears its end, not merely with the raw margin.
180        let remaining = i32::from(view.rules().game_target) - mine.max(theirs);
181        let bias = i32::from(self.config.score_awareness) * (mine - theirs) / remaining.max(1);
182        (base + bias).clamp(0, i32::from(u8::MAX)) as u8
183    }
184
185    /// The shed minimizing `(residual deadwood, weighted danger, -pips)`
186    fn choose_shed(&self, view: &View<'_>) -> (Card, u8) {
187        let hand = view.hand();
188        let taken = view.taken_discard();
189        let weight = i32::from(self.config.safety_weight);
190        hand.iter()
191            .filter(|&card| Some(card) != taken)
192            .map(|card| (card, deadwood(hand - card.into())))
193            .min_by_key(|&(card, rest)| {
194                (
195                    rest,
196                    weight * Self::danger(view, card),
197                    u8::MAX - card.rank.deadwood(),
198                )
199            })
200            .expect("an 11-card hand always has a legal discard")
201    }
202}
203
204impl Strategy for HeuristicBot {
205    fn offer_upcard(&mut self, view: &View<'_>) -> UpcardAction {
206        let top = view.upcard().expect("the upcard offer has an upcard");
207        if improves(view.hand(), top) {
208            UpcardAction::Take
209        } else {
210            UpcardAction::Pass
211        }
212    }
213
214    fn choose_draw(&mut self, view: &View<'_>) -> DrawAction {
215        let top = view.upcard().expect("the pile is never empty on a draw");
216        if improves(view.hand(), top) {
217            DrawAction::TakeDiscard
218        } else {
219            DrawAction::Stock
220        }
221    }
222
223    fn play_turn(&mut self, view: &View<'_>) -> TurnAction {
224        let hand = view.hand();
225        if deadwood(hand) == 0 && view.rules().big_gin_bonus.is_some() {
226            return TurnAction::BigGin(best_melds(hand));
227        }
228
229        let (card, rest) = self.choose_shed(view);
230        if rest <= view.knock_limit().min(self.knock_threshold(view)) {
231            TurnAction::Knock {
232                discard: card,
233                melds: best_melds(hand - card.into()),
234            }
235        } else {
236            TurnAction::Discard(card)
237        }
238    }
239
240    fn choose_layoff(&mut self, view: &View<'_>) -> Option<Layoff> {
241        greedy_layoff(view.hand(), view.spread()).map(|(card, meld)| Layoff { card, meld })
242    }
243
244    fn name(&self) -> &str {
245        "greedy"
246    }
247}
248
249#[cfg(test)]
250mod tests {
251    use super::*;
252    use gin_rummy::Meld;
253
254    fn card(text: &str) -> Card {
255        text.parse().expect("a valid card")
256    }
257
258    #[test]
259    fn best_shed_minimizes_deadwood_then_dumps_pips() {
260        // ♣A♣2♣3 ♦4♦5♦6 ♥7♥8♥9 + ♠K ♠5: shedding the king keeps 5 deadwood.
261        let hand: Hand = "A23.456.789.5K".parse().expect("a valid hand");
262        assert_eq!(best_shed(hand, None), (card("♠K"), 5));
263        // The king may not be shed if it was just taken; the five goes.
264        assert_eq!(best_shed(hand, Some(card("♠K"))), (card("♠5"), 10));
265    }
266
267    #[test]
268    fn improves_is_strict() {
269        let hand: Hand = "A2.456.789.5K".parse().expect("a valid hand");
270        // The ♣3 completes A-2-3: taking it sheds the king, 3+5=8 < 18.
271        assert!(improves(hand, card("♣3")));
272        // The ♦T helps nothing over drawing blind.
273        assert!(!improves(hand, card("♦T")));
274    }
275
276    #[test]
277    fn adjoiners_cover_sets_and_run_neighbors() {
278        let mask = HeuristicBot::adjoiners(card("♦7"));
279        for adjoining in ["♣7", "♥7", "♠7", "♦5", "♦6", "♦8", "♦9"] {
280            assert!(mask.contains(card(adjoining)), "{adjoining} adjoins ♦7");
281        }
282        assert_eq!(mask.len(), 7);
283        // Edges truncate: nothing below the ace.
284        assert_eq!(HeuristicBot::adjoiners(card("♣A")).len(), 5);
285    }
286
287    #[test]
288    fn greedy_layoff_extends_runs_but_never_breaks_melds() {
289        let spread = [
290            Meld::run(Suit::Clubs, Rank::new(5), Rank::new(7)),
291            Meld::set(Rank::new(9), Some(Suit::Spades)),
292        ];
293        // ♣8 extends the run.  The ♠9 would complete the nine-set, but it
294        // is melded into the defender's own ♠9-T-J-Q run and never offered.
295        let hand: Hand = "8...9TJQ".parse().expect("a valid hand");
296        assert_eq!(
297            greedy_layoff(hand, spread.iter().copied()),
298            Some((card("♣8"), 0)),
299        );
300
301        // A card inside the defender's own meld is not offered: laying
302        // off the ♥T would break T-J-Q into pure deadwood.
303        let melded: Hand = "..TJQ.".parse().expect("a valid hand");
304        let sets = [Meld::set(Rank::T, Some(Suit::Hearts))];
305        assert_eq!(greedy_layoff(melded, sets.iter().copied()), None);
306    }
307
308    #[test]
309    fn chained_layoffs_terminate() {
310        let mut spread = [Meld::run(Suit::Clubs, Rank::new(5), Rank::new(7))];
311        // ♣8 ♣9 are two loose cards: each extends the run once the other
312        // has stretched it.
313        let mut hand: Hand = "89...".parse().expect("a valid hand");
314        let mut laid = Vec::new();
315        while let Some((card, index)) = greedy_layoff(hand, spread.iter().copied()) {
316            spread[index] = spread[index].extended(card).expect("a legal extension");
317            hand.remove(card);
318            laid.push(card);
319        }
320        assert_eq!(laid, ["♣8", "♣9"].map(card));
321        assert!(hand.is_empty());
322    }
323
324    #[test]
325    fn score_awareness_shifts_the_knock_threshold() {
326        use crate::Table;
327        use gin_rummy::{Player, Round, Rules};
328
329        let deck: Vec<Card> = Hand::ALL.iter().collect();
330        let hands = [
331            deck.iter().step_by(2).take(10).copied().collect::<Hand>(),
332            deck.iter().skip(1).step_by(2).take(10).copied().collect(),
333        ];
334        let round = Round::from_deal(
335            Rules::default(),
336            Player::One,
337            hands,
338            deck[20],
339            deck[21..].to_vec(),
340        )
341        .expect("a partitioned deck");
342
343        // Base 6, target 100: with a 60-point margin and the leader 40
344        // points from the line the shift is 32 * 60 / 40 = 48, clamped
345        // into knock-limit range.
346        let bot = HeuristicBot::with_config(HeuristicConfig {
347            knock_threshold: 6,
348            score_awareness: 32,
349            ..HeuristicConfig::default()
350        });
351
352        let ahead = Table::new(round.clone()).scores([60, 0]);
353        let level = Table::new(round.clone());
354        let behind = Table::new(round.clone()).scores([0, 60]);
355
356        // Level score leaves the base untouched; ahead raises it, behind
357        // drops it toward zero (hold out for gin).
358        assert_eq!(bot.knock_threshold(&level.view(Player::One)), 6);
359        assert!(
360            bot.knock_threshold(&ahead.view(Player::One))
361                > bot.knock_threshold(&level.view(Player::One))
362        );
363        assert!(bot.knock_threshold(&behind.view(Player::One)) < 6);
364
365        // Proximity to the winning line, not the raw margin, drives the
366        // shift: the same 10-point lead bends the threshold far more when
367        // the leader is a hand from the target (denominator 10) than early
368        // in the game (denominator 90).  The old target-normalized formula
369        // scored these two equal.
370        let near_line = Table::new(round.clone()).scores([90, 80]);
371        let early = Table::new(round).scores([10, 0]);
372        assert!(
373            bot.knock_threshold(&near_line.view(Player::One))
374                > bot.knock_threshold(&early.view(Player::One))
375        );
376
377        // A score-blind bot ignores the margin entirely.
378        let blind = HeuristicBot::with_config(HeuristicConfig {
379            knock_threshold: 6,
380            score_awareness: 0,
381            ..HeuristicConfig::default()
382        });
383        assert_eq!(blind.knock_threshold(&ahead.view(Player::One)), 6);
384        assert_eq!(blind.knock_threshold(&behind.view(Player::One)), 6);
385    }
386}
gin_rummy_engine/heuristic.rs

gin_rummy_engine/
heuristic.rs
