use crate::board::Board;
use crate::lexicon::Lexicon;
use crate::movegen::{MoveGenerator, Play};
use crate::rack::Rack;
use crate::rng::Rng;
use crate::rules::GameConfig;
use crate::tile::Square;
use alloc::vec::Vec;
use std::collections::HashMap;
#[derive(Clone, PartialEq, Debug)]
pub struct EndgameResult {
pub best: Option<Play>,
pub spread: i32,
pub nodes: u64,
pub exact: bool,
}
pub struct EndgameSolver {
config: GameConfig,
generator: MoveGenerator,
table: HashMap<u64, Entry>,
zobrist: Zobrist,
nodes: u64,
budget: u64,
exhausted: bool,
max_depth: u32,
}
#[derive(Clone, Copy, Debug)]
struct Entry {
depth: u32,
value: i32,
kind: Bound,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Bound {
Exact,
Lower,
Upper,
}
impl EndgameSolver {
pub fn new(config: &GameConfig) -> EndgameSolver {
EndgameSolver {
generator: MoveGenerator::new(config),
zobrist: Zobrist::new(config),
config: config.clone(),
table: HashMap::new(),
nodes: 0,
budget: 8_000_000,
exhausted: false,
max_depth: 32,
}
}
pub fn with_budget(mut self, nodes: u64) -> EndgameSolver {
self.budget = nodes;
self
}
pub fn solve(
&mut self,
board: &Board,
mover: &Rack,
opponent: &Rack,
lexicon: &Lexicon,
) -> EndgameResult {
self.nodes = 0;
self.exhausted = false;
self.table.clear();
let mut work = board.clone();
let mut best: Option<Play> = None;
let mut best_value = i32::MIN;
let pass_value = -self.search(
&mut work,
opponent,
mover,
lexicon,
1,
-i32::MAX,
i32::MAX,
1,
);
best_value = best_value.max(pass_value);
let plays = self.ordered_plays(&work, mover, lexicon);
for play in plays {
let Some(leave) = play.leave(mover) else {
continue;
};
play.apply(&mut work);
let value = if leave.is_empty() {
play.score() + 2 * opponent.value(&self.config.alphabet)
} else {
play.score()
- self.search(
&mut work,
opponent,
&leave,
lexicon,
0,
-i32::MAX,
i32::MAX,
1,
)
};
play.undo(&mut work);
if value > best_value {
best_value = value;
best = Some(play);
}
}
EndgameResult {
best,
spread: best_value,
nodes: self.nodes,
exact: !self.exhausted,
}
}
#[allow(clippy::too_many_arguments)]
fn search(
&mut self,
board: &mut Board,
mover: &Rack,
opponent: &Rack,
lexicon: &Lexicon,
passes: u32,
mut alpha: i32,
beta: i32,
depth: u32,
) -> i32 {
self.nodes += 1;
if self.nodes >= self.budget || depth >= self.max_depth {
self.exhausted = true;
return opponent.value(&self.config.alphabet) - mover.value(&self.config.alphabet);
}
if mover.is_empty() {
return opponent.value(&self.config.alphabet) * 2;
}
if passes >= 2 {
return opponent.value(&self.config.alphabet) - mover.value(&self.config.alphabet);
}
let key = self.zobrist.key(board, mover, opponent, passes);
let alpha_orig = alpha;
if let Some(entry) = self.table.get(&key) {
if entry.depth >= depth {
match entry.kind {
Bound::Exact => return entry.value,
Bound::Lower if entry.value >= beta => return entry.value,
Bound::Upper if entry.value <= alpha => return entry.value,
_ => {}
}
}
}
let mut best = -self.search(
board,
opponent,
mover,
lexicon,
passes + 1,
-beta,
-alpha,
depth + 1,
);
alpha = alpha.max(best);
if alpha < beta {
let plays = self.ordered_plays(board, mover, lexicon);
for play in plays {
let Some(leave) = play.leave(mover) else {
continue;
};
play.apply(board);
let value = if leave.is_empty() {
play.score() + 2 * opponent.value(&self.config.alphabet)
} else {
play.score()
- self.search(
board,
opponent,
&leave,
lexicon,
0,
-beta,
-alpha,
depth + 1,
)
};
play.undo(board);
if value > best {
best = value;
}
alpha = alpha.max(best);
if alpha >= beta {
break;
}
}
}
let kind = if best <= alpha_orig {
Bound::Upper
} else if best >= beta {
Bound::Lower
} else {
Bound::Exact
};
self.table.insert(
key,
Entry {
depth,
value: best,
kind,
},
);
best
}
fn ordered_plays(&mut self, board: &Board, rack: &Rack, lexicon: &Lexicon) -> Vec<Play> {
let mut plays = self.generator.generate(board, rack, lexicon).to_vec();
plays.sort_unstable_by_key(|play| core::cmp::Reverse((play.score(), play.tiles_used())));
plays
}
#[inline]
pub fn nodes(&self) -> u64 {
self.nodes
}
}
struct Zobrist {
squares: Vec<u64>,
racks: [Vec<u64>; 2],
passes: [u64; 3],
cells: usize,
}
const SQUARE_STATES: usize = 1 + 2 * crate::tile::MAX_LETTERS;
const MAX_RACK_COUNT: usize = 8;
impl Zobrist {
fn new(config: &GameConfig) -> Zobrist {
let mut rng = Rng::seed_from_u64(0x5CAB_B1E5_1234_9ABCu64);
let cells = config.layout.cells();
let mut squares = Vec::with_capacity(cells * SQUARE_STATES);
for _ in 0..cells * SQUARE_STATES {
squares.push(rng.next_u64());
}
let mut racks = [Vec::new(), Vec::new()];
for side in &mut racks {
for _ in 0..crate::tile::TILE_CODES * MAX_RACK_COUNT {
side.push(rng.next_u64());
}
}
Zobrist {
squares,
racks,
passes: [rng.next_u64(), rng.next_u64(), rng.next_u64()],
cells,
}
}
fn key(&self, board: &Board, mover: &Rack, opponent: &Rack, passes: u32) -> u64 {
let mut h = self.passes[(passes as usize).min(2)];
for (i, square) in board.squares().iter().enumerate() {
let state = square_state(*square);
if state != 0 {
h ^= self.squares[i * SQUARE_STATES + state];
}
}
debug_assert_eq!(board.squares().len(), self.cells);
for (side, rack) in [mover, opponent].iter().enumerate() {
for (code, &n) in rack.counts().iter().enumerate() {
if n > 0 {
let n = (n as usize).min(MAX_RACK_COUNT - 1);
h ^= self.racks[side][code * MAX_RACK_COUNT + n];
}
}
}
h
}
}
#[inline]
fn square_state(square: Square) -> usize {
match square.index() {
None => 0,
Some(letter) => {
1 + letter as usize
+ if square.is_blank() {
crate::tile::MAX_LETTERS
} else {
0
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::rules::Alphabet;
fn lexicon() -> Lexicon {
Lexicon::from_words(
&Alphabet::english(),
[
"AT", "ATE", "CAT", "CATS", "EAT", "EATS", "SAT", "SEAT", "SEATS", "TA", "TAE",
"TAN", "TAB", "NAB", "AB", "BA", "AN", "NA", "AX", "XI", "ZA", "QI", "JO",
],
)
.unwrap()
}
fn config() -> GameConfig {
GameConfig::standard()
}
fn board_with(config: &GameConfig, row: usize, col: usize, word: &str) -> Board {
let mut b = Board::new(&config.layout);
for (i, ch) in word.chars().enumerate() {
let (letter, _) = config.alphabet.parse_char(ch).unwrap();
b.set(row, col + i, Square::letter(letter));
}
b
}
#[test]
fn going_out_collects_twice_the_opponents_rack() {
let config = config();
let lex = lexicon();
let board = board_with(&config, 7, 6, "CAT");
let mover = Rack::parse(&config.alphabet, "S").unwrap();
let opponent = Rack::parse(&config.alphabet, "QZ").unwrap();
let mut solver = EndgameSolver::new(&config);
let result = solver.solve(&board, &mover, &opponent, &lex);
let play = result.best.expect("playing the S goes out");
assert_eq!(play.tiles_used(), 1);
assert_eq!(result.spread, play.score() + 40);
assert!(result.exact);
}
#[test]
fn a_smaller_play_that_goes_out_beats_a_bigger_one_that_does_not() {
let config = config();
let lex = lexicon();
let board = board_with(&config, 7, 6, "CAT");
let mover = Rack::parse(&config.alphabet, "S").unwrap();
let opponent = Rack::parse(&config.alphabet, "QZ").unwrap();
let mut solver = EndgameSolver::new(&config);
let out = solver.solve(&board, &mover, &opponent, &lex).spread;
let stuck = Rack::parse(&config.alphabet, "QZ").unwrap();
let light = Rack::parse(&config.alphabet, "S").unwrap();
let held = solver.solve(&board, &stuck, &light, &lex).spread;
assert!(
out > held,
"going out ({out}) must beat being stuck with the same tiles ({held})"
);
}
#[test]
fn a_hopeless_position_still_returns_the_least_bad_line() {
let config = config();
let lex = lexicon();
let board = Board::new(&config.layout);
let mover = Rack::parse(&config.alphabet, "VVV").unwrap();
let opponent = Rack::parse(&config.alphabet, "A").unwrap();
let mut solver = EndgameSolver::new(&config);
let result = solver.solve(&board, &mover, &opponent, &lex);
assert!(result.best.is_none(), "there is nothing to play");
assert_eq!(result.spread, 1 - 12);
assert!(result.exact);
}
#[test]
fn the_solver_is_deterministic() {
let config = config();
let lex = lexicon();
let board = board_with(&config, 7, 6, "CAT");
let mover = Rack::parse(&config.alphabet, "SE").unwrap();
let opponent = Rack::parse(&config.alphabet, "AB").unwrap();
let mut solver = EndgameSolver::new(&config);
let first = solver.solve(&board, &mover, &opponent, &lex);
let second = solver.solve(&board, &mover, &opponent, &lex);
assert_eq!(first.spread, second.spread);
assert_eq!(first.best, second.best);
assert_eq!(
first.nodes, second.nodes,
"the node count must be reproducible"
);
}
#[test]
fn a_tiny_budget_truncates_rather_than_hanging() {
let config = config();
let lex = lexicon();
let board = board_with(&config, 7, 6, "CAT");
let mover = Rack::parse(&config.alphabet, "SEAT").unwrap();
let opponent = Rack::parse(&config.alphabet, "ABTN").unwrap();
let mut solver = EndgameSolver::new(&config).with_budget(50);
let result = solver.solve(&board, &mover, &opponent, &lex);
assert!(!result.exact, "50 nodes cannot solve this");
assert!(result.nodes >= 50);
}
#[test]
fn transposition_keys_separate_different_positions() {
let config = config();
let z = Zobrist::new(&config);
let empty = Board::new(&config.layout);
let played = board_with(&config, 7, 6, "CAT");
let a = Rack::parse(&config.alphabet, "AB").unwrap();
let b = Rack::parse(&config.alphabet, "CD").unwrap();
assert_ne!(z.key(&empty, &a, &b, 0), z.key(&played, &a, &b, 0));
assert_ne!(z.key(&empty, &a, &b, 0), z.key(&empty, &b, &a, 0));
assert_ne!(z.key(&empty, &a, &b, 0), z.key(&empty, &a, &b, 1));
assert_eq!(z.key(&played, &a, &b, 0), z.key(&played, &a, &b, 0));
}
#[test]
fn a_blank_on_the_board_hashes_differently_from_the_letter() {
let config = config();
let z = Zobrist::new(&config);
let mut plain = Board::new(&config.layout);
plain.set(7, 7, Square::letter(4));
let mut blank = Board::new(&config.layout);
blank.set(7, 7, Square::blank_letter(4));
let r = Rack::new();
assert_ne!(z.key(&plain, &r, &r, 0), z.key(&blank, &r, &r, 0));
}
}