Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vincent Diepeveen

Date: 11:56:11 11/19/02

Go up one level in this thread


On November 19, 2002 at 14:25:18, Gerd Isenberg wrote:

>On November 19, 2002 at 13:57:02, Vincent Diepeveen wrote:
>
>>On November 19, 2002 at 13:30:57, Christophe Theron wrote:
>>
>>>On November 19, 2002 at 13:15:09, Gerd Isenberg wrote:
>>>
>>>>On November 19, 2002 at 12:25:11, Gian-Carlo Pascutto wrote:
>>>>
>>>>>On November 19, 2002 at 11:35:24, Robert Hyatt wrote:
>>>>>
>>>>>>Bitboards have a bit of a performance advantage on 64 bit processors,
>>>>>
>>>>>Proof?
>>>>>
>>>>>--
>>>>>GCP
>>>>
>>>>Hi Gian-Carlo,
>>>>
>>>>I think that's evident. If the none bitboarders have to use implicite native
>>>>data-width of 64 bit integers, they have to transfer 32 additional zero bits
>>>>without any additional information for each integer access. Of course you will
>>>>pack some data, but all the local ints...
>>>>
>>>>So the information density for bitboarders grows with 64bit-architectures
>>>>relative to none bitboarders. That also effects register usage, and that's IMHO
>>>>more important. On x86-32bit architectures you can only hold three bitboards in
>>>>registers, and thats even most a hard task. Actually, if you have a local
>>>>routine with three bitboards and a few ints on the stack, there are a lot
>>>>register/memory moves. Simply the data-width doubles the number of bitboard
>>>>registers, not considered the increase in general purpose registers, or with
>>>>hammer the number of mmx- and 128-bit xmm registers.
>>>>
>>>>Whether a bitboard based program is stronger than a none bitboard program
>>>>depends obviuosly also on other things, but in principle :)
>>>>
>>>>Cheers,
>>>>Gerd
>>>
>>>
>>>
>>>You have just explained why the bitboarders are less handicapped on 64 bits
>>>machines.
>>>
>>>You have not explained why they are supposed to have "a bit of performance
>>>advantage on 64 bits processors".
>>>
>>>
>>>
>>>    Christophe
>>
>>Exactly,
>>
>>But more important is that they are not in the same league at 32 bits
>>processors with knowledge. As soon as they need more knowledge they
>>run into problems. My move generation in itself eats 0.6% of the system
>>time. My evaluation nearly all of it.
>>
>>Yet a crucial aspect of evaluating is scanning and that's something
>>where bitboards are handicapped with 1 or 2 exceptions (you can
>>quickly scan a rank or file for presence of a piece X). So at 64
>>bits CPUs a hybrid model is something which is possible but the
>>majority of the cases just having 1 bit available with bitboards
>>and needing an extra
>>array lookup to index all the different arrays for having the bit
>>set true, that's pretty slow.
>>
>>Yet if you keep your program dumb and fast, you don't suffer from
>>that lack of course and will never be able to realize it.
>>
>>In which case there is no advantage of course, because crafty is
>>at a McKinley like 1.5MLN nodes a second, whereas a program which
>>is equally weak tactical last so many plies and in qsearch (saving
>>out loads of system time which most stronger programs prefer to
>>spent there), to make it in non-bitboards, is easily going to
>>get the same number of nps with those blazing fast 6 instruction
>>bundles a clock.
>>
>>In a simple experiment of mine where i just did recaptures based
>>upon a single simplistic attacktable in qsearch (only generated
>>that attacktable at root in qsearch not the innernodes in qsearch),
>>i got at a P5-100 already blazingly fast. 200k nps initially. When
>>i then tried to search deeper it got down to 100-150k nps, depending
>>whether i tried to do less in qsearch or more.
>>
>>In all these cases bitboards is a major handicap at 32 bits processors
>>and at 64 bits processors the % you lose to bitboards versus non bitboards
>>is depending upon non-bitboards code in the search simply.
>>
>>Best regards,
>>Vincent
>
>Hi Vincent,
>
>May be there are different paradigms and/or thinking schemes. For me specially
>in eval, which takes about 70% of IsiChess including "mate at the glance",
>bitboards are great to define tactical and positional patterns. I fear if i
>switch to another approach, i'll have some difficulties, to define these
>patterns with other structures.
>
>There are algorithms that gain superproportional from 64-bit architectures, like
>flood-fill and Kogge-Stone. I can't imagine that you are not fascinated by the
>possibilities of these algos.
>
>Regards,
>Gerd

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



This page took 0.09 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.