Author: Vincent Diepeveen
Date: 14:35:40 08/30/03
Go up one level in this thread
On August 30, 2003 at 17:07:47, Gerd Isenberg wrote:
>On August 30, 2003 at 14:37:44, Tord Romstad wrote:
>
>>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.
>>
>>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:
>
>
>Thinking bitboards takes some (hard) time, but you will don't regret it.
>Not for generating moves, but for eval patterns and abstraction level.
>Generating pattern is a rather loopless and uncondition task with botboards.
>Unconditional bitwise, arithmetic and shift operations with bitboards have most
>often a loop equivalent in other approaches.
>
>One possible weakness of bitboards is the "conversion" from bitboard metric to
>square index metric. If you have a particular square index "sq", the single
Wrong. The real problem of bitboards is that you have in a huge word of 8 bytes
just 1 bit of relevant information about a particular color at a particular
square.
So in todays chess software where knowledge is important and concentration of
knowledge about squares is important, bitboards need too much overhead to
evaluat for a pattern X just 1 square or pattern.
You need TOO MANY bitboards and to combine all of them using square metrics.
The classical way to detect a pattern is by doing a bunch of 'if then else'
around a certain pawn or queen to find a pattern.
Finding a pattern in bitboards is way way slower because you need to extract all
the bits from the different bitboards.
Even just doing a simple 'AND' won't do because you need to AND like 14
bitboards just like that.
If you try to do it branchless in bitboards you need to scan through *all* the
patterns, so that isn't a good idea either because i just need to scan through
Log n
of all the patterns as a simple IF can eliminate them.
the basic idea of bitboards is clearly written down by hyatt several times and
that is: "we want a rude estimation of the position quickly".
A few things you can do quickly with bitboards.
Do those quickly and never again say that writing knowledge in bitboards is fun.
It is horror & co, and besides that dead slow too.
>populated bitboard has the value of 2**sq == 1<<sq. Addition like sq+x is done
>by some shift. Wraps are handled by appopriate and before or after shifting.
>sq^x (e.g. for some morroring) in square metric is equivalent to rotate in
>bitboard metric.
>
>
>>
>>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?
>
>
>With G5 (how many 64-bit registers?) or Opteron in mind, you may have a closer
>look at Kogge-Stone-fill routines attack generation.
>It is very usefull to get disjoint directions wise attacks, e.g. obviously pawns
>left and right attacks, as well all 8 directions for sliders.
>These algotithms may be implemented for several directions as well as piecesets
>in parallel or interlaced, as long you have 64-bit registers free.
>
>http://peter.fendrich.net/Terra/Terra%20Help-1647.htm
>
>These simple file-fill routines are great to get a lot of pawn patterns, like
>backward, passers, isolanis, etc.:
>
>BitBoard fillUp(BitBoard bb)
>{
> bb |= (bb<<8);
> bb |= (bb<<16);
> bb |= (bb<<32);
> return bb;
>}
>
>BitBoard fillDown(BitBoard bb)
>{
> bb |= (bb>>8);
> bb |= (bb>>16);
> bb |= (bb>>32);
> return bb;
>}
>
>>
>>2. Another problem with bitboards is that there is no obvious way to
>>compute "weighted mobility".
>
>For center control, one may use three parallel popcounts.
>All squares (8*8), no boarder squares(6*6), and combined shifted extended center
>(4*4) and center (2*2). So center is weighted by 4, extended by 3, remaining
>none boarder by 2 and boarder squares by 1. Due to independent instruction
>scheduling, three (or four e.g. squares "near" king) interlaced popcounts are
>very fast, not much slower than a single one with a lot dependencies!
>
>>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"?
>
>The obvious approach is a "slow" bitscan loop, e.g.:
>
>BitBoard bb = ....;
>int score = 0;
>while (bb)
>{
> BitBoard lsb = bb & -bb; // isolate bit
> bb ^= lsb; // reset bit
> unsigned idx = (int)((lsb * deBruijn ) >> (64 - 6));
> score += table[idx];
>}
>
>e.g. with one of millions 64-bit deBruijns:
>const BitBoard deBruijn = 0x03f08c5392cd5dbd;
>
>But one should avoid or delay such loops,
>e.g. by unrolling and conditional write.
>
>> 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).
>>
>>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?
>
>There are other solutions. You may have sets of "tabu" squares, sets controlled
>by pawns, by light pieces, exclusivly by queen or king, etc. And sets of e.g.
>more than triple attacked, triple, double (may include xrays) and single
>attacks. This is fine for eval, considering enprised or hanging pieces, SEE and
>move sorting.
>
>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.