Author: KarinsDad
Date: 13:05:45 04/28/99
Go up one level in this thread
Another advantage of piece attack tables is that it allows you to calculate legal moves very rapidly. For example, pseudo legal moves are more difficult to use with singular extensions than if legal moves are generated. But generating legal moves normally takes considerably more time. With piece attack tables, generating legal only moves is almost as fast as generating pseudo legal moves once the normal bitboards and piece attack table themselves are created. Since these will often be created via a delta of the parent node, this will not be too slow. With piece attack tables, you quickly know: 1) whether your king is in check (i.e. the opponent's piece attack square for the square your king is on is not equal to zero). This is important since only interposing moves and king moves are allowed. 2) whether your king is in double check (i.e. the opponent's piece attack square for the square your king is on has more than one bit set to zero) and hence only king moves are legal. 3) whether your king can castle (i.e. the 2 piece attack squares to it's right or left and the piece attack square for the king square must be equal to zero to allow castling in that direction). 4) what squares are legal king moves (i.e. the opponent's piece attack square for the square being checked must be equal to zero). Checking for pins is fast using a combination of bitboards. You check in all 8 directions from the king and then use one byte for each piece on the board to indicate whether it is not pinned (the default), partially pinned (e.g. pinning a bishop against the king with another bishop, the pinned bishop can only move in at most 2 out of it's 4 normal directions, so only 1 of the 2 diagonal bitboards has to be used to figure out legal moves), or totally pinned (e.g. all knight pins against the king). The byte indicates the directions in which the piece cannot move. A check of zero indicates a non-pinned piece, a check of ff indicates a totally pinned piece, etc. (actually, you only need to use 4 of the 8 bits since there are only 4 bitboard directions). Non-pinned pieces use the piece attack tables and immediately get all of their moves. Partially pinned pieces (a rarety) use the bitboards (the same way as the piece attack tables were set up in the first place). Totally pinned pieces do not calculate moves. So, the 2 different type of moves that are NOT calculated using the piece attack tables are: 1) Pushed pawns (calculated on the fly). 2) Partially pinned pieces (calculated with bitboards). This is a small percentage of all moves in most positions (except early opening and late endgame). Even things such as en passant and castling basically use the piece attack tables to determine if they can be done (along with normal checks to see if they can be done such as, for example, there are no pieces between the king and the rook, this can be done quickly by ANDing a castling mask with the xored bitboard). The main differences between the two methods would appear to be: 1) the checking for legal moves on any considered move in the pseudo legal search (this of course gets pruned due to beta cutoffs) and the check to ensure that non-king related moves are legal (i.e. a piece cannot move to a square that is occupied by it's own side) in the move generation VS. 2) the delta setup of the piece attack tables and bitboards, and the quick legal move checks in the move generation. My gut feel is that method 2 is faster than method 1 since only a small portion (maybe 30%) of the piece attack tables get re-calculated from the parent and an even smaller portion (3% of the bits, up to 17% of the bytes) of the bitboards get re-calculated from the parent. However, I have no statistics to back this perception up. I wonder if anybody has tried both methods and found one to be faster. I also hope the above explanation helps out anyone writing a program who is considering using bitboards and piece attack tables. KarinsDad :)
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.