Author: Tord Romstad
Date: 04:27:41 08/31/03
Go up one level in this thread
On August 30, 2003 at 22:29:56, Sune Fischer wrote: >On August 30, 2003 at 14:37:44, Tord Romstad wrote: > >I think you have found some good arguments against bitboards, >but all representations have some disadvantages. >Ie. in other schemes you must struggle to keep order on a piecelist, getting >things reproducable seems pretty difficult to me with this. I haven't noticed any such problems using a Phalanx-style piece list ... >But looking at different source codes, I think the big difference >is that bitboards use large tables and in return have relative few branches. >Processors and compilers get better in branch pridiction and they get more and >more cache. >Which factor eventually will dominate I can't say, but I believe the cache size >will only grow and it doesn't even seem to be a problem nowadays, so the table >sizes I don't personally worry about too much. Perhaps you are right. Like most people here, you have much more knowledge of hardware than I have. >What I like about bitboards is that you can work on the entire board with just >a few masks. > >As an example, say you have in your move generator a stage where you would like >to generate non-captures to squares not attacked by opponent pawns. > >This would require you only to AND the attack board for the given piece with: >~(occupied | opponent->PawnAttacks()) > >Something which is of course a constant and can be pulled out of the piece loop. > >For move generation, the advantage of bitboards lies not in the speed of which >it can add dumb pseudo legal moves to a list (who does this anyway?), but in the >way it enables you to generate classes of moves with minimal overhead. > >A second classic example, is if you want to know if there is a pawn on the 7th >rank. >With non-bitboards you can do a loop with branches, or if you enumerate your >pieces in power of two's, you could do something like: >if (Pawn & (pc[a7]|pc[b7]|pc[c7]|pc[d7]|pc[e7]|pc[f7]|pc[g7]|pc[h7])) Neither of these examples are very important to me. Generating classes of moves is not very interesting to me. If I recall correctly, I spend less than 2% of the processor time generating moves. Optimizing the program by generating moves in chunks would just complicate my program without giving a noticable speed gain. Concerning the second example, I can simply extract the pawns on the 7th rank from the pawn hash table, at hardly any cost. I have the impression that bitboards are mainly useful for doing rather simple things very quickly. Most of the canonical examples of operations which are fast and simple using bitboards (like generating only captures or detecting passed pawns) are relatively unimportant to me, because such operations consume just a negligible fraction of the processor time in a slow program like mine. Perhaps my impression is coloured by the fact that the only bitboard program I have studied for more than a couple of minutes is Crafty. Is there an open-source bitboard program with a more slow and complicated evaluation function (in particular, a more sophisticated king safety eval) somewhere? >Sure it saves branches, but using bitboards is just the ultimate evolution of >this. > >Another, IMHO, really interesting aspect of bitboards is the floodfiller >techniques. >There is a whole new area yet to explore here, and as far as I know they >have no equivalent in non-bitboard environments. This is entirely unknown territory for me. I hope to find the time to read about it some time soon. >I could go on and on, but I don't really believe that bitboards are way better >than anything else, nor do I think that they completely suck. >To me they are just the easiest and most fun to work with :) I am happy to see that you do not have any religious opinions regarding this subject. I was afraid this discussion would quickly degenerate to a pointless flamewar, but so far it doesn't seem to happen! 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.