Author: Steffan Westcott
Date: 17:09:14 11/19/02
Go up one level in this thread
Vincent,
As Gerd points out, an advantage of the bitboard representation is the inherent
parallel computation. It is somewhat ironic that you perceive complex pattern
recognition as a weakness, as that's where bitboards can be very powerful, in my
opinion.
Let's take your simple example and see some actual code...
> 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?
>
> [snip]
>
> 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]) && ...
No, that's not the best approach when using bitboards. For this particular
example, much better is to find all instances of the pattern at once, like this:
///////////////////////////////////////////////////////////////////////////
typedef unsigned __int64 BitBoard;
// Uses this ordering for bits <->squares
//
// 56 57 58 59 60 61 62 63
// 48 49 50 51 52 53 54 55
// 40 41 42 43 44 45 46 47
// 32 33 34 35 36 37 38 39
// 24 25 26 27 28 29 30 31
// 16 17 18 19 20 21 22 23
// 8 9 10 11 12 13 14 15
// 0 1 2 3 4 5 6 7
BitBoard ShiftRight (BitBoard b) { return (b<<1) & 0xfefefefefefefefe; }
BitBoard ShiftLeft (BitBoard b) { return (b>>1) & 0x7f7f7f7f7f7f7f7f; }
BitBoard ShiftUp (BitBoard b) { return b<<8; }
BitBoard ShiftDown (BitBoard b) { return b>>8; }
BitBoard ShiftUpRight (BitBoard b) { return (b<<9) & 0xfefefefefefefefe; }
BitBoard ShiftUpLeft (BitBoard b) { return (b<<7) & 0x7f7f7f7f7f7f7f7f; }
BitBoard ShiftDownRight(BitBoard b) { return (b>>7) & 0xfefefefefefefefe; }
BitBoard ShiftDownLeft (BitBoard b) { return (b>>9) & 0x7f7f7f7f7f7f7f7f; }
///////////////////////////////////////////////////////////////////////////
BitBoard Vincents_pattern =
ShiftUp(ShiftLeft(Rooks[side]) & Bishops[side]);
///////////////////////////////////////////////////////////////////////////
Here, the result is a bitboard with a set bit for every pattern match on the
whole board. For a machine which manipulates 64-bit quantities natively, it
includes 2 bitwise ANDs (&) and 2 shifts (>> and <<). In your non-bitboard code,
ignoring the (sq >= 8) term, your _best_ case is 56 compares for the whole
board, when the subexpression (board[sq-8] == bishop) is always zero ie. no
bishops on the board.
We see here where the choice of board representation makes a fundamental
difference to the design of the surrounding engine. In the case of bitboards,
position feature/pattern matching is best done on the whole board at once ie. a
parallel method, which results in a bitwise expression. For other
representations, position feature/pattern matching is probably done whilst
iterating (looping) over collections (squares, ranks/files/diagonals, pieces,
etc) ie. a serial method, which results in selection of code execution path(s).
In your example, the serial iterator is sq.
Complex patterns can be decomposed into simpler patterns, many of which are
common (shared by the parent complex patterns). For bitboards, this manifests as
common subexpressions, which can be conveniently stored and retrieved during
evaluation. For other representations, it manifests as common program sequences,
where convenient opportunities to optimise away the repeated code may be less
clear.
I do not say here which representation is 'better'. My main assertion in this
post is that for effective use of bitboards, a parallel evaluation of position
features is usually better than a serial evaluation.
Cheers,
Steffan
This page took 0.01 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.