Author: KarinsDad
Date: 15:19:19 06/10/99
Go up one level in this thread
On June 10, 1999 at 16:25:59, James Swafford wrote: [snip] > >> >>Lastly, I'm thinking of adding attack tables to speed up the search. At >>present, I think they would be helpful in identifying all the squares that a >>pawn or piece can attack when placed at a particular location which would speed >>up the InCheck() function. Where else would these tables be helpful? Since I >>plan to use 64 bit long long values and logical 'and' those with a square mask, >>this will return a boolean value about whether the piece attacks. Can they be >>used in move generation? Other locations? Any comments, pointers, or referances >>to articles or source code would be appreciated. I used a 16 bit piece attack table instead of a 64 bit square attack table. Instead of storing which of the 64 squares a given piece attacks, I store for a given square which of the 16 pieces of one color attacks it. I think it is faster to find out information by pulling it out of a 16 bit structure than a 64 bit structure. For example, this allows me to quickly know how many pieces of a given color attack a given square (as opposed to looking into 16 64 bit structures to pull this information out) by just counting the number of bits out of 16 turned on. Since I have the bits ordered from least powerful pieces to most powerful pieces, I can use masks to quickly check if a given square is controlled by one color or another (assuming no promotions). This is useful for king safety. I can also find out if a square is not attacked by any pieces of given color by checking if the structure has a value of zero (a fast comparison) for things like InCheck(). For move generation, I can quickly pull out which pieces attack a given square since the value of the structure is greater than or equal to the low order bit turned on of the first piece in the structure. For example, if the square has a value >= 256, at least one piece (knight, bishop, rook, queen, or king) attacks the square. If the value is = 0, then no pieces attack the square. If the value < 256, then one or more pawns attack the square, but that is only important if an opposing colored piece is in the square for move generation (assuming no promotions). I can mask out the pawns (since at most 2 pawns can attack a given square, the algorithm for getting them is quick). In the 64 bit square attack system, a pawn will attack either one or two squares everytime. So, there is a quick algorithm to pull out the lowest ordered bit turned on and the highest ordered bit turned on. So, the pawns can be calculated quickly everytime in this scheme. However, the major and minor pieces usually attack more than 2 squares, often 8 or more once you get into the middlegame and the endgame. So, you may have to decide which algorithm is quickest to pull out the information (for a 64 bit structure). In the 16 bit piece attack system, you usually have at most 4 pieces attacking a given square, so you can use the same fast low order bit algorithm to pull out each piece as you use for pawns and that is usually just as fast as any other algorithm. For evaluation, it is more important to know information about a given square than a given piece (IMO). I do not particularly care what a given piece is doing (unless it is pinned). Instead, I care what pieces can do to a particular square (i.e. which pieces of which color and which strength and how many attack a given square and what type of square it is, i.e. edge, center, etc.). This is one reason I have xraying piece attack tables (so that I can calculate data for batteries of pieces). > >They could be used in move generation. If you know a bishop attacks F3, >you can almost always move there, barring some check issues. >They may also be helpful in your evaluation, if you want to add such terms >as bishop/rook/queen mobility. You could just do a pop count of the >64 bit word representing a pieces attacked squares. I think the >possibilities are endless, but you'll pay a heavy price for them. >Be prepared to do a lot of testing. :-) > >-- >James I found that an easy way to test this in move generation is to create two algorithms, one with attack tables and one without (since most programmers do not use attack tables right off the bat, they normally have a non-attack table set of routines to generate moves first anyway). If you have a high level of confidence on the one without attack tables and then compare the results between the two for a lot of random positions and if they are identical, you can have the same high level of confidence for the one with the attack tables. Once you have a high level of confidence of the attack tables in your move generation, then you can also use them in evaluation with a high level of confidence, especially if you use the same macros to access them. 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.