constants.go

package dragontoothmg

import (
	"math/bits"
	"math/rand"
)

// Initialize the magic lookups tables
func init() {
	magicMovesRook = make([][]uint64, 64, 64)
	magicMovesBishop = make([][]uint64, 64, 64)
	for i := 0; i < 64; i++ {
		magicMovesRook[i] = make([]uint64, magicDbSizeRook[i], magicDbSizeRook[i])
		magicMovesBishop[i] = make([]uint64, magicDbSizeBishop[i], magicDbSizeBishop[i])
	}
	generateRookMagicTable()
	generateBishopMagicTable()
	generateZobristConstants()
}

func generateZobristConstants() {
	whiteToMoveZobristC = rand.Uint64()
	for i := 0; i < 12; i++ {
		for j := 0; j < 64; j++ {
			pieceSquareZobristC[i][j] = rand.Uint64()
		}
	}
	for i := 0; i < 4; i++ {
		castleRightsZobristC[i] = rand.Uint64()
	}
}

func generateRookMagicTable() {
	// For a rook at every board position
	for i := 0; i < 64; i++ {
		blockerMask := magicRookBlockerMasks[i]
		generateBlockerPermutations(Square(i), blockerMask, 0, true)
	}
}

func generateBishopMagicTable() {
	// For a bishop at every board position
	for i := 0; i < 64; i++ {
		blockerMask := magicBishopBlockerMasks[i]
		generateBlockerPermutations(Square(i), blockerMask, 0, false)
	}
}

// Recursively generate all permutations of active and inactive bits in the
// blocker mask. Origin is the piece's starting square. BlockerMaskProgress is
// the original blocker bitboard, from which we eliminate bits.
// CurrPerm is the bitboard permutation we are accumulating.
func generateBlockerPermutations(origin Square, blockerMaskProgress uint64, currPerm uint64, rook bool) {
	if blockerMaskProgress == 0 {
		// currPerm represents one possible occupancy pattern on the blocker bitboard
		if rook {
			dbindex := (currPerm * magicNumberRook[origin]) >> magicRookShifts[origin]
			magicMovesRook[origin][dbindex] = rookMovesFromBlockers(origin, currPerm)
		} else {
			dbindex := (currPerm * magicNumberBishop[origin]) >> magicBishopShifts[origin]
			magicMovesBishop[origin][dbindex] = bishopMovesFromBlockers(origin, currPerm)
		}
		return
	}
	nextBit := bits.TrailingZeros64(blockerMaskProgress)
	blockerMaskProgress &= blockerMaskProgress - 1
	without := currPerm
	with := currPerm | (uint64(1) << uint8(nextBit))
	generateBlockerPermutations(origin, blockerMaskProgress, without, rook)
	generateBlockerPermutations(origin, blockerMaskProgress, with, rook)
}

func rookMovesFromBlockers(origin Square, blockers uint64) uint64 {
	var moves uint64
	// Slide up
	nextMoveUp := (uint64(1) << uint8(origin)) << 8
	for {
		if bits.TrailingZeros64(nextMoveUp) >= 64 {
			break // off the board
		}
		moves |= nextMoveUp
		if blockers&(^nextMoveUp) != blockers { // the coord nextMoveUp is occupied
			break
		}
		nextMoveUp <<= 8
	}
	// Slide down
	nextMoveDown := (uint64(1) << uint8(origin)) >> 8
	for {
		if bits.TrailingZeros64(nextMoveDown) >= 64 {
			break // off the board
		}
		moves |= nextMoveDown
		if blockers&(^nextMoveDown) != blockers { // the coord nextMoveDown is occupied
			break
		}
		nextMoveDown >>= 8
	}
	// Slide east
	nextMoveEast := (uint64(1) << uint8(origin)) << 1
	for {
		if bits.TrailingZeros64(nextMoveEast) >= (((int(origin) / 8) + 1) * 8) {
			break
		}
		moves |= nextMoveEast
		if blockers&(^nextMoveEast) != blockers { // the coord nextMoveEast is occupied
			break
		}
		nextMoveEast <<= 1
	}
	// Slide west
	nextMoveWest := (uint64(1) << uint8(origin)) >> 1
	for {
		if bits.TrailingZeros64(nextMoveWest) < ((int(origin)/8)*8) ||
			bits.TrailingZeros64(nextMoveWest) >= 64 { // flowed off the end
			break
		}
		moves |= nextMoveWest
		if blockers&(^nextMoveWest) != blockers { // the coord nextMoveWest is occupied
			break
		}
		nextMoveWest >>= 1
	}
	return moves

}

func bishopMovesFromBlockers(origin Square, blockers uint64) uint64 {
	var moves uint64
	nextSquareNE := origin + 9
	for nextSquareNE%8 > origin%8 {
		nextSquareBitboard := uint64(1) << uint8(nextSquareNE)
		moves |= nextSquareBitboard
		if blockers&nextSquareBitboard != 0 {
			break
		}
		nextSquareNE += 9
	}

	nextSquareNW := origin + 7
	for nextSquareNW%8 < origin%8 {
		nextSquareBitboard := uint64(1) << uint8(nextSquareNW)
		moves |= nextSquareBitboard
		if blockers&nextSquareBitboard != 0 {
			break
		}
		nextSquareNW += 7
	}

	nextSquareSE := origin - 7
	for nextSquareSE%8 > origin%8 {
		nextSquareBitboard := uint64(1) << uint8(nextSquareSE)
		moves |= nextSquareBitboard
		if blockers&nextSquareBitboard != 0 {
			break
		}
		nextSquareSE -= 7
	}

	nextSquareSW := origin - 9
	for nextSquareSW%8 < origin%8 {
		nextSquareBitboard := uint64(1) << uint8(nextSquareSW)
		moves |= nextSquareBitboard
		if blockers&nextSquareBitboard != 0 {
			break
		}
		nextSquareSW -= 9
	}

	return moves
}

// The starting position FEN
const Startpos = "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1"

// Zobrist Constants
var pieceSquareZobristC [12][64]uint64
var castleRightsZobristC [4]uint64
var whiteToMoveZobristC uint64 // active if white is to move

const kDefaultMoveListLength int = 65

// Bitboard where every bit is active
var everything uint64 = ^(uint64(0))

// Only activate one file, A-H (A=0, H=7)
var onlyFile = [8]uint64{
	0x0101010101010101, 0x0202020202020202, 0x0404040404040404, 0x0808080808080808,
	0x1010101010101010, 0x2020202020202020, 0x4040404040404040, 0x8080808080808080}

var onlyRank = [8]uint64{
	0xFF, 0XFF00, 0XFF0000, 0XFF000000,
	0XFF00000000, 0XFF0000000000, 0XFF000000000000, 0XFF00000000000000}

// Masks for attacks
// In order: knight on A1, B1, C1, ... F8, G8, H8
var knightMasks = [64]uint64{
	0x0000000000020400, 0x0000000000050800, 0x00000000000a1100, 0x0000000000142200,
	0x0000000000284400, 0x0000000000508800, 0x0000000000a01000, 0x0000000000402000,
	0x0000000002040004, 0x0000000005080008, 0x000000000a110011, 0x0000000014220022,
	0x0000000028440044, 0x0000000050880088, 0x00000000a0100010, 0x0000000040200020,
	0x0000000204000402, 0x0000000508000805, 0x0000000a1100110a, 0x0000001422002214,
	0x0000002844004428, 0x0000005088008850, 0x000000a0100010a0, 0x0000004020002040,
	0x0000020400040200, 0x0000050800080500, 0x00000a1100110a00, 0x0000142200221400,
	0x0000284400442800, 0x0000508800885000, 0x0000a0100010a000, 0x0000402000204000,
	0x0002040004020000, 0x0005080008050000, 0x000a1100110a0000, 0x0014220022140000,
	0x0028440044280000, 0x0050880088500000, 0x00a0100010a00000, 0x0040200020400000,
	0x0204000402000000, 0x0508000805000000, 0x0a1100110a000000, 0x1422002214000000,
	0x2844004428000000, 0x5088008850000000, 0xa0100010a0000000, 0x4020002040000000,
	0x0400040200000000, 0x0800080500000000, 0x1100110a00000000, 0x2200221400000000,
	0x4400442800000000, 0x8800885000000000, 0x100010a000000000, 0x2000204000000000,
	0x0004020000000000, 0x0008050000000000, 0x00110a0000000000, 0x0022140000000000,
	0x0044280000000000, 0x0088500000000000, 0x0010a00000000000, 0x0020400000000000}

var kingMasks = [64]uint64{
	0x0000000000000302, 0x0000000000000705, 0x0000000000000e0a, 0x0000000000001c14,
	0x0000000000003828, 0x0000000000007050, 0x000000000000e0a0, 0x000000000000c040,
	0x0000000000030203, 0x0000000000070507, 0x00000000000e0a0e, 0x00000000001c141c,
	0x0000000000382838, 0x0000000000705070, 0x0000000000e0a0e0, 0x0000000000c040c0,
	0x0000000003020300, 0x0000000007050700, 0x000000000e0a0e00, 0x000000001c141c00,
	0x0000000038283800, 0x0000000070507000, 0x00000000e0a0e000, 0x00000000c040c000,
	0x0000000302030000, 0x0000000705070000, 0x0000000e0a0e0000, 0x0000001c141c0000,
	0x0000003828380000, 0x0000007050700000, 0x000000e0a0e00000, 0x000000c040c00000,
	0x0000030203000000, 0x0000070507000000, 0x00000e0a0e000000, 0x00001c141c000000,
	0x0000382838000000, 0x0000705070000000, 0x0000e0a0e0000000, 0x0000c040c0000000,
	0x0003020300000000, 0x0007050700000000, 0x000e0a0e00000000, 0x001c141c00000000,
	0x0038283800000000, 0x0070507000000000, 0x00e0a0e000000000, 0x00c040c000000000,
	0x0302030000000000, 0x0705070000000000, 0x0e0a0e0000000000, 0x1c141c0000000000,
	0x3828380000000000, 0x7050700000000000, 0xe0a0e00000000000, 0xc040c00000000000,
	0x0203000000000000, 0x0507000000000000, 0x0a0e000000000000, 0x141c000000000000,
	0x2838000000000000, 0x5070000000000000, 0xa0e0000000000000, 0x40c0000000000000}

// The occupancy masks for a rook or bishop at each index.
// This represents the locations the piece can slide to that don't block it;
// thus, the edges of the board are not included.
// Used for magic bitboards.
var magicRookBlockerMasks = [64]uint64{
	0x000101010101017E, 0x000202020202027C, 0x000404040404047A, 0x0008080808080876,
	0x001010101010106E, 0x002020202020205E, 0x004040404040403E, 0x008080808080807E,
	0x0001010101017E00, 0x0002020202027C00, 0x0004040404047A00, 0x0008080808087600,
	0x0010101010106E00, 0x0020202020205E00, 0x0040404040403E00, 0x0080808080807E00,
	0x00010101017E0100, 0x00020202027C0200, 0x00040404047A0400, 0x0008080808760800,
	0x00101010106E1000, 0x00202020205E2000, 0x00404040403E4000, 0x00808080807E8000,
	0x000101017E010100, 0x000202027C020200, 0x000404047A040400, 0x0008080876080800,
	0x001010106E101000, 0x002020205E202000, 0x004040403E404000, 0x008080807E808000,
	0x0001017E01010100, 0x0002027C02020200, 0x0004047A04040400, 0x0008087608080800,
	0x0010106E10101000, 0x0020205E20202000, 0x0040403E40404000, 0x0080807E80808000,
	0x00017E0101010100, 0x00027C0202020200, 0x00047A0404040400, 0x0008760808080800,
	0x00106E1010101000, 0x00205E2020202000, 0x00403E4040404000, 0x00807E8080808000,
	0x007E010101010100, 0x007C020202020200, 0x007A040404040400, 0x0076080808080800,
	0x006E101010101000, 0x005E202020202000, 0x003E404040404000, 0x007E808080808000,
	0x7E01010101010100, 0x7C02020202020200, 0x7A04040404040400, 0x7608080808080800,
	0x6E10101010101000, 0x5E20202020202000, 0x3E40404040404000, 0x7E80808080808000}

var magicBishopBlockerMasks = [64]uint64{
	0x0040201008040200, 0x0000402010080400, 0x0000004020100A00, 0x0000000040221400,
	0x0000000002442800, 0x0000000204085000, 0x0000020408102000, 0x0002040810204000,
	0x0020100804020000, 0x0040201008040000, 0x00004020100A0000, 0x0000004022140000,
	0x0000000244280000, 0x0000020408500000, 0x0002040810200000, 0x0004081020400000,
	0x0010080402000200, 0x0020100804000400, 0x004020100A000A00, 0x0000402214001400,
	0x0000024428002800, 0x0002040850005000, 0x0004081020002000, 0x0008102040004000,
	0x0008040200020400, 0x0010080400040800, 0x0020100A000A1000, 0x0040221400142200,
	0x0002442800284400, 0x0004085000500800, 0x0008102000201000, 0x0010204000402000,
	0x0004020002040800, 0x0008040004081000, 0x00100A000A102000, 0x0022140014224000,
	0x0044280028440200, 0x0008500050080400, 0x0010200020100800, 0x0020400040201000,
	0x0002000204081000, 0x0004000408102000, 0x000A000A10204000, 0x0014001422400000,
	0x0028002844020000, 0x0050005008040200, 0x0020002010080400, 0x0040004020100800,
	0x0000020408102000, 0x0000040810204000, 0x00000A1020400000, 0x0000142240000000,
	0x0000284402000000, 0x0000500804020000, 0x0000201008040200, 0x0000402010080400,
	0x0002040810204000, 0x0004081020400000, 0x000A102040000000, 0x0014224000000000,
	0x0028440200000000, 0x0050080402000000, 0x0020100804020000, 0x0040201008040200}

// Shifts for magic bitboards.
var magicRookShifts = [64]uint64{
	52, 53, 53, 53, 53, 53, 53, 52,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 54, 54, 54, 54, 53,
	53, 54, 54, 53, 53, 53, 53, 53}

var magicBishopShifts = [64]uint64{
	58, 59, 59, 59, 59, 59, 59, 58,
	59, 59, 59, 59, 59, 59, 59, 59,
	59, 59, 57, 57, 57, 57, 59, 59,
	59, 59, 57, 55, 55, 57, 59, 59,
	59, 59, 57, 55, 55, 57, 59, 59,
	59, 59, 57, 57, 57, 57, 59, 59,
	59, 59, 59, 59, 59, 59, 59, 59,
	58, 59, 59, 59, 59, 59, 59, 58}

// Magic numbers for magic bitboards.
var magicNumberRook = [64]uint64{
	0x0080001020400080, 0x0040001000200040, 0x0080081000200080, 0x0080040800100080,
	0x0080020400080080, 0x0080010200040080, 0x0080008001000200, 0x0080002040800100,
	0x0000800020400080, 0x0000400020005000, 0x0000801000200080, 0x0000800800100080,
	0x0000800400080080, 0x0000800200040080, 0x0000800100020080, 0x0000800040800100,
	0x0000208000400080, 0x0000404000201000, 0x0000808010002000, 0x0000808008001000,
	0x0000808004000800, 0x0000808002000400, 0x0000010100020004, 0x0000020000408104,
	0x0000208080004000, 0x0000200040005000, 0x0000100080200080, 0x0000080080100080,
	0x0000040080080080, 0x0000020080040080, 0x0000010080800200, 0x0000800080004100,
	0x0000204000800080, 0x0000200040401000, 0x0000100080802000, 0x0000080080801000,
	0x0000040080800800, 0x0000020080800400, 0x0000020001010004, 0x0000800040800100,
	0x0000204000808000, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080,
	0x0000040008008080, 0x0000020004008080, 0x0000010002008080, 0x0000004081020004,
	0x0000204000800080, 0x0000200040008080, 0x0000100020008080, 0x0000080010008080,
	0x0000040008008080, 0x0000020004008080, 0x0000800100020080, 0x0000800041000080,
	0x00FFFCDDFCED714A, 0x007FFCDDFCED714A, 0x003FFFCDFFD88096, 0x0000040810002101,
	0x0001000204080011, 0x0001000204000801, 0x0001000082000401, 0x0001FFFAABFAD1A2}

var magicNumberBishop = [64]uint64{
	0x0002020202020200, 0x0002020202020000, 0x0004010202000000, 0x0004040080000000,
	0x0001104000000000, 0x0000821040000000, 0x0000410410400000, 0x0000104104104000,
	0x0000040404040400, 0x0000020202020200, 0x0000040102020000, 0x0000040400800000,
	0x0000011040000000, 0x0000008210400000, 0x0000004104104000, 0x0000002082082000,
	0x0004000808080800, 0x0002000404040400, 0x0001000202020200, 0x0000800802004000,
	0x0000800400A00000, 0x0000200100884000, 0x0000400082082000, 0x0000200041041000,
	0x0002080010101000, 0x0001040008080800, 0x0000208004010400, 0x0000404004010200,
	0x0000840000802000, 0x0000404002011000, 0x0000808001041000, 0x0000404000820800,
	0x0001041000202000, 0x0000820800101000, 0x0000104400080800, 0x0000020080080080,
	0x0000404040040100, 0x0000808100020100, 0x0001010100020800, 0x0000808080010400,
	0x0000820820004000, 0x0000410410002000, 0x0000082088001000, 0x0000002011000800,
	0x0000080100400400, 0x0001010101000200, 0x0002020202000400, 0x0001010101000200,
	0x0000410410400000, 0x0000208208200000, 0x0000002084100000, 0x0000000020880000,
	0x0000001002020000, 0x0000040408020000, 0x0004040404040000, 0x0002020202020000,
	0x0000104104104000, 0x0000002082082000, 0x0000000020841000, 0x0000000000208800,
	0x0000000010020200, 0x0000000404080200, 0x0000040404040400, 0x0002020202020200}

// Database sizes for the magic database, organized by square ID:
var magicDbSizeRook = [64]uint64{
	4096, 2048, 2048, 2048, 2048, 2048, 2048, 4096,
	2048, 1024, 1024, 1024, 1024, 1024, 1024, 2048,
	2048, 1024, 1024, 1024, 1024, 1024, 1024, 2048,
	2048, 1024, 1024, 1024, 1024, 1024, 1024, 2048,
	2048, 1024, 1024, 1024, 1024, 1024, 1024, 2048,
	2048, 1024, 1024, 1024, 1024, 1024, 1024, 2048,
	2048, 1024, 1024, 1024, 1024, 1024, 1024, 2048,
	2048, 1024, 1024, 2048, 2048, 2048, 2048, 2048}

var magicDbSizeBishop = [64]uint64{
	64, 32, 32, 32, 32, 32, 32, 64, 32, 32, 32, 32, 32, 32, 32, 32,
	32, 32, 128, 128, 128, 128, 32, 32, 32, 32, 128, 512, 512, 128, 32, 32,
	32, 32, 128, 512, 512, 128, 32, 32, 32, 32, 128, 128, 128, 128, 32, 32,
	32, 32, 32, 32, 32, 32, 32, 32, 64, 32, 32, 32, 32, 32, 32, 64}

// The actual magic moves database, populated by init
var magicMovesRook [][]uint64
var magicMovesBishop [][]uint64