use crate::heuristic::{
greedy_pass, greedy_play, moon_defense, pass_key, rollout_play, shoot_play,
};
use crate::{HeuristicConfig, Strategy, View};
use hearts::{Card, Hand, PassDirection, Phase, Rank, Round, RoundResult, Rules, Seat, Suit};
use rand::{Rng, RngExt as _};
const MAX_CANDIDATES: usize = 8;
const PASS_POOL: usize = 6;
const BATCH: usize = 32;
const MAX_WIDTH_MULTIPLIER: usize = 3;
type Scored = (Vec<f64>, f64, u32);
struct Candidate {
label: String,
choice: Choice,
shoot: bool,
}
#[derive(Clone, Copy)]
enum Choice {
Pass([Card; 3]),
Play(Card),
}
impl Choice {
fn roll(self, round: &mut Round, me: Seat, shoot: bool) -> RoundResult {
match self {
Self::Pass(cards) => round
.pass(me, cards.into_iter().collect())
.expect("a candidate pass is legal in every sampled world"),
Self::Play(card) => round
.play(me, card)
.expect("a candidate play is legal in every sampled world"),
}
let mut played = round.played();
while let Some(seat) = round.turn() {
let card = rollout_play(round, seat, shoot.then_some(me), played);
round
.play(seat, card)
.expect("the rollout policy picks from legal_plays");
played.insert(card);
}
round.result().expect("a turnless round is finished")
}
}
pub struct MonteCarloBot<R: Rng> {
rng: R,
samples: u32,
gate: f64,
pass_model: HeuristicConfig,
shooting: bool,
moon_attempts: u32,
moon_passes: u32,
}
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct Assessment {
pub action: String,
pub equity: f64,
pub ev: f64,
pub recommended: bool,
}
impl<R: Rng> MonteCarloBot<R> {
pub const fn new(rng: R) -> Self {
Self {
rng,
samples: 128,
gate: 1.5,
pass_model: HeuristicConfig::new(),
shooting: false,
moon_attempts: 0,
moon_passes: 0,
}
}
#[must_use]
pub const fn samples(mut self, samples: u32) -> Self {
self.samples = samples;
self
}
#[must_use]
pub const fn gate(mut self, gate: f64) -> Self {
self.gate = gate;
self
}
#[must_use]
pub const fn pass_model(mut self, config: HeuristicConfig) -> Self {
self.pass_model = config;
self
}
pub const fn moon_attempts(&self) -> u32 {
self.moon_attempts
}
pub const fn moon_passes(&self) -> u32 {
self.moon_passes
}
fn sample_hands(&mut self, view: &View<'_>) -> Option<[Hand; 4]> {
let me = view.seat();
let mut hands = [Hand::EMPTY; 4];
let mut room = [0usize; 4];
hands[me as usize] = view.hand();
for seat in Seat::ALL {
if seat != me {
let known = view.known_cards(seat);
hands[seat as usize] = known;
let size = if view.phase() == Phase::Passing {
13
} else {
view.hand_len(seat)
};
room[seat as usize] = size - known.len();
}
}
let mut cards: Vec<Card> = view.unseen().into_iter().collect();
for i in (1..cards.len()).rev() {
let j = self.rng.random_range(0..=i);
cards.swap(i, j);
}
let allowed = |card: Card, seat: Seat| seat != me && !view.is_void(seat, card.suit);
cards.sort_by_key(|&card| Seat::ALL.iter().filter(|&&s| allowed(card, s)).count());
fn place(
cards: &[Card],
allowed: &impl Fn(Card, Seat) -> bool,
hands: &mut [Hand; 4],
room: &mut [usize; 4],
rng: &mut (impl Rng + ?Sized),
) -> bool {
let Some((&card, rest)) = cards.split_first() else {
return true;
};
let mut order = Seat::ALL;
for i in (1..4).rev() {
let j = rng.random_range(0..=i);
order.swap(i, j);
}
for seat in order {
if room[seat as usize] > 0 && allowed(card, seat) {
room[seat as usize] -= 1;
hands[seat as usize].insert(card);
if place(rest, allowed, hands, room, rng) {
return true;
}
hands[seat as usize].remove(card);
room[seat as usize] += 1;
}
}
false
}
if !place(&cards, &allowed, &mut hands, &mut room, &mut self.rng) {
return None;
}
if let Some(received) = view.received() {
let giver = view.direction().giver(me);
let mut plausible = hands[giver as usize] | received;
for trick in view.tricks().iter().copied().chain(view.current_trick()) {
if let Some(card) = trick.card_from(giver) {
plausible.insert(card);
}
}
let likelihood = pass_observation_likelihood(plausible, received, self.pass_model);
if self.rng.random::<f64>() > likelihood {
return None;
}
}
Some(hands)
}
fn sample_world(&mut self, view: &View<'_>) -> Option<Round> {
let me = view.seat();
let hands = self.sample_hands(view)?;
if view.phase() == Phase::Passing {
let mut round = Round::from_deal(*view.rules(), view.direction(), hands).ok()?;
for seat in Seat::ALL {
if seat != me {
let pass: Hand = greedy_pass(hands[seat as usize], self.pass_model)
.into_iter()
.collect();
round.pass(seat, pass).ok()?;
}
}
return Some(round);
}
let mut originals = hands;
for trick in view.tricks().iter().copied().chain(view.current_trick()) {
for (seat, card) in trick.plays() {
originals[seat as usize].insert(card);
}
}
let mut round = Round::from_deal(*view.rules(), PassDirection::Hold, originals).ok()?;
for trick in view.tricks().iter().copied().chain(view.current_trick()) {
for (seat, card) in trick.plays() {
round.play(seat, card).ok()?;
}
}
Some(round)
}
fn sample_worlds(&mut self, view: &View<'_>, count: u32) -> Vec<Round> {
let mut worlds = Vec::with_capacity(count as usize);
let mut attempts = count * 4 + 64;
while worlds.len() < count as usize && attempts > 0 {
attempts -= 1;
if let Some(world) = self.sample_world(view) {
worlds.push(world);
}
}
worlds
}
fn candidates(&self, view: &View<'_>) -> Vec<Candidate> {
match view.phase() {
Phase::Passing => pass_candidates(view, self.pass_model),
Phase::Playing => play_candidates(view),
Phase::Finished => Vec::new(),
}
}
fn choose(&mut self, view: &View<'_>, candidates: &[Candidate]) -> Choice {
let scored = self.score(view, candidates);
let best = recommended(&scored, candidates, self.gate);
if candidates[best].shoot {
self.moon_passes += 1;
}
candidates[best].choice
}
fn score(&mut self, view: &View<'_>, candidates: &[Candidate]) -> Vec<Scored> {
let mut scored: Vec<Scored> = vec![(Vec::new(), 0.0, 0); candidates.len()];
let mut alive: Vec<usize> = (1..candidates.len()).collect();
for _ in 0..MAX_WIDTH_MULTIPLIER {
let worlds = self.sample_worlds(view, self.samples);
if worlds.is_empty() {
break;
}
score_worlds(
view,
&worlds,
candidates,
self.gate,
&mut scored,
&mut alive,
);
if !contested(&scored, &alive, self.gate) {
break;
}
}
scored
}
#[must_use]
pub fn assess(&mut self, view: &View<'_>) -> Vec<Assessment> {
let candidates = self.candidates(view);
if candidates.is_empty() {
return Vec::new();
}
let scored = self.score(view, &candidates);
if scored[0].0.is_empty() {
return Vec::new();
}
let mean = |(equities, ev_sum, _): &Scored| {
let n = equities.len() as f64;
(equities.iter().sum::<f64>() / n, ev_sum / n)
};
if candidates.len() == 1 {
let (equity, ev) = mean(&scored[0]);
return view
.legal_plays()
.into_iter()
.map(|card| Assessment {
action: format!("play {card}"),
equity,
ev,
recommended: true,
})
.collect();
}
let best = recommended(&scored, &candidates, self.gate);
let mut out: Vec<Assessment> = candidates
.iter()
.zip(&scored)
.enumerate()
.map(|(i, (candidate, score))| {
let (equity, ev) = mean(score);
Assessment {
action: candidate.label.clone(),
equity,
ev,
recommended: i == best,
}
})
.collect();
out.sort_by(|a, b| b.equity.total_cmp(&a.equity));
out
}
}
fn pass_observation_likelihood(plausible: Hand, received: Hand, config: HeuristicConfig) -> f64 {
let modeled: Hand = greedy_pass(plausible, config).into_iter().collect();
let misses = 3 - (modeled & received).len() as i32;
0.75f64.powi(misses)
}
fn push_new(triples: &mut Vec<[Card; 3]>, triple: [Card; 3]) {
let set: Hand = triple.into_iter().collect();
if !triples
.iter()
.any(|old| old.iter().copied().collect::<Hand>() == set)
{
triples.push(triple);
}
}
fn pass_candidates(view: &View<'_>, config: HeuristicConfig) -> Vec<Candidate> {
let hand = view.hand();
let mut ranked: Vec<Card> = hand.into_iter().collect();
ranked.sort_unstable_by_key(|&card| core::cmp::Reverse(pass_key(hand, card, config)));
let mut ducker = config;
ducker.queen_insurance = 0;
let mut ballast: Vec<Card> = hand.into_iter().collect();
ballast.sort_unstable_by_key(|&card| core::cmp::Reverse(pass_key(hand, card, ducker)));
let losers: [Card; 3] = ballast[ballast.len() - 3..]
.try_into()
.expect("a passing hand holds thirteen cards");
let pool = &ranked[..ranked.len().min(PASS_POOL)];
let mut triples = Vec::<[Card; 3]>::with_capacity(24);
triples.push(greedy_pass(hand, config));
for i in 0..pool.len() {
for j in i + 1..pool.len() {
for k in j + 1..pool.len() {
push_new(&mut triples, [pool[i], pool[j], pool[k]]);
}
}
}
for suit in Suit::ASC.into_iter().filter(|&suit| suit != Suit::Spades) {
let suited: Vec<Card> = hand[suit].iter().map(|rank| Card { suit, rank }).collect();
if suited.is_empty() || suited.len() > 3 {
continue;
}
let mut cards = suited;
cards.extend(
ranked
.iter()
.copied()
.filter(|card| card.suit != suit)
.take(3 - cards.len()),
);
push_new(
&mut triples,
cards.try_into().expect("a passing hand has filler"),
);
}
let mut out: Vec<Candidate> = triples
.into_iter()
.map(|triple| Candidate {
label: format!("pass {} {} {}", triple[0], triple[1], triple[2]),
choice: Choice::Pass(triple),
shoot: false,
})
.collect();
out.push(Candidate {
label: format!("shoot, pass {} {} {}", losers[0], losers[1], losers[2]),
choice: Choice::Pass(losers),
shoot: true,
});
out
}
fn play_candidates(view: &View<'_>) -> Vec<Candidate> {
let legal = view.legal_plays();
if legal.len() < 2 {
return Vec::new();
}
let trick = view.current_trick().expect("a play decision has a trick");
let played = view.played();
let incumbent = greedy_play(legal, trick, played);
let seen = view.hand() | (played - trick.cards());
let mut reps = vec![incumbent];
for suit in Suit::ASC {
let mut group: Vec<Rank> = Vec::new();
let flush = |group: &mut Vec<Rank>, reps: &mut Vec<Card>| {
if let Some(&low) = group.first() {
let card = |rank| Card { suit, rank };
if !group.iter().any(|&rank| card(rank) == incumbent) {
reps.push(card(low));
}
}
group.clear();
};
let mut prev: Option<Rank> = None;
for rank in legal[suit] {
if let Some(prev) = prev {
let same_value =
(Card { suit, rank: prev }).points() == (Card { suit, rank }).points();
let contiguous = same_value
&& (prev.get() + 1..rank.get()).all(|gap| seen[suit].contains(Rank::new(gap)));
if !contiguous {
flush(&mut group, &mut reps);
}
}
group.push(rank);
prev = Some(rank);
}
flush(&mut group, &mut reps);
}
reps.truncate(MAX_CANDIDATES);
let mut out: Vec<Candidate> = reps
.into_iter()
.map(|card| Candidate {
label: format!("play {card}"),
choice: Choice::Play(card),
shoot: false,
})
.collect();
let alive = Seat::ALL
.into_iter()
.all(|seat| seat == view.seat() || view.points_taken(seat) == 0);
if alive && out.len() > 1 {
let card = shoot_play(legal, trick, played);
out.push(Candidate {
label: format!("shoot, play {card}"),
choice: Choice::Play(card),
shoot: true,
});
}
out
}
fn score_worlds(
view: &View<'_>,
worlds: &[Round],
candidates: &[Candidate],
gate: f64,
scored: &mut [Scored],
alive: &mut Vec<usize>,
) {
let me = view.seat();
let rules = view.rules();
let standing = absolute_standing(me, view.game_scores());
let eval = |candidate: &Candidate, world: &Round, scratch: &mut Round| {
scratch.clone_from(world);
let result = candidate.choice.roll(scratch, me, candidate.shoot);
let moon = u32::from(result.shooter() == Some(me));
let scores = result.scores(rules);
(
equity(&scores, me, standing, rules),
f64::from(scores[me as usize]),
moon,
)
};
#[cfg(not(feature = "parallel"))]
let mut scratch = worlds.first().cloned();
let mut done = 0;
while done < worlds.len() {
let batch = &worlds[done..worlds.len().min(done + done.max(BATCH))];
for &i in std::iter::once(&0).chain(alive.iter()) {
let candidate = &candidates[i];
#[cfg(feature = "parallel")]
let results: Vec<(f64, f64, u32)> = {
use rayon::prelude::*;
batch
.par_iter()
.map_init(
|| batch[0].clone(),
|scratch, world| eval(candidate, world, scratch),
)
.collect()
};
#[cfg(not(feature = "parallel"))]
let results = batch.iter().map(|world| {
eval(
candidate,
world,
scratch
.as_mut()
.expect("a non-empty batch has a scratch round"),
)
});
let (equities, ev_sum, moons) = &mut scored[i];
for (equity, points, moon) in results {
equities.push(equity);
*ev_sum += points;
*moons += moon;
}
}
done += batch.len();
alive.retain(|&i| !beats(&scored[0].0, &scored[i].0, gate));
if alive.is_empty() {
break;
}
}
}
fn contested(scored: &[Scored], alive: &[usize], gate: f64) -> bool {
let mean = |e: &[f64]| e.iter().sum::<f64>() / e.len() as f64;
let defend = &scored[0].0;
if alive.iter().any(|&i| beats(&scored[i].0, defend, gate)) {
return false;
}
alive
.iter()
.copied()
.max_by(|&a, &b| mean(&scored[a].0).total_cmp(&mean(&scored[b].0)))
.is_some_and(|best| !beats(defend, &scored[best].0, gate))
}
fn recommended(scored: &[Scored], candidates: &[Candidate], gate: f64) -> usize {
let mean = |e: &[f64]| e.iter().sum::<f64>() / e.len() as f64;
let likely = |i: usize| 2 * scored[i].2 as usize > scored[i].0.len();
let defend = &scored[0].0;
(1..scored.len())
.filter(|&i| beats(&scored[i].0, defend, gate))
.filter(|&i| !candidates[i].shoot || likely(i))
.max_by(|&a, &b| mean(&scored[a].0).total_cmp(&mean(&scored[b].0)))
.unwrap_or(0)
}
fn beats(challenger: &[f64], incumbent: &[f64], gate: f64) -> bool {
let n = challenger.len() as f64;
let mean = challenger
.iter()
.zip(incumbent)
.map(|(c, i)| c - i)
.sum::<f64>()
/ n;
if mean <= 0.0 {
return false;
}
let var = challenger
.iter()
.zip(incumbent)
.map(|(c, i)| (c - i - mean).powi(2))
.sum::<f64>()
/ n;
mean > gate * (var / n).sqrt()
}
fn absolute_standing(me: Seat, relative: [u16; 4]) -> [u16; 4] {
let mut standing = [0; 4];
standing[me as usize] = relative[0];
standing[me.left() as usize] = relative[1];
standing[me.across() as usize] = relative[2];
standing[me.right() as usize] = relative[3];
standing
}
fn equity(scores: &[u16; 4], me: Seat, standing: [u16; 4], rules: &Rules) -> f64 {
let mut totals = standing;
for seat in Seat::ALL {
let total = &mut totals[seat as usize];
*total = total.saturating_add(scores[seat as usize]);
}
if totals.iter().any(|&total| total >= rules.game_target) {
let mine = totals[me as usize];
let ahead = totals.iter().filter(|&&total| total < mine).count();
let share = totals.iter().filter(|&&total| total == mine).count();
return (6 - 2 * ahead - (share - 1)) as f64 / 6.0;
}
let mine = f64::from(scores[me as usize]);
let others: f64 = Seat::ALL
.iter()
.filter(|&&seat| seat != me)
.map(|&seat| f64::from(scores[seat as usize]))
.sum::<f64>()
/ 3.0;
0.5 + (others - mine) / 112.0
}
impl<R: Rng> Strategy for MonteCarloBot<R> {
fn pass_cards(&mut self, view: &View<'_>) -> [Card; 3] {
let candidates = self.candidates(view);
match self.choose(view, &candidates) {
Choice::Pass(cards) => cards,
Choice::Play(_) => unreachable!("the passing phase yields pass choices"),
}
}
fn play_card(&mut self, view: &View<'_>) -> Card {
if let Some(card) = moon_defense(view, 8) {
return card;
}
let legal = view.legal_plays();
if legal.len() == 1 {
return legal.into_iter().next().expect("checked non-empty");
}
let trick = view.current_trick().expect("a play decision has a trick");
if view.tricks().is_empty()
|| Seat::ALL
.into_iter()
.any(|seat| seat != view.seat() && view.points_taken(seat) > 0)
{
self.shooting = false;
}
if self.shooting {
return shoot_play(legal, trick, view.played());
}
let candidates = self.candidates(view);
if candidates.len() < 2 {
return greedy_play(legal, trick, view.played());
}
let scored = self.score(view, &candidates);
let best = recommended(&scored, &candidates, self.gate);
if candidates[best].shoot {
self.moon_attempts += 1;
}
self.shooting = candidates[best].shoot;
match candidates[best].choice {
Choice::Play(card) => card,
Choice::Pass(_) => unreachable!("the playing phase yields play choices"),
}
}
fn name(&self) -> &str {
"mc"
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{HeuristicBot, Table};
use hearts::Holding;
use rand::SeedableRng as _;
use rand::rngs::StdRng;
fn fixed_table() -> Table {
let mut hands = [Hand::EMPTY; 4];
for (i, card) in Hand::ALL.into_iter().enumerate() {
hands[i % 4].insert(card);
}
let round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
.expect("a round-robin deal partitions the deck");
Table::new(round)
}
fn mid_round() -> Table {
let mut table = fixed_table();
let mut bot = crate::HeuristicBot::new();
while table.round().tricks().len() < 5 {
table.step(&mut bot).expect("greedy plays are legal");
}
table
}
#[test]
fn sampled_worlds_are_consistent_with_the_view() {
let table = mid_round();
let me = table.turn().expect("a mid-round table has a mover");
let view = table.view(me);
let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(1));
let worlds = bot.sample_worlds(&view, 32);
assert_eq!(worlds.len(), 32);
for world in &worlds {
assert_eq!(world.tricks(), view.tricks());
assert_eq!(world.current_trick(), view.current_trick());
assert_eq!(world.played(), view.played());
assert_eq!(world.hand(me), view.hand());
assert_eq!(world.phase(), Phase::Playing);
for seat in Seat::ALL {
let hand = world.hand(seat);
assert_eq!(hand.len(), view.hand_len(seat));
assert_eq!(hand - view.possible_cards(seat), Hand::EMPTY);
let known = view.known_cards(seat);
assert_eq!(hand & known, known);
}
}
}
#[test]
fn a_dangerous_pass_is_more_likely() {
fn hand(text: &str) -> Hand {
text.parse().expect("a valid hand")
}
let plausible = hand("2345.6789.TJ.QKA");
let modeled: Hand = greedy_pass(plausible, HeuristicConfig::default())
.into_iter()
.collect();
let quiet = hand("234...");
let default = HeuristicConfig::default();
assert_eq!(
pass_observation_likelihood(plausible, modeled, default),
1.0
);
assert!(pass_observation_likelihood(plausible, quiet, default) < 1.0);
}
#[test]
fn the_pass_model_reaches_every_role() {
let wild = HeuristicConfig {
heart_weight: 9,
..HeuristicConfig::default()
};
let bot = |config| MonteCarloBot::new(StdRng::seed_from_u64(4)).pass_model(config);
let mut deal = StdRng::seed_from_u64(5);
let mut table = Table::deal(Rules::new(), PassDirection::Left, &mut deal);
let me = table.turn().expect("passing starts at North");
let labels = |config| {
bot(config)
.candidates(&table.view(me))
.into_iter()
.map(|candidate| candidate.label)
.collect::<Vec<String>>()
};
assert_ne!(labels(HeuristicConfig::default()), labels(wild));
let population = |config| {
bot(config)
.sample_worlds(&table.view(me), 1)
.first()
.expect("a pass-phase world samples")
.passed(me.left())
};
assert_ne!(
population(HeuristicConfig::default()),
population(wild),
"the modeled opponents ignored the pass model"
);
for _ in 0..4 {
table
.step(&mut HeuristicBot::new())
.expect("greedy passes are legal");
}
let view = table.view(me);
assert!(view.received().is_some(), "the observation model is live");
let rejects = |config| {
let mut bot = bot(config);
(0..64)
.filter(|_| bot.sample_hands(&view).is_none())
.count()
};
assert_ne!(
rejects(HeuristicConfig::default()),
rejects(wild),
"the observation model ignored the pass model"
);
}
#[test]
fn reconstruction_replays_any_real_position() {
let mut rng = StdRng::seed_from_u64(7);
for _ in 0..20 {
let mut table = Table::deal(Rules::new(), PassDirection::Left, &mut rng);
let mut bot = crate::HeuristicBot::new();
for _ in 0..rng.random_range(4..30) {
table.step(&mut bot).expect("greedy plays are legal");
}
let round = table.round();
if round.phase() != Phase::Playing {
continue;
}
let mut originals = [Hand::EMPTY; 4];
for seat in Seat::ALL {
let mut own = round.hand(seat);
for trick in round.tricks().iter().copied().chain(round.current_trick()) {
if let Some(card) = trick.card_from(seat) {
own.insert(card);
}
}
originals[seat as usize] = own;
}
let mut replay = Round::from_deal(*round.rules(), PassDirection::Hold, originals)
.expect("original hands partition the deck");
for trick in round.tricks().iter().copied().chain(round.current_trick()) {
for (seat, card) in trick.plays() {
replay.play(seat, card).expect("the real history is legal");
}
}
assert_eq!(replay.tricks(), round.tricks());
assert_eq!(replay.current_trick(), round.current_trick());
for seat in Seat::ALL {
assert_eq!(replay.hand(seat), round.hand(seat));
}
}
}
#[test]
fn seeded_bots_repeat_their_decisions() {
let table = mid_round();
let me = table.turn().expect("a mid-round table has a mover");
let decide = |seed| {
let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(seed)).samples(16);
bot.play_card(&table.view(me))
};
assert_eq!(decide(3), decide(3));
}
#[test]
fn equity_is_terminal_at_the_target() {
let rules = Rules::new();
let me = Seat::North;
let win = equity(&[0, 10, 10, 6], me, [50, 60, 70, 95], &rules);
assert_eq!(win, 1.0);
let loss = equity(&[13, 13, 0, 0], me, [95, 0, 0, 0], &rules);
assert_eq!(loss, 0.0);
let second = equity(&[0, 0, 13, 13], me, [50, 40, 60, 95], &rules);
assert_eq!(second, 2.0 / 3.0);
let third = equity(&[0, 0, 13, 13], me, [50, 40, 30, 95], &rules);
assert_eq!(third, 1.0 / 3.0);
let crowns = equity(&[0, 0, 13, 13], me, [50, 50, 60, 95], &rules);
assert_eq!(crowns, 5.0 / 6.0);
let level = equity(&[13, 7, 3, 3], me, [87, 93, 97, 97], &rules);
assert_eq!(level, 0.5);
assert_eq!(equity(&[13, 13, 0, 0], me, [87, 0, 0, 0], &rules), 0.0);
let running = equity(&[13, 13, 0, 0], me, [86, 0, 0, 0], &rules);
assert!((0.25..=0.75).contains(&running), "{running} is mid-game");
}
#[test]
fn equity_orders_round_outcomes_mid_game() {
let rules = Rules::new();
let me = Seat::North;
let level = [0u16; 4];
let clean = equity(&[0, 13, 13, 0], me, level, &rules);
let queen = equity(&[13, 13, 0, 0], me, level, &rules);
let moon = equity(&[0, 26, 26, 26], me, level, &rules);
let mooned = equity(&[26, 0, 26, 26], me, level, &rules);
assert!(moon > clean && clean > queen);
assert!((queen - mooned).abs() < 1e-12);
for value in [clean, queen, moon, mooned] {
assert!((0.25..=0.75).contains(&value), "{value} is mid-game");
}
}
#[test]
fn beats_requires_a_clear_margin() {
let base: Vec<f64> = (0..32).map(|i| f64::from(i % 5)).collect();
let noisy: Vec<f64> = base
.iter()
.enumerate()
.map(|(i, x)| x + if i % 2 == 0 { 1.05 } else { -0.95 })
.collect();
assert!(!beats(&noisy, &base, 1.5));
assert!(beats(&noisy, &base, 0.1));
let better: Vec<f64> = base.iter().map(|x| x + 1.0).collect();
assert!(beats(&better, &base, 1.5));
assert!(!beats(&base, &better, 1.5));
assert!(!beats(&base, &base, 1.5));
}
#[test]
fn shoot_candidate_requires_a_strict_majority() {
let candidates = [
Candidate {
label: "incumbent".into(),
choice: Choice::Play(Card::TWO_OF_CLUBS),
shoot: false,
},
Candidate {
label: "shoot".into(),
choice: Choice::Play(Card::TWO_OF_CLUBS),
shoot: true,
},
];
let incumbent = vec![0.0; 4];
let challenger = vec![1.0; 4];
let mut scored = vec![(incumbent, 0.0, 0), (challenger, 0.0, 2)];
assert_eq!(recommended(&scored, &candidates, 1.5), 0);
scored[1].2 = 3;
assert_eq!(recommended(&scored, &candidates, 1.5), 1);
}
#[test]
fn only_an_unresolved_best_challenger_is_contested() {
let base: Vec<f64> = (0..32).map(|i| f64::from(i % 5)).collect();
let uncertain: Vec<f64> = base
.iter()
.enumerate()
.map(|(i, x)| x + if i % 2 == 0 { 1.05 } else { -0.95 })
.collect();
let better: Vec<f64> = base.iter().map(|x| x + 1.0).collect();
let worse: Vec<f64> = base.iter().map(|x| x - 1.0).collect();
let scores = |challenger| vec![(base.clone(), 0.0, 0), (challenger, 0.0, 0)];
assert!(contested(&scores(uncertain), &[1], 1.5));
assert!(!contested(&scores(better), &[1], 1.5));
assert!(!contested(&scores(worse), &[1], 1.5));
assert!(!contested(&scores(base.clone()), &[], 1.5));
}
#[test]
fn play_candidates_collapse_touching_ranks() {
let table = fixed_table();
let north = table.turn().expect("a fresh hold deal has a leader");
assert_eq!(play_candidates(&table.view(north)).len(), 0);
}
#[test]
fn play_candidates_keep_queen_distinct_from_neighbors() {
let hand = |cards: &str| -> Hand {
cards
.split_whitespace()
.map(|c| c.parse().expect("valid card"))
.collect()
};
let hands = [
hand("2C 6C 7C 8C 6D 7D 8D 9D 6H 7H 8H 3S 4S"), hand("9C TC AC TD JD QD 9H TH JH 2S 5S 6S 7S"), hand("3C 4C 5C 2D 3D 4D 5D 2H 3H 4H 5H JS QS"), hand("JC QC KC KD AD QH KH AH 8S 9S TS KS AS"), ];
let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
.expect("a full partition deals");
for (seat, card) in [
(Seat::North, "2C"),
(Seat::East, "AC"),
(Seat::South, "3C"),
(Seat::West, "JC"),
(Seat::East, "2S"), ] {
round
.play(seat, card.parse().expect("valid card"))
.expect("a legal scripted play");
}
let table = Table::new(round);
assert_eq!(
table.turn(),
Some(Seat::South),
"South is to follow the spade"
);
let view = table.view(Seat::South);
let cands = play_candidates(&view);
assert_eq!(
cands.iter().filter(|c| !c.shoot).count(),
2,
"Q♠ must not collapse into J♠"
);
assert!(
cands
.iter()
.any(|c| matches!(c.choice, Choice::Play(card) if card == Card::QUEEN_OF_SPADES)),
"Q♠ is weighed as its own play",
);
let mut solver = MonteCarloBot::new(StdRng::seed_from_u64(7)).samples(64);
assert!(!solver.assess(&view).is_empty(), "the hint offers a read");
}
#[test]
fn assess_lists_an_all_equivalent_class_rather_than_refusing() {
let hand = |cards: &str| -> Hand {
cards
.split_whitespace()
.map(|c| c.parse().expect("valid card"))
.collect()
};
let hands = [
hand("2C 3C 4C 5C 2S 3S 4S 2D 3D 4D 5D 2H 3H"), hand("AC KC QC 9S 6D 7D 8D 9D 5H 6H 7H 8H 9H"), hand("6C 7C 8C 9C TC JC 5S 7S TD JD QD KD AD"), hand("6S 8S TS JS QS KS AS 4H TH JH QH KH AH"), ];
let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
.expect("a full partition deals");
for (seat, card) in [
(Seat::North, "2C"),
(Seat::East, "AC"),
(Seat::South, "6C"),
(Seat::West, "6S"), (Seat::East, "9S"), ] {
round
.play(seat, card.parse().expect("valid card"))
.expect("a legal scripted play");
}
let table = Table::new(round);
assert_eq!(
table.turn(),
Some(Seat::South),
"South is to follow the spade"
);
let view = table.view(Seat::South);
assert_eq!(
play_candidates(&view).len(),
1,
"5♠ and 7♠ collapse across the played 6♠",
);
let mut solver = MonteCarloBot::new(StdRng::seed_from_u64(11)).samples(64);
let rows = solver.assess(&view);
assert_eq!(rows.len(), 2, "both equivalent spades are shown");
assert!(
rows.iter().all(|r| r.recommended),
"an equivalent class is all-tied",
);
assert!(
rows[0].equity == rows[1].equity && rows[0].ev == rows[1].ev,
"equivalent plays carry the same read",
);
}
#[test]
fn a_rank_in_the_live_trick_does_not_bridge_a_sequence() {
let hand = |cards: &str| -> Hand {
cards
.split_whitespace()
.map(|c| c.parse().expect("valid card"))
.collect()
};
let hands = [
hand("9D 2D 3D 4D 2S 3S 4S 5S 6S 2H 3H 4H 5H"), hand("TC JC QC KC AC JD QS KS AS JH QH KH AH"), hand("2C 3C 4C 5C 6C 7C 8C 9C 7D TD QD KD AD"), hand("8D 5D 6D 7S 8S 9S TS JS 6H 7H 8H 9H TH"), ];
let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
.expect("a full partition deals");
for (seat, card) in [
(Seat::South, "2C"),
(Seat::West, "8D"),
(Seat::North, "9D"),
(Seat::East, "AC"),
(Seat::East, "JD"), ] {
round
.play(seat, card.parse().expect("valid card"))
.expect("a legal scripted play");
}
let table = Table::new(round);
assert_eq!(
table.turn(),
Some(Seat::South),
"South is to follow the diamond"
);
let view = table.view(Seat::South);
let plays: Vec<Card> = play_candidates(&view)
.iter()
.filter(|c| !c.shoot)
.filter_map(|c| match c.choice {
Choice::Play(card) => Some(card),
Choice::Pass(_) => None,
})
.collect();
let jack: Card = "JD".parse().expect("valid card");
assert!(
plays.iter().any(|card| card.rank > jack.rank),
"a play that takes the trick is weighed: {plays:?}",
);
assert!(
plays.iter().any(|card| card.rank < jack.rank),
"a play that ducks the trick is weighed: {plays:?}",
);
}
#[test]
fn void_respecting_worlds() {
let mut rng = StdRng::seed_from_u64(21);
let mut table = Table::deal(Rules::new(), PassDirection::Hold, &mut rng);
let mut bot = crate::HeuristicBot::new();
let (observer, void_seat, void_suit) = loop {
table.step(&mut bot).expect("greedy plays are legal");
let round = table.round();
assert_eq!(round.phase(), Phase::Playing, "a void shows up first");
let found = Seat::ALL.iter().find_map(|&seat| {
let observer = round.turn()?;
Suit::ASC
.into_iter()
.find(|&suit| observer != seat && table.view(observer).is_void(seat, suit))
.map(|suit| (observer, seat, suit))
});
if let Some(found) = found {
break found;
}
};
let view = table.view(observer);
let mut mc = MonteCarloBot::new(StdRng::seed_from_u64(2));
for world in mc.sample_worlds(&view, 16) {
assert_eq!(world.hand(void_seat)[void_suit], Holding::EMPTY);
}
}
#[test]
fn assess_ranks_candidates_and_flags_the_bots_pick() {
let table = mid_round();
let me = table.turn().expect("a mid-round table has a mover");
let view = table.view(me);
let mut solver = MonteCarloBot::new(StdRng::seed_from_u64(7)).samples(64);
let mut chooser = MonteCarloBot::new(StdRng::seed_from_u64(7)).samples(64);
let rows = solver.assess(&view);
if rows.is_empty() {
assert!(view.legal_plays().len() == 1 || play_candidates(&view).len() < 2);
return;
}
for row in &rows {
assert!((0.0..=1.0).contains(&row.equity));
assert!(row.ev >= 0.0);
}
assert!(rows.windows(2).all(|w| w[0].equity >= w[1].equity));
assert_eq!(rows.iter().filter(|r| r.recommended).count(), 1);
let picked = rows.iter().find(|r| r.recommended).expect("a flagged pick");
let played = chooser.play_card(&view);
assert!(
picked.action.ends_with(&format!("play {played}")),
"{} is the card {played} was picked for",
picked.action,
);
}
#[test]
fn pass_assessment_covers_twenty_triples() {
let mut rng = StdRng::seed_from_u64(5);
let table = Table::deal(Rules::new(), PassDirection::Left, &mut rng);
let me = table.turn().expect("passing starts at North");
let view = table.view(me);
let cands = pass_candidates(&view, HeuristicConfig::default());
assert!(cands.iter().filter(|c| !c.shoot).count() >= 20);
assert_eq!(cands.iter().filter(|c| c.shoot).count(), 1, "the moon pass");
let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(6)).samples(16);
let picks = bot.pass_cards(&view);
assert_eq!(
picks.into_iter().collect::<Hand>().len(),
3,
"three distinct cards"
);
for card in picks {
assert!(view.hand().contains(card));
}
assert_eq!(bot.moon_passes(), 0);
}
#[test]
fn pass_candidate_zero_is_the_greedy_incumbent() {
fn hand(text: &str) -> Hand {
text.parse().expect("a valid hand")
}
let mine = hand("234679.2K.6A.68J");
let mut hands = [mine, Hand::EMPTY, Hand::EMPTY, Hand::EMPTY];
for (i, card) in (Hand::ALL - mine).into_iter().enumerate() {
hands[1 + i % 3].insert(card);
}
let round = Round::from_deal(Rules::new(), PassDirection::Left, hands).unwrap();
let table = Table::new(round);
let config = HeuristicConfig::default();
let incumbent = greedy_pass(mine, config);
let cands = pass_candidates(&table.view(Seat::North), config);
assert!(
matches!(cands[0].choice, Choice::Pass(triple) if triple == incumbent),
"candidate 0 is not the greedy pass: {}",
cands[0].label,
);
let set: Hand = incumbent.into_iter().collect();
assert_eq!(
cands
.iter()
.filter(|candidate| !candidate.shoot)
.filter(|candidate| matches!(candidate.choice, Choice::Pass(triple)
if triple.into_iter().collect::<Hand>() == set))
.count(),
1,
"the pool re-rolled the incumbent as a second candidate",
);
}
#[test]
fn pass_candidates_can_create_a_void_outside_the_top_six() {
fn hand(text: &str) -> Hand {
text.parse().expect("a valid hand")
}
let mine = hand("234.QKA.QKA.JQKA");
let mut hands = [mine, Hand::EMPTY, Hand::EMPTY, Hand::EMPTY];
for (i, card) in (Hand::ALL - mine).into_iter().enumerate() {
hands[1 + i % 3].insert(card);
}
let round = Round::from_deal(Rules::new(), PassDirection::Left, hands).unwrap();
let table = Table::new(round);
let void = hand("234...");
assert!(
pass_candidates(&table.view(Seat::North), HeuristicConfig::default())
.iter()
.any(|candidate| matches!(candidate.choice, Choice::Pass(cards)
if cards.into_iter().collect::<Hand>() == void))
);
}
#[test]
fn a_hand_that_cannot_win_a_trick_does_not_try() {
fn hand(text: &str) -> Hand {
text.parse().expect("a valid hand")
}
let hands = [
hand("234.234.234.2345"), hand("5678.567.567.678"),
hand("9TJ.89TJ.89T.9TJ"),
hand("QKA.QKA.JQKA.QKA"),
];
let round = Round::from_deal(Rules::new(), PassDirection::Left, hands)
.expect("a full partition deals");
let table = Table::new(round);
let view = table.view(Seat::North);
let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(0xC0DE)).samples(128);
let picked = bot
.assess(&view)
.into_iter()
.find(|row| row.recommended)
.expect("a flagged pick");
assert!(
!picked.action.starts_with("shoot"),
"shot the moon holding nothing: {}",
picked.action,
);
}
#[test]
fn seeded_pick_is_identical_across_serial_and_parallel_builds() {
let table = mid_round();
let me = table.turn().expect("a mid-round table has a mover");
let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(11)).samples(64);
let first = bot.play_card(&table.view(me));
let mut again = MonteCarloBot::new(StdRng::seed_from_u64(11)).samples(64);
assert_eq!(first, again.play_card(&table.view(me)));
}
#[test]
fn breaks_a_moon_the_rollouts_never_see() {
fn card(text: &str) -> Card {
text.parse().expect("a valid card")
}
fn hand(cards: &[&str]) -> Hand {
cards.iter().map(|c| card(c)).collect()
}
struct Fixed(Card);
impl Strategy for Fixed {
fn pass_cards(&mut self, _: &View<'_>) -> [Card; 3] {
unreachable!()
}
fn play_card(&mut self, _: &View<'_>) -> Card {
self.0
}
}
let hands = [
hand(&[
"2♣", "3♣", "3♠", "K♠", "A♦", "3♥", "4♥", "5♥", "6♥", "7♥", "8♥", "9♥", "T♥",
]),
hand(&[
"A♣", "K♣", "Q♣", "J♣", "5♠", "6♠", "7♠", "8♠", "9♠", "T♠", "J♠", "A♠", "2♦",
]),
hand(&[
"Q♠", "2♠", "4♠", "J♥", "Q♥", "K♥", "A♥", "3♦", "4♦", "5♦", "6♦", "7♦", "8♦",
]),
hand(&[
"4♣", "5♣", "6♣", "7♣", "8♣", "9♣", "T♣", "9♦", "T♦", "J♦", "Q♦", "K♦", "2♥",
]),
];
let round = Round::from_deal(Rules::new(), PassDirection::Hold, hands).unwrap();
let mut table = Table::new(round);
let script = [
(Seat::North, "2♣"), (Seat::East, "A♣"),
(Seat::South, "3♦"), (Seat::West, "4♣"),
(Seat::East, "K♣"), (Seat::South, "Q♠"),
(Seat::West, "5♣"),
(Seat::North, "3♣"),
(Seat::East, "5♠"), (Seat::South, "4♠"),
(Seat::West, "2♥"), ];
for (seat, text) in script {
assert_eq!(table.turn(), Some(seat));
table.step(&mut Fixed(card(text))).unwrap();
}
let view = table.view(Seat::North);
assert_eq!(view.points_taken(Seat::East), 13, "East swept the queen");
assert_eq!(
greedy_play(
view.legal_plays(),
view.current_trick().unwrap(),
view.played()
),
card("3♠")
);
let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(1)).samples(64);
assert_eq!(bot.play_card(&view), card("K♠"));
assert_eq!(bot.moon_attempts(), 0);
assert!(
!play_candidates(&view).iter().any(|c| c.shoot),
"a dead moon is not a candidate",
);
}
#[test]
fn a_laydown_moon_is_rolled_as_one() {
fn card(text: &str) -> Card {
text.parse().expect("a valid card")
}
fn hand(text: &str) -> Hand {
text.parse().expect("a valid hand")
}
let hands = [
hand("QKA..QKA.29TJQKA"), hand("2345.234567.234."), hand("6789.89T.567.456"),
hand("TJ.JQKA.89TJ.378"),
];
let mut round = Round::from_deal(Rules::new(), PassDirection::Hold, hands)
.expect("a full partition deals");
for (seat, text) in [(Seat::East, "2♣"), (Seat::South, "6♣"), (Seat::West, "T♣")] {
round
.play(seat, card(text))
.expect("a legal scripted play, North last to the deuce");
}
let ace = Choice::Play(card("A♣"));
let mut continuation = round.clone();
assert_eq!(
ace.roll(&mut continuation, Seat::North, true).shooter(),
Some(Seat::North),
"the shooting continuation takes all thirteen tricks",
);
let mut bot = MonteCarloBot::new(StdRng::seed_from_u64(3)).samples(64);
let mut east = HeuristicBot::new();
let mut south = HeuristicBot::new();
let mut west = HeuristicBot::new();
let result = Table::new(round)
.play([&mut bot, &mut east, &mut south, &mut west])
.expect("no seat cheats");
assert_eq!(result.shooter(), Some(Seat::North), "the bot shot it");
assert_eq!(bot.moon_attempts(), 1);
}
}