How can I implement a Bitboard in VB.NET?

Question

My Questions are:

Is is possible to implement a bitboard in vb.net?
Any Tutorial/Reference to do bitboard in VB?

C# answers are acceptable because it's not that hard to translate.

Hm, nice. Didn't know about them. But it's not hard coming up with an implementation given the description on the Wikipedia page. — Joey, Mar 09 '12 at 14:11
You'll need to use logical bitwise operators, see this for example: [Absolute Beginner's Guide to Bit Shifting?](http://stackoverflow.com/questions/141525/absolute-beginners-guide-to-bit-shifting) — AVIDeveloper, Mar 09 '12 at 14:22

HTTP 410 · Answer 1 · 2012-03-17T12:49:00.600

To implement a bitboard in VB (or C#), use System.UInt64. This can hold 64 bits, 1 for each square of the chess board. This value type lends itself to many fast bitwise operations. I don't advise using BitArray as recommended by another poster, as it is simply too slow. One of the basic requirements for any decent chess engine is speed.

To answer your second question, this is a good bitboard tutorial.

Here are some examples from my own C# chess engine. As you can see from the code, it can take a while to wrap your head around using bitboards, but they are typically very fast, especially for position evaluation.

Example 1 - Bitboard definition:

internal UInt64 WhiteKing;
internal UInt64 WhiteQueens;
internal UInt64 WhiteRooks;
internal UInt64 WhiteBishops;
internal UInt64 WhiteKnights;
internal UInt64 WhitePawns;
internal UInt64 WhitePieces;

Example 2 - Bitboard initialisation:

// Initialise piece bitboards using square contents.
private void InitPieceBitboards()
{
    this.WhiteKing = 0; 
    this.WhiteQueens = 0; 
    this.WhiteRooks = 0; 
    this.WhiteBishops = 0; 
    this.WhiteKnights = 0; 
    this.WhitePawns = 0;

    for (Int16 i = 0; i < 64; i++)
    {
        if (this.Squares[i] == Constants.WHITE_KING)
        {
            this.WhiteKing = this.WhiteKing | Constants.BITSET[i];
        }
        if (this.Squares[i] == Constants.WHITE_QUEEN)
        {
            this.WhiteQueens = this.WhiteQueens | Constants.BITSET[i];
        } 
        if (this.Squares[i] == Constants.WHITE_ROOK) 
        {
            this.WhiteRooks = this.WhiteRooks | Constants.BITSET[i];
        }
        if (this.Squares[i] == Constants.WHITE_BISHOP) 
        {
            this.WhiteBishops = this.WhiteBishops | Constants.BITSET[i];
        }
        if (this.Squares[i] == Constants.WHITE_KNIGHT) 
        {
            this.WhiteKnights = this.WhiteKnights | Constants.BITSET[i];
        }
        if (this.Squares[i] == Constants.WHITE_PAWN) 
        {
            this.WhitePawns = this.WhitePawns | Constants.BITSET[i];
        }

        this.WhitePieces = this.WhiteKing | this.WhiteQueens | 
                           this.WhiteRooks | this.WhiteBishops | 
                           this.WhiteKnights | this.WhitePawns;
        this.BlackPieces = this.BlackKing | this.BlackQueens | 
                           this.BlackRooks | this.BlackBishops | 
                           this.BlackKnights | this.BlackPawns;
        this.SquaresOccupied = this.WhitePieces | this.BlackPieces;
    }
}

Example 3 - Move generation:

// We can't capture one of our own pieces.
eligibleSquares = ~this.WhitePieces;

// Generate moves for white knights.
remainingKnights = this.WhiteKnights;

// Generate the moves for each knight...
while (remainingKnights != 0)
{
    squareFrom = BitOps.BitScanForward(remainingKnights);
    generatedMoves = Constants.ATTACKS_KNIGHT[squareFrom] & eligibleSquares;
    while (generatedMoves != 0)
    {
        squareTo = BitOps.BitScanForward(generatedMoves);
        moveList.Add(new Move(squareFrom, squareTo, Constants.WHITE_KNIGHT, 
                              this.Squares[squareTo], Constants.EMPTY));
        generatedMoves ^= Constants.BITSET[squareTo];
    }
    // Finished with this knight - move on to the next one.
    remainingKnights ^= Constants.BITSET[squareFrom];
}

Example 4 - Calculate material score:

// Material score from scratch, in centipawns from White's perspective.
internal static Int32 ScoreMaterial(Board position)
{
    return BitOps.BitCountWegner(position.WhitePawns)   * Constants.VALUE_PAWN +
           BitOps.BitCountWegner(position.WhiteKnights) * Constants.VALUE_KNIGHT +
           BitOps.BitCountWegner(position.WhiteBishops) * Constants.VALUE_BISHOP +
           BitOps.BitCountWegner(position.WhiteRooks)   * Constants.VALUE_ROOK   +
           BitOps.BitCountWegner(position.WhiteQueens)  * Constants.VALUE_QUEEN  -
           BitOps.BitCountWegner(position.BlackPawns)   * Constants.VALUE_PAWN   -
           BitOps.BitCountWegner(position.BlackKnights) * Constants.VALUE_KNIGHT -
           BitOps.BitCountWegner(position.BlackBishops) * Constants.VALUE_BISHOP -
           BitOps.BitCountWegner(position.BlackRooks)   * Constants.VALUE_ROOK   -
           BitOps.BitCountWegner(position.BlackQueens)  * Constants.VALUE_QUEEN;
}

Example 5 - Calculating piece mobility:

// Calculate mobility score for white knights.
remainingPieces = position.WhiteKnights;
while (remainingPieces != 0)
{
    squareFrom = BitOps.BitScanForward(remainingPieces);
    mobilityKnight += BitOps.BitCountWegner(Constants.ATTACKS_KNIGHT[squareFrom]
                                            & unoccupiedSquares);
    remainingPieces ^= Constants.BITSET[squareFrom];
 }

Hey @RoadWarrior, this is very interesting piece of code you have posted, have you published full source code anywhere? — Lu4, Aug 29 '13 at 13:21
@Lu4: Amaia is currently a private chess program, so the full source code isn't available. — HTTP 410, Aug 29 '13 at 16:41

Meta-Knight · Accepted Answer · 2012-03-09T19:36:44.453

4

From the Wikipedia article, a bitboard seems to be a simple array of bits. There is a class in .NET called BitArray, with methods to perform bitwise operations.

For example, a bitboard for white rook positions could be declared like this:

'Create bit array to store white rooks
Dim whiteRooks As New BitArray(64)

'Set white rooks at initial position
whiteRooks(0) = True 'Corresponds to A1 on chess board
whiteRooks(56) = True 'Corresponds to H1 on chess board

edited Mar 09 '12 at 19:36

answered Mar 09 '12 at 14:20

Meta-Knight

17,626
1
48
58

1

The whole point of bitboards in chess is the availability and speed of certain operations. For both of these aspects, a BitArray is significantly inferior to a simple UInt64. I will shortly add an answer with some examples. – HTTP 410 Mar 16 '12 at 11:16
Agree with RoadWarrior above. BitArray might be a good option for extensibility reasons which doesn't apply to chess as there will always be 64 squares. More importantly however, most binary operations involving UInt64's will be done in single CPU cycle on x64 architecture, something I doubt BitArray guarantees. – bytefire May 31 '13 at 13:28

score 0 · Answer 3 · edited May 23 '17 at 12:33

0

There have been a few other posts on here about this that have some useful information in the answers, hope they help.

How hard is it to implement a chess engine?

Chess Optimizations

edited May 23 '17 at 12:33

Community

1
1

answered Mar 09 '12 at 14:15

GrandMasterFlush

6,269
19
81
104

i'll try to apply the first link later.. i have to go this time – jasperagrante Mar 09 '12 at 14:20

score 0 · Answer 4 · answered Mar 09 '12 at 14:19

0

How about ...

Dim mArray(8,8) As Boolean

Substitute the Boolean for your own class or structure and extend the functionalty to your requirements.

answered Mar 09 '12 at 14:19

Jodrell

34,946
5
87
124

score 0 · Answer 5 · answered Mar 09 '12 at 15:20

Another option, if you don't want to use arrays, is to simply create a class/struct that contains the board or state in however many "sectors" you want to specify. For example, you can specify 4 longs to represent a 128x128 board, with each long representing one "sector" (assuming 32 bit processor). Then, all you have to do is override the Equals method (or == operator) to run a straight comparison to check for equality of each "section", IE this.Quadrant1 == that.Quadrant1.

Ultimately, the whole concept of a bitboard is that you're using the bits of the datatype itself to represent position/state of your environment (int = 32bits = 32 positions, long = 64bits = 64 positions, etc). For numeric value types, that means you can easily do a straight equality comparison (x == y) to see if the bits are equal. This also makes checking for valid moves incredibly easy, as it only requires shifting the bit X number of positions to represent a move, and do a bitwise & against the opponents board.

Pawns, for example, can move one space "up" (relative to their board), two if they haven't moved yet, or can capture. So to check for valid moves, you would shift the pawns position 8 (one space), 16 (two spaces, check if hasn't moved yet first), or 7/9 (capture). For one or two space moves, you must do a bitwise & on both your board and the opponents board for the new "position" and check if it's greater than 0 (indicating someone occupies the space, so invalid move). For the capture move, you only check your opponents board and allow the move only if the resulting & is greater than 0. For two spaces, you'd first have to do a bitwise comparison on the initial pawn "row" (255 << 8 for white, 255 << 48 for black) with the pawn in question to see if it is possible. If you're creating objects for every chess piece, you can simply check a boolean on the Pawn object itself indicating whether it has already moved or not.

One last thing to consider when using the bitboard is whether or not you are using signed values (at least in .NET). This is important because if the negative bit is set on a signed value, this negative bit will propogate on a right shift (meaning it will introduce as many 1's in the value as the number you shift by). Definitely consider using unsigned value types in this situation, or else you will get some funky results.

How can I implement a Bitboard in VB.NET?

5 Answers5