path: root/Sources/SwiftChessNeo/Bitboard.swift

//
//  Bitboard.swift
//  Sage
//
//  Copyright 2016-2017 Nikolai Vazquez
//  Modified by SuperGeroy
//
//  Licensed under the Apache License, Version 2.0 (the "License");
//  you may not use this file except in compliance with the License.
//  You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
//  Unless required by applicable law or agreed to in writing, software
//  distributed under the License is distributed on an "AS IS" BASIS,
//  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//  See the License for the specific language governing permissions and
//  limitations under the License.
//

/// A lookup table of least significant bit indices.
private let _lsbTable: [Int] = [00, 01, 48, 02, 57, 49, 28, 03,
                                61, 58, 50, 42, 38, 29, 17, 04,
                                62, 55, 59, 36, 53, 51, 43, 22,
                                45, 39, 33, 30, 24, 18, 12, 05,
                                63, 47, 56, 27, 60, 41, 37, 16,
                                54, 35, 52, 21, 44, 32, 23, 11,
                                46, 26, 40, 15, 34, 20, 31, 10,
                                25, 14, 19, 09, 13, 08, 07, 06]

/// A lookup table of most significant bit indices.
private let _msbTable: [Int] = [00, 47, 01, 56, 48, 27, 02, 60,
                                57, 49, 41, 37, 28, 16, 03, 61,
                                54, 58, 35, 52, 50, 42, 21, 44,
                                38, 32, 29, 23, 17, 11, 04, 62,
                                46, 55, 26, 59, 40, 36, 15, 53,
                                34, 51, 20, 43, 31, 22, 10, 45,
                                25, 39, 14, 33, 19, 30, 09, 24,
                                13, 18, 08, 12, 07, 06, 05, 63]

/// A lookup table of bitboards for all squares.
private let _bitboardTable: [Bitboard] = (0 ..< 64).map { Bitboard(rawValue: 1 << $0) }

/// The De Bruijn multiplier.
private let _debruijn64: UInt64 = 0x03f79d71b4cb0a89

/// Returns the index of the lsb value.
private func _index(lsb value: Bitboard) -> Int? {
    guard value != 0 else {
        return nil
    }
    return _lsbTable[Int((value.rawValue &* _debruijn64) >> 58)]
}

/// Mask for bits not in File A.
private let _notFileA: Bitboard = 0xfefefefefefefefe

/// Mask for bits not in Files A and B.
private let _notFileAB: Bitboard = 0xfcfcfcfcfcfcfcfc

/// Mask for bits not in File H.
private let _notFileH: Bitboard = 0x7f7f7f7f7f7f7f7f

/// Mask for bits not in Files G and H.
private let _notFileGH: Bitboard = 0x3f3f3f3f3f3f3f3f

/// A bitmap of sixty-four bits suitable for storing squares for various pieces.
///
/// The first bit refers to `Square.A1` the last (64th) bit refers to `Square.H8`.
///
/// Due to their compact nature, bitboards can store information such as positions in memory very efficiently. Bitboards
/// can also be used to answer questions about the state of a `Board` quickly with very few operations.
///
/// Bitboards are used internally within `Board` to store positions for all twelve cases of `Piece`.
///
/// - see also: [Bitboard (Wikipedia)](https://en.wikipedia.org/wiki/Bitboard ),
///            [Bitboards (Chess Programming Wiki)](https://chessprogramming.org/Bitboards)
public struct Bitboard: RawRepresentable, Hashable, CustomStringConvertible {

    /// A bitboard shift direction.
    public enum ShiftDirection {

        /// North direction.
        case north

        /// South direction.
        case south

        /// East direction.
        case east

        /// West direction.
        case west

        /// Northeast direction.
        case northeast

        /// Southeast direction.
        case southeast

        /// Northwest direction.
        case northwest

        /// Southwest direction.
        case southwest

        /// North regardless of Swift version.
        internal static let _north = ShiftDirection.north

        /// South regardless of Swift version.
        internal static let _south = ShiftDirection.south

        /// East regardless of Swift version.
        internal static let _east = ShiftDirection.east

        /// West regardless of Swift version.
        internal static let _west = ShiftDirection.west

        /// Northeast regardless of Swift version.
        internal static let _northeast = ShiftDirection.northeast

        /// Southeast regardless of Swift version.
        internal static let _southeast = ShiftDirection.southeast

        /// Northwest regardless of Swift version.
        internal static let _northwest = ShiftDirection.northwest

        /// Southwest regardless of Swift version.
        internal static let _southwest = ShiftDirection.southwest

    }

    /// An iterator for the squares of a `Bitboard`.
    public struct Iterator: IteratorProtocol {

        fileprivate var _bitboard: Bitboard

        /// Advances and returns the next element of the underlying sequence, or
        /// `nil` if no next element exists.
        public mutating func next() -> Square? {
            return _bitboard.popLSBSquare()
        }

    }

    /// The empty bitset.
    public static var allZeros: Bitboard {
        return Bitboard(rawValue: 0)
    }

    /// The edges of a board.
    public static let edges: Bitboard = 0xff818181818181ff

    /// The corresponding value of the "raw" type.
    ///
    /// `Self(rawValue: self.rawValue)!` is equivalent to `self`.
    public var rawValue: UInt64

    /// A textual representation of `self`.
    public var description: String {
        let num = String(rawValue, radix: 16)
        let str = repeatElement("0", count: 16 - num.count).joined(separator: "")
        return "Bitboard(0x\(str + num))"
    }

    /// The hash value.
    public var hashValue: Int {
        return rawValue.hashValue
    }

    /// An ASCII art representation of `self`.
    ///
    /// The ASCII representation for the starting board's bitboard:
    ///
    /// ```
    ///   +-----------------+
    /// 8 | 1 1 1 1 1 1 1 1 |
    /// 7 | 1 1 1 1 1 1 1 1 |
    /// 6 | . . . . . . . . |
    /// 5 | . . . . . . . . |
    /// 4 | . . . . . . . . |
    /// 3 | . . . . . . . . |
    /// 2 | 1 1 1 1 1 1 1 1 |
    /// 1 | 1 1 1 1 1 1 1 1 |
    ///   +-----------------+
    ///     a b c d e f g h
    /// ```
    public var ascii: String {
        let edge = "  +-----------------+\n"
        var result = edge
        let ranks = Rank.all.reversed()
        for rank in ranks {
            let strings = File.all.map({ file in self[(file, rank)] ? "1" : "." })
            let str = strings.joined(separator: " ")
            result += "\(rank) | \(str) |\n"
        }
        result += "\(edge)    a b c d e f g h  "
        return result
    }

    /// The number of bits set in `self`.
    public var count: Int {
        var n = rawValue
        n = n - ((n >> 1) & 0x5555555555555555)
        n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333)
        return Int((((n + (n >> 4)) & 0xF0F0F0F0F0F0F0F) &* 0x101010101010101) >> 56)
    }

    /// `true` if `self` is empty.
    public var isEmpty: Bool {
        return self == 0
    }

    /// `self` has more than one bit set.
    public var hasMoreThanOne: Bool {
        return rawValue & (rawValue &- 1) != 0
    }

    /// The least significant bit.
    public var lsb: Bitboard {
        return Bitboard(rawValue: rawValue & (0 &- rawValue))
    }

    /// The index for the least significant bit of `self`.
    public var lsbIndex: Int? {
        return _index(lsb: lsb)
    }

    /// The square for the least significant bit of `self`.
    public var lsbSquare: Square? {
        return lsbIndex.flatMap({ Square(rawValue: $0) })
    }

    private var _msbShifted: UInt64 {
        var x = rawValue
        x |= x >> 1
        x |= x >> 2
        x |= x >> 4
        x |= x >> 8
        x |= x >> 16
        x |= x >> 32
        return x
    }

    /// The most significant bit.
    public var msb: Bitboard {
        return Bitboard(rawValue: (_msbShifted >> 1) + 1)
    }

    /// The index for the most significant bit of `self`.
    public var msbIndex: Int? {
        guard rawValue != 0 else {
            return nil
        }
        return _msbTable[Int((_msbShifted &* _debruijn64) >> 58)]
    }

    /// The square for the most significant bit of `self`.
    public var msbSquare: Square? {
        return msbIndex.flatMap({ Square(rawValue: $0) })
    }

    /// Convert from a raw value of `UInt64`.
    public init(rawValue: UInt64) {
        self.rawValue = rawValue
    }

    /// Create an empty bitboard.
    public init() {
        rawValue = 0
    }

    /// Create a starting bitboard for `piece`.
    public init(startFor piece: Piece) {
        let value: Bitboard
        switch piece.kind {
            case .pawn:   value = 0xFF00
            case .knight: value = 0x0042
            case .bishop: value = 0x0024
            case .rook:   value = 0x0081
            case .queen:  value = 0x0008
            case .king:   value = 0x0010
        }
        self = piece.color.isWhite ? value : value << (piece.kind.isPawn ? 40 : 56)
    }

    /// Create a bitboard from `squares`.
    public init<S: Sequence>(squares: S) where S.Iterator.Element == Square {
        rawValue = squares.reduce(0) { $0 | (1 << UInt64($1.rawValue)) }
    }

    /// Create a bitboard from `locations`.
    public init<S: Sequence>(locations: S) where S.Iterator.Element == Location {
        self.init(squares: locations.map(Square.init(location:)))
    }

    /// Create a bitboard from the start and end of `move`.
    public init(move: Move) {
        self.init(squares: [move.start, move.end])
    }

    /// Create a bitboard mask for `file`.
    public init(file: File) {
        switch file {
            case .a: rawValue = 0x0101010101010101
            case .b: rawValue = 0x0202020202020202
            case .c: rawValue = 0x0404040404040404
            case .d: rawValue = 0x0808080808080808
            case .e: rawValue = 0x1010101010101010
            case .f: rawValue = 0x2020202020202020
            case .g: rawValue = 0x4040404040404040
            case .h: rawValue = 0x8080808080808080
        }
    }

    /// Create a bitboard mask for `rank`.
    public init(rank: Rank) {
        rawValue = 0xFF << (UInt64(rank.index) * 8)
    }

    /// Create a bitboard mask for `square`.
    ///
    /// - complexity: O(1).
    public init(square: Square) {
        self = _bitboardTable[square.rawValue]
    }

    /// The `Bool` value for the bit at `square`.
    ///
    /// - complexity: O(1).
    public subscript(square: Square) -> Bool {
        get {
            return intersects(_bitboardTable[square.rawValue])
        }
        set {
            let bit = Bitboard(square: square)
            if newValue {
                rawValue |= bit.rawValue
            } else {
                rawValue &= ~bit.rawValue
            }
        }
    }

    /// The `Bool` value for the bit at `location`.
    ///
    /// - complexity: O(1).
    public subscript(location: Location) -> Bool {
        get {
            return self[Square(location: location)]
        }
        set {
            self[Square(location: location)] = newValue
        }
    }

    /// Returns the pawn pushes available for `color` in `self`.
    internal func _pawnPushes(for color: Color, empty: Bitboard) -> Bitboard {
        return (color.isWhite ? shifted(toward: ._north) : shifted(toward: ._south)) & empty
    }

    /// Returns the attacks available to the pawns for `color` in `self`.
    internal func _pawnAttacks(for color: Color) -> Bitboard {
        if color.isWhite {
            return shifted(toward: ._northeast) | shifted(toward: ._northwest)
        } else {
            return shifted(toward: ._southeast) | shifted(toward: ._southwest)
        }
    }

    /// Returns the attacks available to the knight in `self`.
    internal func _knightAttacks() -> Bitboard {
        let x = self
        let a = ((x << 17) | (x >> 15)) & _notFileA
        let b = ((x << 10) | (x >> 06)) & _notFileAB
        let c = ((x << 15) | (x >> 17)) & _notFileH
        let d = ((x << 06) | (x >> 10)) & _notFileGH
        return a | b | c | d
    }

    /// Returns the attacks available to the bishop in `self`.
    internal func _bishopAttacks(stoppers bitboard: Bitboard = 0) -> Bitboard {
        return filled(toward: ._northeast, stoppers: bitboard).shifted(toward: ._northeast)
            |  filled(toward: ._northwest, stoppers: bitboard).shifted(toward: ._northwest)
            |  filled(toward: ._southeast, stoppers: bitboard).shifted(toward: ._southeast)
            |  filled(toward: ._southwest, stoppers: bitboard).shifted(toward: ._southwest)
    }

    /// Returns the attacks available to the rook in `self`.
    internal func _rookAttacks(stoppers bitboard: Bitboard = 0) -> Bitboard {
        return filled(toward: ._north, stoppers: bitboard).shifted(toward: ._north)
            |  filled(toward: ._south, stoppers: bitboard).shifted(toward: ._south)
            |  filled(toward: ._east,  stoppers: bitboard).shifted(toward: ._east)
            |  filled(toward: ._west,  stoppers: bitboard).shifted(toward: ._west)
    }

    /// Returns the x-ray attacks available to the bishop in `self`.
    internal func _xrayBishopAttacks(occupied occ: Bitboard, stoppers: Bitboard) -> Bitboard {
        let attacks = _bishopAttacks(stoppers: occ)
        return attacks ^ _bishopAttacks(stoppers: (stoppers & attacks) ^ stoppers)
    }

    /// Returns the x-ray attacks available to the rook in `self`.
    internal func _xrayRookAttacks(occupied occ: Bitboard, stoppers: Bitboard) -> Bitboard {
        let attacks = _rookAttacks(stoppers: occ)
        return attacks ^ _rookAttacks(stoppers: (stoppers & attacks) ^ stoppers)
    }

    /// Returns the attacks available to the queen in `self`.
    internal func _queenAttacks(stoppers bitboard: Bitboard = 0) -> Bitboard {
        return _rookAttacks(stoppers: bitboard) | _bishopAttacks(stoppers: bitboard)
    }

    /// Returns the attacks available to the king in `self`.
    internal func _kingAttacks() -> Bitboard {
        let attacks = shifted(toward: ._east) | shifted(toward: ._west)
        let bitboard = self | attacks
        return attacks
            | bitboard.shifted(toward: ._north)
            | bitboard.shifted(toward: ._south)
    }

    /// Returns the attacks available to `piece` in `self`.
    internal func _attacks(for piece: Piece, stoppers: Bitboard = 0) -> Bitboard {
        switch piece.kind {
            case .pawn:
                return _pawnAttacks(for: piece.color)
            case .knight:
                return _knightAttacks()
            case .bishop:
                return _bishopAttacks(stoppers: stoppers)
            case .rook:
                return _rookAttacks(stoppers: stoppers)
            case .queen:
                return _queenAttacks(stoppers: stoppers)
            case .king:
                return _kingAttacks()
        }
    }

    /// Returns `true` if `self` intersects `other`.
    public func intersects(_ other: Bitboard) -> Bool {
        return rawValue & other.rawValue != 0
    }

    /// Returns `self` flipped horizontally.
    public func flippedHorizontally() -> Bitboard {
        let x = 0x5555555555555555 as Bitboard
        let y = 0x3333333333333333 as Bitboard
        let z = 0x0F0F0F0F0F0F0F0F as Bitboard
        var n = self
        n = ((n >> 1) & x) | ((n & x) << 1)
        n = ((n >> 2) & y) | ((n & y) << 2)
        n = ((n >> 4) & z) | ((n & z) << 4)
        return n
    }

    /// Returns `self` flipped vertically.
    public func flippedVertically() -> Bitboard {
        let x = 0x00FF00FF00FF00FF as Bitboard
        let y = 0x0000FFFF0000FFFF as Bitboard
        var n = self
        n = ((n >>  8) & x) | ((n & x) <<  8)
        n = ((n >> 16) & y) | ((n & y) << 16)
        n =  (n >> 32)      |       (n << 32)
        return n
    }

    /// Returns the bits of `self` filled toward `direction` stopped by `stoppers`.
    public func filled(toward direction: ShiftDirection, stoppers: Bitboard) -> Bitboard {
        let empty = ~stoppers
        var bitboard = self
        for _ in 0 ..< 7 {
            bitboard |= empty & bitboard.shifted(toward: direction)
        }
        return bitboard
    }

    /// Returns the bits of `self` shifted once toward `direction`.
    public func shifted(toward direction: ShiftDirection) -> Bitboard {
        switch direction {
            case .north:     return  self << 8
            case .south:     return  self >> 8
            case .east:      return (self << 1) & _notFileA
            case .northeast: return (self << 9) & _notFileA
            case .southeast: return (self >> 7) & _notFileA
            case .west:      return (self >> 1) & _notFileH
            case .southwest: return (self >> 9) & _notFileH
            case .northwest: return (self << 7) & _notFileH
        }
    }

    /// Flips `self` horizontally.
    public mutating func flipHorizontally() {
        self = flippedHorizontally()
    }

    /// Flips `self` vertically.
    public mutating func flipVertically() {
        self = flippedVertically()
    }

    /// Shifts the bits of `self` once toward `direction`.
    public mutating func shift(toward direction: ShiftDirection) {
        self = shifted(toward: direction)
    }

    /// Fills the bits of `self` toward `direction` stopped by `stoppers`.
    public mutating func fill(toward direction: ShiftDirection, stoppers: Bitboard = 0) {
        self = filled(toward: direction, stoppers: stoppers)
    }

    /// Swaps the bits between the two squares.
    public mutating func swap(_ first: Square, _ second: Square) {
        (self[first], self[second]) = (self[second], self[first])
    }

    /// Removes the least significant bit and returns it.
    public mutating func popLSB() -> Bitboard {
        let lsb = self.lsb
        rawValue -= lsb.rawValue
        return lsb
    }

    /// Removes the least significant bit and returns its index, if any.
    public mutating func popLSBIndex() -> Int? {
        return _index(lsb: popLSB())
    }

    /// Removes the least significant bit and returns its square, if any.
    public mutating func popLSBSquare() -> Square? {
        return popLSBIndex().flatMap({ Square(rawValue: $0) })
    }

    /// Removes the most significant bit and returns it.
    public mutating func popMSB() -> Bitboard {
        let msb = self.msb
        rawValue -= msb.rawValue
        return msb
    }

    /// Removes the most significant bit and returns its index, if any.
    public mutating func popMSBIndex() -> Int? {
        guard rawValue != 0 else { return nil }
        let shifted = _msbShifted
        rawValue -= (shifted >> 1) + 1
        return _msbTable[Int((shifted &* _debruijn64) >> 58)]
    }

    /// Removes the most significant bit and returns its square, if any.
    public mutating func popMSBSquare() -> Square? {
        return popMSBIndex().flatMap({ Square(rawValue: $0) })
    }

    /// Returns the ranks of `self` as eight 8-bit integers.
    public func ranks() -> [UInt8] {
        return (0 ..< 8).map { UInt8((rawValue >> ($0 * 8)) & 255) }
    }

}

extension Bitboard: Sequence {

    /// A value less than or equal to the number of elements in
    /// the sequence, calculated nondestructively.
    ///
    /// - complexity: O(1).
    public var underestimatedCount: Int {
        return count
    }

    /// Returns a Boolean value indicating whether the sequence contains the
    /// given element.
    ///
    /// - complexity: O(1).
    public func contains(_ element: Square) -> Bool {
        return self[element]
    }

    /// Returns an iterator over the squares of the board.
    public func makeIterator() -> Iterator {
        return Iterator(_bitboard: self)
    }

}

extension Bitboard: ExpressibleByIntegerLiteral {
    
    /// Create an instance initialized to `value`.
    public init(integerLiteral value: UInt64) {
        rawValue = value
    }
}

/// Returns the intersection of bits set in `lhs` and `rhs`.
///
/// - complexity: O(1).
public func & (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
    return Bitboard(rawValue: lhs.rawValue & rhs.rawValue)
}

/// Returns the union of bits set in `lhs` and `rhs`.
///
/// - complexity: O(1).
public func | (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
    return Bitboard(rawValue: lhs.rawValue | rhs.rawValue)
}

/// Stores the result of performing a bitwise OR operation on the two given values in the left-hand-side variable.
public func |= (lhs: inout Bitboard, rhs: Bitboard) {
    lhs.rawValue |= rhs.rawValue
}

/// Returns the bits that are set in exactly one of `lhs` and `rhs`.
///
/// - complexity: O(1).
public func ^ (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
    return Bitboard(rawValue: lhs.rawValue ^ rhs.rawValue)
}

/// Returns `x ^ ~Self.allZeros`.
///
/// - complexity: O(1).
public prefix func ~ (x: Bitboard) -> Bitboard {
    return Bitboard(rawValue: ~x.rawValue)
}

/// Returns the bits of `lhs` shifted right by `rhs`.
public func >> (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
    return Bitboard(rawValue: lhs.rawValue >> rhs.rawValue)
}

/// Returns the bits of `lhs` shifted left by `rhs`.
public func << (lhs: Bitboard, rhs: Bitboard) -> Bitboard {
    return Bitboard(rawValue: lhs.rawValue << rhs.rawValue)
}

/// Shifts the bits of `lhs` right by `rhs`.
public func >>= (lhs: inout Bitboard, rhs: Bitboard) {
    lhs.rawValue >>= rhs.rawValue
}

/// Shifts the bits of `lhs` left by `rhs`.
public func <<= (lhs: inout Bitboard, rhs: Bitboard) {
    lhs.rawValue <<= rhs.rawValue
}