Author: Robert Hyatt
Date: 08:01:46 01/15/04
Go up one level in this thread
On January 15, 2004 at 08:29:44, martin fierz wrote: >On January 14, 2004 at 23:20:24, Robert Hyatt wrote: > >>On January 14, 2004 at 21:38:08, Federico Corigliano wrote: >> >>>Hi to all >>> >>>In my engine I use some bitboards, but nothing about rotated bitboards for >>>bishop, rooks and queen moves. >>> >>>What chess sources or web pages can you recommend me? >>> >>>One answer can be Crafty. Seems to be a little difficult to understand but I >>>don't tried yet :-) >>> >>>Greetings, >>>Federico >> >> >>go to >> >>www.cis.uab.edu/info/faculty/hyatt/hyatt.html >> >>go down about 2/3 and look for "online reports". Click that, then click >>the link for rotated bitmaps and read away. :) > >bob, i have i question about this: how much faster are rotated bitboards than >"normal" bitboards? my program uses bitboards, but i compute attacks of sliders >by looping over the board. can you give any kind of estimate of how much faster >you are by using rotated bitboards for attack generation (i don't mean the >overall program speed)? i couldn't find that in the paper... > That is really a good question, and unfortunately I don't have an answer. The reason I didn't address that is that I could not do it scientifically and chose to simply "pass". IE the right way to do the comparison is to pick the "best" non-rotated implementation and compare it to the "best" rotated implementation. First, I am pretty sure my old non-rotated approach was not optimal, in that Joel Rivat and I used to compare notes all the time as I got him interested in bitmaps and he decided to write his own bitmap program (ChessGuru, France). He eventually ended up without having tried rotated bitmaps, yet his speed was (on equal hardware) only somewhat slower than mine. I don't remember the exact number as that was a long while back. However, going to "second" (first is above) I am not sure that my current implementation is "optimal" either. So even if I did a comparison, I'm not sure it would be valid. All I can say with any authority is that I did it both ways, ie non-rotated and later on rotated, and the speed difference was very significant for me. However, my non-rotated approach did all the incremental attacks_to[] and attacks_from[] stuff as well, while my current approach doesn't incrementally do both. I believe that so long as the attack table lookups don't kill cache, rotated will always be faster, since it is just table lookups. But for machines with very small cache (IE old original pentium had 32kb for example) the tables were way more expensive than doing many more computational instructions to compute the bitmaps directly. Mark wrote the compact_attacks stuff years ago. I recently noticed on the opteron that with the larger L2 cache of today, compact_attacks was no longer faster, and actually was costing a little in terms of speed. I removed it, and then made the non-compact_attacks tables smaller for a bit further improvement. Right now, I am running Crafty with three ASM functions, PopCnt(), FirstOne() and LastOne(). And it is _still_ faster than it was a month ago (only a couple of percent, but the movgen stuff is much easier to understand once again.) My rambling point is that your question might not be easy to answer. Rotated bitmaps certainly simplify attack generation as this turns into two or four table lookups (two for bishops/rooks, four for queens) which is very simple in instruction count. However, MakeMove() becomes more complex since there are now three extra occupied_squares bitmaps (rotated in three different angles) to update. It would be an interesting question to actually answer, of course. Unfortunately I don't particularly like guessing, so all I can offer is a "seat of the pants" theory that rotated bitmaps are faster. But I can't say by how much, as that seems to be very hardware dependent. Sorry I can't be more specific. I could say "they are faster and here is a 'proof'" but I'll leave that to others since we already know that bitmaps "suck". :) >cheers > martin
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.