Author: Ratko V Tomic
Date: 19:48:42 11/19/99
Go up one level in this thread
> When a piece moves, all squares that are now "pseudo-unattacked" by the > move I undo the attacks, by XORing them. Does the bitmask refer to the actual attacks or to the potential uncovered attacks? If it is potential attacks, they would still have to be decoupled into real and potential before actual move list is produced. If they are real attacks, then when a piece moves from a square, all sliding attackers to that square would have to be identified (I guess from the bitmask via a LeastBit[] array getting back the index of the least bit set) and their movement xored into the right squares. I am not sure that this would perform much (if at all) better than the regular adding/stepping generator. Namely setting a bit is more expensive than writing a whole byte or a whole word to memory since setting a bit involves reading a data word from memory (implicitly by the processor) then writing the changed data to memory (even though the asm instruction mnemonics may appear visually to only write to the memory). Writing a byte or a word involves only writing, hence it uses the memory bandwidth (which is the main bottleneck on the current micros due to CPU running several times faster than the memory bus) much better. What I was thinking, regarding the incremental updates, would be a linked list (probably a doubly linked list to be able to insert & delete quickly at random point in the list), attached to each square containing a piece, and containing linked all attackers to that square (by linking either to the source square or to the attacker in the piece list, and continuing through the piece list). The attack list would be split into 2 sublists, as friendly attackers/defenders (of the same color) and the hostile attackers (of the opposite color). Since a square can be simultaneously attacked/defended from 8 sliding and 8 jumping sources, one would need space for 16 lists going from each square. If one keeps separate attack/defender sublists, each square would have 32 pointers (or 128 bytes for 4 byte pointers), so the whole board would take 8K. One would also have a counter board which would give for each square count of pointers active from that square at any given time (alternatively a 32-bit bitmask could be added to a square to indicate which of the 32 link fields are active, in that case each of the 16 pairs of pointers would corrspond to the predefined 8 sliding directions and 8 jumping outposts attacking this square). On the piece list (where the square pointers are pointing into) queen, knight and king would have 8 link fields (each field with Next & Previous pointer) since they can attack 8 pieces at once, thus they could be members of 8 different attack lists, while rook and bishop would have 4 link fields and pawns only 2 link fields. Thus, looking for the attackers to a given piece would involve following the list starting at the square of that piece, each pointer dereference brings in the next attacker, without any scans of empty squares. When a piece moves, one would start at the source square and follow the chain of attackers and update them, as appropriately, to either attack whatever was on the same diagonal or line or to take them out of the attack list if the're not sliding pieces or are now hitting the edge of the board. A new list would be built at the destination square, using a scan looking for attackers onto that previously empty square. If the destination was occupied and a capture occured, the new list would inherit the old links, with merely reversed head pointers for the attack & the defense sublists. So this method has the best performance when pursuing the sequence of captures, since the destination square lists are already there. I am curious if anyone had tried something along these lines, as sketched above, and what kind of performance were they able to get out of it?
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.