1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

#![no_std]

#[rustfmt::skip]
mod consts;

mod test;

/// An 8x8 Othello game state.
///
/// This crate currently does not implement unchecked versions of methods, but you can use
/// `.unwrap_or_else(|| unsafe { unreachable_unchecked() })` with link time optimization.
#[derive(Clone)]
pub struct Game(u64, u64);
impl Default for Game {
    fn default() -> Self {
        Self(0x0000_0008_1000_0000, 0x0000_0010_0800_0000)
    }
}
impl core::fmt::Debug for Game {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        for i in (0..64).rev() {
            f.write_str(match (self.0 >> i & 1, self.1 >> i & 1) {
                (0, 0) => " ",
                (1, 0) => "O",
                (0, 1) => "X",
                (_, _) => unreachable!(),
            })?;
            if i % 8 == 0 {
                f.write_str("\n")?;
            }
        }
        Ok(())
    }
}

impl Game {
    /// Creates new `Game` from two bitboards.
    ///
    /// `p` : player to play
    ///
    /// `n` : player just played
    #[must_use]
    pub fn new(p: u64, n: u64) -> Option<Self> {
        if p & n == 0 {
            Some(Self(p, n))
        } else {
            None
        }
    }
    /// Returns bitboards of `self`.
    #[must_use]
    pub const fn get(&self) -> [u64; 2] {
        [self.0, self.1]
    }
    /// Passes without playing.
    pub fn pass_move(&mut self) {
        core::mem::swap(&mut self.0, &mut self.1);
    }
    /// Returns the `Game` state after playing the given move.
    /// Panics when `place` is larger than 63.
    #[must_use]
    pub fn make_move(&self, place: usize) -> Option<Self> {
        let diff = (0..4)
            .map(|i| unsafe {
                use bitintr::*;
                use consts::*;
                //maybe we should change INDEX to LUT of raw pointers
                //and save some instructions
                //not sure if that saves some CPU cycles
                //wait before bench
                u64::from(*consts::RESULT.get_unchecked(
                    //https://github.com/rust-lang/rust/issues/51713
                    INDEX[place][i] as usize * 32
                        + self.0.pext(MASK[place][i][0]) as usize * 64
                        + self.1.pext(MASK[place][i][1]) as usize,
                ))
                .pdep(MASK[place][i][1])
            })
            .fold(0, core::ops::BitOr::bitor);
        //for arm processors, we should use brev and hyperbola quintessence, as arm has rbit instruction
        //https://www.chessprogramming.org/Hyperbola_Quintessence
        //or maybe magic bitboards
        //even RISC-V has bdep bext
        if diff == 0 || ((self.0 | self.1) & 1 << place != 0) {
            None
        } else {
            Some(Self(self.1 ^ diff, self.0 ^ diff ^ 1 << place))
        }
    }
    /// Returns the bitboard representation of available moves.
    #[must_use]
    pub fn available_moves(&self) -> u64 {
        //the below should compile to AVX2 instructions(256bit)
        [-9, -8, -7, -1, 1, 7, 8, 9]
            //we use iter_mut because of the noalias bug
            .iter_mut()
            .map(|i| self.gen(*i))
            .fold(0, core::ops::BitOr::bitor)
            & !self.0
            & !self.1
    }
    #[must_use]
    fn gen(&self, dir: isize) -> u64 {
        //rotate might be faster on AVX-512
        fn shift(x: u64, y: isize) -> u64 {
            if y > 0 {
                x >> y
            } else {
                x << -y
            }
        }
        let x = self.0;
        //if we change above to rotate, we should also modify the following
        let y = self.1
            & match dir.rem_euclid(8) {
                0 => !0,
                1 | 7 => 0x7E7E_7E7E_7E7E_7E7E,
                _ => unreachable!(),
            };
        let d = dir;
        let x = x | y & shift(x, d);
        let y = y & shift(y, d);
        let d = d * 2;
        let x = x | y & shift(x, d);
        let y = y & shift(y, d);
        let d = d * 2;
        let x = x | y & shift(x, d);
        shift(x ^ self.0, dir)
    }
}