| | | 1 | | using Rudim.Common; |
| | | 2 | | using System.Diagnostics.CodeAnalysis; |
| | | 3 | | using System.Linq; |
| | | 4 | | using System.Numerics; |
| | | 5 | | |
| | | 6 | | namespace Rudim |
| | | 7 | | { |
| | | 8 | | public partial struct Bitboard |
| | | 9 | | { |
| | | 10 | | [ExcludeFromCodeCoverage] // This is only used as a helper in the beginning to generate numbers - never used in |
| | | 11 | | public static ulong FindMagicNumber(Square square, int bitsInMask, bool isBishop) |
| | | 12 | | { |
| | | 13 | | int maxIndex = 1 << bitsInMask; |
| | | 14 | | Bitboard[] occupancyMappings = new Bitboard[Constants.MaxMaskIndex]; |
| | | 15 | | Bitboard[] attacks = new Bitboard[Constants.MaxMaskIndex]; |
| | | 16 | | Bitboard mask = isBishop ? GetBishopMask(square) : GetRookMask(square); |
| | | 17 | | |
| | | 18 | | for (int index = 0; index < maxIndex; ++index) |
| | | 19 | | { |
| | | 20 | | occupancyMappings[index] = GetOccupancyMapping(index, bitsInMask, mask); |
| | | 21 | | attacks[index] = isBishop ? GetBishopAttacks(square, occupancyMappings[index]) : GetRookAttacks(square, |
| | | 22 | | } |
| | | 23 | | |
| | | 24 | | for (int count = 0; count < Constants.MaxRetryCount; ++count) |
| | | 25 | | { |
| | | 26 | | ulong potentialMagicNumber = GeneratePotentialMagicNumber(); |
| | | 27 | | |
| | | 28 | | // Early exit impossible magics |
| | | 29 | | if (BitOperations.PopCount((mask.Board * potentialMagicNumber) & 0xFF00000000000000) < 6) |
| | | 30 | | continue; |
| | | 31 | | |
| | | 32 | | Bitboard[] magicAttacks = Enumerable.Repeat(new Bitboard(0xFFFFFFFFFFFFFFFF), Constants.MaxMaskIndex).To |
| | | 33 | | bool failureFlag = false; |
| | | 34 | | for (int index = 0; index < maxIndex; ++index) |
| | | 35 | | { |
| | | 36 | | int magicIndex = (int)((occupancyMappings[index].Board * potentialMagicNumber) >> (64 - bitsInMask)) |
| | | 37 | | if (magicAttacks[magicIndex].Board == 0xFFFFFFFFFFFFFFFF) |
| | | 38 | | magicAttacks[magicIndex] = attacks[index]; |
| | | 39 | | else if (!Equals(magicAttacks[magicIndex], attacks[index])) |
| | | 40 | | failureFlag = true; |
| | | 41 | | } |
| | | 42 | | // PotentialMagicNumber is actually the magic number |
| | | 43 | | if (!failureFlag) |
| | | 44 | | return potentialMagicNumber; |
| | | 45 | | } |
| | | 46 | | throw new ExceededMaximumRetryException("No magic number found"); |
| | | 47 | | } |
| | | 48 | | public static Bitboard GetBishopMask(Square square) |
| | | 49 | | { |
| | 67 | 50 | | Bitboard resultBoard = new Bitboard(0); |
| | | 51 | | // Masking equivalent to attacks with zero blockers and no edge square |
| | 67 | 52 | | Bitboard occupancyBoard = new Bitboard(0); |
| | 67 | 53 | | int bishopRank = (int)square >> 3; |
| | 67 | 54 | | int bishopFile = (int)square & (8 - 1); |
| | | 55 | | |
| | 486 | 56 | | for (int rank = bishopRank + 1, file = bishopFile + 1; rank < 7 && file < 7; ++rank, ++file) |
| | 95 | 57 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rank, file, occupancyBoard)) |
| | | 58 | | break; |
| | | 59 | | |
| | 504 | 60 | | for (int rank = bishopRank - 1, file = bishopFile + 1; rank >= 1 && file < 7; --rank, ++file) |
| | 101 | 61 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rank, file, occupancyBoard)) |
| | | 62 | | break; |
| | | 63 | | |
| | 486 | 64 | | for (int rank = bishopRank - 1, file = bishopFile - 1; rank >= 1 && file >= 1; --rank, --file) |
| | 95 | 65 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rank, file, occupancyBoard)) |
| | | 66 | | break; |
| | | 67 | | |
| | 492 | 68 | | for (int rank = bishopRank + 1, file = bishopFile - 1; rank < 7 && file >= 1; ++rank, --file) |
| | 97 | 69 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rank, file, occupancyBoard)) |
| | | 70 | | break; |
| | | 71 | | |
| | 67 | 72 | | return resultBoard; |
| | | 73 | | } |
| | | 74 | | |
| | | 75 | | public static Bitboard GetRookMask(Square square) |
| | | 76 | | { |
| | 67 | 77 | | Bitboard resultBoard = new Bitboard(0); |
| | | 78 | | // Masking equivalent to attacks with zero blockers and no edge square |
| | 67 | 79 | | Bitboard occupancyBoard = new Bitboard(0); |
| | 67 | 80 | | int rookRank = (int)square >> 3; |
| | 67 | 81 | | int rookFile = (int)square & (8 - 1); |
| | | 82 | | |
| | 482 | 83 | | for (int rank = rookRank + 1; rank < 7; ++rank) |
| | 174 | 84 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rank, rookFile, occupancyBoard)) |
| | | 85 | | break; |
| | | 86 | | |
| | 490 | 87 | | for (int rank = rookRank - 1; rank >= 1; --rank) |
| | 178 | 88 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rank, rookFile, occupancyBoard)) |
| | | 89 | | break; |
| | | 90 | | |
| | 490 | 91 | | for (int file = rookFile + 1; file < 7; ++file) |
| | 178 | 92 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rookRank, file, occupancyBoard)) |
| | | 93 | | break; |
| | | 94 | | |
| | 482 | 95 | | for (int file = rookFile - 1; file >= 1; --file) |
| | 174 | 96 | | if (AddSquareToBoardAndStopAtOccupiedSquare(ref resultBoard, rookRank, file, occupancyBoard)) |
| | | 97 | | break; |
| | | 98 | | |
| | 67 | 99 | | return resultBoard; |
| | | 100 | | } |
| | | 101 | | |
| | | 102 | | public static Bitboard GetOccupancyMapping(int index, int nBitsInMask, Bitboard mask) |
| | | 103 | | { |
| | 107650 | 104 | | Bitboard occupancyMapping = new Bitboard(0); |
| | 107650 | 105 | | Bitboard temporaryMask = new Bitboard(mask.Board); |
| | 2502698 | 106 | | for (int count = 0; count < nBitsInMask; ++count) |
| | | 107 | | { |
| | 1143699 | 108 | | int square = BitOperations.TrailingZeroCount(temporaryMask.Board); |
| | 1143699 | 109 | | temporaryMask.ClearBit(square); |
| | | 110 | | |
| | 1143699 | 111 | | if ((index & (1 << count)) != 0) |
| | 571846 | 112 | | occupancyMapping.Board |= 1ul << square; |
| | | 113 | | } |
| | 107650 | 114 | | return occupancyMapping; |
| | | 115 | | } |
| | | 116 | | private static ulong GeneratePotentialMagicNumber() |
| | | 117 | | { |
| | 0 | 118 | | return Random.NextULong() & Random.NextULong() & Random.NextULong(); |
| | | 119 | | } |
| | | 120 | | } |
| | | 121 | | } |