Magic Castles

[Grant Osborne]

Hello everyone

The rules of chess state that when castling the king must not pass through or land on a square that is attacked by an enemy piece, therefore two squares need to be assessed before the move is allowed. It is possible to consider the two critical squares together when checking for enemy attacks.
For example the white kingside castle move. We can check for attacks by pawns, knights and king on F1 & G1 :-


[if ((BlackPawns & 0x00F0000000000000) || (BlackKnights & 0x0098F00000000000) || (BlackKing & 0x00F0000000000000))
castle move not allowed;
]

For the sliding pieces we can use a slight variation of Lasse Hansen's magic number system to check for attacks on F1 & G1 :-

[pattern = Occupied & 0x0060606060606000;
address1 = (int) ((pattern * 0x1082008020020008) >> 52);
pattern = Occupied & 0x0070180C06020000;
address2 = (int) ((pattern * 0x0010842004001120) >> 54);
if ((castleAttacks[address1] & BlackBishopsQueens) | (diagCastleAttacks[address2] & BlackRooksQueens))
castle move not allowed;
]

The variation is of course the fact that 2 squares are being considered at once.

Each of the 64 x 64 elements of the attack tables for the files contain two set 1 bits pertaining to the msb of the occupancy (for white castle moves) or lsb (for black) of each file to the castling squares. Each of the 32 x 32 elements of the attack tables for the diagonals contain four set 1 bits because of the 2 directions to the castling squares. The table sizes for the attacks are, for files 4 * 4096 * 8 = 131072 and diagonals 4 * 1024 * 8 = 32768 a total of 160Kb.
I have found all the magics to calculate king and queenside castling for black and white

White kingside files magic 0x1082008020020008
White kingside diagonals magic 0x0010842004001120
White queenside files magic 0x0874100040040100
White queenside diagonals magic 0x0081A03818202800
Black kingside files magic 0x1082008020020008
Black kingside diagonals magic 0x614880100300E408
Black queenside files magic 0x0874100040040100
Black queenside diagonals magic 0x880800A00C601609

I have this working in my engine and gives a slight speed up in my moves generation.

Grant

[Gerd Isenberg]

Hi Grant,

Wow - there is no taboo with and/mul/shift-hashing

With chess960 castles in mind, you can also do two diagonal and one vertical Kogge-Stone-fills and intersect the diagonals with opposite queens/bishops and the vertical with opposite queens/rooks. So for instance if in frc the king castle goes from b1-g1, you can pass {c1-f1} as generator to the multi-piece direction wise attack getters. Vertical attacks are northAttacks for the white side and southAttacks for the black backrank. Propagator is the set of empty squares. Parallel prefix Kogge-Stone routines by Steffan Westcott:

Code: Select all

u64 northAttacks(u64 gen, u64 pro) {
    gen |= pro & (gen <<  8);
    pro  = pro & (pro <<  8);
    gen |= pro & (gen << 16);
    pro  = pro & (pro << 16);
    gen |= pro & (gen << 32);
    return (gen <<  8);
}

u64 southAttacks(u64 gen, u64 pro) {
    gen |= pro & (gen >>  8);
    pro  = pro & (pro >>  8);
    gen |= pro & (gen >> 16);
    pro  = pro & (pro >> 16);
    gen |= pro & (gen >> 32);
    return (gen >>  8);
}


Gerd

[Grant Osborne]

Thanks Gerd

Grant