Author: Robert Hyatt
Date: 15:13:24 10/20/98
Go up one level in this thread
On October 20, 1998 at 13:02:59, Roberto Waldteufel wrote: >Hi all > >I have been wodering about ways to improve the efficiency of my search engine, >and in particular the utility of the data structures I use. At present my >program uses a bitboard representation for everything possible, and I maintain >two arrays of 64 bitboards each to indicate attacks from and to each square, >very much along the lines of Chess 4.x of earlier days. My search incrementally >updates these attack tables as moves are made/unmade, and the code is very >efficient in updating the attack from tables, but requires a loop to update the >attack-to tables, which makes me wonder if I could do without the attack-to >tables. However, the attack-to tables seem to make up for their overhead in the >following ways: > >1) they allow an efficient MVV/LVA order generation of all capture moves. This >is important because I don't generate a list of moves (some of which might never >be searched if I get a cut-off), but try instead to generate only one move at a >time without compromising the ordering too much. > >2) they allow instant detection of check > >3) They are used heavily by the evaluation function to determine the >safety/exposure of the kings > >I would be interested to know how others tackle these issues, especially if they >do not use attack from and attack to tables like I do. I know Crafty uses >rotated bitboards, but I am not quite sure if this means that moves are >generated directly from the (rotated) bitboards representing the *locations* of >the pieces or from other bitboards like attack tables for instance. If the moves >are generated directly from location bitboards, that reduces the overhead of >actually making/unmaking the moves, but then come other overhead issues >regarding move generation efficiency (perhaps this can be done very fast with >rotated bitboards for location only?) , check detection, king safety, etc. > >Thanks in advance for any comments, > >Roberto The main idea of rotated bitmaps is that it eliminates that incremental updating of the attack bitmaps as pieces are moved. I've written a rough draft of a paper for the ICCA perhaps, and can certainly email you a copy if you'd like to read it... remember it is *rough*... but it gives lots of precise technical implementation details...
This page took 0.01 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.