Skip to main content

ai_backgammon/
board.rs

1use crate::Dice;
2use crate::movegen;
3use crate::play::{Location, Play, PlayError, PlayOutcome, Step, destination};
4use std::fmt;
5
6const CHECKERS: u8 = 15;
7
8#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
9/// A side, with White moving toward point 1 and Black toward point 24.
10pub enum Player {
11    White,
12    Black,
13}
14
15impl Player {
16    pub const fn other(self) -> Self {
17        match self {
18            Self::White => Self::Black,
19            Self::Black => Self::White,
20        }
21    }
22
23    pub const fn index(self) -> usize {
24        match self {
25            Self::White => 0,
26            Self::Black => 1,
27        }
28    }
29
30    pub const fn as_str(self) -> &'static str {
31        match self {
32            Self::White => "white",
33            Self::Black => "black",
34        }
35    }
36}
37
38impl fmt::Display for Player {
39    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
40        formatter.write_str(self.as_str())
41    }
42}
43
44#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
45pub struct Point(u8);
46
47impl Point {
48    pub const fn new(number: u8) -> Option<Self> {
49        if number >= 1 && number <= 24 {
50            Some(Self(number))
51        } else {
52            None
53        }
54    }
55
56    pub const fn number(self) -> u8 {
57        self.0
58    }
59
60    pub(crate) const fn index(self) -> usize {
61        (self.0 - 1) as usize
62    }
63}
64
65impl fmt::Display for Point {
66    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
67        self.0.fmt(formatter)
68    }
69}
70
71#[derive(Clone, Copy, Debug, Eq, PartialEq)]
72pub enum GameKind {
73    Single,
74    Gammon,
75    Backgammon,
76}
77
78impl GameKind {
79    pub const fn multiplier(self) -> u32 {
80        match self {
81            Self::Single => 1,
82            Self::Gammon => 2,
83            Self::Backgammon => 3,
84        }
85    }
86}
87
88#[derive(Clone, Copy, Debug, Eq, PartialEq)]
89pub struct GameOutcome {
90    pub winner: Player,
91    pub kind: GameKind,
92}
93
94#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
95/// A complete checker position.
96///
97/// Positive point counts are White checkers and negative counts are Black.
98pub struct Position {
99    points: [i8; 24],
100    bar: [u8; 2],
101    off: [u8; 2],
102    side_to_move: Player,
103}
104
105impl Default for Position {
106    fn default() -> Self {
107        Self::new()
108    }
109}
110
111impl Position {
112    pub const fn new() -> Self {
113        let mut points = [0; 24];
114        points[23] = 2;
115        points[12] = 5;
116        points[7] = 3;
117        points[5] = 5;
118        points[0] = -2;
119        points[11] = -5;
120        points[16] = -3;
121        points[18] = -5;
122        Self {
123            points,
124            bar: [0; 2],
125            off: [0; 2],
126            side_to_move: Player::White,
127        }
128    }
129
130    /// Builds a position from signed point counts and the remaining game state.
131    ///
132    /// Positive point counts are White checkers, negative counts are Black,
133    /// and both `bar` and `off` are ordered `[White, Black]`.
134    pub fn from_parts(
135        points: [i8; 24],
136        bar: [u8; 2],
137        off: [u8; 2],
138        side_to_move: Player,
139    ) -> Result<Self, PositionError> {
140        let position = Self {
141            points,
142            bar,
143            off,
144            side_to_move,
145        };
146        position.validate()?;
147        Ok(position)
148    }
149
150    pub const fn side_to_move(self) -> Player {
151        self.side_to_move
152    }
153
154    /// Returns points 1 through 24 as signed checker counts.
155    pub const fn points(self) -> [i8; 24] {
156        self.points
157    }
158
159    pub const fn bar(self, player: Player) -> u8 {
160        self.bar[player.index()]
161    }
162
163    pub const fn off(self, player: Player) -> u8 {
164        self.off[player.index()]
165    }
166
167    pub fn count(self, player: Player, point: Point) -> u8 {
168        let count = self.points[point.index()];
169        match player {
170            Player::White if count > 0 => count as u8,
171            Player::Black if count < 0 => count.unsigned_abs(),
172            _ => 0,
173        }
174    }
175
176    /// Returns the legal next checker steps for one die.
177    ///
178    /// This is a partial-turn helper. [`Self::legal_plays`] enforces using the
179    /// maximum number of dice and the higher-die rule across the complete turn.
180    pub fn legal_steps(self, die: u8) -> Vec<Step> {
181        if !(1..=6).contains(&die) || self.game_outcome().is_some() {
182            return Vec::new();
183        }
184        let player = self.side_to_move;
185        if self.bar(player) > 0 {
186            let point = match player {
187                Player::White => Point::new(25 - die).expect("entry die is valid"),
188                Player::Black => Point::new(die).expect("entry die is valid"),
189            };
190            return self
191                .is_open(player, point)
192                .then(|| Step::unchecked(Location::Bar, Location::Point(point), die))
193                .into_iter()
194                .collect();
195        }
196
197        let mut steps = Vec::new();
198        for number in 1..=24 {
199            let point = Point::new(number).expect("board point is valid");
200            if self.count(player, point) == 0 {
201                continue;
202            }
203            let to = destination(player, point, die);
204            match to {
205                Location::Point(target) if self.is_open(player, target) => {
206                    steps.push(Step::unchecked(Location::Point(point), to, die));
207                }
208                Location::Off if self.can_bear_off(player, point, die) => {
209                    steps.push(Step::unchecked(Location::Point(point), Location::Off, die));
210                }
211                _ => {}
212            }
213        }
214        steps.sort();
215        steps
216    }
217
218    /// Generates every legal complete turn for `dice`, retaining checker-step order.
219    pub fn legal_plays(self, dice: Dice) -> Vec<Play> {
220        movegen::legal_plays(self, dice)
221    }
222
223    /// Groups legal step sequences that reach the same resulting position.
224    pub fn legal_outcomes(self, dice: Dice) -> Vec<PlayOutcome> {
225        let mut outcomes: Vec<PlayOutcome> = Vec::new();
226        for play in self.legal_plays(dice) {
227            let mut next = self;
228            next.apply_play_unchecked(&play);
229            if let Some(outcome) = outcomes
230                .iter_mut()
231                .find(|outcome| outcome.position() == next)
232            {
233                outcome.push(play);
234            } else {
235                outcomes.push(PlayOutcome::new(next, play));
236            }
237        }
238        outcomes.sort_by(|left, right| left.representative().cmp(right.representative()));
239        outcomes
240    }
241
242    /// Validates and applies one complete checker play.
243    pub fn play(self, dice: Dice, play: &Play) -> Result<Self, PlayError> {
244        let mut next = self;
245        next.make_play(dice, play)?;
246        Ok(next)
247    }
248
249    /// Applies a complete legal turn and returns the state needed to undo it.
250    pub fn make_play(&mut self, dice: Dice, play: &Play) -> Result<Undo, PlayError> {
251        if self.game_outcome().is_some() {
252            return Err(PlayError::GameOver);
253        }
254        if !self.legal_plays(dice).iter().any(|legal| legal == play) {
255            return Err(PlayError::IllegalPlay);
256        }
257        let undo = Undo { previous: *self };
258        self.apply_play_unchecked(play);
259        Ok(undo)
260    }
261
262    pub fn unmake(&mut self, undo: Undo) {
263        *self = undo.previous;
264    }
265
266    pub fn game_outcome(self) -> Option<GameOutcome> {
267        let winner = if self.off(Player::White) == CHECKERS {
268            Player::White
269        } else if self.off(Player::Black) == CHECKERS {
270            Player::Black
271        } else {
272            return None;
273        };
274        let loser = winner.other();
275        let kind = if self.off(loser) > 0 {
276            GameKind::Single
277        } else if self.bar(loser) > 0 || self.has_checker_in_home(loser, winner) {
278            GameKind::Backgammon
279        } else {
280            GameKind::Gammon
281        };
282        Some(GameOutcome { winner, kind })
283    }
284
285    /// Returns a deterministic transposition key for this crate version.
286    ///
287    /// This is an in-memory search key, not a stable serialization format.
288    pub fn hash(self) -> u64 {
289        let mut hash = 0xcbf2_9ce4_8422_2325_u64;
290        for value in self.points {
291            hash ^= u64::from(value as u8);
292            hash = hash.wrapping_mul(0x100_0000_01b3);
293        }
294        for value in self.bar.into_iter().chain(self.off) {
295            hash ^= u64::from(value);
296            hash = hash.wrapping_mul(0x100_0000_01b3);
297        }
298        hash ^ (self.side_to_move.index() as u64)
299    }
300
301    pub fn validate(self) -> Result<(), PositionError> {
302        if self
303            .points
304            .iter()
305            .any(|count| count.unsigned_abs() > CHECKERS)
306        {
307            return Err(PositionError::PointOverflow);
308        }
309        for player in [Player::White, Player::Black] {
310            let on_board: u16 = (1..=24)
311                .map(|number| {
312                    self.count(player, Point::new(number).expect("board point is valid")) as u16
313                })
314                .sum();
315            let total = on_board + u16::from(self.bar(player)) + u16::from(self.off(player));
316            if total != u16::from(CHECKERS) {
317                return Err(PositionError::CheckerCount {
318                    player,
319                    found: total,
320                });
321            }
322        }
323        if self.off(Player::White) == CHECKERS && self.off(Player::Black) == CHECKERS {
324            return Err(PositionError::TwoWinners);
325        }
326        Ok(())
327    }
328
329    pub(crate) fn apply_step_unchecked(&mut self, step: Step) {
330        let player = self.side_to_move;
331        match step.from() {
332            Location::Bar => self.bar[player.index()] -= 1,
333            Location::Point(point) => self.remove_checker(player, point),
334            Location::Off => unreachable!("borne-off checkers cannot move"),
335        }
336        match step.to() {
337            Location::Point(point) => {
338                let opponent = player.other();
339                if self.count(opponent, point) == 1 {
340                    self.remove_checker(opponent, point);
341                    self.bar[opponent.index()] += 1;
342                }
343                self.add_checker(player, point);
344            }
345            Location::Off => self.off[player.index()] += 1,
346            Location::Bar => unreachable!("checkers cannot move to the bar directly"),
347        }
348    }
349
350    pub(crate) fn apply_play_unchecked(&mut self, play: &Play) {
351        for &step in play.steps() {
352            self.apply_step_unchecked(step);
353        }
354        self.side_to_move = self.side_to_move.other();
355    }
356
357    pub(crate) fn set_side_to_move(&mut self, player: Player) {
358        self.side_to_move = player;
359    }
360
361    fn is_open(self, player: Player, point: Point) -> bool {
362        self.count(player.other(), point) < 2
363    }
364
365    fn all_in_home(self, player: Player) -> bool {
366        if self.bar(player) > 0 {
367            return false;
368        }
369        match player {
370            Player::White => (7..=24).all(|number| {
371                self.count(player, Point::new(number).expect("board point is valid")) == 0
372            }),
373            Player::Black => (1..=18).all(|number| {
374                self.count(player, Point::new(number).expect("board point is valid")) == 0
375            }),
376        }
377    }
378
379    fn can_bear_off(self, player: Player, point: Point, die: u8) -> bool {
380        if !self.all_in_home(player) {
381            return false;
382        }
383        let distance = match player {
384            Player::White => point.number(),
385            Player::Black => 25 - point.number(),
386        };
387        if die == distance {
388            return true;
389        }
390        if die < distance {
391            return false;
392        }
393        match player {
394            Player::White => ((point.number() + 1)..=6).all(|number| {
395                self.count(player, Point::new(number).expect("home point is valid")) == 0
396            }),
397            Player::Black => (19..point.number()).all(|number| {
398                self.count(player, Point::new(number).expect("home point is valid")) == 0
399            }),
400        }
401    }
402
403    fn has_checker_in_home(self, checker: Player, owner: Player) -> bool {
404        let mut range = match owner {
405            Player::White => 1..=6,
406            Player::Black => 19..=24,
407        };
408        range
409            .any(|number| self.count(checker, Point::new(number).expect("home point is valid")) > 0)
410    }
411
412    fn remove_checker(&mut self, player: Player, point: Point) {
413        match player {
414            Player::White => self.points[point.index()] -= 1,
415            Player::Black => self.points[point.index()] += 1,
416        }
417    }
418
419    fn add_checker(&mut self, player: Player, point: Point) {
420        match player {
421            Player::White => self.points[point.index()] += 1,
422            Player::Black => self.points[point.index()] -= 1,
423        }
424    }
425}
426
427#[derive(Clone, Copy, Debug, Eq, PartialEq)]
428pub struct Undo {
429    previous: Position,
430}
431
432#[derive(Clone, Copy, Debug, Eq, PartialEq)]
433pub enum PositionError {
434    CheckerCount { player: Player, found: u16 },
435    PointOverflow,
436    TwoWinners,
437}
438
439impl fmt::Display for PositionError {
440    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
441        match self {
442            Self::CheckerCount { player, found } => {
443                write!(
444                    formatter,
445                    "{player} has {found} checkers instead of fifteen"
446                )
447            }
448            Self::PointOverflow => {
449                formatter.write_str("a point contains more than fifteen checkers")
450            }
451            Self::TwoWinners => {
452                formatter.write_str("both players cannot have borne off every checker")
453            }
454        }
455    }
456}
457
458impl std::error::Error for PositionError {}