chess/
position.rs

1//! # Chess positions
2//!
3//! Any [`Position`] is determined by:
4//! - the location of pieces on the [`Board`]
5//! - parameters for the next turn (these are not visible from the board itself)
6//!   - the [`Player`] whose turn it is
7//!   - the possible castle [`Sides`]
8//!   - the possible en-passant [`Square`] if any
9//! - counter for "reversible" turns since last "non-reversible" (aka pawn moves + captures) [`Move`], aka "halfmoves"
10//! - counter of full rounds, aka "fullmoves"
11//!
12//! Compared to `shakmaty` our position is a concrete `struct`
13#[cfg(test)]
14extern crate alloc;
15
16use core::{
17    num::{NonZeroI32, NonZeroU32},
18    ops::Deref,
19};
20
21use crate::{Board, Player, Role, Scharnagl, Square, board::Bitboard, square::File};
22
23use Player::*;
24use Role::*;
25
26mod play;
27mod plays;
28mod rights;
29mod validate;
30
31pub use play::*;
32pub use rights::*;
33
34pub use Kind::Normal;
35pub use Special::{Castle, Promote};
36
37#[derive(Clone, Copy, Debug, Eq, PartialEq, thiserror::Error)]
38pub enum Error {
39    #[error("inconsistent board bitboards")]
40    InconsistentBoard,
41    #[error("expected exactly one {0} king")]
42    KingCount(Player),
43    #[error("pawns cannot be on the first or eighth rank")]
44    PawnOnBackrank,
45    #[error("kings cannot be adjacent")]
46    AdjacentKings,
47    #[error("{0} king is attacked")]
48    KingAttacked(Player),
49    #[error("{0} king with castling rights is not on its back rank")]
50    CastleKing(Player),
51    #[error("no {player} rook for {side:?}-side castling on {file}")]
52    CastleRook { player: Player, side: Side, file: File },
53    #[error("{player} castling rook on {file} is not on the {side:?} side")]
54    CastleSide { player: Player, side: Side, file: File },
55    #[error("no piece on {0}")]
56    MissingPiece(Square),
57}
58
59pub type Result<T, E = Error> = core::result::Result<T, E>;
60
61/// Chess position, including the board, turn, rights, and counters.
62///
63/// Size:
64/// - board: 9 * 8 = 72 bytes
65/// - turn: 1 byte (really 1 bit)
66/// - castle rights: 2 bytes (really 2 bits)
67/// - en passant square: 1 bytes (really 65 options)
68/// - reversible move counter: 4 bytes (modeled as u32, really 1 byte would be enough)
69/// - round counter: 4 bytes (value >=1, u16 or even u8 should be enough, who has 65536 rounds in a game of chess?)
70///
71/// Unpacked, this amounts to 88 bytes (Rust 1.91).
72/// Packed it is 84 bytes.
73///
74/// <https://lichess.org/@/revoof/blog/adapting-nnue-pytorchs-binary-position-format-for-lichess/cpeeAMeY>
75/// shows that about 18.7 bytes is enough
76///
77/// Besides size, a goal is also to stick these into SQLite3 (or DuckDB), and make something
78/// similar to [Chess Query Language][cql] (with a less weird syntax...) efficently implementable.
79///
80/// The contents can be split in:
81/// - board
82/// - rights: turn + castle + en passant
83/// - counters
84///
85/// [cql]: https://en.wikipedia.org/wiki/Chess_Query_Language
86#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
87pub struct Position {
88    /// location of the pieces on the board
89    board: Board,
90    /// player to move
91    turn: Player,
92    /// possible castle sides
93    castles: Castles,
94    /// possible en passant square
95    en_passant: Option<EnPassant>,
96    /// ply counter since last capture or pawn move (reversible moves)
97    reversible: u32,
98    /// starts at 1 and increments after every Black move
99    round: NonZeroU32,
100}
101
102/// The raw parts from which a position can be constructed.
103#[derive(Clone, Copy, Debug, Eq, Ord, PartialEq, PartialOrd)]
104pub struct Parts {
105    /// location of the pieces on the board
106    pub board: Board,
107    /// player to move
108    pub turn: Player,
109    /// possible castle sides
110    pub castles: Castles,
111    /// possible en passant square
112    pub en_passant: Option<EnPassant>,
113    /// ply counter since last capture or pawn move (reversible moves)
114    pub reversible: u32,
115    /// starts at 1 and increments after every Black move
116    pub round: NonZeroU32,
117}
118
119#[derive(Clone, Copy, Debug, Eq, PartialEq)]
120pub enum Check {
121    Check,
122    Checkmate,
123}
124
125#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
126#[serde(untagged)]
127pub enum Evaluation<M = Move> {
128    Terminal(Terminal),
129    Lines(Lines<M>),
130}
131
132#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
133pub struct Line<M = Move> {
134    #[serde(flatten)]
135    pub score: Score,
136    pub moves: Vec1<M>,
137}
138
139#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
140pub struct Lines<M = Move> {
141    pub depth: u16,
142    pub lines: Vec1<Line<M>>,
143}
144
145#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
146#[serde(rename_all = "lowercase")]
147pub enum Score {
148    Centipawns(i32),
149    Mate(NonZeroI32),
150}
151
152/// Why a position has no legal moves.
153#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
154#[serde(rename_all = "lowercase")]
155pub enum Terminal {
156    Checkmate,
157    Stalemate,
158}
159
160#[derive(Clone, Copy, Debug, Deserialize, Eq, PartialEq, Serialize)]
161#[serde(untagged)]
162pub enum Valuation<M = Move> {
163    Score {
164        depth: u16,
165        #[serde(flatten)]
166        score: Score,
167        best: M,
168    },
169    Terminal(Terminal),
170}
171
172#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
173#[serde(try_from = "Vec<T>")]
174pub struct Vec1<T>(Vec<T>);
175
176impl Parts {
177    pub const fn new(board: Board, turn: Player) -> Self {
178        Self {
179            board,
180            turn,
181            castles: Castles::empty(),
182            en_passant: None,
183            reversible: 0,
184            round: NonZeroU32::MIN,
185        }
186    }
187
188    pub const fn empty() -> Self {
189        Self::new(Board::EMPTY, White)
190    }
191
192    pub const fn ply(&self) -> usize {
193        let round = self.round.get() as usize - 1;
194        round * 2 + self.turn.eq(Black) as usize
195    }
196}
197
198impl Default for Parts {
199    fn default() -> Self {
200        Self::empty()
201    }
202}
203
204impl Position {
205    pub fn is_terminal(&self) -> bool {
206        self.legal_plays().is_empty()
207    }
208
209    pub fn terminal(&self) -> Option<Terminal> {
210        if !self.is_terminal() {
211            return None;
212        }
213        Terminal::new(self.is_check(), true)
214    }
215
216    pub const fn start() -> Position {
217        Position {
218            board: Board::standard(),
219            turn: White,
220            castles: Castles::chess(),
221            en_passant: None,
222            reversible: 0,
223            round: NonZeroU32::MIN,
224        }
225    }
226
227    pub const fn freestyle(i: Scharnagl) -> Position {
228        // Construct board
229        let board = Board::freestyle(i);
230
231        // Extract castle rights
232        let king = board.king_of(White).unwrap();
233        let mut rooks = board.rooks();
234        let queen_rook = rooks.pop_first().unwrap().file();
235        let king_rook = rooks.first().unwrap().file();
236
237        let mut castles = Castles::empty();
238        castles.set(White, Side::of_rook(king, queen_rook), queen_rook);
239        castles.set(White, Side::of_rook(king, king_rook), king_rook);
240        castles.set(Black, Side::Queen, queen_rook);
241        castles.set(Black, Side::King, king_rook);
242
243        Position {
244            board,
245            turn: White,
246            castles,
247            en_passant: None,
248            reversible: 0,
249            round: NonZeroU32::MIN,
250        }
251    }
252}
253
254impl Position {
255    #[inline]
256    pub const fn board(&self) -> Board {
257        self.board
258    }
259
260    #[inline]
261    pub const fn turn(&self) -> Player {
262        self.turn
263    }
264
265    #[inline]
266    pub const fn castles(&self) -> Castles {
267        self.castles
268    }
269
270    #[inline]
271    pub const fn en_passant(&self) -> Option<EnPassant> {
272        self.en_passant
273    }
274
275    #[inline]
276    pub const fn reversible(&self) -> u32 {
277        self.reversible
278    }
279
280    #[inline]
281    pub const fn round(&self) -> NonZeroU32 {
282        self.round
283    }
284
285    pub const fn requires_freestyle(&self) -> bool {
286        !self.castles.chess_compatible()
287    }
288
289    pub const fn checkers(&self) -> Bitboard {
290        match self.board.king_of(self.turn) {
291            Some(king) => self.board.attacks_on(king, self.turn.other(), self.board.occupied()),
292            None => Bitboard::EMPTY,
293        }
294    }
295
296    pub const fn is_check(&self) -> bool {
297        !self.checkers().is_empty()
298    }
299}
300
301impl Position {
302    pub fn capture_plays(&self) -> Vec<Move> {
303        self.legal_plays().into_iter().filter(|play| play.is_capture()).collect()
304    }
305
306    pub fn castle_side_plays(&self, side: Side) -> Vec<Move> {
307        self.legal_plays().into_iter().filter(|play| play.is_castle_side(side)).collect()
308    }
309
310    pub fn castle_plays(&self) -> Vec<Move> {
311        self.legal_plays().into_iter().filter(|play| play.is_castle()).collect()
312    }
313}
314
315impl Position {
316    pub const fn parts(self) -> Parts {
317        Parts {
318            board: self.board,
319            turn: self.turn,
320            castles: self.castles,
321            en_passant: self.en_passant,
322            reversible: self.reversible,
323            round: self.round,
324        }
325    }
326
327    pub fn first_ply(&self) -> usize {
328        let round = self.round.get() as usize - 1;
329        round * 2 + usize::from(self.turn == Black)
330    }
331}
332
333impl From<Position> for Parts {
334    fn from(position: Position) -> Self {
335        position.parts()
336    }
337}
338
339impl Position {
340    pub(crate) fn apply_unchecked(mut self, play: Move) -> Position {
341        let player = self.turn;
342        let captured = if play.is_en_passant() {
343            Some(Square::new(play.to.file(), play.from.rank()))
344        } else if play.capture.is_some() {
345            Some(play.to)
346        } else {
347            None
348        };
349
350        if play.role == King {
351            self.castles.clear_player(player);
352        }
353
354        if play.role == Rook {
355            self.clear_castle_rook(player, play.from);
356        }
357
358        if let Some(captured) = captured {
359            self.clear_castle_rook(player.other(), captured);
360        }
361
362        self.board.play_unchecked(player, play);
363
364        let mut en_passant = None;
365        if play.role == Pawn {
366            let from = play.from as u8;
367            let to = play.to as u8;
368            if from.abs_diff(to) == 16 {
369                en_passant = EnPassant::try_from(Square::panicky_from_index((from + to) / 2)).ok();
370            }
371        }
372
373        if play.role == Pawn || play.capture.is_some() || play.is_en_passant() {
374            self.reversible = 0;
375        } else {
376            self.reversible += 1;
377        }
378
379        if player == Black {
380            self.round = self.round.saturating_add(1);
381        }
382
383        self.turn = player.other();
384        self.en_passant = match en_passant {
385            Some(en_passant) => self.board.attacked_en_passant(en_passant, self.turn),
386            None => None,
387        };
388        self
389    }
390
391    fn clear_castle_rook(&mut self, player: Player, square: Square) {
392        if square.rank() != player.backrank() {
393            return;
394        }
395
396        for side in Side::ALL {
397            if self.castles.get(player, side) == Some(square.file()) {
398                self.castles.clear(player, side);
399            }
400        }
401    }
402}
403
404impl Check {
405    pub const fn new(is_check: bool, terminal: bool) -> Option<Self> {
406        if !is_check {
407            return None;
408        }
409        Some(if terminal { Self::Checkmate } else { Self::Check })
410    }
411}
412
413impl<M: Clone> Evaluation<M> {
414    pub fn valuation(&self) -> Valuation<M> {
415        match self {
416            Self::Terminal(terminal) => Valuation::Terminal(*terminal),
417            Self::Lines(lines) => Valuation::Score {
418                depth: lines.depth,
419                score: lines.lines.first().score,
420                best: lines.best().clone(),
421            },
422        }
423    }
424}
425
426impl<M> Lines<M> {
427    pub fn best(&self) -> &M {
428        self.lines.first().moves.first()
429    }
430}
431
432impl Score {
433    pub fn flip(self) -> Self {
434        match self {
435            Self::Centipawns(value) => Self::Centipawns(-value),
436            Self::Mate(value) => Self::Mate(-value),
437        }
438    }
439}
440
441impl Terminal {
442    pub const fn new(is_check: bool, terminal: bool) -> Option<Self> {
443        if !terminal {
444            return None;
445        }
446        Some(if is_check { Self::Checkmate } else { Self::Stalemate })
447    }
448}
449
450impl<T> Vec1<T> {
451    pub fn new(values: Vec<T>) -> Option<Self> {
452        (!values.is_empty()).then_some(Self(values))
453    }
454
455    pub fn first(&self) -> &T {
456        self.0.first().expect("Vec1 is non-empty")
457    }
458}
459
460impl<T> Deref for Vec1<T> {
461    type Target = Vec<T>;
462
463    fn deref(&self) -> &Self::Target {
464        &self.0
465    }
466}
467
468impl<T> TryFrom<Vec<T>> for Vec1<T> {
469    type Error = &'static str;
470
471    fn try_from(values: Vec<T>) -> core::result::Result<Self, Self::Error> {
472        Self::new(values).ok_or("expected a non-empty array")
473    }
474}
475
476#[test]
477fn all_random() {
478    use alloc::collections::BTreeSet as Set;
479
480    let mut positions = Vec::new();
481    let all = Set::from_iter(1usize..=8);
482    for rook_l in 1usize..=8 {
483        for rook_r in rook_l + 2..=8 {
484            for king in (rook_l + 1)..rook_r {
485                assert!(rook_l < king);
486                assert!(king < rook_r);
487                let it = (1usize..rook_l)
488                    .chain((rook_l + 1)..king)
489                    .chain((king + 1)..rook_r)
490                    .chain((rook_r + 1)..=8);
491                for bishop_b in it.clone().filter(|i| (i & 1) == 1) {
492                    for bishop_w in it.clone().filter(|i| (i & 1) == 0) {
493                        let used = Set::from([rook_l, rook_r, king, bishop_b, bishop_w]);
494                        let remaining = all.difference(&used);
495                        for queen in remaining.clone() {
496                            let mut position = vec!['-'; 8];
497                            position[rook_l - 1] = 'r';
498                            position[rook_r - 1] = 'r';
499                            position[king - 1] = 'k';
500                            position[queen - 1] = 'q';
501                            position[bishop_w - 1] = 'b';
502                            position[bishop_b - 1] = 'b';
503                            for knight in remaining.clone() {
504                                if knight != queen {
505                                    position[knight - 1] = 'n';
506                                }
507                            }
508                            assert!(!position.contains(&'-'));
509                            positions.push(position);
510                        }
511                    }
512                }
513            }
514        }
515    }
516    for position in positions.iter() {
517        println!("{}", position.iter().collect::<String>());
518    }
519    assert_eq!(960, positions.len());
520}
chess/position.rs

chess/
position.rs
