Author: Vincent Diepeveen
Date: 13:59:02 08/30/03
Go up one level in this thread
On August 30, 2003 at 15:04:57, Peter Fendrich wrote: you m ean to say that there is hard proof from my posted datastructure + move generator that it is more than 2 times faster on generating, scanning (very important for forward pruning, mobility, activity, square control etcetera) than bitboards will deliver at any hardware (except alpha 21264 perhaps when you write in assembly for it, but let's ignore that processor). Knowing x86-64 is the future and what it can and cannot do and knowing that it speeds up bitboards quite some but not the factor 2 it is behind in speed, we have hard proof what is faster at 64 bits too. The bitboard technique is a combination of L2 cache techniques (something hardly fitting in L2 cache) with register techniques. DIEP's generator is L1 cache technique + register technique. A fast L1 cache favours my generator bigtime (which is what you arguably can call intel friendly as they got the fastest L1 caches). Trivially it is 2 times faster than bitboards and 2.5 to 4 times faster when more complex knowledge is put in evaluation. When attacks get considered in evaluation or move generation a lot, then it's over 5 times faster. Hyatt said that he doesn't need attacks in his program. That leaves still a factor 2. Thank you, Vincent >On August 30, 2003 at 14:37:44, Tord Romstad wrote: > >Well Tord, You have probably started one of most longwinded and infected threads >for a long time... :-) >I started to use bitboards, only becaues it's fun and not because I think it is >more efficient than other techniques. I'm quite convinced that a combination is >the best approach but I have no proof for that. > >>My program has reached the stage where it is so complicated and ugly that I >>no longer understand clearly how it works (it's rather miraculous that it >>works at all), and there are many parts of the code which I am afraid of >>touching because I am sure I will break something. Besides, the program >>is horribly slow, searching only about 120 kN/s on a PIV 2.4 GHz. > >If you're looking for non complicated code you're not longing for bitboartds! >I have no indications and have never seen any proofs of that bitboard techniques >are faster than others. > >>Because of this, I think it is time to throw away all the old code and >>start from scratch. Before I do this, I will consider replacing my >>data structures with something more efficient. >> >>Today, my board representation consists of a 256-byte array of squares >>(visualised as a 16x16 board with the real board in the left half of >>the middle 8 ranks) and a Phalanx-style piece list. At every node in >>the tree, I generate "attack tables" similar to those found in Rebel, >>Phalanx and Diep (the tables are not updated incrementally). >> >>I have never really liked bitboards, but because my next computer will >>almost certainly be a PowerMac G5, I am considering to give them a try. >>First, however, I have a few questions to the more experienced bitboard >>users: >> >>1. One of the things I dislike about bitboards (at least the modern >>approach with rotated bitboards) is that even very simple operations >>like generating moves seem to require either using huge lookup tables >>(like in Crafty without -DCOMPACT_ATTACKS) or writing some extremely >>complicated and unreadable code (like Crafty _with_ -DCOMPACT_ATTACKS). >>Is there a way to use rotated bitboards without having big tables, >>and still keeping the code short, clean and readable? > >As I said before, bitboards are not for making the program short and clean. When >you introduce bitboards you have to waste 10 times more time for debugging and >worry about things like cashe lines and other machine related issues. > >>2. Another problem with bitboards is that there is no obvious way to >>compute "weighted mobility". While it is trivial to compute the number >>of pseudo-legal moves for a piece with bitboards, this number is usually >>not very interesting (at least not in my program). In most cases, some >>squares are much more valuable to attack than others. Given a 64-byte >>array of weights, and a bitboard of squares attacked by a piece, is there >>a fast way to compute the "dot product"? I have browsed the archive >>and noticed that this question has been discussed numerous times before, >>but I have never seen a good answer (Bob has explained a lot of times >>how to do this on a Cray, which is not very useful to me). > >I don't think so but what is fast? OTOH you will get some very elegant solutions >for othere things like generating pawn moves, captures etc. > >>3. I also dislike the fact that bitboards are much too big to be used >>as indexes to lookup tables, and that extracting information from them >>is often difficult to do without looping through all the 1 bits. It is >>easy to compute a bitboard of all pieces which attack a given square, >>but in my evaluation I want to extract information about the number and >>types of attackers in a small and compact bitfield (which can be used >>as an index to a lookup table), while throwing away information about >>the locations of all the attackers. How do I achieve this with bitboards? > >I think that you have to "think bitboard" and adjust your ideas to it instead of >trying to adjust the bitboard techniques to your ideas. With bitboards you get >some real nice possibilities but also some drawbacks of course. > >/Peter >>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.