ai_othello/
position.rs

1use crate::{Move, MoveList, Square};
2use std::fmt;
3
4const FILE_A: u64 = 0x0101_0101_0101_0101;
5const FILE_H: u64 = 0x8080_8080_8080_8080;
6
7#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
8pub enum Side {
9    Black,
10    White,
11}
12
13impl Side {
14    pub const fn other(self) -> Self {
15        match self {
16            Self::Black => Self::White,
17            Self::White => Self::Black,
18        }
19    }
20
21    pub const fn as_char(self) -> char {
22        match self {
23            Self::Black => 'B',
24            Self::White => 'W',
25        }
26    }
27}
28
29impl fmt::Display for Side {
30    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
31        write!(f, "{}", self.as_char())
32    }
33}
34
35#[derive(Debug, Clone, Copy, PartialEq, Eq)]
36pub enum GameResult {
37    Ongoing,
38    Draw { black: u8, white: u8 },
39    Win { winner: Side, black: u8, white: u8 },
40}
41
42#[derive(Debug, Clone, Copy, PartialEq, Eq)]
43pub enum MoveError {
44    GameOver,
45    IllegalSquare(Square),
46    PassNotAllowed,
47    MustPass,
48}
49
50impl fmt::Display for MoveError {
51    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
52        match self {
53            Self::GameOver => write!(f, "the game is already over"),
54            Self::IllegalSquare(square) => {
55                write!(f, "placing at {square} captures no opponent discs")
56            }
57            Self::PassNotAllowed => write!(f, "pass is only legal when no placement is legal"),
58            Self::MustPass => write!(f, "the side to move has no placement and must pass"),
59        }
60    }
61}
62
63impl std::error::Error for MoveError {}
64
65#[derive(Debug, Clone, Copy, PartialEq, Eq)]
66pub struct Undo {
67    mv: Move,
68    side: Side,
69    flipped: u64,
70}
71
72impl Undo {
73    pub const fn mv(self) -> Move {
74        self.mv
75    }
76
77    pub const fn side(self) -> Side {
78        self.side
79    }
80
81    pub const fn flipped(self) -> u64 {
82        self.flipped
83    }
84}
85
86#[derive(Debug, Clone, Copy, PartialEq, Eq)]
87enum Direction {
88    North,
89    South,
90    East,
91    West,
92    NorthEast,
93    NorthWest,
94    SouthEast,
95    SouthWest,
96}
97
98const DIRECTIONS: [Direction; 8] = [
99    Direction::North,
100    Direction::South,
101    Direction::East,
102    Direction::West,
103    Direction::NorthEast,
104    Direction::NorthWest,
105    Direction::SouthEast,
106    Direction::SouthWest,
107];
108
109/// Two disjoint bitboards and the side whose transition comes next.
110#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
111pub struct Position {
112    black: u64,
113    white: u64,
114    side_to_move: Side,
115}
116
117impl Default for Position {
118    fn default() -> Self {
119        Self::start()
120    }
121}
122
123impl Position {
124    pub const fn start() -> Self {
125        Self {
126            black: (1u64 << 28) | (1u64 << 35),
127            white: (1u64 << 27) | (1u64 << 36),
128            side_to_move: Side::Black,
129        }
130    }
131
132    pub fn from_bits(black: u64, white: u64, side_to_move: Side) -> Result<Self, &'static str> {
133        if black & white != 0 {
134            return Err("black and white bitboards overlap");
135        }
136        Ok(Self {
137            black,
138            white,
139            side_to_move,
140        })
141    }
142
143    /// Parse the 64-cell board plus side token used by Cassio's engine
144    /// protocol. `X`, `B`, or `*` denotes black; `O` or `W` denotes white.
145    pub fn from_cassio(board: &str, side: &str) -> Result<Self, &'static str> {
146        if !board.is_ascii() || board.len() != 64 {
147            return Err("Cassio board must contain exactly 64 ASCII cells");
148        }
149        let mut black = 0u64;
150        let mut white = 0u64;
151        for (index, cell) in board.bytes().enumerate() {
152            let bit = 1u64 << index;
153            match cell.to_ascii_lowercase() {
154                b'x' | b'b' | b'*' => black |= bit,
155                b'o' | b'w' => white |= bit,
156                b'-' | b'.' => {}
157                _ => return Err("Cassio board cells must be X, O, -, or ."),
158            }
159        }
160        let side_to_move = match side.as_bytes() {
161            [b'X' | b'x' | b'B' | b'b' | b'*'] => Side::Black,
162            [b'O' | b'o' | b'W' | b'w'] => Side::White,
163            _ => return Err("Cassio side must be X, O, B, or W"),
164        };
165        Self::from_bits(black, white, side_to_move)
166    }
167
168    /// Serialize a Cassio position as 64 cells followed immediately by `X`
169    /// or `O` for the side to move.
170    pub fn to_cassio(self) -> String {
171        let mut value = String::with_capacity(65);
172        for index in 0..64u8 {
173            value.push(match self.side_at(Square::new(index)) {
174                Some(Side::Black) => 'X',
175                Some(Side::White) => 'O',
176                None => '-',
177            });
178        }
179        value.push(match self.side_to_move {
180            Side::Black => 'X',
181            Side::White => 'O',
182        });
183        value
184    }
185
186    pub const fn bits(self, side: Side) -> u64 {
187        match side {
188            Side::Black => self.black,
189            Side::White => self.white,
190        }
191    }
192
193    pub const fn occupied(self) -> u64 {
194        self.black | self.white
195    }
196
197    pub const fn side_to_move(self) -> Side {
198        self.side_to_move
199    }
200
201    pub const fn empty_count(self) -> u8 {
202        (!self.occupied()).count_ones() as u8
203    }
204
205    pub const fn occupied_count(self) -> u8 {
206        self.occupied().count_ones() as u8
207    }
208
209    pub const fn disc_count(self, side: Side) -> u8 {
210        self.bits(side).count_ones() as u8
211    }
212
213    pub fn side_at(self, square: Square) -> Option<Side> {
214        let bit = 1u64 << square.index();
215        if self.black & bit != 0 {
216            Some(Side::Black)
217        } else if self.white & bit != 0 {
218            Some(Side::White)
219        } else {
220            None
221        }
222    }
223
224    pub fn legal_placement_bits(self) -> u64 {
225        legal_bits(
226            self.bits(self.side_to_move),
227            self.bits(self.side_to_move.other()),
228        )
229    }
230
231    pub fn legal_placements_for(self, side: Side) -> u64 {
232        legal_bits(self.bits(side), self.bits(side.other()))
233    }
234
235    pub fn frontier_bits(self, side: Side) -> u64 {
236        self.bits(side) & adjacent(!self.occupied())
237    }
238
239    pub fn potential_mobility_bits(self, side: Side) -> u64 {
240        !self.occupied() & adjacent(self.bits(side.other()))
241    }
242
243    /// Returns every legal placement, or a single pass when one is required.
244    pub fn legal_moves(self) -> MoveList {
245        let mut moves = MoveList::default();
246        let mut bits = self.legal_placement_bits();
247        while bits != 0 {
248            let index = bits.trailing_zeros() as u8;
249            moves.push(Move::Place(Square::new(index)));
250            bits &= bits - 1;
251        }
252        if moves.is_empty() && self.legal_placements_for(self.side_to_move.other()) != 0 {
253            moves.push(Move::Pass);
254        }
255        moves
256    }
257
258    pub fn flips_for(self, square: Square) -> u64 {
259        let move_bit = 1u64 << square.index();
260        if self.occupied() & move_bit != 0 {
261            return 0;
262        }
263        let own = self.bits(self.side_to_move);
264        let opponent = self.bits(self.side_to_move.other());
265        let mut flips = 0;
266        for direction in DIRECTIONS {
267            let mut captured = 0;
268            let mut ray = shift(move_bit, direction) & opponent;
269            while ray != 0 {
270                captured |= ray;
271                let next = shift(ray, direction);
272                if next & own != 0 {
273                    flips |= captured;
274                    break;
275                }
276                ray = next & opponent;
277            }
278        }
279        flips
280    }
281
282    pub fn result(self) -> GameResult {
283        if self.legal_placement_bits() != 0
284            || self.legal_placements_for(self.side_to_move.other()) != 0
285        {
286            return GameResult::Ongoing;
287        }
288        let black = self.disc_count(Side::Black);
289        let white = self.disc_count(Side::White);
290        match black.cmp(&white) {
291            std::cmp::Ordering::Greater => GameResult::Win {
292                winner: Side::Black,
293                black,
294                white,
295            },
296            std::cmp::Ordering::Less => GameResult::Win {
297                winner: Side::White,
298                black,
299                white,
300            },
301            std::cmp::Ordering::Equal => GameResult::Draw { black, white },
302        }
303    }
304
305    /// Plays one placement or forced pass and returns exact undo data.
306    pub fn make_move(&mut self, mv: Move) -> Result<Undo, MoveError> {
307        if self.result() != GameResult::Ongoing {
308            return Err(MoveError::GameOver);
309        }
310        let side = self.side_to_move;
311        let flips = match mv {
312            Move::Pass => {
313                if self.legal_placement_bits() != 0 {
314                    return Err(MoveError::PassNotAllowed);
315                }
316                if self.legal_placements_for(side.other()) == 0 {
317                    return Err(MoveError::GameOver);
318                }
319                0
320            }
321            Move::Place(square) => {
322                if self.legal_placement_bits() == 0 {
323                    return Err(MoveError::MustPass);
324                }
325                let flips = self.flips_for(square);
326                if flips == 0 {
327                    return Err(MoveError::IllegalSquare(square));
328                }
329                let placed = 1u64 << square.index();
330                match side {
331                    Side::Black => {
332                        self.black |= placed | flips;
333                        self.white &= !flips;
334                    }
335                    Side::White => {
336                        self.white |= placed | flips;
337                        self.black &= !flips;
338                    }
339                }
340                flips
341            }
342        };
343        self.side_to_move = side.other();
344        debug_assert!(self.is_consistent());
345        Ok(Undo {
346            mv,
347            side,
348            flipped: flips,
349        })
350    }
351
352    /// Restores the position that existed before `undo` was produced.
353    pub fn unmake_move(&mut self, undo: Undo) {
354        debug_assert_eq!(self.side_to_move, undo.side.other());
355        self.side_to_move = undo.side;
356        if let Move::Place(square) = undo.mv {
357            let placed = 1u64 << square.index();
358            match undo.side {
359                Side::Black => {
360                    self.black &= !(placed | undo.flipped);
361                    self.white |= undo.flipped;
362                }
363                Side::White => {
364                    self.white &= !(placed | undo.flipped);
365                    self.black |= undo.flipped;
366                }
367            }
368        }
369        debug_assert!(self.is_consistent());
370    }
371
372    pub fn from_moves(moves: &[Move]) -> Result<Self, MoveError> {
373        let mut position = Self::start();
374        for &mv in moves {
375            position.make_move(mv)?;
376        }
377        Ok(position)
378    }
379
380    pub fn mirrored(self) -> Self {
381        let mut black = 0;
382        let mut white = 0;
383        for square in Square::all() {
384            let target = square.mirrored();
385            let target_bit = 1u64 << target.index();
386            match self.side_at(square) {
387                Some(Side::Black) => black |= target_bit,
388                Some(Side::White) => white |= target_bit,
389                None => {}
390            }
391        }
392        Self {
393            black,
394            white,
395            side_to_move: self.side_to_move,
396        }
397    }
398
399    fn is_consistent(self) -> bool {
400        self.black & self.white == 0
401    }
402}
403
404fn legal_bits(own: u64, opponent: u64) -> u64 {
405    let empty = !(own | opponent);
406    let mut legal = 0;
407    for direction in DIRECTIONS {
408        let mut run = shift(own, direction) & opponent;
409        // At most six opponent discs can lie between the anchor and target.
410        for _ in 0..5 {
411            run |= shift(run, direction) & opponent;
412        }
413        legal |= shift(run, direction) & empty;
414    }
415    legal
416}
417
418fn adjacent(bits: u64) -> u64 {
419    DIRECTIONS
420        .into_iter()
421        .fold(0, |neighbors, direction| neighbors | shift(bits, direction))
422}
423
424const fn shift(bits: u64, direction: Direction) -> u64 {
425    match direction {
426        Direction::North => bits << 8,
427        Direction::South => bits >> 8,
428        Direction::East => (bits & !FILE_H) << 1,
429        Direction::West => (bits & !FILE_A) >> 1,
430        Direction::NorthEast => (bits & !FILE_H) << 9,
431        Direction::NorthWest => (bits & !FILE_A) << 7,
432        Direction::SouthEast => (bits & !FILE_H) >> 7,
433        Direction::SouthWest => (bits & !FILE_A) >> 9,
434    }
435}
ai_othello/position.rs

ai_othello/
position.rs
