Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: To bitboard or not to bitboard?

Author: Gerd Isenberg

Date: 15:44:22 08/30/03

Go up one level in this thread


On August 30, 2003 at 17:35:40, Vincent Diepeveen wrote:

>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.

But on the other hand the popularty of a bitboard don't cares - it simply avoid
loops if more bits are set, e.g. to get a set of squares, pieces of same kind
may reach in 2 (or n) moves. A lot of my bitboards have more bits set than one.

>
>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.
>

Your general point is, that it is better to have a bunch of easy to predict
conditional jumps inside a loop, rather than more disjoint less populated loops,
with small unconditional bodies, but where the while-condition breaks quickly
with missprediction. I do have respect to this point and do consider it.

Anyway, even BTB is a limited ressource.
There are pattern where bitboard preselection makes sense.
Each "and" outside a loop avoids an "if" inside a loop.
Sometimes it makes even sense to traverse final bitboards by serializing them
into a stream of square metrics - and to handle these squares in your
"classical" way with further "if then elses".

>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.
>

A lot - and thanks to the set theory, more elegant and more effiecient than
other approaches.

>Do those quickly and never again say that writing knowledge in bitboards is fun.
>
>It is horror & co, and besides that dead slow too.

hehe, i guess set theory wasn't your favourite school subject?
Maybe as a strong chessplayer, you concentrate on a single property of a
particular square, rather than looking for property sets of squares.

Gerd

>
<snip>



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.