gin-rummy-engine 0.1.1

//! [`HeuristicBot`]: a deterministic knowledge-based player
//!
//! The knowledge-free greedy core in this module — draw only on strict
//! deadwood improvement, shed the least useful card, knock as soon as
//! allowed — is the policy the sibling crate's `simulate` example proved
//! out, and it doubles as the rollout policy of the Monte Carlo bot.  The
//! bot itself layers opponent knowledge on top: discards are penalized by
//! how much they could help the opponent's melds.

use crate::{DrawAction, Layoff, Strategy, TurnAction, UpcardAction, View};
use gin_rummy::{Card, Hand, Meld, Rank, Suit, best_melds, deadwood};

/// The discard leaving the least deadwood, skipping the just-taken card
///
/// Ties prefer shedding higher pip values, then the lowest card in hand
/// order.  This is the knowledge-free greedy shed shared with the Monte
/// Carlo rollout policy.
pub(crate) fn best_shed(hand: Hand, taken: Option<Card>) -> (Card, u8) {
    hand.iter()
        .filter(|&card| Some(card) != taken)
        .map(|card| (card, deadwood(hand - card.into())))
        .min_by_key(|&(card, rest)| (rest, u8::MAX - card.rank.deadwood()))
        .expect("a hand with a draw always has a legal discard")
}

/// Whether taking `top` strictly lowers deadwood after the best legal shed
/// (which may not be `top` itself)
pub(crate) fn improves(hand: Hand, top: Card) -> bool {
    let with = hand | top.into();
    let (_, rest) = best_shed(with, Some(top));
    rest < deadwood(hand)
}

/// The greedy layoff: the highest-pip own deadwood card that extends a
/// spread meld, with the target meld's index
///
/// Restricted to deadwood cards of an optimal arrangement — laying off a
/// melded card could *increase* final deadwood, since the defender's
/// remainder is melded optimally at settlement.  Shared with the Monte
/// Carlo rollout policy.
pub(crate) fn greedy_layoff(
    hand: Hand,
    spread: impl Iterator<Item = Meld>,
) -> Option<(Card, usize)> {
    let dead = best_melds(hand).deadwood_cards();
    spread
        .enumerate()
        .flat_map(|(index, meld)| {
            dead.iter()
                .filter(move |&card| meld.extended(card).is_some())
                .map(move |card| (card, index))
        })
        .max_by_key(|&(card, _)| card.rank.deadwood())
}

/// Tuning knobs for [`HeuristicBot`]
///
/// Like [`gin_rummy::Rules`], the struct is non-exhaustive: start from
/// [`HeuristicConfig::default`] and adjust fields.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub struct HeuristicConfig {
    /// Knock whenever the residual deadwood is at most
    /// `min(knock_limit, knock_threshold)`
    ///
    /// The default of 10 knocks as soon as the rules allow; lower values
    /// hold out for gin.
    pub knock_threshold: u8,
    /// Weight of discard safety against the opponent's revealed cards
    ///
    /// Zero ignores the opponent entirely, reproducing the pure greedy
    /// player.  The default is 1.
    pub safety_weight: u8,
}

impl Default for HeuristicConfig {
    fn default() -> Self {
        Self {
            knock_threshold: 10,
            safety_weight: 1,
        }
    }
}

/// A deterministic knowledge-based player
///
/// Fast enough for tournaments at any scale: every decision costs a few
/// deadwood-solver calls, each microseconds.
#[derive(Debug, Clone, Copy, Default)]
pub struct HeuristicBot {
    config: HeuristicConfig,
}

impl HeuristicBot {
    /// A bot with the default configuration
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// A bot with custom tuning
    #[must_use]
    pub const fn with_config(config: HeuristicConfig) -> Self {
        Self { config }
    }

    /// The cards that could meld with `card`: its rank in the other suits,
    /// and its suit within two ranks
    fn adjoiners(card: Card) -> Hand {
        let mut mask = Hand::EMPTY;
        for suit in Suit::ASC {
            if suit != card.suit {
                mask.insert(Card {
                    suit,
                    rank: card.rank,
                });
            }
        }
        let pivot = card.rank.get();
        for rank in pivot.saturating_sub(2).max(1)..=(pivot + 2).min(13) {
            if rank != pivot {
                mask.insert(Card {
                    suit: card.suit,
                    rank: Rank::new(rank),
                });
            }
        }
        mask
    }

    /// How much discarding `card` could help the opponent
    ///
    /// Adjoining cards the opponent is known to hold weigh double, unseen
    /// adjoiners weigh single, and adjoiners the opponent shed or declined
    /// count against — they signal disinterest, and shed adjoiners are
    /// physically unavailable.
    fn danger(view: &View<'_>, card: Card) -> i32 {
        let mask = Self::adjoiners(card);
        let known = (mask & view.opponent_known()).len() as i32;
        let unseen = (mask & view.unseen()).len() as i32;
        let cold = (mask & (view.opponent_shed() | view.opponent_passed())).len() as i32;
        2 * known + unseen - 2 * cold
    }

    /// The shed minimizing `(residual deadwood, weighted danger, -pips)`
    fn choose_shed(&self, view: &View<'_>) -> (Card, u8) {
        let hand = view.hand();
        let taken = view.taken_discard();
        let weight = i32::from(self.config.safety_weight);
        hand.iter()
            .filter(|&card| Some(card) != taken)
            .map(|card| (card, deadwood(hand - card.into())))
            .min_by_key(|&(card, rest)| {
                (
                    rest,
                    weight * Self::danger(view, card),
                    u8::MAX - card.rank.deadwood(),
                )
            })
            .expect("an 11-card hand always has a legal discard")
    }
}

impl Strategy for HeuristicBot {
    fn offer_upcard(&mut self, view: &View<'_>) -> UpcardAction {
        let top = view.upcard().expect("the upcard offer has an upcard");
        if improves(view.hand(), top) {
            UpcardAction::Take
        } else {
            UpcardAction::Pass
        }
    }

    fn choose_draw(&mut self, view: &View<'_>) -> DrawAction {
        let top = view.upcard().expect("the pile is never empty on a draw");
        if improves(view.hand(), top) {
            DrawAction::TakeDiscard
        } else {
            DrawAction::Stock
        }
    }

    fn play_turn(&mut self, view: &View<'_>) -> TurnAction {
        let hand = view.hand();
        if deadwood(hand) == 0 && view.rules().big_gin_bonus.is_some() {
            return TurnAction::BigGin(best_melds(hand));
        }

        let (card, rest) = self.choose_shed(view);
        if rest <= view.knock_limit().min(self.config.knock_threshold) {
            TurnAction::Knock {
                discard: card,
                melds: best_melds(hand - card.into()),
            }
        } else {
            TurnAction::Discard(card)
        }
    }

    fn choose_layoff(&mut self, view: &View<'_>) -> Option<Layoff> {
        greedy_layoff(view.hand(), view.spread()).map(|(card, meld)| Layoff { card, meld })
    }

    fn name(&self) -> &str {
        "greedy"
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use gin_rummy::Meld;

    fn card(text: &str) -> Card {
        text.parse().expect("a valid card")
    }

    #[test]
    fn best_shed_minimizes_deadwood_then_dumps_pips() {
        // ♣A♣2♣3 ♦4♦5♦6 ♥7♥8♥9 + ♠K ♠5: shedding the king keeps 5 deadwood.
        let hand: Hand = "A23.456.789.5K".parse().expect("a valid hand");
        assert_eq!(best_shed(hand, None), (card("♠K"), 5));
        // The king may not be shed if it was just taken; the five goes.
        assert_eq!(best_shed(hand, Some(card("♠K"))), (card("♠5"), 10));
    }

    #[test]
    fn improves_is_strict() {
        let hand: Hand = "A2.456.789.5K".parse().expect("a valid hand");
        // The ♣3 completes A-2-3: taking it sheds the king, 3+5=8 < 18.
        assert!(improves(hand, card("♣3")));
        // The ♦T helps nothing over drawing blind.
        assert!(!improves(hand, card("♦T")));
    }

    #[test]
    fn adjoiners_cover_sets_and_run_neighbors() {
        let mask = HeuristicBot::adjoiners(card("♦7"));
        for adjoining in ["♣7", "♥7", "♠7", "♦5", "♦6", "♦8", "♦9"] {
            assert!(mask.contains(card(adjoining)), "{adjoining} adjoins ♦7");
        }
        assert_eq!(mask.len(), 7);
        // Edges truncate: nothing below the ace.
        assert_eq!(HeuristicBot::adjoiners(card("♣A")).len(), 5);
    }

    #[test]
    fn greedy_layoff_extends_runs_but_never_breaks_melds() {
        let spread = [
            Meld::run(Suit::Clubs, Rank::new(5), Rank::new(7)),
            Meld::set(Rank::new(9), Some(Suit::Spades)),
        ];
        // ♣8 extends the run.  The ♠9 would complete the nine-set, but it
        // is melded into the defender's own ♠9-T-J-Q run and never offered.
        let hand: Hand = "8...9TJQ".parse().expect("a valid hand");
        assert_eq!(
            greedy_layoff(hand, spread.iter().copied()),
            Some((card("♣8"), 0)),
        );

        // A card inside the defender's own meld is not offered: laying
        // off the ♥T would break T-J-Q into pure deadwood.
        let melded: Hand = "..TJQ.".parse().expect("a valid hand");
        let sets = [Meld::set(Rank::T, Some(Suit::Hearts))];
        assert_eq!(greedy_layoff(melded, sets.iter().copied()), None);
    }

    #[test]
    fn chained_layoffs_terminate() {
        let mut spread = [Meld::run(Suit::Clubs, Rank::new(5), Rank::new(7))];
        // ♣8 ♣9 are two loose cards: each extends the run once the other
        // has stretched it.
        let mut hand: Hand = "89...".parse().expect("a valid hand");
        let mut laid = Vec::new();
        while let Some((card, index)) = greedy_layoff(hand, spread.iter().copied()) {
            spread[index] = spread[index].extended(card).expect("a legal extension");
            hand.remove(card);
            laid.push(card);
        }
        assert_eq!(laid, ["♣8", "♣9"].map(card));
        assert!(hand.is_empty());
    }
}