Author: Bas Hamstra
Date: 06:25:41 11/20/99
Go up one level in this thread
On November 19, 1999 at 22:48:42, Ratko V Tomic wrote: >> When a piece moves, all squares that are now "pseudo-unattacked" by the >> move I undo the attacks, by XORing them. Hi again Ratko! >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. Basically yes. I don't use a LeastBit[] array but the asm BSF instruction, which is faster. And no, the movegenerator alone will not be faster with this approach. But in a chess program in my opinion (apart from eval) 2 things are most important: 1. How to generate captures fast 2. How to generate all attacks to a square fast If you want to skip losing captures by a SEE, you must have all attacks from both colors to a given square for that. To be more precise: not only the attacks, but I *want* the pseudo attacks. Or else batteries (two rooks lined up) will be ignored. My movegen() isn't ultrafast, but the pseudoattacks are free! More than that: I have them sorting in the right order. To be honest: I *hoped* that this made a ultrafast movegenerator, at least for captures, but when it comes to the generator alone it appeared to be not the fastest way in the world. >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. Agreed. If I am not mistaken Bob Hyatt tried more or less what you described, but without too much success. KnightCap() does something like me, but for real attacks, in stead of peudo. It isn't extremely fast, I think, and hard to code. But most problematic is that you have *not* enough info for SEE, IE you can not see what is behind an attacking piece. >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. See above. It sounds good, and it can be done, and has been tried, but so far I know of none that made a significantly faster program this way. Which doesn't mean it isn't possible of course. >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? Ask Bob. Early versions of Crafty used this idea (though not the exact implementation maybe). But I suspect the make/unmake will be slower than mine. Regards, Bas Hamstra.
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.