scrabble 0.1.0

A fast, complete crossword-game engine: move generation, scoring, simulation, and endgame solving.
Documentation
use crate::eval::Unseen;
use crate::rack::Rack;
use crate::rng::Rng;
use crate::tile::{Tile, TILE_CODES};
use alloc::vec::Vec;

pub trait RackFilter {
    fn accepts(&self, rack: &Rack) -> bool;
}

impl<F: Fn(&Rack) -> bool> RackFilter for F {
    fn accepts(&self, rack: &Rack) -> bool {
        self(rack)
    }
}

#[derive(Clone, Copy, Debug)]
pub struct AnyRack;

impl RackFilter for AnyRack {
    fn accepts(&self, _rack: &Rack) -> bool {
        true
    }
}

#[derive(Clone, Copy, Debug)]
pub struct WithoutTiles {
    excluded: [u8; TILE_CODES],
}

impl WithoutTiles {
    pub fn new() -> WithoutTiles {
        WithoutTiles {
            excluded: [u8::MAX; TILE_CODES],
        }
    }

    pub fn at_most(mut self, tile: Tile, max: u8) -> WithoutTiles {
        self.excluded[tile.code() as usize] = max;
        self
    }

    pub fn without(self, tile: Tile) -> WithoutTiles {
        self.at_most(tile, 0)
    }
}

impl Default for WithoutTiles {
    fn default() -> Self {
        WithoutTiles::new()
    }
}

impl RackFilter for WithoutTiles {
    fn accepts(&self, rack: &Rack) -> bool {
        rack.counts()
            .iter()
            .zip(self.excluded.iter())
            .all(|(&held, &max)| held <= max)
    }
}

#[derive(Clone, Debug)]
pub struct Inference {
    pool: Vec<Tile>,
    pub max_attempts: usize,
}

impl Inference {
    pub fn uniform(unseen: &Unseen) -> Inference {
        let mut pool = Vec::with_capacity(unseen.len());
        for (code, &n) in unseen.counts().iter().enumerate() {
            for _ in 0..n {
                pool.push(Tile::from_code(code as u8));
            }
        }
        Inference {
            pool,
            max_attempts: 64,
        }
    }

    #[inline]
    pub fn pool_size(&self) -> usize {
        self.pool.len()
    }

    pub fn sample(&self, rng: &mut Rng, size: usize) -> Rack {
        let take = size.min(self.pool.len());
        let mut rack = Rack::new();

        let mut indices: Vec<usize> = (0..self.pool.len()).collect();
        for i in 0..take {
            let j = i + rng.below((indices.len() - i) as u64) as usize;
            indices.swap(i, j);
            rack.add(self.pool[indices[i]]);
        }
        rack
    }

    pub fn sample_filtered(
        &self,
        rng: &mut Rng,
        size: usize,
        filter: &impl RackFilter,
    ) -> Option<Rack> {
        for _ in 0..self.max_attempts {
            let rack = self.sample(rng, size);
            if filter.accepts(&rack) {
                return Some(rack);
            }
        }
        None
    }

    pub fn sample_split(&self, rng: &mut Rng, size: usize) -> (Rack, Vec<Tile>) {
        let mut shuffled = self.pool.clone();
        rng.shuffle(&mut shuffled);
        let take = size.min(shuffled.len());
        let rest = shuffled.split_off(take);
        (Rack::from_tiles(shuffled), rest)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::board::Board;
    use crate::rules::{Alphabet, GameConfig};

    fn setup() -> (GameConfig, Board) {
        let config = GameConfig::standard();
        let board = Board::new(&config.layout);
        (config, board)
    }

    #[test]
    fn sampling_never_invents_tiles() {
        let (config, board) = setup();
        let own = Rack::parse(&Alphabet::english(), "AEINRST").unwrap();
        let unseen = Unseen::new(&config, &board, &own);
        let inference = Inference::uniform(&unseen);
        let mut rng = Rng::seed_from_u64(1);

        for _ in 0..200 {
            let rack = inference.sample(&mut rng, 7);
            assert_eq!(rack.len(), 7);
            for (code, &n) in rack.counts().iter().enumerate() {
                assert!(
                    n <= unseen.counts()[code],
                    "drew {n} of tile {code} but only {} are unseen",
                    unseen.counts()[code]
                );
            }
        }
    }

    #[test]
    fn sampling_from_a_small_pool_takes_what_is_there() {
        let (config, board) = setup();
        let unseen = Unseen::new(&config, &board, &Rack::new());
        let mut inference = Inference::uniform(&unseen);
        inference.pool.truncate(3);
        let mut rng = Rng::seed_from_u64(2);
        assert_eq!(inference.sample(&mut rng, 7).len(), 3);
    }

    #[test]
    fn samples_vary_and_cover_the_pool() {
        let (config, board) = setup();
        let unseen = Unseen::new(&config, &board, &Rack::new());
        let inference = Inference::uniform(&unseen);
        let mut rng = Rng::seed_from_u64(3);

        let mut seen_blank = false;
        let mut distinct = alloc::collections::BTreeSet::new();
        for _ in 0..500 {
            let rack = inference.sample(&mut rng, 7);
            distinct.insert(rack.key());
            if rack.has_blank() {
                seen_blank = true;
            }
        }
        assert!(distinct.len() > 400, "samples should not repeat much");
        assert!(
            seen_blank,
            "500 draws of 7 from 100 tiles should turn up a blank"
        );
    }

    #[test]
    fn a_filter_excludes_what_it_says_it_does() {
        let (config, board) = setup();
        let unseen = Unseen::new(&config, &board, &Rack::new());
        let inference = Inference::uniform(&unseen);
        let mut rng = Rng::seed_from_u64(4);
        let filter = WithoutTiles::new().without(Tile::BLANK);

        for _ in 0..100 {
            if let Some(rack) = inference.sample_filtered(&mut rng, 7, &filter) {
                assert!(!rack.has_blank(), "the filter rules blanks out");
            }
        }
    }

    #[test]
    fn an_impossible_filter_gives_up_rather_than_looping() {
        let (config, board) = setup();
        let unseen = Unseen::new(&config, &board, &Rack::new());
        let inference = Inference::uniform(&unseen);
        let mut rng = Rng::seed_from_u64(5);
        let impossible = |_: &Rack| false;
        assert_eq!(inference.sample_filtered(&mut rng, 7, &impossible), None);
    }

    #[test]
    fn a_split_partitions_the_pool_exactly() {
        let (config, board) = setup();
        let own = Rack::parse(&Alphabet::english(), "AEINRST").unwrap();
        let unseen = Unseen::new(&config, &board, &own);
        let inference = Inference::uniform(&unseen);
        let mut rng = Rng::seed_from_u64(6);

        let (rack, rest) = inference.sample_split(&mut rng, 7);
        assert_eq!(rack.len() + rest.len(), unseen.len());

        let mut counts = [0u8; TILE_CODES];
        for (code, n) in rack.counts().iter().enumerate() {
            counts[code] += n;
        }
        for t in &rest {
            counts[t.code() as usize] += 1;
        }
        assert_eq!(&counts, unseen.counts(), "the split must conserve tiles");
    }

    #[test]
    fn a_closure_works_as_a_filter() {
        let (config, board) = setup();
        let unseen = Unseen::new(&config, &board, &Rack::new());
        let inference = Inference::uniform(&unseen);
        let mut rng = Rng::seed_from_u64(7);
        let no_q = |r: &Rack| !r.contains(Tile::letter(16));
        for _ in 0..50 {
            if let Some(rack) = inference.sample_filtered(&mut rng, 7, &no_q) {
                assert!(!rack.contains(Tile::letter(16)));
            }
        }
    }
}