Author: Robert Hyatt
Date: 18:25:51 05/31/01
Go up one level in this thread
On May 31, 2001 at 18:49:16, Bas Hamstra wrote: >On May 31, 2001 at 17:01:44, Robert Hyatt wrote: > >>On May 31, 2001 at 10:47:27, Bas Hamstra wrote: >> >>>>I'm not a factor of 3 slower. That is your imagination working. Somethings >>>>are faster in bitmaps, some slower. You want to harp on the move generation. >>>>That is less than 10% of my execution time, so it doesn't count. Evaluation >>>>is very good in bitmaps. >>> >>>For most things, yes, but not everything. If you want to use AttacksTo info >>>heavily, like some tactical programs do, you have a problem doing that with >>>bitboards. You could do it either "on the fly" using a couple of dozens >>>AttacksTo()'s and end up with a *very* low nps. The alternative would be to >>>calculate AttackTo tables (or even keep them incrementally). Now that is a >>>problem with bitboards too. It *can* be done, of course, but as a result for >>>instance Crafty could then divide it's nps by 4 (if not more). >>> >>>(and remember I use bitboards myself) >> >> >>I used to incrementally update the attacks_to and attacks_from. It made my >>program not quite twice as slow, NPS-wise, once I used rotated bitmaps to do >>the updates. In fact, it was something on the order of 50-60% faster when I >>stopped the incremental update. But _if_ I wanted that information, I would >>certainly go back to doing it that way. I just happen to not like using that >>info in the evaluation. I did for a while and didn't like the result. After >>taking it out, getting rid of the incremental update was the next natural step. > >I suspect you have to get used to it, and not judge too quickly. There are >really strong programs (mostly non bitboard) exploiting it very well. The King >for sure. Maybe Hiarcs. Diep. Probably most of them slow ones. But anyway, I am >interested how you managed to do it. Suppose you move just a pawn. Now you have >to check the to and from squares, and see which sliders attack them. Ok, that's >doable. Then, for each slider, you have to recompute the map of attacked >squares, and *SLOWLY* pop the bits out one by one. First, you only recompute the map for one direction, the one the slider was blocked on by this pawn (that just moved). That goes very quickly with the rotated lookup. I don't remember the specifics any longer, but since so few attacks_to bits change, very few attacks_from bits change either. I did use a copy/make approach for this so that there was no unmake at all. > Bitboards are great when few >bits are set, but horrible if you have to pop out all the bits of the >queenattacks on an empty board. How did you manage to let nps NOT totally >collapse? Ok, for that pawnmove I can think of some shortcuts, but not for a >queenmove on an empty board...? And did you recompute with unmake, or read it >from memory? Read from memory. As far as the updates go, if you think about it, you only change part of things. MakeMove() was horribly large, because it absolutely did the minimum amount of work necessary to make a move and update _nothing_ but the bits that changed (I debugged with lots of asserts to be sure I never tried to set a bit that was already set nor clear a bit that was already zero. It wasn't horrible. I went nearly twice as fast after getting rid of the copy and make plus eliminating the incremental update. But then I lost somewhere else, such as asking "am I in check" which was free before, but now has a small computational cost... > >(In my case I calculated that when I would build them non-incrementally I would >get about 50k nps doing only material, where I normally do 150k full eval) > >Best regards, >Bas.
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.