diff options
Diffstat (limited to 'Sources/SwiftChessNeo/Bitboard.swift')
| -rw-r--r-- | Sources/SwiftChessNeo/Bitboard.swift | 646 |
1 files changed, 646 insertions, 0 deletions
diff --git a/Sources/SwiftChessNeo/Bitboard.swift b/Sources/SwiftChessNeo/Bitboard.swift new file mode 100644 index 0000000..f8c3dba --- /dev/null +++ b/Sources/SwiftChessNeo/Bitboard.swift @@ -0,0 +1,646 @@ +// +// 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 +} |