Author: Gerd Isenberg
Date: 12:34:51 10/09/03
Go up one level in this thread
On October 09, 2003 at 09:37:43, Robert Hyatt wrote: >On October 09, 2003 at 06:25:54, Tord Romstad wrote: > >>On October 08, 2003 at 16:36:48, Robert Hyatt wrote: >> >>>On October 08, 2003 at 15:01:55, Tord Romstad wrote: >>>> >>>>People keeps claiming that, but all the bitboard code I have seen includes >>>>lots of loops (mostly loops through all the 1s in a bitboard). >>>> >>> >>>The point is this. (for loops). A bishop is on e4. It attacks a piece >>>at h7 and at c6. All other diagonal squares are empty. A bitboard program >>>that is generating captures (which is by far the most common case due to >>>the q-search) will go through a loop, but only _two_ iterations, one for >>>each capture. What about a program that doesn't use bitmaps? You will have to >>>traverse each diagonal until the end or hitting a blocker, in all 4 directions. >>> >>>So yes, both do loops, but one does _way_ fewer iterations. That is the >>>savings. >> >>But this advantage disappears when you are interested in *all* squares a >>piece attacks, not just the squares which happen to contain enemy pieces. >>In my evaluation function, I am almost always interested in doing operations >>for all the attacked squares. > >The question is, what are you doing with all the attacked squares? IE in >Cray Blitz I did a "qualitative mobility" calculation, which summed a bunch >of square's "usefulness" depending on whether the piece could reach them or >not. I didn't need to enumerate each square, I worked with the entire bitmap >as an "entity" and summed without enumerating. > > >> >>Generating captures without too many loops is not a problem for me anyway. >>My evaluation function does almost all the work. It does not just return >>a value, but also produces an ordered list of the hanging pieces for both >>sides, and the pieces which attack them (this information is used in the >>evaluation, move ordering, and for pruning and extension decisions). If I >>wanted, I could easily write an incremental capture generator which produced >>just one capture at the time (with reasonably good ordering), without having >>to loop through a lot of squares. So far I haven't bothered to do this, >>because my program spends just a tiny fraction of its time on generating >>captures. > > >The point is, of course, how you find the hanging pieces. You can loop over >all the pieces, checking to see if they are attacked, but you still loop over >all of them. With bitmaps, you immediately reduce that to the set of pieces >that are attacked at all. > >It just takes a different way of thinking. And it is better to think in >terms of "sets" rather than individual things. IMHO the most important feature, even if most sets have low popcount. Less loops in general, but sometimes more loops over disjoint sets with small unconditional bodies instead of one with a lot of conditions in it. With todays and future processors with very smart branch prediction heuristics, the latter may not that bad as in the past. The disadvantage of more less populated loops with disjoint sets is the probably wrong predicted branch, if the traversed set becomes zero very soon in the repeat condition. I guess that's one justifiable point of Vincent's bitboard criticism. Aggressive unconditional unrolling may be a solution - and of course trying to avoid bitboard traversal at all, e.g. with some weighted "parallel" popcounts. Another main feature of bitboards is IMO to gain more from parallel work. How many independent instructions may AMD64, G5, Itanium etc. may execute in parallel with so much pipes, execution units and register files? Of course kogge stone and other fill stuff in mind ;-) Gerd > > > >> >>Tord
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.