Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Differences between 0x88 ,10x12 and Bitboards!?

Author: Robert Hyatt

Date: 17:09:40 11/19/02

Go up one level in this thread


On November 19, 2002 at 19:09:23, Vincent Diepeveen wrote:

>On November 19, 2002 at 15:48:57, Gerd Isenberg wrote:
>
>><snip
>>>
>>>If you agree with me that the focus in the future is on evaluation,
>>>it will not come as a surprise that more complex patterns get more
>>>crucial.
>>>
>>>Let me present you a simple example. suppose you are scanning the board
>>>for example for your king safety, mobility or whatever, for complex
>>>patterns to evaluate:
>>>
>>>We are now at square sq and want to know whether a complex pattern is
>>>happening. For example:
>>>
>>>if( sq >= 8 && board[sq-8] == bishop && board[sq-7] == rook && ...
>>>
>>>What's your bitboard equivalent here?
>>>
>>>snelbord is in the L1 cache of course. Let's not worry about L1 or L2
>>>caches here. Also let's not worry about that both in bitboards *and*
>>>non bitboards you can get rid of at least 1 compare here.
>>>
>>>AFAIK you need an array for each value sq-8 and sq-7 to lookup the
>>>mask needed for the bitboard to AND with.
>>>
>>>lemme give a shot out of the hand, writing compatible code
>>>(so not writing out black & white :
>>>
>>>So here the bitboard equivalent without caring that in both
>>>examples we can save out a CMP:
>>>
>>>if( sq >= 8 && (Bishops[side]&Mask[sq-8]) && (Rooks[side]&Mask[sq-7]) && ...
>>>
>>>Best regards,
>>>Vincent
>>
>>Yes Vincent, exactly.
>>
>>But the sequence is wrong and that's the point.
>>
>>Instead of a loop over all squares looking for one ore more properties, one get
>>a set of squares with the desired property, simply with a few bitwise
>>operations. Then you may traverse the found bits, if any.
>>
>>Bitboards work like SIMD.
>
>That is not possible with a big evaluation.
>
>That is like doing n operations at n elements instead of log n.
>
>Also another effect is there which is very intuitively true and very
>easy to understand for everyone except Bob.
>
>That's that with more difficult knowledge patterns, the bitboard
>pseudo code is too difficult to read and bugfix a month later.


Maybe it is harder for _you_.  That doesn't mean it is harder for _me_.

I don't have a bit of trouble looking at code written 4 years ago and changing
it as needed...  It reads quite well to me.

This is about experience with bitmaps.  I have it.  You don't.  So of _course_
you
are going to think it looks like gibberish.  Just as a C programmer will think
that
lisp looks like a stuck paren key.  However, lisp _does_ work.  As do bitmaps.
And
_plenty_ of us are using them.

BTW, macros also help make them more readable, if you know what a C macro
is..


>
>>Btw. instead of Mask[sq] you should use 1<<sq on 64 bit hardware. Often, if you
>
>SHL is too slow on P4 to use. 2 cycles. Array lookup might be faster
>than that.

Rarely.  In fact almost never.  Unless you use a newer xeon with L2 at core
speed.  And even
then it isn't so clear.  And if you are waiting on other memory reads, then that
becomes a
bottleneck where the shift is a computational task.



>
>>traverse bitboards, it's even not necesseray to have a bitindex of a singular
>>bitboard at all. The singular bitboard (bb & -bb) is fine to get attacks or
>>attacks from with Kogge-Stone of a particulare square. That saves even the
>>bsf-instruction.
>
>>But the advantage of Kogge-Stone is to avoid a loop totally, the routine may be
>>supplied with a set of multiple squares. If you want to know whether a white
>>rook may reach a set of squares in n moves, without get being captured...
>
>>Regards,
>>Gerd



This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.