Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: BitBoard challenge to Ernst A. Heinz and bitboard fans - no moderation

Author: Carsten Kossendey

Date: 19:23:17 01/16/99

Go up one level in this thread


On January 16, 1999 at 14:37:49, Vincent Diepeveen wrote:

>On January 15, 1999 at 22:09:04, Robert Hyatt wrote:
>
>>On January 15, 1999 at 21:26:17, Vincent Diepeveen wrote:
>>
>>>On January 13, 1999 at 07:19:54, Ernst A. Heinz wrote:
>>>
>>>>On January 13, 1999 at 06:13:30, Vincent Diepeveen wrote:

[mega-snip]

>>>At a PII-450 diep generates 250k attacktables a second in the position
>>>after openingsposition+1.e4,e5 2.d4,d5
>>>
>>>I'm only using C code. Not a single assembler instruction is in my code,
>>>as far as i know your bitboards are written in C? In that case
>>>there is no unfair comparision.
>>>
>>>An attacktable is a table in my program of
>>>int attacktable [2][64];
>>>First i clean the attacktable, then i store for every piece all attacks.
>>>
>>>that includes
>>>  a) piece that attacks      (what square it is from)
>>>  b) number of attackers     (clear i guess)
>>>  c) kind of piece           (pawn,knight,bishop ...)
>>>
>>>I need this to evaluate in my program, as it evaluates also 'relationships'
>>>between pieces and mobility is also depending upon it.
>>>
>>>My mobility goes like this: i loop over all squares of a piece, including
>>>xray squares and then find out how important control over such a square is
>>>depending on all kind of chessknowlege where info from attacktable is
>>>used using lookup of attacktable[c][sq] where sq are all squares that
>>>need to be considered. And as i use this 'attacktable' info a lot,
>>>i therefore store it in this a simple way in [2][64] array.
>>>Every time i use something out of my attacktable i definitely not
>>>am gonna add all values of the different bitboards *just* to get the
>>>number of attackers. That would slow down my program *considerable*.
>>>
>>>Now a problem using attacktables with mobility is:
>>>if you do all squares at once (otherwise bitboards not rewarding),
>>>that is kind of tough, considering that values are different
>>>for every square. So where i simply count a+b+c, where probably
>>>a != b != c then you run into problems, as for a range of -50 to +50
>>>you need to do 101 bitboard counts.
>>>
>>
>>
>>I've already pointed out that this is false.  Here's how to do this _fast_ on
>>the cray:
>
>>first compute the bitmap for the squares a piece on "sq" attacks.  This produces
>>a set of zeros and ones.  Then take a static const array sqval[64] where you
>>have filled in the value of attacking each square.  IE values for e4 d5 and
>>so forth, and _every_ value can be different.
>
>>ON the cray, we use the vector load instruction, but from this sqval[] array
>>we only load the values with 1's set in the according bitmap.  We sum these
>>and we are done, and it takes roughly 20 clock cycles to get the first value
>
>The problem is that according bitmaps. If value can range from -50 to 50
>then you need to do this 101 times, because you need a bitcount for
>every value.

You don't quite seem to understand. You have a 64 bit quantity, and an array
with
64 integers (between -50 and 50, if you like). Then you say "for every 1 bit,
add
up the corresponding array entries" with a single instruction (or something
along
that line). No loop involved. You do this once, not 101 times.

>>from the sq array, and assuming you have 20 squares you attack, the entire
>>thing will complete in about 50 clock ticks _total_.
>>Not very inefficient.  So things you think are hard are actually trivial on the
>>right hardware...
>
>A rude way of mobility can be done quickly. NO doubt. Please don't talk
>about the cray. We're talking general audience here. General audience
>doesn't have a cray nor alpha 533 and also will not buy it.

The general audience should consider getting a PowerPC which offers the same
kind of vector processing, only that you're limited to 16 bytes at a time, so
you'll need four instructions for a whole bitboard.

[snip]

>I don't doubt we all generate that quickly. Actually in DIEP i generate
>15 million move generations a second after 1.e4,e5 2.d4,d5 at a PII-450

Nice number, but what are you talking about? 15 million calls to your move
generator(s), 15 million legal moves, or 15 million pseudo-legal moves?
And are we talking about captures, quiet moves, or both?  What does "generating
a move" mean to you? Just say this piece attacks that square or store all the
nasty info like what piece is captured and how this will affect the board state
(e.g. castling rights, ep square, attack tables ...)

Also just generating moves for the very same position over and over again is
kind
of silly. You could as well have your move generator check whether the current
position is the same you last generated moves for, and just return a pointer to
the previous result in that case. That will yield much more than 15 million
<whatever> ...

So why not take a position and calculate the tree size to some depth (a la
Crafty's
"perft")?

Also take note that bitboard based move generation works much better in
positions
where pieces can slide far.

>>>
>>>Assuming in all cases lossless code,
>
>This was my point. Your code is lossy to mine.
>
>>>Greetings,
>>>Vincent
>>>
>>>>=Ernst=
>>>
>>>Please guys don't moderate Ernst too tough, if you do, then i dunno
>>>what Heinz thinks of himselve.



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.