Author: Roberto Waldteufel
Date: 17:02:44 10/20/98
Go up one level in this thread
On October 20, 1998 at 18:13:24, Robert Hyatt wrote: >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... Hi Bob, Yes please - I would be very interested indeed. My own efforts at eliminating the attack maps have always been slower, but I probably was doing something wrong. It would be great to save all that updating work, especially the attack-to tables, which, at least for my implementation, take more effort than the attack-from tables. But if I could get by with neither, the move making/unmaking would be a lot faster. As you seem to have cracked it, I would be fascinated to read how you did it, and perhaps to see if I can improve my search by following your example. If I can make it faster without the attack tables than it presently runs with them, I'll post my results. My e-mail address is RWaldteufe@aol.com (you have to leave the last letter off the end of my name- AOL don't allow enough characters!) Best wishes, Roberto
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.