Skip to main content

ai_chess/
position.rs

1use crate::attacks;
2use crate::zobrist;
3use crate::{Color, Move, MoveKind, MoveList, Piece, PieceKind, Square};
4use std::fmt;
5
6pub(crate) const START_FEN: &str = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1";
7
8/// Four-bit set of orthodox castling permissions.
9#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
10pub struct CastlingRights(u8);
11
12impl CastlingRights {
13    pub const WHITE_KING: u8 = 1;
14    pub const WHITE_QUEEN: u8 = 2;
15    pub const BLACK_KING: u8 = 4;
16    pub const BLACK_QUEEN: u8 = 8;
17
18    pub const fn new(bits: u8) -> Self {
19        Self(bits & 0x0f)
20    }
21
22    pub const fn bits(self) -> u8 {
23        self.0
24    }
25
26    pub const fn has(self, flag: u8) -> bool {
27        self.0 & flag != 0
28    }
29
30    pub(crate) fn remove(&mut self, flags: u8) {
31        self.0 &= !flags;
32    }
33}
34
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub enum GameResult {
37    Ongoing,
38    Checkmate { winner: Color },
39    Stalemate,
40    FiftyMoveDraw,
41    InsufficientMaterialDraw,
42}
43
44#[derive(Debug, Clone, Copy, PartialEq, Eq)]
45pub enum MoveError {
46    NoPiece(Square),
47    WrongSide(Square),
48    Illegal(Move),
49}
50
51impl fmt::Display for MoveError {
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        match self {
54            Self::NoPiece(square) => write!(f, "there is no piece on {square}"),
55            Self::WrongSide(square) => write!(f, "the piece on {square} is not the side to move"),
56            Self::Illegal(mv) => write!(f, "{mv} is not legal in this position"),
57        }
58    }
59}
60
61impl std::error::Error for MoveError {}
62
63/// Opaque record containing every field changed by one move.
64///
65/// Pass it back to [`Position::unmake_move`] to restore the exact prior
66/// position, including clocks, castling, en-passant state, and hash key.
67#[derive(Debug, Clone, Copy, PartialEq, Eq)]
68pub struct Undo {
69    mv: Move,
70    moved: Piece,
71    captured: Option<(Piece, Square)>,
72    castling: CastlingRights,
73    en_passant: Option<Square>,
74    halfmove_clock: u16,
75    fullmove_number: u16,
76    key: u64,
77}
78
79/// Complete, reversible chess position.
80///
81/// Piece placement is held in synchronized bitboards and a mailbox. The
82/// position also owns all rule state and its incremental Zobrist key.
83#[derive(Debug, Clone, PartialEq, Eq)]
84pub struct Position {
85    pub(crate) pieces: [[u64; 6]; 2],
86    pub(crate) color_occupancy: [u64; 2],
87    pub(crate) occupied: u64,
88    pub(crate) mailbox: [Option<Piece>; 64],
89    pub(crate) side_to_move: Color,
90    pub(crate) castling: CastlingRights,
91    pub(crate) en_passant: Option<Square>,
92    pub(crate) halfmove_clock: u16,
93    pub(crate) fullmove_number: u16,
94    pub(crate) key: u64,
95}
96
97impl Default for Position {
98    fn default() -> Self {
99        Self::start()
100    }
101}
102
103impl Position {
104    pub fn start() -> Self {
105        Self::from_fen(START_FEN).expect("the built-in starting FEN must be valid")
106    }
107
108    pub(crate) fn empty() -> Self {
109        Self {
110            pieces: [[0; 6]; 2],
111            color_occupancy: [0; 2],
112            occupied: 0,
113            mailbox: [None; 64],
114            side_to_move: Color::White,
115            castling: CastlingRights::default(),
116            en_passant: None,
117            halfmove_clock: 0,
118            fullmove_number: 1,
119            key: 0,
120        }
121    }
122
123    pub const fn side_to_move(&self) -> Color {
124        self.side_to_move
125    }
126
127    pub const fn castling_rights(&self) -> CastlingRights {
128        self.castling
129    }
130
131    pub const fn en_passant(&self) -> Option<Square> {
132        self.en_passant
133    }
134
135    pub const fn halfmove_clock(&self) -> u16 {
136        self.halfmove_clock
137    }
138
139    pub const fn fullmove_number(&self) -> u16 {
140        self.fullmove_number
141    }
142
143    pub const fn key(&self) -> u64 {
144        self.key
145    }
146
147    pub const fn occupied(&self) -> u64 {
148        self.occupied
149    }
150
151    pub const fn occupancy(&self, color: Color) -> u64 {
152        self.color_occupancy[color.index()]
153    }
154
155    pub const fn pieces(&self, color: Color, kind: PieceKind) -> u64 {
156        self.pieces[color.index()][kind.index()]
157    }
158
159    pub fn piece_at(&self, square: Square) -> Option<Piece> {
160        self.mailbox[square.index()]
161    }
162
163    pub fn king_square(&self, color: Color) -> Option<Square> {
164        let king = self.pieces(color, PieceKind::King);
165        (king != 0).then(|| Square::new(king.trailing_zeros() as u8))
166    }
167
168    pub fn in_check(&self, color: Color) -> bool {
169        self.king_square(color)
170            .is_some_and(|king| attacks::square_is_attacked(self, king, color.other()))
171    }
172
173    /// Generates every legal move in deterministic order.
174    ///
175    /// Move generation temporarily makes pseudo-legal moves to reject those
176    /// that leave the moving side's king in check.
177    pub fn legal_moves(&mut self) -> MoveList {
178        let pseudo = crate::movegen::pseudo_legal(self);
179        let mover = self.side_to_move;
180        let mut legal = MoveList::default();
181        for mv in pseudo {
182            let undo = self
183                .make_unchecked(mv)
184                .expect("generated pseudo-legal move must have a moving piece");
185            let leaves_king_safe = !self.in_check(mover);
186            self.unmake_move(undo);
187            if leaves_king_safe {
188                legal.push(mv);
189            }
190        }
191        legal
192    }
193
194    pub fn find_move(&mut self, notation: &str) -> Result<Move, &'static str> {
195        self.legal_moves()
196            .into_iter()
197            .find(|mv| mv.to_string() == notation)
198            .ok_or("move is not legal in this position")
199    }
200
201    pub fn make_move(&mut self, mv: Move) -> Result<Undo, MoveError> {
202        let piece = self
203            .piece_at(mv.from())
204            .ok_or(MoveError::NoPiece(mv.from()))?;
205        if piece.color != self.side_to_move {
206            return Err(MoveError::WrongSide(mv.from()));
207        }
208        if !self.legal_moves().as_slice().contains(&mv) {
209            return Err(MoveError::Illegal(mv));
210        }
211        self.make_unchecked(mv)
212    }
213
214    pub fn play_uci(&mut self, notation: &str) -> Result<Undo, &'static str> {
215        let mv = self.find_move(notation)?;
216        self.make_unchecked(mv)
217            .map_err(|_| "move could not be made")
218    }
219
220    /// Restores the exact position that existed before `undo`.
221    pub fn unmake_move(&mut self, undo: Undo) {
222        self.side_to_move = undo.moved.color;
223        let destination_piece = self
224            .piece_at(undo.mv.to())
225            .expect("made move must leave a piece on its destination");
226        self.remove_piece(undo.mv.to(), destination_piece);
227
228        match undo.mv.kind() {
229            MoveKind::CastleKingSide => {
230                let rank = undo.moved.color.home_rank();
231                let rook_to = Square::from_file_rank(5, rank);
232                let rook_from = Square::from_file_rank(7, rank);
233                let rook = self
234                    .piece_at(rook_to)
235                    .expect("castling must leave its rook on f-file");
236                self.remove_piece(rook_to, rook);
237                self.put_piece(rook_from, rook);
238            }
239            MoveKind::CastleQueenSide => {
240                let rank = undo.moved.color.home_rank();
241                let rook_to = Square::from_file_rank(3, rank);
242                let rook_from = Square::from_file_rank(0, rank);
243                let rook = self
244                    .piece_at(rook_to)
245                    .expect("castling must leave its rook on d-file");
246                self.remove_piece(rook_to, rook);
247                self.put_piece(rook_from, rook);
248            }
249            MoveKind::Normal | MoveKind::EnPassant | MoveKind::Promotion(_) => {}
250        }
251
252        self.put_piece(undo.mv.from(), undo.moved);
253        if let Some((captured, square)) = undo.captured {
254            self.put_piece(square, captured);
255        }
256        self.castling = undo.castling;
257        self.en_passant = undo.en_passant;
258        self.halfmove_clock = undo.halfmove_clock;
259        self.fullmove_number = undo.fullmove_number;
260        self.key = undo.key;
261        debug_assert!(self.is_consistent());
262    }
263
264    /// Returns the current rules-level result.
265    ///
266    /// Threefold repetition depends on history outside a single position and
267    /// is therefore handled by the search/session layer.
268    pub fn result(&mut self) -> GameResult {
269        if self.legal_moves().is_empty() {
270            if self.in_check(self.side_to_move) {
271                GameResult::Checkmate {
272                    winner: self.side_to_move.other(),
273                }
274            } else {
275                GameResult::Stalemate
276            }
277        } else if self.halfmove_clock >= 100 {
278            GameResult::FiftyMoveDraw
279        } else if self.has_insufficient_material() {
280            GameResult::InsufficientMaterialDraw
281        } else {
282            GameResult::Ongoing
283        }
284    }
285
286    /// Returns true only for material sets from which no legal sequence can
287    /// end in checkmate. This intentionally avoids broad "minor pieces only"
288    /// shortcuts: two knights, bishop-and-knight, and opposite-colored bishops
289    /// can all participate in a helpmate.
290    pub fn has_insufficient_material(&self) -> bool {
291        let pawns =
292            self.pieces(Color::White, PieceKind::Pawn) | self.pieces(Color::Black, PieceKind::Pawn);
293        let rooks =
294            self.pieces(Color::White, PieceKind::Rook) | self.pieces(Color::Black, PieceKind::Rook);
295        let queens = self.pieces(Color::White, PieceKind::Queen)
296            | self.pieces(Color::Black, PieceKind::Queen);
297        if pawns | rooks | queens != 0 {
298            return false;
299        }
300
301        let knights = self.pieces(Color::White, PieceKind::Knight)
302            | self.pieces(Color::Black, PieceKind::Knight);
303        let bishops = self.pieces(Color::White, PieceKind::Bishop)
304            | self.pieces(Color::Black, PieceKind::Bishop);
305        if bishops == 0 {
306            return knights.count_ones() <= 1;
307        }
308        if knights != 0 {
309            return false;
310        }
311
312        let mut remaining = bishops;
313        let first = remaining.trailing_zeros() as u8;
314        let first_color = ((first & 7) + (first >> 3)) & 1;
315        remaining &= remaining - 1;
316        while remaining != 0 {
317            let square = remaining.trailing_zeros() as u8;
318            let color = ((square & 7) + (square >> 3)) & 1;
319            if color != first_color {
320                return false;
321            }
322            remaining &= remaining - 1;
323        }
324        true
325    }
326
327    pub fn assert_consistent(&self) {
328        assert!(
329            self.is_consistent(),
330            "chess position representations drifted"
331        );
332    }
333
334    pub(crate) fn make_unchecked(&mut self, mv: Move) -> Result<Undo, MoveError> {
335        let moved = self
336            .piece_at(mv.from())
337            .ok_or(MoveError::NoPiece(mv.from()))?;
338        if moved.color != self.side_to_move {
339            return Err(MoveError::WrongSide(mv.from()));
340        }
341        let previous = Undo {
342            mv,
343            moved,
344            captured: None,
345            castling: self.castling,
346            en_passant: self.en_passant,
347            halfmove_clock: self.halfmove_clock,
348            fullmove_number: self.fullmove_number,
349            key: self.key,
350        };
351
352        self.key ^= zobrist::castling(self.castling.bits());
353        if let Some(file) = self.hashed_en_passant_file() {
354            self.key ^= zobrist::en_passant(file);
355        }
356        self.en_passant = None;
357        self.remove_piece(mv.from(), moved);
358
359        let capture_square = if mv.kind() == MoveKind::EnPassant {
360            mv.to()
361                .offset(0, -moved.color.pawn_step())
362                .expect("en-passant destination must have a square behind it")
363        } else {
364            mv.to()
365        };
366        let captured = self.piece_at(capture_square);
367        if let Some(piece) = captured {
368            self.remove_piece(capture_square, piece);
369        }
370
371        let placed = match mv.kind() {
372            MoveKind::Promotion(kind) => Piece::new(moved.color, kind),
373            MoveKind::Normal
374            | MoveKind::CastleKingSide
375            | MoveKind::CastleQueenSide
376            | MoveKind::EnPassant => moved,
377        };
378        self.put_piece(mv.to(), placed);
379
380        match mv.kind() {
381            MoveKind::CastleKingSide => {
382                let rank = moved.color.home_rank();
383                self.move_piece(
384                    Square::from_file_rank(7, rank),
385                    Square::from_file_rank(5, rank),
386                );
387            }
388            MoveKind::CastleQueenSide => {
389                let rank = moved.color.home_rank();
390                self.move_piece(
391                    Square::from_file_rank(0, rank),
392                    Square::from_file_rank(3, rank),
393                );
394            }
395            MoveKind::Normal | MoveKind::EnPassant | MoveKind::Promotion(_) => {}
396        }
397
398        self.update_castling_rights(
399            moved,
400            mv.from(),
401            captured.map(|piece| (piece, capture_square)),
402        );
403        if moved.kind == PieceKind::Pawn && mv.from().rank().abs_diff(mv.to().rank()) == 2 {
404            self.en_passant = mv.from().offset(0, moved.color.pawn_step());
405        }
406        self.halfmove_clock = if moved.kind == PieceKind::Pawn || captured.is_some() {
407            0
408        } else {
409            self.halfmove_clock.saturating_add(1)
410        };
411        if moved.color == Color::Black {
412            self.fullmove_number = self.fullmove_number.saturating_add(1);
413        }
414        self.side_to_move = moved.color.other();
415        self.key ^= zobrist::side();
416        self.key ^= zobrist::castling(self.castling.bits());
417        if let Some(file) = self.hashed_en_passant_file() {
418            self.key ^= zobrist::en_passant(file);
419        }
420        debug_assert!(self.is_consistent());
421        Ok(Undo {
422            captured: captured.map(|piece| (piece, capture_square)),
423            ..previous
424        })
425    }
426
427    pub(crate) fn put_piece(&mut self, square: Square, piece: Piece) {
428        debug_assert!(self.mailbox[square.index()].is_none());
429        let bit = attacks::bit(square);
430        self.pieces[piece.color.index()][piece.kind.index()] |= bit;
431        self.color_occupancy[piece.color.index()] |= bit;
432        self.occupied |= bit;
433        self.mailbox[square.index()] = Some(piece);
434        self.key ^= zobrist::piece(piece, square);
435    }
436
437    fn remove_piece(&mut self, square: Square, piece: Piece) {
438        debug_assert_eq!(self.mailbox[square.index()], Some(piece));
439        let bit = attacks::bit(square);
440        self.pieces[piece.color.index()][piece.kind.index()] &= !bit;
441        self.color_occupancy[piece.color.index()] &= !bit;
442        self.occupied &= !bit;
443        self.mailbox[square.index()] = None;
444        self.key ^= zobrist::piece(piece, square);
445    }
446
447    fn move_piece(&mut self, from: Square, to: Square) {
448        let piece = self
449            .piece_at(from)
450            .expect("moving a piece internally requires a source piece");
451        self.remove_piece(from, piece);
452        self.put_piece(to, piece);
453    }
454
455    fn update_castling_rights(
456        &mut self,
457        moved: Piece,
458        from: Square,
459        captured: Option<(Piece, Square)>,
460    ) {
461        if moved.kind == PieceKind::King {
462            self.castling.remove(match moved.color {
463                Color::White => CastlingRights::WHITE_KING | CastlingRights::WHITE_QUEEN,
464                Color::Black => CastlingRights::BLACK_KING | CastlingRights::BLACK_QUEEN,
465            });
466        }
467        if moved.kind == PieceKind::Rook {
468            self.revoke_rook_square(from);
469        }
470        if let Some((piece, square)) = captured {
471            if piece.kind == PieceKind::Rook {
472                self.revoke_rook_square(square);
473            }
474        }
475    }
476
477    fn revoke_rook_square(&mut self, square: Square) {
478        let flag = match (square.file(), square.rank()) {
479            (7, 0) => CastlingRights::WHITE_KING,
480            (0, 0) => CastlingRights::WHITE_QUEEN,
481            (7, 7) => CastlingRights::BLACK_KING,
482            (0, 7) => CastlingRights::BLACK_QUEEN,
483            _ => 0,
484        };
485        self.castling.remove(flag);
486    }
487
488    pub(crate) fn hashed_en_passant_file(&self) -> Option<u8> {
489        let target = self.en_passant?;
490        let source_rank_delta = -self.side_to_move.pawn_step();
491        [-1, 1].into_iter().find_map(|file_delta| {
492            let source = target.offset(file_delta, source_rank_delta)?;
493            (self.piece_at(source) == Some(Piece::new(self.side_to_move, PieceKind::Pawn)))
494                .then_some(target.file())
495        })
496    }
497
498    fn is_consistent(&self) -> bool {
499        let mut pieces = [[0u64; 6]; 2];
500        let mut colors = [0u64; 2];
501        let mut occupied = 0;
502        for square in Square::all() {
503            if let Some(piece) = self.mailbox[square.index()] {
504                let bit = attacks::bit(square);
505                pieces[piece.color.index()][piece.kind.index()] |= bit;
506                colors[piece.color.index()] |= bit;
507                occupied |= bit;
508            }
509        }
510        pieces == self.pieces
511            && colors == self.color_occupancy
512            && occupied == self.occupied
513            && colors[0] & colors[1] == 0
514            && zobrist::compute(self) == self.key
515    }
516}