Skip to main content

hearts_engine/
mc.rs

1//! [`MonteCarloBot`]: determinized Monte Carlo move selection
2//!
3//! Unlike the gin engine this crate mirrors, there is no separate rollout
4//! simulator to keep in sync with the rules: every Hearts observation
5//! except the hidden hands is public, so a sampled world is a real
6//! [`hearts::Round`] — reconstructed as a hold deal of the sampled original
7//! hands with the public history replayed — and rollouts run on the real
8//! state machine.
9
10use crate::heuristic::{
11    greedy_pass, greedy_play, moon_defense, pass_key, rollout_play, shoot_play,
12};
13use crate::{HeuristicConfig, Strategy, View};
14use hearts::{Card, Hand, PassDirection, Phase, Rank, Round, RoundResult, Rules, Seat, Suit};
15use rand::{Rng, RngExt as _};
16
17/// How many candidate plays a decision weighs after collapsing
18/// rank-adjacent equal-value equivalents; the rest are never worth a rollout.
19const MAX_CANDIDATES: usize = 8;
20
21/// How many of the highest [`pass_key`] cards seed the pass triples: every
22/// triple of the top 6 is rolled, after the greedy incumbent and before the
23/// short-suit void candidates.
24const PASS_POOL: usize = 6;
25
26/// The world count of the first scoring batch; each later batch doubles the
27/// evaluated total, so elimination checkpoints fall after 32, 64, 128, ...
28/// worlds.  A decision of 32 samples or fewer is a single batch, identical
29/// to an unbatched run.
30const BATCH: usize = 32;
31
32/// Maximum multiple of the configured world count for a contested decision.
33const MAX_WIDTH_MULTIPLIER: usize = 3;
34
35/// What the rollouts said about one candidate: its per-world equities, its
36/// summed round points, and how many of those worlds it shot the moon in
37type Scored = (Vec<f64>, f64, u32);
38
39/// One candidate action to score: the move a [`Strategy`] method would
40/// return, paired with its rendered [`Assessment::action`] label
41struct Candidate {
42    label: String,
43    choice: Choice,
44    /// Whether to roll the continuation as a moon attempt by the deciding
45    /// seat rather than with the greedy policy.  Shooting is a plan, not a
46    /// single card, so it lives on the rollout instead of on [`Choice`].
47    shoot: bool,
48}
49
50/// A typed candidate move
51#[derive(Clone, Copy)]
52enum Choice {
53    /// Pass these three cards.
54    Pass([Card; 3]),
55    /// Play this card.
56    Play(Card),
57}
58
59impl Choice {
60    /// Apply the move to a world and play it out: greedily, or with `me`
61    /// shooting the moon against a table that defends.
62    fn roll(self, round: &mut Round, me: Seat, shoot: bool) -> RoundResult {
63        match self {
64            Self::Pass(cards) => round
65                .pass(me, cards.into_iter().collect())
66                .expect("a candidate pass is legal in every sampled world"),
67            Self::Play(card) => round
68                .play(me, card)
69                .expect("a candidate play is legal in every sampled world"),
70        }
71        let mut played = round.played();
72        while let Some(seat) = round.turn() {
73            let card = rollout_play(round, seat, shoot.then_some(me), played);
74            round
75                .play(seat, card)
76                .expect("the rollout policy picks from legal_plays");
77            played.insert(card);
78        }
79        round.result().expect("a turnless round is finished")
80    }
81}
82
83/// A determinized Monte Carlo player
84///
85/// At every decision the bot samples hidden worlds consistent with its
86/// [`View`] — the receiver of its pass holds every passed card not yet
87/// played, seats shown void in a suit receive none of it, and the
88/// remaining unseen cards are distributed randomly.  The known incoming pass
89/// then softly favors worlds that fit the same pass model without becoming a
90/// hard card-location claim.  The bot plays each world out with the greedy
91/// policy on all seats and picks the action with the best
92/// expected value *for the game*: each rollout's result lands on the
93/// running [`game scores`](View::game_scores), a result that reaches
94/// [`game_target`](Rules::game_target) counts the final standings as
95/// normalized `3-2-1-0` matchpoints with ties averaged, and anything
96/// short of one counts its round points.
97/// The same worlds are reused across candidate actions (common random
98/// numbers), and the bot deviates from the greedy baseline only when the
99/// paired samples show a statistically clear gain.  Worlds are rolled in
100/// growing batches, and a challenger the incumbent already statistically
101/// dominates is dropped at a batch boundary — once none remain, the
102/// remaining worlds are never rolled at all — so an easy decision costs a
103/// fraction of the full sample count.  If the configured width leaves the
104/// mean-best challenger inside the gate in both directions, the bot adds
105/// base-width samples for the surviving candidates, capped at three times
106/// the configured width.
107///
108/// One candidate per decision is a moon attempt, rolled with the deciding
109/// seat shooting and the other three defending the way the live table
110/// does, once the shot shows eight points.  It has
111/// to clear the usual significance gate *and* actually reach the moon in
112/// most of the sampled worlds, and once chosen it is carried to the end of
113/// the round rather than re-argued each trick — a shot re-decided per trick
114/// takes the points and misses the moon.
115///
116/// The bot owns its random number generator, so a seeded generator makes
117/// its play reproducible.
118pub struct MonteCarloBot<R: Rng> {
119    rng: R,
120    samples: u32,
121    /// How many paired standard errors a challenger must clear in
122    /// [`beats`] before the bot deviates from the greedy incumbent.
123    gate: f64,
124    /// The pass policy the search models with, in all three of its roles:
125    /// the rollout opponents' passes, the observation reweight, and the
126    /// bot's own candidate ranking.
127    pass_model: HeuristicConfig,
128    /// Whether a moon attempt is under way, carried across the tricks of
129    /// one round so the search does not re-litigate it every turn.
130    shooting: bool,
131    moon_attempts: u32,
132    moon_passes: u32,
133}
134
135/// One candidate action's Monte Carlo assessment, for a solver or hint view
136///
137/// Produced by [`MonteCarloBot::assess`]: the same rollouts the bot chooses
138/// with, surfaced per candidate instead of collapsed to the single action a
139/// [`Strategy`] method returns.
140#[derive(Debug, Clone)]
141#[non_exhaustive]
142pub struct Assessment {
143    /// A rendered label for the action, e.g. `"play Q♠"` or
144    /// `"pass Q♠ A♥ K♥"`.
145    pub action: String,
146    /// Mean equity in `[0, 1]` — the quantity the bot maximizes, so
147    /// candidates rank by it.  A rollout that ends the game pays its
148    /// normalized `3-2-1-0` matchpoints (a sole win 1, a sole last 0,
149    /// ties averaged); one that does not pays the mid-game margin band.
150    /// For a player-facing figure, `4 − 3·equity` is the expected
151    /// finishing place.  A candidate the bot eliminated early averages
152    /// over the worlds it saw before elimination rather than the full
153    /// sample count.
154    pub equity: f64,
155    /// Mean round points this action costs the deciding seat — **lower is
156    /// better**, unlike the gin engine's signed gain.  Averaged over the
157    /// same worlds as [`equity`](Self::equity).
158    pub ev: f64,
159    /// Whether this is the bot's own pick — the move a [`Strategy`] method
160    /// would return on this view.  Because the bot deviates from the greedy
161    /// baseline only on a statistically clear gain, this need not be the
162    /// highest-equity candidate.
163    pub recommended: bool,
164}
165
166impl<R: Rng> MonteCarloBot<R> {
167    /// A bot with a default base width of 128 worlds per decision
168    pub const fn new(rng: R) -> Self {
169        Self {
170            rng,
171            samples: 128,
172            gate: 1.5,
173            pass_model: HeuristicConfig::new(),
174            shooting: false,
175            moon_attempts: 0,
176            moon_passes: 0,
177        }
178    }
179
180    /// Set how many worlds each decision samples
181    ///
182    /// More samples play stronger and slower; easy decisions stop at a
183    /// fraction of the budget, while a contested decision may extend to
184    /// three times it.  The `parallel` feature divides the cost by most of a
185    /// machine's cores without changing a single decision.
186    #[must_use]
187    pub const fn samples(mut self, samples: u32) -> Self {
188        self.samples = samples;
189        self
190    }
191
192    /// Set the significance gate: how many paired standard errors a
193    /// challenger must clear before the bot deviates from the greedy
194    /// incumbent
195    ///
196    /// The default is 1.5.  Duplicate-deal measurement found strength
197    /// monotone falling in the threshold over `[1.0, 2.5]` — the old 2.0
198    /// over-corrected for multiplicity by about 0.2 points a deal — while
199    /// a lower gate trusts more of the rollout noise.
200    #[must_use]
201    pub const fn gate(mut self, gate: f64) -> Self {
202        self.gate = gate;
203        self
204    }
205
206    /// Set the pass policy the search models with
207    ///
208    /// One config serves all three of the search's pass-model roles at
209    /// once: the passes the three rollout opponents submit in a sampled
210    /// world, the policy the observation reweight re-passes a plausible
211    /// giver holding with, and the ranking that orders the bot's own pass
212    /// candidates — whose first triple is the incumbent challengers must
213    /// beat by [`gate`](Self::gate) standard errors.  The default is
214    /// [`HeuristicConfig::new`], so a bot tuned away from the shipped
215    /// knobs must be told, or it models the shipped policy instead of its
216    /// own.
217    ///
218    /// Play-side knobs are not read: `moon_defense` belongs to the live
219    /// overlay and the rollout policy, not to passing.
220    #[must_use]
221    pub const fn pass_model(mut self, config: HeuristicConfig) -> Self {
222        self.pass_model = config;
223        self
224    }
225
226    /// How many shoot-the-moon plans this bot has begun
227    ///
228    /// The count is lifetime-monotone across rounds; callers can diff it
229    /// before and after any interval they want to measure.
230    pub const fn moon_attempts(&self) -> u32 {
231        self.moon_attempts
232    }
233
234    /// How many shoot-shaped passes this bot has chosen
235    ///
236    /// The count is lifetime-monotone across rounds; callers can diff it
237    /// before and after any interval they want to measure.
238    pub const fn moon_passes(&self) -> u32 {
239        self.moon_passes
240    }
241
242    /// Sample one set of current hidden hands consistent with the view, by
243    /// randomized most-constrained-first backtracking over the unseen cards,
244    /// softly weighted by the known incoming pass
245    ///
246    /// Hard constraints: exact hand sizes, no card in a suit the seat is void
247    /// in, and the still-unplayed passed cards pinned to the receiver.  Soft
248    /// evidence comes from the known incoming pass.  The true deal satisfies
249    /// every hard constraint, so failure is a sampling accident — the caller
250    /// retries.
251    fn sample_hands(&mut self, view: &View<'_>) -> Option<[Hand; 4]> {
252        let me = view.seat();
253        let mut hands = [Hand::EMPTY; 4];
254        let mut room = [0usize; 4];
255        hands[me as usize] = view.hand();
256        for seat in Seat::ALL {
257            if seat != me {
258                let known = view.known_cards(seat);
259                hands[seat as usize] = known;
260                // A pass-phase world samples *pre-pass* hands: a seat that
261                // already passed holds 10 now, but its 3 hidden passes are
262                // part of the unseen pool and belong back in its hand.
263                let size = if view.phase() == Phase::Passing {
264                    13
265                } else {
266                    view.hand_len(seat)
267                };
268                room[seat as usize] = size - known.len();
269            }
270        }
271
272        // Shuffle for randomness, then most-constrained cards first.
273        let mut cards: Vec<Card> = view.unseen().into_iter().collect();
274        for i in (1..cards.len()).rev() {
275            let j = self.rng.random_range(0..=i);
276            cards.swap(i, j);
277        }
278        let allowed = |card: Card, seat: Seat| seat != me && !view.is_void(seat, card.suit);
279        cards.sort_by_key(|&card| Seat::ALL.iter().filter(|&&s| allowed(card, s)).count());
280
281        fn place(
282            cards: &[Card],
283            allowed: &impl Fn(Card, Seat) -> bool,
284            hands: &mut [Hand; 4],
285            room: &mut [usize; 4],
286            rng: &mut (impl Rng + ?Sized),
287        ) -> bool {
288            let Some((&card, rest)) = cards.split_first() else {
289                return true;
290            };
291            let mut order = Seat::ALL;
292            for i in (1..4).rev() {
293                let j = rng.random_range(0..=i);
294                order.swap(i, j);
295            }
296            for seat in order {
297                if room[seat as usize] > 0 && allowed(card, seat) {
298                    room[seat as usize] -= 1;
299                    hands[seat as usize].insert(card);
300                    if place(rest, allowed, hands, room, rng) {
301                        return true;
302                    }
303                    hands[seat as usize].remove(card);
304                    room[seat as usize] += 1;
305                }
306            }
307            false
308        }
309
310        if !place(&cards, &allowed, &mut hands, &mut room, &mut self.rng) {
311            return None;
312        }
313
314        if let Some(received) = view.received() {
315            let giver = view.direction().giver(me);
316            let mut plausible = hands[giver as usize] | received;
317            for trick in view.tricks().iter().copied().chain(view.current_trick()) {
318                if let Some(card) = trick.card_from(giver) {
319                    plausible.insert(card);
320                }
321            }
322            let likelihood = pass_observation_likelihood(plausible, received, self.pass_model);
323            if self.rng.random::<f64>() > likelihood {
324                return None;
325            }
326        }
327        Some(hands)
328    }
329
330    /// Sample one world: a real [`Round`] at this decision point
331    ///
332    /// A play-phase world is a hold deal of the sampled *original* hands
333    /// (current hand plus own plays) with the public history replayed; a
334    /// pass-phase world is a fresh deal of sampled pre-pass hands with the
335    /// three opponents' greedy passes already submitted, waiting on ours.
336    fn sample_world(&mut self, view: &View<'_>) -> Option<Round> {
337        let me = view.seat();
338        let hands = self.sample_hands(view)?;
339
340        if view.phase() == Phase::Passing {
341            let mut round = Round::from_deal(*view.rules(), view.direction(), hands).ok()?;
342            for seat in Seat::ALL {
343                if seat != me {
344                    let pass: Hand = greedy_pass(hands[seat as usize], self.pass_model)
345                        .into_iter()
346                        .collect();
347                    round.pass(seat, pass).ok()?;
348                }
349            }
350            return Some(round);
351        }
352
353        // Original post-pass hands: what each seat holds now plus what it
354        // has already played.
355        let mut originals = hands;
356        for trick in view.tricks().iter().copied().chain(view.current_trick()) {
357            for (seat, card) in trick.plays() {
358                originals[seat as usize].insert(card);
359            }
360        }
361        let mut round = Round::from_deal(*view.rules(), PassDirection::Hold, originals).ok()?;
362        for trick in view.tricks().iter().copied().chain(view.current_trick()) {
363            for (seat, card) in trick.plays() {
364                round.play(seat, card).ok()?;
365            }
366        }
367        Some(round)
368    }
369
370    /// Sample `count` worlds, retrying the rare inconsistent construction
371    fn sample_worlds(&mut self, view: &View<'_>, count: u32) -> Vec<Round> {
372        let mut worlds = Vec::with_capacity(count as usize);
373        // The true deal is always consistent, so failures are sampling
374        // accidents; the budget only guards against a pathological view.
375        let mut attempts = count * 4 + 64;
376        while worlds.len() < count as usize && attempts > 0 {
377            attempts -= 1;
378            if let Some(world) = self.sample_world(view) {
379                worlds.push(world);
380            }
381        }
382        worlds
383    }
384
385    /// The ordered candidate moves for the current decision, the greedy
386    /// incumbent first; empty when the seat has no real choice
387    fn candidates(&self, view: &View<'_>) -> Vec<Candidate> {
388        match view.phase() {
389            Phase::Passing => pass_candidates(view, self.pass_model),
390            Phase::Playing => play_candidates(view),
391            Phase::Finished => Vec::new(),
392        }
393    }
394
395    /// Score every candidate on freshly sampled worlds and return the move
396    /// to play: the greedy incumbent (`candidates[0]`) unless a challenger
397    /// clears the significance gate
398    fn choose(&mut self, view: &View<'_>, candidates: &[Candidate]) -> Choice {
399        let scored = self.score(view, candidates);
400        let best = recommended(&scored, candidates, self.gate);
401        if candidates[best].shoot {
402            self.moon_passes += 1;
403        }
404        candidates[best].choice
405    }
406
407    /// Score one decision, extending only an unresolved incumbent/challenger
408    /// comparison by another base-width sample, up to three times the budget.
409    fn score(&mut self, view: &View<'_>, candidates: &[Candidate]) -> Vec<Scored> {
410        let mut scored: Vec<Scored> = vec![(Vec::new(), 0.0, 0); candidates.len()];
411        let mut alive: Vec<usize> = (1..candidates.len()).collect();
412        for _ in 0..MAX_WIDTH_MULTIPLIER {
413            let worlds = self.sample_worlds(view, self.samples);
414            if worlds.is_empty() {
415                break;
416            }
417            score_worlds(
418                view,
419                &worlds,
420                candidates,
421                self.gate,
422                &mut scored,
423                &mut alive,
424            );
425            if !contested(&scored, &alive, self.gate) {
426                break;
427            }
428        }
429        scored
430    }
431
432    /// Assess every candidate action for the current decision, each with
433    /// its Monte Carlo equity and expected round points, ranked by equity
434    /// with the bot's own pick flagged — the read a solver or hint view
435    /// shows
436    ///
437    /// When every legal play collapses into one equivalence class the read
438    /// is still offered, against each legal play tied: a human cannot see
439    /// from the hand alone that the ranks between the cards are already gone,
440    /// so refusing the read would look like a bug.
441    ///
442    /// Returns empty only when there is genuinely nothing to weigh: a single
443    /// legal play, a finished round, or a view no consistent world can be
444    /// sampled for (e.g. a seat mid-pass).
445    #[must_use]
446    pub fn assess(&mut self, view: &View<'_>) -> Vec<Assessment> {
447        let candidates = self.candidates(view);
448        if candidates.is_empty() {
449            return Vec::new();
450        }
451        let scored = self.score(view, &candidates);
452        if scored[0].0.is_empty() {
453            // No consistent world: averaging zero rollouts would put NaN
454            // in the public rows.
455            return Vec::new();
456        }
457        let mean = |(equities, ev_sum, _): &Scored| {
458            let n = equities.len() as f64;
459            (equities.iter().sum::<f64>() / n, ev_sum / n)
460        };
461
462        // A single candidate means the legal plays all collapsed into one
463        // class — every one interchangeable.  List them as tied so the panel
464        // says "any of these" instead of going blank.
465        if candidates.len() == 1 {
466            let (equity, ev) = mean(&scored[0]);
467            return view
468                .legal_plays()
469                .into_iter()
470                .map(|card| Assessment {
471                    action: format!("play {card}"),
472                    equity,
473                    ev,
474                    recommended: true,
475                })
476                .collect();
477        }
478
479        let best = recommended(&scored, &candidates, self.gate);
480        let mut out: Vec<Assessment> = candidates
481            .iter()
482            .zip(&scored)
483            .enumerate()
484            .map(|(i, (candidate, score))| {
485                let (equity, ev) = mean(score);
486                Assessment {
487                    action: candidate.label.clone(),
488                    equity,
489                    ev,
490                    recommended: i == best,
491                }
492            })
493            .collect();
494        out.sort_by(|a, b| b.equity.total_cmp(&a.equity));
495        out
496    }
497}
498
499/// A soft likelihood for the cards known to have arrived from our giver
500///
501/// We cannot distinguish the giver's ten kept cards from its three incoming
502/// cards, so score the known pass against that deliberately over-broad
503/// plausible pre-pass holding.  Every mismatch costs only a quarter of the
504/// weight; an opponent need not share our pass policy.
505fn pass_observation_likelihood(plausible: Hand, received: Hand, config: HeuristicConfig) -> f64 {
506    let modeled: Hand = greedy_pass(plausible, config).into_iter().collect();
507    let misses = 3 - (modeled & received).len() as i32;
508    0.75f64.powi(misses)
509}
510
511/// Add `triple` unless the pool already holds those three cards
512///
513/// A pass is a set, so two orderings of one triple are one candidate.  The
514/// incumbent is seeded first and is exactly the triple the pool loop is most
515/// likely to regenerate, which is why this is shared rather than inline.
516fn push_new(triples: &mut Vec<[Card; 3]>, triple: [Card; 3]) {
517    let set: Hand = triple.into_iter().collect();
518    if !triples
519        .iter()
520        .any(|old| old.iter().copied().collect::<Hand>() == set)
521    {
522        triples.push(triple);
523    }
524}
525
526/// The candidate passes: the greedy incumbent first, then every triple of the
527/// [`PASS_POOL`] highest-ranked cards, passes that empty a short side suit,
528/// plus the one moon pass
529///
530/// Candidate 0 is [`greedy_pass`] itself, built rather than inferred.  The
531/// ranking below agrees with the policy on the first card and nowhere after
532/// it — the policy rescores against the shrinking hand — so the invariant the
533/// significance gate defends can no longer be inherited from two sorts that
534/// happened to agree.
535fn pass_candidates(view: &View<'_>, config: HeuristicConfig) -> Vec<Candidate> {
536    let hand = view.hand();
537    let mut ranked: Vec<Card> = hand.into_iter().collect();
538    // `pass_key` is injective over a hand, so the sort needs no stability and
539    // the order is the same on every build.
540    ranked.sort_unstable_by_key(|&card| core::cmp::Reverse(pass_key(hand, card, config)));
541
542    // The mirror of the greedy triple: the three cards the pass policy least
543    // wants gone are low cards of long suits, which is exactly the ballast a
544    // shot sheds.  One candidate, rolled with a shooting continuation.
545    // Ranked without queen insurance: it keeps low spades to duck an incoming
546    // Q♠, which a shooter wants, and ranking them dead last would make them
547    // the ballast (measured: −8 SE of the seat's own moons).
548    let mut ducker = config;
549    ducker.queen_insurance = 0;
550    let mut ballast: Vec<Card> = hand.into_iter().collect();
551    ballast.sort_unstable_by_key(|&card| core::cmp::Reverse(pass_key(hand, card, ducker)));
552    let losers: [Card; 3] = ballast[ballast.len() - 3..]
553        .try_into()
554        .expect("a passing hand holds thirteen cards");
555
556    let pool = &ranked[..ranked.len().min(PASS_POOL)];
557    let mut triples = Vec::<[Card; 3]>::with_capacity(24);
558    triples.push(greedy_pass(hand, config));
559    for i in 0..pool.len() {
560        for j in i + 1..pool.len() {
561            for k in j + 1..pool.len() {
562                push_new(&mut triples, [pool[i], pool[j], pool[k]]);
563            }
564        }
565    }
566
567    // Independent card scores can award three separate void bonuses without
568    // actually emptying a suit.  Make every short non-spade void reachable,
569    // filling a one- or two-card suit's triple with the most dangerous cards
570    // outside it.
571    for suit in Suit::ASC.into_iter().filter(|&suit| suit != Suit::Spades) {
572        let suited: Vec<Card> = hand[suit].iter().map(|rank| Card { suit, rank }).collect();
573        if suited.is_empty() || suited.len() > 3 {
574            continue;
575        }
576        let mut cards = suited;
577        cards.extend(
578            ranked
579                .iter()
580                .copied()
581                .filter(|card| card.suit != suit)
582                .take(3 - cards.len()),
583        );
584        push_new(
585            &mut triples,
586            cards.try_into().expect("a passing hand has filler"),
587        );
588    }
589
590    let mut out: Vec<Candidate> = triples
591        .into_iter()
592        .map(|triple| Candidate {
593            label: format!("pass {} {} {}", triple[0], triple[1], triple[2]),
594            choice: Choice::Pass(triple),
595            shoot: false,
596        })
597        .collect();
598    out.push(Candidate {
599        label: format!("shoot, pass {} {} {}", losers[0], losers[1], losers[2]),
600        choice: Choice::Pass(losers),
601        shoot: true,
602    });
603    out
604}
605
606/// The candidate plays: the legal set collapsed by rank adjacency — cards
607/// of a suit separated only by ranks this seat has seen (own hand, or
608/// played to a **completed** trick — a rank sitting in the trick in progress
609/// still separates the cards above it from the cards below) *and* of equal
610/// penalty value are interchangeable — the greedy incumbent first, capped at
611/// [`MAX_CANDIDATES`]
612fn play_candidates(view: &View<'_>) -> Vec<Candidate> {
613    let legal = view.legal_plays();
614    if legal.len() < 2 {
615        return Vec::new();
616    }
617    let trick = view.current_trick().expect("a play decision has a trick");
618    let played = view.played();
619    let incumbent = greedy_play(legal, trick, played);
620    // Cards in the trick in progress are committed but still contest THIS
621    // trick — behind a led J♦ the Q♦ wins and the T♦ does not, so they are no
622    // sequence.  Collapse only across ranks gone in completed tricks.
623    let seen = view.hand() | (played - trick.cards());
624
625    let mut reps = vec![incumbent];
626    for suit in Suit::ASC {
627        let mut group: Vec<Rank> = Vec::new();
628        let flush = |group: &mut Vec<Rank>, reps: &mut Vec<Card>| {
629            if let Some(&low) = group.first() {
630                let card = |rank| Card { suit, rank };
631                if !group.iter().any(|&rank| card(rank) == incumbent) {
632                    reps.push(card(low));
633                }
634            }
635            group.clear();
636        };
637        let mut prev: Option<Rank> = None;
638        for rank in legal[suit] {
639            if let Some(prev) = prev {
640                // Rank-adjacency is not equivalence: two touching cards of
641                // unequal penalty value (Q♠ vs J♠) are distinct plays.
642                // ponytail: keys on Card::points() (u8, standard Hearts); a
643                // variant like Omnibus (J♦ = -10, 10♣ doubler) must widen the
644                // value function this consults, then this line follows it.
645                let same_value =
646                    (Card { suit, rank: prev }).points() == (Card { suit, rank }).points();
647                let contiguous = same_value
648                    && (prev.get() + 1..rank.get()).all(|gap| seen[suit].contains(Rank::new(gap)));
649                if !contiguous {
650                    flush(&mut group, &mut reps);
651                }
652            }
653            group.push(rank);
654            prev = Some(rank);
655        }
656        flush(&mut group, &mut reps);
657    }
658
659    reps.truncate(MAX_CANDIDATES);
660    let mut out: Vec<Candidate> = reps
661        .into_iter()
662        .map(|card| Candidate {
663            label: format!("play {card}"),
664            choice: Choice::Play(card),
665            shoot: false,
666        })
667        .collect();
668
669    // One moon candidate, past the cap: the truncation runs in suit order
670    // and would otherwise drop the very high cards a shot opens with.
671    // Offered only while nobody else has scored — a moon is dead the moment
672    // they do — and only when the plays differ at all, so a fully collapsed
673    // legal set keeps `assess`'s "every play tied" read.
674    let alive = Seat::ALL
675        .into_iter()
676        .all(|seat| seat == view.seat() || view.points_taken(seat) == 0);
677    if alive && out.len() > 1 {
678        let card = shoot_play(legal, trick, played);
679        out.push(Candidate {
680            label: format!("shoot, play {card}"),
681            choice: Choice::Play(card),
682            shoot: true,
683        });
684    }
685    out
686}
687
688/// Roll candidates through the same `worlds` (common random numbers) in
689/// growing batches, eliminating challengers the incumbent already
690/// dominates, and return per candidate its per-world equities and summed
691/// round points
692///
693/// Survivors always reach the full world count, so the final
694/// [`recommended`] read over them is exactly the unbatched one.  An
695/// eliminated candidate keeps the equities it accumulated: its paired mean
696/// against the incumbent is negative on that prefix, and [`beats`] zips to
697/// the shorter slice, so [`recommended`] rejects it with no special
698/// casing.  Each serial evaluator or parallel worker reuses a scratch
699/// [`Round`], whose `clone_from` retains the completed-trick allocation.
700fn score_worlds(
701    view: &View<'_>,
702    worlds: &[Round],
703    candidates: &[Candidate],
704    gate: f64,
705    scored: &mut [Scored],
706    alive: &mut Vec<usize>,
707) {
708    let me = view.seat();
709    let rules = view.rules();
710    let standing = absolute_standing(me, view.game_scores());
711    let eval = |candidate: &Candidate, world: &Round, scratch: &mut Round| {
712        scratch.clone_from(world);
713        let result = candidate.choice.roll(scratch, me, candidate.shoot);
714        let moon = u32::from(result.shooter() == Some(me));
715        let scores = result.scores(rules);
716        (
717            equity(&scores, me, standing, rules),
718            f64::from(scores[me as usize]),
719            moon,
720        )
721    };
722
723    #[cfg(not(feature = "parallel"))]
724    let mut scratch = worlds.first().cloned();
725    let mut done = 0;
726    while done < worlds.len() {
727        let batch = &worlds[done..worlds.len().min(done + done.max(BATCH))];
728        for &i in std::iter::once(&0).chain(alive.iter()) {
729            let candidate = &candidates[i];
730            #[cfg(feature = "parallel")]
731            let results: Vec<(f64, f64, u32)> = {
732                use rayon::prelude::*;
733                batch
734                    .par_iter()
735                    .map_init(
736                        || batch[0].clone(),
737                        |scratch, world| eval(candidate, world, scratch),
738                    )
739                    .collect()
740            };
741            #[cfg(not(feature = "parallel"))]
742            let results = batch.iter().map(|world| {
743                eval(
744                    candidate,
745                    world,
746                    scratch
747                        .as_mut()
748                        .expect("a non-empty batch has a scratch round"),
749                )
750            });
751
752            // Reduced sequentially in world order in both builds, so a
753            // parallel bot makes bit-identical decisions to a serial one.
754            let (equities, ev_sum, moons) = &mut scored[i];
755            for (equity, points, moon) in results {
756                equities.push(equity);
757                *ev_sum += points;
758                *moons += moon;
759            }
760        }
761        done += batch.len();
762        alive.retain(|&i| !beats(&scored[0].0, &scored[i].0, gate));
763        if alive.is_empty() {
764            break;
765        }
766    }
767}
768
769/// Whether the strongest surviving challenger remains inside the
770/// significance gate in both directions, with no challenger already clear.
771fn contested(scored: &[Scored], alive: &[usize], gate: f64) -> bool {
772    let mean = |e: &[f64]| e.iter().sum::<f64>() / e.len() as f64;
773    let defend = &scored[0].0;
774    if alive.iter().any(|&i| beats(&scored[i].0, defend, gate)) {
775        return false;
776    }
777    alive
778        .iter()
779        .copied()
780        .max_by(|&a, &b| mean(&scored[a].0).total_cmp(&mean(&scored[b].0)))
781        .is_some_and(|best| !beats(defend, &scored[best].0, gate))
782}
783
784/// The index of the recommended candidate: the greedy incumbent
785/// (`scored[0]`) unless a challenger's paired advantage clears the
786/// [`beats`] gate, in which case the largest such gain
787///
788/// A moon challenger must clear a second bar: the rollouts have to actually
789/// shoot it more often than not.
790///
791/// Its per-world equities are bimodal — the moon band's ceiling against a
792/// heap of failures — and a paired test on heavy-tailed differences waves
793/// through edges that are not there: measured against the greedy field, the
794/// gate alone attempted a moon in two rounds in five to land one in twenty,
795/// at a cost of over two points a round.  The break-even is arithmetic
796/// rather than taste.  A moon is worth `0.5 + 26/112 ≈ 0.732` mid-game, a
797/// failed shot leaves us holding about half the deck's points for roughly
798/// `0.423`, and the greedy line is worth about `0.577`; the indifference
799/// point between them sits within a hair of an even chance.  A moon rate
800/// over the sampled worlds is a plain Bernoulli count with none of the tail
801/// trouble, so require it to be a majority.
802fn recommended(scored: &[Scored], candidates: &[Candidate], gate: f64) -> usize {
803    let mean = |e: &[f64]| e.iter().sum::<f64>() / e.len() as f64;
804    let likely = |i: usize| 2 * scored[i].2 as usize > scored[i].0.len();
805    let defend = &scored[0].0;
806    (1..scored.len())
807        .filter(|&i| beats(&scored[i].0, defend, gate))
808        .filter(|&i| !candidates[i].shoot || likely(i))
809        .max_by(|&a, &b| mean(&scored[a].0).total_cmp(&mean(&scored[b].0)))
810        .unwrap_or(0)
811}
812
813/// Whether the challenger's paired advantage over the incumbent is large
814/// enough to trust
815///
816/// The true value difference between most candidate actions is well below
817/// the rollout noise floor, and deviating from the solid greedy baseline
818/// on noise alone plays *worse* than the baseline.  A one-sided paired
819/// test — the mean difference at least `gate` standard errors above zero,
820/// since several challengers get tested per decision — keeps only the
821/// deviations the samples actually support.
822fn beats(challenger: &[f64], incumbent: &[f64], gate: f64) -> bool {
823    let n = challenger.len() as f64;
824    let mean = challenger
825        .iter()
826        .zip(incumbent)
827        .map(|(c, i)| c - i)
828        .sum::<f64>()
829        / n;
830    if mean <= 0.0 {
831        return false;
832    }
833    let var = challenger
834        .iter()
835        .zip(incumbent)
836        .map(|(c, i)| (c - i - mean).powi(2))
837        .sum::<f64>()
838        / n;
839    mean > gate * (var / n).sqrt()
840}
841
842/// Re-key the seat-relative [`View::game_scores`] by absolute [`Seat`]
843fn absolute_standing(me: Seat, relative: [u16; 4]) -> [u16; 4] {
844    let mut standing = [0; 4];
845    standing[me as usize] = relative[0];
846    standing[me.left() as usize] = relative[1];
847    standing[me.across() as usize] = relative[2];
848    standing[me.right() as usize] = relative[3];
849    standing
850}
851
852/// The value to `me` of a rollout that charged `scores`, from the
853/// `standing` game totals: normalized `3-2-1-0` matchpoints if the game
854/// ends, otherwise affine in the round-point margin
855///
856/// A game ends when a post-round total reaches the target, and the lowest
857/// total finishes first.  A finished game pays its matchpoints over three
858/// — a sole win 1, then ⅔, ⅓, and 0 for a sole last, ties averaged — the
859/// same payoff the arena's `rank` column scores, so the search keeps
860/// fighting for placement after the win is gone.  Short of a clinch the
861/// value is `0.5` plus the margin between the opponents' average round
862/// points and ours, scaled into `(1/4, 3/4)` — strictly below a sole win
863/// and strictly above a sole last, so [`beats`] deviates from the
864/// round-point objective only when a rollout can actually end the game.
865/// A two-way crown (⅚) also outranks any running position; deeper ties
866/// and the middle placements interleave with the band on purpose — a
867/// middling finish is commensurate with a middling position in a game
868/// still running.
869fn equity(scores: &[u16; 4], me: Seat, standing: [u16; 4], rules: &Rules) -> f64 {
870    let mut totals = standing;
871    for seat in Seat::ALL {
872        let total = &mut totals[seat as usize];
873        *total = total.saturating_add(scores[seat as usize]);
874    }
875    if totals.iter().any(|&total| total >= rules.game_target) {
876        // Twice the 3-2-1-0 matchpoints stays an integer through the tie
877        // average; `ahead + share ≤ 4` bounds the subtraction at 6.
878        let mine = totals[me as usize];
879        let ahead = totals.iter().filter(|&&total| total < mine).count();
880        let share = totals.iter().filter(|&&total| total == mine).count();
881        return (6 - 2 * ahead - (share - 1)) as f64 / 6.0;
882    }
883    let mine = f64::from(scores[me as usize]);
884    let others: f64 = Seat::ALL
885        .iter()
886        .filter(|&&seat| seat != me)
887        .map(|&seat| f64::from(scores[seat as usize]))
888        .sum::<f64>()
889        / 3.0;
890    0.5 + (others - mine) / 112.0
891}
892
893impl<R: Rng> Strategy for MonteCarloBot<R> {
894    fn pass_cards(&mut self, view: &View<'_>) -> [Card; 3] {
895        let candidates = self.candidates(view);
896        match self.choose(view, &candidates) {
897            Choice::Pass(cards) => cards,
898            Choice::Play(_) => unreachable!("the passing phase yields pass choices"),
899        }
900    }
901
902    fn play_card(&mut self, view: &View<'_>) -> Card {
903        // Reactive moon defense: the rollout policy models every opponent as
904        // a greedy ducker who never shoots the moon, so the search is blind
905        // to a moon in progress.  Break it with the same overlay HeuristicBot
906        // uses (threshold 8, its default).  Draws no randomness, so seeded
907        // play stays reproducible.
908        if let Some(card) = moon_defense(view, 8) {
909            return card;
910        }
911        let legal = view.legal_plays();
912        if legal.len() == 1 {
913            // A forced card needs no rollout — and draws no randomness,
914            // keeping seeded play reproducible.
915            return legal.into_iter().next().expect("checked non-empty");
916        }
917        let trick = view.current_trick().expect("a play decision has a trick");
918
919        // A moon is a plan, not a card, and the rollouts that chose it
920        // priced thirteen tricks of shooting.  Re-deciding it every trick
921        // instead measured out at three overrides in ten — the search kept
922        // wandering back to the greedy line holding points it had already
923        // paid for, which is the worst of both.  So carry the plan: the
924        // first trick of a round clears it, another seat scoring kills it,
925        // and in between the shot is simply played.
926        if view.tricks().is_empty()
927            || Seat::ALL
928                .into_iter()
929                .any(|seat| seat != view.seat() && view.points_taken(seat) > 0)
930        {
931            self.shooting = false;
932        }
933        if self.shooting {
934            return shoot_play(legal, trick, view.played());
935        }
936
937        let candidates = self.candidates(view);
938        if candidates.len() < 2 {
939            // Every legal card collapsed into one equivalence class.
940            return greedy_play(legal, trick, view.played());
941        }
942        let scored = self.score(view, &candidates);
943        let best = recommended(&scored, &candidates, self.gate);
944        if candidates[best].shoot {
945            self.moon_attempts += 1;
946        }
947        self.shooting = candidates[best].shoot;
948        match candidates[best].choice {
949            Choice::Play(card) => card,
950            Choice::Pass(_) => unreachable!("the playing phase yields play choices"),
951        }
952    }
953
954    fn name(&self) -> &str {
955        "mc"
956    }
957}
958
959#[cfg(test)]
960mod tests {
961    use super::*;
962    use crate::{HeuristicBot, Table};
963    use hearts::Holding;
964    use rand::SeedableRng as _;
965    use rand::rngs::StdRng;
966
967    /// The sorted deck dealt round-robin on a hold deal.
968    fn fixed_table() -> Table {
969        let mut hands = [Hand::EMPTY; 4];
970        for (i, card) in Hand::ALL.into_iter().enumerate() {
971            hands[i % 4].insert(card);
972        }
973        let round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
974            .expect("a round-robin deal partitions the deck");
975        Table::new(round)
976    }
977
978    /// Drive a few tricks with the greedy bot to reach a mid-round spot.
979    fn mid_round() -> Table {
980        let mut table = fixed_table();
981        let mut bot = crate::HeuristicBot::new();
982        while table.round().tricks().len() < 5 {
983            table.step(&mut bot).expect("greedy plays are legal");
984        }
985        table
986    }
987
988    #[test]
989    fn sampled_worlds_are_consistent_with_the_view() {
990        let table = mid_round();
991        let me = table.turn().expect("a mid-round table has a mover");
992        let view = table.view(me);
993        let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(1));
994
995        let worlds = bot.sample_worlds(&view, 32);
996        assert_eq!(worlds.len(), 32);
997        for world in &worlds {
998            // The public position is reproduced exactly.
999            assert_eq!(world.tricks(), view.tricks());
1000            assert_eq!(world.current_trick(), view.current_trick());
1001            assert_eq!(world.played(), view.played());
1002            assert_eq!(world.hand(me), view.hand());
1003            assert_eq!(world.phase(), Phase::Playing);
1004
1005            for seat in Seat::ALL {
1006                let hand = world.hand(seat);
1007                // Right sizes, only possible cards, known cards pinned.
1008                assert_eq!(hand.len(), view.hand_len(seat));
1009                assert_eq!(hand - view.possible_cards(seat), Hand::EMPTY);
1010                let known = view.known_cards(seat);
1011                assert_eq!(hand & known, known);
1012            }
1013        }
1014    }
1015
1016    #[test]
1017    fn a_dangerous_pass_is_more_likely() {
1018        fn hand(text: &str) -> Hand {
1019            text.parse().expect("a valid hand")
1020        }
1021        let plausible = hand("2345.6789.TJ.QKA");
1022        let modeled: Hand = greedy_pass(plausible, HeuristicConfig::default())
1023            .into_iter()
1024            .collect();
1025        let quiet = hand("234...");
1026        let default = HeuristicConfig::default();
1027        assert_eq!(
1028            pass_observation_likelihood(plausible, modeled, default),
1029            1.0
1030        );
1031        assert!(pass_observation_likelihood(plausible, quiet, default) < 1.0);
1032    }
1033
1034    #[test]
1035    fn the_pass_model_reaches_every_role() {
1036        // The knob is worthless if it stops at the struct, and the
1037        // byte-identical arena CSV cannot tell a wired knob from an unwired
1038        // one — it only pins the default path.  So exercise all three roles
1039        // through the bot, with a config that re-sorts almost any hand.
1040        let wild = HeuristicConfig {
1041            heart_weight: 9,
1042            ..HeuristicConfig::default()
1043        };
1044        let bot = |config| MonteCarloBot::new(StdRng::seed_from_u64(4)).pass_model(config);
1045
1046        let mut deal = StdRng::seed_from_u64(5);
1047        let mut table = Table::deal(Rules::new(), PassDirection::Left, &mut deal);
1048        let me = table.turn().expect("passing starts at North");
1049
1050        // Ranking (and so candidate 0, the incumbent): a pure function of
1051        // the view and the config, no rollouts.
1052        let labels = |config| {
1053            bot(config)
1054                .candidates(&table.view(me))
1055                .into_iter()
1056                .map(|candidate| candidate.label)
1057                .collect::<Vec<String>>()
1058        };
1059        assert_ne!(labels(HeuristicConfig::default()), labels(wild));
1060
1061        // The rollout population: at `Phase::Passing` nothing is observed,
1062        // so both configs draw the identical hands from the identical seed
1063        // and the modeled pass is the only thing that can differ.
1064        let population = |config| {
1065            bot(config)
1066                .sample_worlds(&table.view(me), 1)
1067                .first()
1068                .expect("a pass-phase world samples")
1069                .passed(me.left())
1070        };
1071        assert_ne!(
1072            population(HeuristicConfig::default()),
1073            population(wild),
1074            "the modeled opponents ignored the pass model"
1075        );
1076
1077        // The observation model, once the exchange resolves.  Both configs
1078        // consume the same RNG prefix and exactly one uniform per attempt,
1079        // so they differ only in the `0.75^misses` threshold they compare
1080        // against — and so in how many samples they reject.
1081        for _ in 0..4 {
1082            table
1083                .step(&mut HeuristicBot::new())
1084                .expect("greedy passes are legal");
1085        }
1086        let view = table.view(me);
1087        assert!(view.received().is_some(), "the observation model is live");
1088        let rejects = |config| {
1089            let mut bot = bot(config);
1090            (0..64)
1091                .filter(|_| bot.sample_hands(&view).is_none())
1092                .count()
1093        };
1094        assert_ne!(
1095            rejects(HeuristicConfig::default()),
1096            rejects(wild),
1097            "the observation model ignored the pass model"
1098        );
1099    }
1100
1101    #[test]
1102    fn reconstruction_replays_any_real_position() {
1103        // The omniscient reconstruction — original hands as a hold deal,
1104        // history replayed — must land on the real position, whatever the
1105        // real pass direction was.  This is the guard the gin engine needed
1106        // a whole sync-sim skill for.
1107        let mut rng = StdRng::seed_from_u64(7);
1108        for _ in 0..20 {
1109            let mut table = Table::deal(Rules::new(), PassDirection::Left, &mut rng);
1110            let mut bot = crate::HeuristicBot::new();
1111            for _ in 0..rng.random_range(4..30) {
1112                table.step(&mut bot).expect("greedy plays are legal");
1113            }
1114            let round = table.round();
1115            if round.phase() != Phase::Playing {
1116                continue;
1117            }
1118
1119            // Original hands: what each seat holds now plus what it played.
1120            let mut originals = [Hand::EMPTY; 4];
1121            for seat in Seat::ALL {
1122                let mut own = round.hand(seat);
1123                for trick in round.tricks().iter().copied().chain(round.current_trick()) {
1124                    if let Some(card) = trick.card_from(seat) {
1125                        own.insert(card);
1126                    }
1127                }
1128                originals[seat as usize] = own;
1129            }
1130
1131            let mut replay = Round::from_deal(*round.rules(), PassDirection::Hold, originals)
1132                .expect("original hands partition the deck");
1133            for trick in round.tricks().iter().copied().chain(round.current_trick()) {
1134                for (seat, card) in trick.plays() {
1135                    replay.play(seat, card).expect("the real history is legal");
1136                }
1137            }
1138            assert_eq!(replay.tricks(), round.tricks());
1139            assert_eq!(replay.current_trick(), round.current_trick());
1140            for seat in Seat::ALL {
1141                assert_eq!(replay.hand(seat), round.hand(seat));
1142            }
1143        }
1144    }
1145
1146    #[test]
1147    fn seeded_bots_repeat_their_decisions() {
1148        let table = mid_round();
1149        let me = table.turn().expect("a mid-round table has a mover");
1150        let decide = |seed| {
1151            let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(seed)).samples(16);
1152            bot.play_card(&table.view(me))
1153        };
1154        assert_eq!(decide(3), decide(3));
1155    }
1156
1157    #[test]
1158    fn equity_is_terminal_at_the_target() {
1159        let rules = Rules::new();
1160        let me = Seat::North;
1161        // North ends lowest when West crosses: a sole win.
1162        let win = equity(&[0, 10, 10, 6], me, [50, 60, 70, 95], &rules);
1163        assert_eq!(win, 1.0);
1164        // North crosses alone: a sole last.
1165        let loss = equity(&[13, 13, 0, 0], me, [95, 0, 0, 0], &rules);
1166        assert_eq!(loss, 0.0);
1167        // The middle placements pay their matchpoints over three.
1168        let second = equity(&[0, 0, 13, 13], me, [50, 40, 60, 95], &rules);
1169        assert_eq!(second, 2.0 / 3.0);
1170        let third = equity(&[0, 0, 13, 13], me, [50, 40, 30, 95], &rules);
1171        assert_eq!(third, 1.0 / 3.0);
1172        // Ties average: two crowns share 2½ matchpoints, four share 1½.
1173        let crowns = equity(&[0, 0, 13, 13], me, [50, 50, 60, 95], &rules);
1174        assert_eq!(crowns, 5.0 / 6.0);
1175        let level = equity(&[13, 7, 3, 3], me, [87, 93, 97, 97], &rules);
1176        assert_eq!(level, 0.5);
1177        // Exactly the target ends the game; one point short stays a round.
1178        assert_eq!(equity(&[13, 13, 0, 0], me, [87, 0, 0, 0], &rules), 0.0);
1179        let running = equity(&[13, 13, 0, 0], me, [86, 0, 0, 0], &rules);
1180        assert!((0.25..=0.75).contains(&running), "{running} is mid-game");
1181    }
1182
1183    #[test]
1184    fn equity_orders_round_outcomes_mid_game() {
1185        let rules = Rules::new();
1186        let me = Seat::North;
1187        let level = [0u16; 4];
1188        let clean = equity(&[0, 13, 13, 0], me, level, &rules);
1189        let queen = equity(&[13, 13, 0, 0], me, level, &rules);
1190        let moon = equity(&[0, 26, 26, 26], me, level, &rules);
1191        let mooned = equity(&[26, 0, 26, 26], me, level, &rules);
1192        assert!(moon > clean && clean > queen);
1193        // Relative to the field, eating the queen and being mooned cost
1194        // the same 8⅔-point margin — the measure is zero-sum on purpose.
1195        assert!((queen - mooned).abs() < 1e-12);
1196        for value in [clean, queen, moon, mooned] {
1197            assert!((0.25..=0.75).contains(&value), "{value} is mid-game");
1198        }
1199    }
1200
1201    #[test]
1202    fn beats_requires_a_clear_margin() {
1203        let base: Vec<f64> = (0..32).map(|i| f64::from(i % 5)).collect();
1204        let noisy: Vec<f64> = base
1205            .iter()
1206            .enumerate()
1207            .map(|(i, x)| x + if i % 2 == 0 { 1.05 } else { -0.95 })
1208            .collect();
1209        assert!(!beats(&noisy, &base, 1.5));
1210        // The same slim edge passes a gate loose enough to trust it.
1211        assert!(beats(&noisy, &base, 0.1));
1212
1213        let better: Vec<f64> = base.iter().map(|x| x + 1.0).collect();
1214        assert!(beats(&better, &base, 1.5));
1215        assert!(!beats(&base, &better, 1.5));
1216        assert!(!beats(&base, &base, 1.5));
1217    }
1218
1219    #[test]
1220    fn shoot_candidate_requires_a_strict_majority() {
1221        let candidates = [
1222            Candidate {
1223                label: "incumbent".into(),
1224                choice: Choice::Play(Card::TWO_OF_CLUBS),
1225                shoot: false,
1226            },
1227            Candidate {
1228                label: "shoot".into(),
1229                choice: Choice::Play(Card::TWO_OF_CLUBS),
1230                shoot: true,
1231            },
1232        ];
1233        let incumbent = vec![0.0; 4];
1234        let challenger = vec![1.0; 4];
1235        let mut scored = vec![(incumbent, 0.0, 0), (challenger, 0.0, 2)];
1236
1237        assert_eq!(recommended(&scored, &candidates, 1.5), 0);
1238        scored[1].2 = 3;
1239        assert_eq!(recommended(&scored, &candidates, 1.5), 1);
1240    }
1241
1242    #[test]
1243    fn only_an_unresolved_best_challenger_is_contested() {
1244        let base: Vec<f64> = (0..32).map(|i| f64::from(i % 5)).collect();
1245        let uncertain: Vec<f64> = base
1246            .iter()
1247            .enumerate()
1248            .map(|(i, x)| x + if i % 2 == 0 { 1.05 } else { -0.95 })
1249            .collect();
1250        let better: Vec<f64> = base.iter().map(|x| x + 1.0).collect();
1251        let worse: Vec<f64> = base.iter().map(|x| x - 1.0).collect();
1252        let scores = |challenger| vec![(base.clone(), 0.0, 0), (challenger, 0.0, 0)];
1253
1254        assert!(contested(&scores(uncertain), &[1], 1.5));
1255        assert!(!contested(&scores(better), &[1], 1.5));
1256        assert!(!contested(&scores(worse), &[1], 1.5));
1257        assert!(!contested(&scores(base.clone()), &[], 1.5));
1258    }
1259
1260    #[test]
1261    fn play_candidates_collapse_touching_ranks() {
1262        let table = fixed_table();
1263        // North leads trick 1: only the 2♣ is legal, no real choice.
1264        let north = table.turn().expect("a fresh hold deal has a leader");
1265        assert_eq!(play_candidates(&table.view(north)).len(), 0);
1266    }
1267
1268    #[test]
1269    fn play_candidates_keep_queen_distinct_from_neighbors() {
1270        // South must follow a led spade holding only J♠ and Q♠. They are
1271        // rank-adjacent, but Q♠ is worth 13 penalty points and J♠ nothing —
1272        // they are not one candidate, and the solver must not refuse the read.
1273        let hand = |cards: &str| -> Hand {
1274            cards
1275                .split_whitespace()
1276                .map(|c| c.parse().expect("valid card"))
1277                .collect()
1278        };
1279        let hands = [
1280            hand("2C 6C 7C 8C 6D 7D 8D 9D 6H 7H 8H 3S 4S"), // North: leads 2♣
1281            hand("9C TC AC TD JD QD 9H TH JH 2S 5S 6S 7S"), // East: wins T1, leads a spade
1282            hand("3C 4C 5C 2D 3D 4D 5D 2H 3H 4H 5H JS QS"), // South: only spades are J♠ Q♠
1283            hand("JC QC KC KD AD QH KH AH 8S 9S TS KS AS"), // West
1284        ];
1285        let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
1286            .expect("a full partition deals");
1287        for (seat, card) in [
1288            (Seat::North, "2C"),
1289            (Seat::East, "AC"),
1290            (Seat::South, "3C"),
1291            (Seat::West, "JC"),
1292            (Seat::East, "2S"), // East won trick 1; now it leads a low spade
1293        ] {
1294            round
1295                .play(seat, card.parse().expect("valid card"))
1296                .expect("a legal scripted play");
1297        }
1298
1299        let table = Table::new(round);
1300        assert_eq!(
1301            table.turn(),
1302            Some(Seat::South),
1303            "South is to follow the spade"
1304        );
1305        let view = table.view(Seat::South);
1306
1307        let cands = play_candidates(&view);
1308        assert_eq!(
1309            cands.iter().filter(|c| !c.shoot).count(),
1310            2,
1311            "Q♠ must not collapse into J♠"
1312        );
1313        assert!(
1314            cands
1315                .iter()
1316                .any(|c| matches!(c.choice, Choice::Play(card) if card == Card::QUEEN_OF_SPADES)),
1317            "Q♠ is weighed as its own play",
1318        );
1319
1320        let mut solver = MonteCarloBot::new(StdRng::seed_from_u64(7)).samples(64);
1321        assert!(!solver.assess(&view).is_empty(), "the hint offers a read");
1322    }
1323
1324    #[test]
1325    fn assess_lists_an_all_equivalent_class_rather_than_refusing() {
1326        // South follows a led spade holding only 5♠ and 7♠.  From the hand
1327        // they look like two separate plays; but 6♠ is gone in a completed
1328        // trick, so they are interchangeable — one class, one candidate.  A
1329        // human cannot read that off the hand, so the hint must still list
1330        // both tied instead of going blank.
1331        let hand = |cards: &str| -> Hand {
1332            cards
1333                .split_whitespace()
1334                .map(|c| c.parse().expect("valid card"))
1335                .collect()
1336        };
1337        let hands = [
1338            hand("2C 3C 4C 5C 2S 3S 4S 2D 3D 4D 5D 2H 3H"), // North: leads 2♣
1339            hand("AC KC QC 9S 6D 7D 8D 9D 5H 6H 7H 8H 9H"), // East: wins T1, leads 9♠
1340            hand("6C 7C 8C 9C TC JC 5S 7S TD JD QD KD AD"), // South: spades are 5♠ 7♠ only
1341            hand("6S 8S TS JS QS KS AS 4H TH JH QH KH AH"), // West: club-void, sheds 6♠
1342        ];
1343        let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
1344            .expect("a full partition deals");
1345        for (seat, card) in [
1346            (Seat::North, "2C"),
1347            (Seat::East, "AC"),
1348            (Seat::South, "6C"),
1349            (Seat::West, "6S"), // the gap card, gone in a completed trick
1350            (Seat::East, "9S"), // East won trick 1; it leads above the 5-7 span
1351        ] {
1352            round
1353                .play(seat, card.parse().expect("valid card"))
1354                .expect("a legal scripted play");
1355        }
1356
1357        let table = Table::new(round);
1358        assert_eq!(
1359            table.turn(),
1360            Some(Seat::South),
1361            "South is to follow the spade"
1362        );
1363        let view = table.view(Seat::South);
1364
1365        // One equivalence class, so the bot weighs a single candidate...
1366        assert_eq!(
1367            play_candidates(&view).len(),
1368            1,
1369            "5♠ and 7♠ collapse across the played 6♠",
1370        );
1371
1372        // ...yet the hint lists both legal plays, tied and flagged.
1373        let mut solver = MonteCarloBot::new(StdRng::seed_from_u64(11)).samples(64);
1374        let rows = solver.assess(&view);
1375        assert_eq!(rows.len(), 2, "both equivalent spades are shown");
1376        assert!(
1377            rows.iter().all(|r| r.recommended),
1378            "an equivalent class is all-tied",
1379        );
1380        assert!(
1381            rows[0].equity == rows[1].equity && rows[0].ev == rows[1].ev,
1382            "equivalent plays carry the same read",
1383        );
1384    }
1385
1386    #[test]
1387    fn a_rank_in_the_live_trick_does_not_bridge_a_sequence() {
1388        // South follows a led J♦ holding 7♦ T♦ Q♦ K♦ A♦, with 8♦ and 9♦ gone
1389        // in trick 1.  The J♦ is committed but still contests THIS trick:
1390        // Q♦ K♦ A♦ take it and 7♦ T♦ do not, so the holding is two classes,
1391        // not one.  Counting the live J♦ as gone collapsed all five.
1392        let hand = |cards: &str| -> Hand {
1393            cards
1394                .split_whitespace()
1395                .map(|c| c.parse().expect("valid card"))
1396                .collect()
1397        };
1398        let hands = [
1399            hand("9D 2D 3D 4D 2S 3S 4S 5S 6S 2H 3H 4H 5H"), // North: club-void, sheds 9♦
1400            hand("TC JC QC KC AC JD QS KS AS JH QH KH AH"), // East: wins T1, leads J♦
1401            hand("2C 3C 4C 5C 6C 7C 8C 9C 7D TD QD KD AD"), // South: leads 2♣, follows the J♦
1402            hand("8D 5D 6D 7S 8S 9S TS JS 6H 7H 8H 9H TH"), // West: club-void, sheds 8♦
1403        ];
1404        let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
1405            .expect("a full partition deals");
1406        for (seat, card) in [
1407            (Seat::South, "2C"),
1408            (Seat::West, "8D"),
1409            (Seat::North, "9D"),
1410            (Seat::East, "AC"),
1411            (Seat::East, "JD"), // East won trick 1; now it leads into the gap
1412        ] {
1413            round
1414                .play(seat, card.parse().expect("valid card"))
1415                .expect("a legal scripted play");
1416        }
1417
1418        let table = Table::new(round);
1419        assert_eq!(
1420            table.turn(),
1421            Some(Seat::South),
1422            "South is to follow the diamond"
1423        );
1424        let view = table.view(Seat::South);
1425
1426        let plays: Vec<Card> = play_candidates(&view)
1427            .iter()
1428            .filter(|c| !c.shoot)
1429            .filter_map(|c| match c.choice {
1430                Choice::Play(card) => Some(card),
1431                Choice::Pass(_) => None,
1432            })
1433            .collect();
1434        let jack: Card = "JD".parse().expect("valid card");
1435        assert!(
1436            plays.iter().any(|card| card.rank > jack.rank),
1437            "a play that takes the trick is weighed: {plays:?}",
1438        );
1439        assert!(
1440            plays.iter().any(|card| card.rank < jack.rank),
1441            "a play that ducks the trick is weighed: {plays:?}",
1442        );
1443    }
1444
1445    #[test]
1446    fn void_respecting_worlds() {
1447        // Play until somebody shows a void, then check every sampled world
1448        // honors it.
1449        let mut rng = StdRng::seed_from_u64(21);
1450        let mut table = Table::deal(Rules::new(), PassDirection::Hold, &mut rng);
1451        let mut bot = crate::HeuristicBot::new();
1452        let (observer, void_seat, void_suit) = loop {
1453            table.step(&mut bot).expect("greedy plays are legal");
1454            let round = table.round();
1455            assert_eq!(round.phase(), Phase::Playing, "a void shows up first");
1456            let found = Seat::ALL.iter().find_map(|&seat| {
1457                let observer = round.turn()?;
1458                Suit::ASC
1459                    .into_iter()
1460                    .find(|&suit| observer != seat && table.view(observer).is_void(seat, suit))
1461                    .map(|suit| (observer, seat, suit))
1462            });
1463            if let Some(found) = found {
1464                break found;
1465            }
1466        };
1467
1468        let view = table.view(observer);
1469        let mut mc = MonteCarloBot::new(StdRng::seed_from_u64(2));
1470        for world in mc.sample_worlds(&view, 16) {
1471            assert_eq!(world.hand(void_seat)[void_suit], Holding::EMPTY);
1472        }
1473    }
1474
1475    #[test]
1476    fn assess_ranks_candidates_and_flags_the_bots_pick() {
1477        let table = mid_round();
1478        let me = table.turn().expect("a mid-round table has a mover");
1479        let view = table.view(me);
1480
1481        let mut solver = MonteCarloBot::new(StdRng::seed_from_u64(7)).samples(64);
1482        let mut chooser = MonteCarloBot::new(StdRng::seed_from_u64(7)).samples(64);
1483
1484        let rows = solver.assess(&view);
1485        if rows.is_empty() {
1486            // A forced spot: the chooser must agree it is forced.
1487            assert!(view.legal_plays().len() == 1 || play_candidates(&view).len() < 2);
1488            return;
1489        }
1490        for row in &rows {
1491            assert!((0.0..=1.0).contains(&row.equity));
1492            assert!(row.ev >= 0.0);
1493        }
1494        assert!(rows.windows(2).all(|w| w[0].equity >= w[1].equity));
1495        assert_eq!(rows.iter().filter(|r| r.recommended).count(), 1);
1496
1497        let picked = rows.iter().find(|r| r.recommended).expect("a flagged pick");
1498        let played = chooser.play_card(&view);
1499        assert!(
1500            picked.action.ends_with(&format!("play {played}")),
1501            "{} is the card {played} was picked for",
1502            picked.action,
1503        );
1504    }
1505
1506    #[test]
1507    fn pass_assessment_covers_twenty_triples() {
1508        let mut rng = StdRng::seed_from_u64(5);
1509        let table = Table::deal(Rules::new(), PassDirection::Left, &mut rng);
1510        let me = table.turn().expect("passing starts at North");
1511        let view = table.view(me);
1512        let cands = pass_candidates(&view, HeuristicConfig::default());
1513        assert!(cands.iter().filter(|c| !c.shoot).count() >= 20);
1514        assert_eq!(cands.iter().filter(|c| c.shoot).count(), 1, "the moon pass");
1515
1516        let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(6)).samples(16);
1517        let picks = bot.pass_cards(&view);
1518        assert_eq!(
1519            picks.into_iter().collect::<Hand>().len(),
1520            3,
1521            "three distinct cards"
1522        );
1523        for card in picks {
1524            assert!(view.hand().contains(card));
1525        }
1526        assert_eq!(bot.moon_passes(), 0);
1527    }
1528
1529    #[test]
1530    fn pass_candidate_zero_is_the_greedy_incumbent() {
1531        // The invariant the significance gate defends: candidate 0 is the
1532        // pass the policy would make unaided.  It used to hold by accident,
1533        // two sorts of the same key agreeing; the sequential policy rescores
1534        // against the shrinking hand and agrees only on the first card, so
1535        // the incumbent is now built rather than inferred.  This is the hand
1536        // where they part: flat ranks J♠ third, sequential takes 6♥.
1537        fn hand(text: &str) -> Hand {
1538            text.parse().expect("a valid hand")
1539        }
1540        let mine = hand("234679.2K.6A.68J");
1541        let mut hands = [mine, Hand::EMPTY, Hand::EMPTY, Hand::EMPTY];
1542        for (i, card) in (Hand::ALL - mine).into_iter().enumerate() {
1543            hands[1 + i % 3].insert(card);
1544        }
1545        let round = Round::from_deal(Rules::new(), PassDirection::Left, hands).unwrap();
1546        let table = Table::new(round);
1547        let config = HeuristicConfig::default();
1548
1549        let incumbent = greedy_pass(mine, config);
1550        let cands = pass_candidates(&table.view(Seat::North), config);
1551        assert!(
1552            matches!(cands[0].choice, Choice::Pass(triple) if triple == incumbent),
1553            "candidate 0 is not the greedy pass: {}",
1554            cands[0].label,
1555        );
1556
1557        // And it is offered once: the pool regenerates the same set, since
1558        // every card of it ranks inside the top six.
1559        let set: Hand = incumbent.into_iter().collect();
1560        assert_eq!(
1561            cands
1562                .iter()
1563                .filter(|candidate| !candidate.shoot)
1564                .filter(|candidate| matches!(candidate.choice, Choice::Pass(triple)
1565                    if triple.into_iter().collect::<Hand>() == set))
1566                .count(),
1567            1,
1568            "the pool re-rolled the incumbent as a second candidate",
1569        );
1570    }
1571
1572    #[test]
1573    fn pass_candidates_can_create_a_void_outside_the_top_six() {
1574        fn hand(text: &str) -> Hand {
1575            text.parse().expect("a valid hand")
1576        }
1577        let mine = hand("234.QKA.QKA.JQKA");
1578        let mut hands = [mine, Hand::EMPTY, Hand::EMPTY, Hand::EMPTY];
1579        for (i, card) in (Hand::ALL - mine).into_iter().enumerate() {
1580            hands[1 + i % 3].insert(card);
1581        }
1582        let round = Round::from_deal(Rules::new(), PassDirection::Left, hands).unwrap();
1583        let table = Table::new(round);
1584        let void = hand("234...");
1585        assert!(
1586            pass_candidates(&table.view(Seat::North), HeuristicConfig::default())
1587                .iter()
1588                .any(|candidate| matches!(candidate.choice, Choice::Pass(cards)
1589                if cards.into_iter().collect::<Hand>() == void))
1590        );
1591    }
1592
1593    #[test]
1594    fn a_hand_that_cannot_win_a_trick_does_not_try() {
1595        // The guard against the opposite failure.  A moon candidate is on
1596        // offer at every pass, so it has to lose on a hand with no length,
1597        // no ace and nothing above a five: the shot dies on trick two and
1598        // the rollout charges us for having kept the queen.
1599        fn hand(text: &str) -> Hand {
1600            text.parse().expect("a valid hand")
1601        }
1602        let hands = [
1603            hand("234.234.234.2345"), // North: the worst hand in the deck
1604            hand("5678.567.567.678"),
1605            hand("9TJ.89TJ.89T.9TJ"),
1606            hand("QKA.QKA.JQKA.QKA"),
1607        ];
1608        let round = Round::from_deal(Rules::new(), PassDirection::Left, hands)
1609            .expect("a full partition deals");
1610        let table = Table::new(round);
1611        let view = table.view(Seat::North);
1612
1613        let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(0xC0DE)).samples(128);
1614        let picked = bot
1615            .assess(&view)
1616            .into_iter()
1617            .find(|row| row.recommended)
1618            .expect("a flagged pick");
1619        assert!(
1620            !picked.action.starts_with("shoot"),
1621            "shot the moon holding nothing: {}",
1622            picked.action,
1623        );
1624    }
1625
1626    #[test]
1627    fn seeded_pick_is_identical_across_serial_and_parallel_builds() {
1628        // The `parallel` feature must not change a single decision: batch
1629        // results are collected in world order and reduced sequentially in
1630        // both builds.  CI runs the suite with and without the feature; a
1631        // failure in only one build means the parallel reduce stopped
1632        // being order-exact.  Re-pin the expected card whenever sampling
1633        // logic changes.
1634        let table = mid_round();
1635        let me = table.turn().expect("a mid-round table has a mover");
1636        let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(11)).samples(64);
1637        let first = bot.play_card(&table.view(me));
1638        let mut again = MonteCarloBot::new(StdRng::seed_from_u64(11)).samples(64);
1639        assert_eq!(first, again.play_card(&table.view(me)));
1640    }
1641
1642    #[test]
1643    fn breaks_a_moon_the_rollouts_never_see() {
1644        // The rollout policy models every opponent as a greedy ducker who
1645        // never shoots, so a moon in progress is invisible to the search.
1646        // Drive a position where East has already swept the Q♠ (13 points),
1647        // then confirm the MC bot takes the trick to break the sweep instead
1648        // of ducking the way its own rollout policy would.
1649        fn card(text: &str) -> Card {
1650            text.parse().expect("a valid card")
1651        }
1652        fn hand(cards: &[&str]) -> Hand {
1653            cards.iter().map(|c| card(c)).collect()
1654        }
1655        struct Fixed(Card);
1656        impl Strategy for Fixed {
1657            fn pass_cards(&mut self, _: &View<'_>) -> [Card; 3] {
1658                unreachable!()
1659            }
1660            fn play_card(&mut self, _: &View<'_>) -> Card {
1661                self.0
1662            }
1663        }
1664
1665        let hands = [
1666            // North: leads 2♣, and ends holding S3 (duck) vs SK (break).
1667            hand(&[
1668                "2♣", "3♣", "3♠", "K♠", "A♦", "3♥", "4♥", "5♥", "6♥", "7♥", "8♥", "9♥", "T♥",
1669            ]),
1670            // East: wins two club tricks and scoops the dumped Q♠.
1671            hand(&[
1672                "A♣", "K♣", "Q♣", "J♣", "5♠", "6♠", "7♠", "8♠", "9♠", "T♠", "J♠", "A♠", "2♦",
1673            ]),
1674            // South: void in clubs, dumps Q♠ into East's second trick.
1675            hand(&[
1676                "Q♠", "2♠", "4♠", "J♥", "Q♥", "K♥", "A♥", "3♦", "4♦", "5♦", "6♦", "7♦", "8♦",
1677            ]),
1678            // West: void in spades, never overtakes the sweep.
1679            hand(&[
1680                "4♣", "5♣", "6♣", "7♣", "8♣", "9♣", "T♣", "9♦", "T♦", "J♦", "Q♦", "K♦", "2♥",
1681            ]),
1682        ];
1683        let round = Round::from_deal(Rules::new(), PassDirection::Hold, hands).unwrap();
1684        let mut table = Table::new(round);
1685        let script = [
1686            (Seat::North, "2♣"), // trick 1: clubs, East wins with A♣
1687            (Seat::East, "A♣"),
1688            (Seat::South, "3♦"), // void in clubs, sheds a diamond (no T1 penalties)
1689            (Seat::West, "4♣"),
1690            (Seat::East, "K♣"), // trick 2: East leads, South dumps the queen
1691            (Seat::South, "Q♠"),
1692            (Seat::West, "5♣"),
1693            (Seat::North, "3♣"),
1694            (Seat::East, "5♠"), // trick 3: East leads a low spade into North
1695            (Seat::South, "4♠"),
1696            (Seat::West, "2♥"), // keep the trick costly, so plain greedy ducks
1697        ];
1698        for (seat, text) in script {
1699            assert_eq!(table.turn(), Some(seat));
1700            table.step(&mut Fixed(card(text))).unwrap();
1701        }
1702
1703        let view = table.view(Seat::North);
1704        assert_eq!(view.points_taken(Seat::East), 13, "East swept the queen");
1705        // Greedy — the rollout policy — would duck with the 3♠; the moon
1706        // defense overrides it to break the sweep with the cheapest winner.
1707        assert_eq!(
1708            greedy_play(
1709                view.legal_plays(),
1710                view.current_trick().unwrap(),
1711                view.played()
1712            ),
1713            card("3♠")
1714        );
1715        let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(1)).samples(64);
1716        assert_eq!(bot.play_card(&view), card("K♠"));
1717        assert_eq!(bot.moon_attempts(), 0);
1718
1719        // East already holds points, so the moon is dead for North and the
1720        // shoot candidate is not even generated.
1721        assert!(
1722            !play_candidates(&view).iter().any(|c| c.shoot),
1723            "a dead moon is not a candidate",
1724        );
1725    }
1726
1727    #[test]
1728    fn a_laydown_moon_is_rolled_as_one() {
1729        fn card(text: &str) -> Card {
1730            text.parse().expect("a valid card")
1731        }
1732        fn hand(text: &str) -> Hand {
1733            text.parse().expect("a valid hand")
1734        }
1735
1736        // North holds the top of every suit but diamonds, and never loses
1737        // the lead long enough for anyone to lead one.  East, void in
1738        // spades, discards on every spade lead — a heart under the greedy
1739        // policy, a diamond once the table knows it is defending a moon.
1740        let hands = [
1741            hand("QKA..QKA.29TJQKA"), // North: the monster, and the 2♠ ballast
1742            hand("2345.234567.234."), // East: holds the deuce, void in spades
1743            hand("6789.89T.567.456"),
1744            hand("TJ.JQKA.89TJ.378"),
1745        ];
1746        let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
1747            .expect("a full partition deals");
1748        for (seat, text) in [(Seat::East, "2♣"), (Seat::South, "6♣"), (Seat::West, "T♣")] {
1749            round
1750                .play(seat, card(text))
1751                .expect("a legal scripted play, North last to the deuce");
1752        }
1753
1754        let ace = Choice::Play(card("A♣"));
1755        let mut continuation = round.clone();
1756        assert_eq!(
1757            ace.roll(&mut continuation, Seat::North, true).shooter(),
1758            Some(Seat::North),
1759            "the shooting continuation takes all thirteen tricks",
1760        );
1761        // End to end, against three bots that defend: the search has to find
1762        // the shot *and* carry it across all thirteen tricks.  The point-aware
1763        // greedy policy can also take this clean opening trick now, so the
1764        // fixture no longer requires the non-shoot continuation to fail.
1765        let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(3)).samples(64);
1766        let mut east = HeuristicBot::new();
1767        let mut south = HeuristicBot::new();
1768        let mut west = HeuristicBot::new();
1769        let result = Table::new(round)
1770            .play([&mut bot, &mut east, &mut south, &mut west])
1771            .expect("no seat cheats");
1772        assert_eq!(result.shooter(), Some(Seat::North), "the bot shot it");
1773        assert_eq!(bot.moon_attempts(), 1);
1774    }
1775}