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

#![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]
    }
    /// Returns the `Game` state after playing the given move.
    /// If `place` is larger than 64
    #[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) {
                7 => consts::RIGHTY,
                0 => !0,
                1 => consts::LEFTY,
                _ => 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)
    }
}