Author: Charles L. Williams
Date: 14:23:12 04/29/99
Go up one level in this thread
On April 28, 1999 at 16:05:45, KarinsDad wrote: >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 :) At first I generated only legal moves using a "check vector," a line of bits between the checked king, leading to and including the attacking piece. This could be used to AND with any piece's generated moves, to eliminate the illegals. A knight didn't have a vector, only one bit for its position. It became complicated when it came to pins, so I switched to generating all possible moves, and checking the legality at the next ply. Why? Because that was the general consensus on how to do it. Now I'm not so sure. I never have been entirely comfortable with generating illegal moves, and sorting them out later. On the other hand, if I get a lot of cutoffs, I never have to find out. Chuck
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.