chess/
key.rs

1pub mod base58;
2#[cfg(any(rust_chess_compile_time_polyglot_basis, test))]
3pub mod polyglot;
4#[cfg(any(rust_chess_compile_time_standard_basis, test))]
5pub mod standard;
6
7use crate::{
8    board::{Board, Player, PlayerTable, Role, RoleTable},
9    finite::Empty as _,
10    game::{Game, Line},
11    position::{Castles, EnPassant, EnPassantTable, Move, Position, Side},
12    square::{FileTable, SquareTable},
13};
14
15/// Type of chess lookup keys.
16#[derive(Clone, Copy, Debug, Default, Eq, Ord, PartialEq, PartialOrd)]
17pub struct Key(pub u128);
18
19// Our standard basis has 802 consistent keys:
20// - board: 64 * 2 * 6 = 768
21// - turn: 2, castle: 2 * 8 = 16, en-passant: 16 squares
22//
23// Polyglot basis has 781 "random" keys:
24// - pieces: 12 * 64 = 768
25// - side to move: 1, castling: 4, en-passant files: 8
26// We set zeros and repeated values to achieve compatibility.
27#[derive(Clone, Copy, Debug, Eq, PartialEq)]
28pub struct Basis {
29    pub board: BoardTable<Key>,
30    pub turn: PlayerTable<Key>,
31    pub castle: CastleTable<Key>,
32    pub en_passant: EnPassantTable<Key>,
33}
34
35impl Position {
36    // our 128-bit replacement of the classical Polyglot hash
37    pub const fn key(self) -> Key {
38        self.key_with_basis(Basis::standard())
39    }
40
41    // the classical Polyglot hash, just embedded into u128
42    pub const fn polyglot_key(self) -> Key {
43        self.key_with_basis(Basis::polyglot())
44    }
45
46    pub const fn key_with_basis(self, basis: &Basis) -> Key {
47        // In validated positions, en_passant is normalized to effective rights.
48        self.apparent_key(basis)
49            .xor(castle_key(basis, self.castles()))
50            .xor(en_passant_key(basis, self.en_passant()))
51    }
52
53    // What one typically sees in a depicted position: The board, and the player to move
54    pub const fn apparent_key(self, basis: &Basis) -> Key {
55        self.board().key_with_basis(basis).xor(turn_key(basis, self.turn()))
56    }
57
58    // standard key plus counters
59    pub fn full_key(self) -> Key {
60        self.key()
61            .xor(counter_key("reversible", self.reversible()))
62            .xor(counter_key("round", self.round().get()))
63    }
64}
65
66impl Board {
67    pub const fn polyglot_key(self) -> Key {
68        self.key_with_basis(Basis::polyglot())
69    }
70
71    pub const fn key(self) -> Key {
72        self.key_with_basis(Basis::standard())
73    }
74
75    pub const fn key_with_basis(self, basis: &Basis) -> Key {
76        let mut key = Key(0);
77
78        finite_for!(player in Player {
79            finite_for!(role in Role {
80                let mut squares = self.player(player).intersection(self.role(role));
81                while let Some(square) = squares.pop_first() {
82                    key = key.xor(basis.board.get(square).get(player).get(role));
83                }
84            });
85        });
86
87        key
88    }
89}
90
91impl Game {
92    // Experimental: A globally unique key for all games
93    pub fn key(&self) -> Key {
94        let mut hash = sha2_const::Sha256::new()
95            .update(b"game:")
96            .update(&self.start().position().full_key().u128().to_be_bytes());
97
98        let mut position = self.start();
99        while let Ok(play) = position.main() {
100            hash = hash.update(b":").update(play.play().uci_960().to_string().as_bytes());
101            position = play.position();
102        }
103
104        Key(fold(hash.finalize()))
105    }
106}
107
108impl Line<Position, Move> {
109    pub fn key(&self) -> Key {
110        let mut hash = sha2_const::Sha256::new()
111            .update(b"line:")
112            .update(self.position.key().to_string().as_bytes());
113
114        for play in &self.moves {
115            hash = hash.update(b":").update(play.to_string().as_bytes());
116        }
117
118        Key(fold(hash.finalize()))
119    }
120}
121
122impl Key {
123    pub const fn xor(self, other: Key) -> Key {
124        Key(self.0 ^ other.0)
125    }
126
127    pub const fn u128(self) -> u128 {
128        self.0
129    }
130
131    pub const fn be_bytes(self) -> [u8; 16] {
132        self.0.to_be_bytes()
133    }
134
135    pub fn nonce() -> Self {
136        let nonce = base58::Base58::random_str(12);
137        let bytes = nonce.as_bytes();
138        let mut key = [0; 16];
139        let start = key.len() - bytes.len();
140        key[start..].copy_from_slice(bytes);
141        Key(u128::from_be_bytes(key))
142    }
143}
144
145type U256 = [u8; 32];
146
147pub const fn hash(bytes: &[u8]) -> Key {
148    Key(fold(sha256(bytes)))
149}
150
151const fn sha256(bytes: &[u8]) -> U256 {
152    sha2_const::Sha256::new().update(bytes).finalize()
153}
154
155const fn fold(hash: U256) -> u128 {
156    let (upper, lower) = split(hash);
157    upper ^ lower
158}
159
160const fn split(hash: U256) -> (u128, u128) {
161    let mut upper = [0u8; 16];
162    let mut lower = [0u8; 16];
163
164    let mut i = 0;
165    while i < 16 {
166        upper[i] = hash[i];
167        lower[i] = hash[i + 16];
168        i += 1;
169    }
170
171    (u128::from_be_bytes(upper), u128::from_be_bytes(lower))
172}
173
174type BoardTable<T> = SquareTable<PlayerTable<RoleTable<T>>>;
175type CastleTable<T> = PlayerTable<FileTable<T>>;
176
177impl Basis {
178    pub const fn empty() -> Self {
179        Self {
180            board: BoardTable::EMPTY,
181            turn: PlayerTable::EMPTY,
182            castle: CastleTable::EMPTY,
183            en_passant: EnPassantTable::EMPTY,
184        }
185    }
186
187    pub const fn polyglot() -> &'static Self {
188        #[cfg(rust_chess_compile_time_polyglot_basis)]
189        static BASIS: Basis = polyglot::compute_basis();
190        #[cfg(not(rust_chess_compile_time_polyglot_basis))]
191        static BASIS: Basis = include!("key/POLYGLOT-BASIS.rs");
192
193        &BASIS
194    }
195
196    pub const fn standard() -> &'static Self {
197        #[cfg(rust_chess_compile_time_standard_basis)]
198        #[allow(long_running_const_eval)]
199        static BASIS: Basis = standard::compute_table();
200        #[cfg(not(rust_chess_compile_time_standard_basis))]
201        static BASIS: Basis = include!("key/STANDARD-BASIS.rs");
202
203        &BASIS
204    }
205}
206
207fn counter_key(prefix: &str, counter: u32) -> Key {
208    hash(format!("{prefix}:{counter}").as_bytes())
209}
210
211const fn turn_key(basis: &Basis, turn: Player) -> Key {
212    basis.turn.get(turn)
213}
214
215const fn en_passant_key(basis: &Basis, en_passant: Option<EnPassant>) -> Key {
216    match en_passant {
217        Some(square) => basis.en_passant.get(square),
218        None => Key(0),
219    }
220}
221
222const fn castle_key(basis: &Basis, castles: Castles) -> Key {
223    let mut key = Key(0);
224
225    finite_for!(player in Player {
226        finite_for!(side in Side {
227            if let Some(file) = castles.get(player, side) {
228                key = key.xor(basis.castle.get(player).get(file));
229            }
230        });
231    });
232
233    key
234}
235
236#[cfg(test)]
237mod tests {
238    use super::*;
239    use crate::{Move, board::Role::*, game::Cursor, square::Square::*};
240
241    const COLLISION_FEN: &str = "2b1kqr1/p2p3p/3p4/p2PpP2/PpP2p2/6P1/8/RRB1KQ1N w - - 21 32";
242    const COLLISION_GAME: &str = "
243        1. e4 c5 2. Ba6 bxa6 3. b4 g6 4. f4 Bh6 5. f5 Bf4 6. g3 Nf6
244        7. gxf4 Nh5 8. c4 cxb4 9. Ne2 Ng3 10. Nd4 a5 11. hxg3 Nc6
245        12. Nxc6 Rb8 13. Nxb8 g5 14. d4 f6 15. Na6 gxf4 16. Nc5 Rg8
246        17. Nb7 Rh8 18. Nd6+ exd6 19. e5 fxe5 20. d5 Qf6 21. a4 Rg8
247        22. Nd2 Qf7 23. Rb1 Qf6 24. Ne4 Qf7 25. Rh2 Qf6 26. Nf2 Qf7
248        27. Nh1 Qf6 28. Qd3 Qf7 29. Qf1 Qf6 30. Ra2 Qf7 31. Raa1 Qf8 *";
249    const START: Position = Position::start();
250
251    #[test]
252    fn document_line_keys() {
253        let d4 = Move::normal(Pawn, D2, D4);
254        let e4 = Move::normal(Pawn, E2, E4);
255        let e5 = Move::normal(Pawn, E7, E5);
256        let c5 = Move::normal(Pawn, C7, C5);
257        let nf3 = Move::normal(Knight, G1, F3);
258        let key =
259            |moves: &[Move]| Line { position: START, moves: moves.to_vec() }.key().to_string();
260
261        assert_eq!(key(&[]), "Y4LCEFvKgeZxrQoFJeeQZ8");
262        assert_eq!(key(&[e4]), "95asNCfiG3MeWa1q5jsZ1n");
263        assert_eq!(key(&[e4, c5]), "JQt9mENjV4RUbvog6oWGtb");
264        assert_eq!(key(&[e4, e5, nf3]), "LR2zFDKgxYWDcLHp9nME2i");
265        assert_eq!(key(&[nf3, d4]), "75SZLN4dvpcbErRJaDcnKR");
266    }
267
268    #[test]
269    fn document_game_keys() {
270        use crate::formats::{Parser as _, pgn};
271
272        // start position, no moves
273        let game = Game::chess(START).unwrap();
274        let key = game.key();
275        assert_eq!(key.to_string(), "36MkWJmbeTWaYEDrfrGxNn");
276        assert_eq!(key.u128(), 22523061550585735571242541243028587795);
277
278        // 1. e4 on start position
279        let mut cursor = Cursor::new(game);
280        cursor.option_mut_or_push(Move::normal(Pawn, E2, E4)).unwrap();
281        let e4 = cursor.into_game();
282        assert_eq!(e4.key().to_string(), "46osJVmEGh3XxSk2FKcFbr");
283        assert_eq!(e4.key().u128(), 33370984391190127392068542153345756661);
284
285        // The weird game
286        let pgn = pgn::pgn.parse(COLLISION_GAME).unwrap();
287        let game: Game = pgn.try_into().unwrap();
288        assert_eq!(game.key().to_string(), "DL7b2eDrC8LVtpBQFL9BYT");
289        assert_eq!(game.key().u128(), 132719545793121815798994835819316023416);
290    }
291
292    #[test]
293    fn document_polyglot_start_position_hash() {
294        assert_eq!(START.polyglot_key(), Key(0x463b_9618_1691_fc9c));
295    }
296
297    #[test]
298    fn document_polyglot_start_position_collision() {
299        // Polyglot collision with the standard start position:
300        // https://talkchess.com/viewtopic.php?sid=19ffa9bbce9b0b8c00e176365ba29da6&start=20&t=57255
301        // https://talkchess.com/viewtopic.php?start=40&t=57255
302        let start = Position::start();
303        let position = Position::from_fen(COLLISION_FEN).unwrap();
304
305        assert_eq!(position.polyglot_key(), start.polyglot_key());
306        assert_ne!(position.key(), start.key());
307    }
308
309    #[test]
310    fn reach_polyglot_collision_position_from_linked_movetext() {
311        use crate::formats::{Parser as _, pgn};
312
313        // The first TalkChess thread referenced by
314        // `documents_polyglot_start_position_collision` gives this game
315        // reaching the collision position.
316        let pgn = pgn::pgn.parse(COLLISION_GAME).unwrap();
317        let game: Game = pgn.try_into().unwrap();
318        let mut cursor = Cursor::new(game);
319        cursor.mainline_end();
320        let constructed = cursor.position();
321
322        let expected = Position::from_fen(COLLISION_FEN).unwrap();
323
324        assert_eq!(constructed.fen(), expected.fen());
325        assert_eq!(constructed.transposition_fen(), expected.transposition_fen());
326        assert_eq!(constructed.key(), expected.key());
327        assert_eq!(constructed.polyglot_key(), expected.polyglot_key());
328    }
329
330    #[test]
331    fn document_polyglot_zero_hash_position() {
332        // Polyglot zero-hash position:
333        // https://talkchess.com/forum/viewtopic.php?p=482951
334        // https://talkchess.com/viewtopic.php?sid=19ffa9bbce9b0b8c00e176365ba29da6&start=20&t=57255
335        let position =
336            Position::from_fen("2b1k3/4p3/3p1p2/p2P2p1/P2P4/2P2PP1/4P3/2NQKB2 b - - 0 1").unwrap();
337
338        assert_eq!(position.polyglot_key(), Key(0));
339        assert_ne!(position.key_with_basis(Basis::standard()), Key(0));
340    }
341}
chess/key.rs

chess/
key.rs
