Author: KarinsDad
Date: 23:53:26 05/10/99
Go up one level in this thread
On May 10, 1999 at 23:04:49, Kristo Miettinen wrote: >Hi Dad! > >Thanks for your post. Indeed, I am a bit confused. > >One of my hangups with implementing rotated bitboards is that I need (for my >peculiar low-NPS approach) to evaluate square control for all 64 squares of the >board, whether occupied or not, for which I do indeed need to keep track of Xray >attackers as well as direct attackers. Obviously with "beyond[][]" and >first/last selective identifiers this is no too difficult. How might this be >accelerated with rotated bitboards? > Ok, here is my first cut at it. However, it is late at night and Monday nights are the only night of the week that I work on my program with my partner (5 1/2 hours tonight), so my brain is a little fried at this point (and this will be a lengthy explanation). You will have to determine yourself based on the number of operations I list below whether this will be faster or slower than how you do it. Similar to how you do it, rotated bitboards keep track of what the normal bitboards keep track of, but in a 45 or 135 degree direction. At the moment, my code has 16 bytes to represent each rotated direction (although this can be done in 8 bytes, I will explain shortly). There are 15 45 degree diagonals and 15 135 diagonals on a chess board. So, my 16 byte structure has an extra unused byte. Secondly, for the 45 degree diagonal (a1, a2-b1, a3-c1, etc.), there are 2 bytes that have no meaning, a1 and h8 (the next diagonal square for them in both directions is off of the board). The same applies to the 135 degree diagonals, however, the unused bytes are h1 and a8. So, in reality, I am using 13 bytes out of my 16 byte structure. To keep track of this in 8 bytes (which I will do one day when it becomes a high enough priority), you merely put a1 with the b8-h2 diagonal (1 bit plus 7 bits), the a2-b1 diagonal with the c8-h3 diagonal, etc. in both directions. In other words, since there are 64 squares, all 64 can be represented in 8 bytes. Ok, so now we have a rotated bitboard structure (I will discuss the 16 byte version since it is slightly simpler). I first have to create the rotated bitboard for the current board. To create a rotated bitboard from scratch, I go through the piecelocation table for each piece and turn on a bit in the rotated board through a row/column lookup table. So, a lookup and an OR for each piece in each table for a maximum total of 32 pieces * 2 rotated bitboards * (1 lookup + 1 OR) or: 1 memory structure clear and 64 lookups and 64 ORs. Now let us say for argument sake that I am using a recursive search system with the stack so that the parent's rotated bitboard exists (or I keep the structure around for all nodes in some other scheme). In this case, I can calculate a delta rotated bitboard for the child based on the rotated bitboard of the parent. First, I remove the moving piece's source square from the appropriate place in each rotated bitboard based on column and row (e.g. an AND with 11011111 type of thing or an XOR with 00100000 type of thing) and then I add it's destination square (e.g. an OR with 00001000). I also have to clear the destination square for the rotated bitboard in the same direction for the opposite color. So, a maximum total of one memory structure copy and 3 lookups and 2 ANDs and 1 OR. Considerably faster than doing it by scratch. So, all in all, the creation of the rotated bitboard tables (either from scratch or with delta information) is not too bad. I then create the square attack table (used to generate legal moves and to calculate square control). From scratch, this is somewhat time consuming and I will leave it to you to figure it all out (for every piece on the board). This is a huge routine in my code, but most of it was cut and paste with a few minor changes each time. If I am doing a delta square attack table calculation (for diagonal pieces), I then figure out for the move being performed all bishop and queen moves that could have been added due to a piece leaving a square; and all of the bishop and queen moves that could have been deleted due to a piece entering an empty square in the square attack table (similar to how this is done for rooks and queens in a non-rotated direction). The rotated bitboard is used with a table lookup for the appropriate column and row for the source square (the same is then done for the destination square. I store my rotated bitboards as: rxxxxxxx a1 rrxxxxxx a2-b1 rrrxxxxx rrrrxxxx rrrrrxxx rrrrrrxx rrrrrrrx rrrrrrrr a8-h1 xrrrrrrr xxrrrrrr xxxrrrrr xxxxrrrr xxxxxrrr xxxxxxrr xxxxxxxr h8 where r is the row (0-7) and x is an unused zeroed bit. So, for g2, it would be row 6, column 1 (also 0-7). The index into the array is row + column + 1 (this will change when I go to an 8 byte structure). The bit in the byte is row. If the square was not empty, then all of it's moves have to be removed first. There are several steps (and a few shortcuts) that can be done here, however, the basics are that you remove all of the moves at the source square, you add all of the moves at the destination square, you add all the additional horizontal, vertical, and diagonal moves at the source square, and you either prune all of the horizontal, vertical, and diagonal moves at the destination square (if there was no piece captured) or you just remove all of the moves for the piece being taken. For my code, this maxes out at about 60 lookups (20 bitboard and 40 lookup tables), 40 XORs, and 40 ANDs (based on the position, some moves have more, some have less). For example, a castling move has minimal calculations involved with the exception of the rook (in horizontal and vertical direction), the king, and the closest rook or queen on the back rank (or 6 bitboard, 6 lookup tables, 6 XORs and 6 ANDs in this case max). So, as you can see, the creation of the square attack table is more time consuming than the actual rotated bitboards. So, now you have both bitboards for each color and each direction, and square attack tables for each color/square. The square attack tables then give you a good majority of the moves for your legal move engine for the children of this position. Every square that a minor or major piece attacks is a potential move if that piece is not pinned. Every square that a pawn attacks that has an enemy piece on it is a potential move. Every square that is attacked by the opponent is a square the king cannot move to, etc. There is still some code involved for legal move generation, but it is a lot simpler since you just use the bitboards (rotated and non-rotated) to determine pins and then a good majority of the rest of the moves are in the square attack table (the main exceptions being the pushing of pawns and castling). Now, you have to create xraying square attack tables (used for REAL square control). This is a little harder, but it uses the same equations as creating the delta square attack tables. You take the square attack tables and copy them to a xraying square attack table structure (same structure, different name). For each battery piece (rook, bishop, and queen), you use the bitboards to calculate the last square that can be attacked by that piece in each direction. If there is a same direction moving piece of the same color there (i.e. a rook in front of a queen), then you temporarily remove the end piece (i.e. the rook) and recalculate for the queen. You continue to do this until you get to the end of the board in both directions (per bitboard). So, if you have QRRxxxxx, then the Q xrays all 7 squares, the first rook xrays 7 squares, and the second rook xrays 7 squares. This was done by temporarily creating a 10100000 bitboard from the 11100000 bitboard, then a 10000000 bitboard from the 10100000 bitboard (for the queen). So, this is about as time consuming as creating the delta square attack tables (although it is fairly fast if you have no batteries). Not too hard, but a little time consuming. Fortunately, there are usually only 10 pieces on the board that have this capability at any given time (although this number increases or decreases based on pieces being captured and pawns being promoted). Hope this explains it at a top level somewhat. The advantage of this system is that the rotated bitboards do the EXACT same thing for all of these structures for bishops and queens that the non-rotated bitboards do for rooks and queens. The only difference is the indexing into the array (which for me is row + column + 1, row for 45 diagonals; row + column + 1, column for 135 diagonals; column, row for horizontal; row, column for vertical). KarinsDad :) >I want to be converted, but I'm skeptical... > >Sine cera, > >-Kristo.
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.