Magic Castles
Posted: 14 Sep 2006, 08:39
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
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