[graham_ashe]

I need some information. How does one go about setting up a 64-bit bitboard (for chess) in VB6 and comparing it against another bitboard? What kind of variable needs to be used to store the bitboard and how exactly could I take it apart bit by bit for comparison purposes? A simple example of actual code would be a great help. Thanks in advance.

[passel]

I'm not planning on trying to set up bitboards, but from the wikipedia description I would think that you would use, in VB6, a pair of Longs (32-bits each) to represent the 64-bit board. You would need a set of these for piece type and color. You might need several for targeted areas of the board, or perhaps those would be generated on the fly.
You would probably want to set up a few functions to implement bit set, clear and test functions, using an array of 32 preset masks with a single bit set in each bit position. You would normally use the And, Or and Not binary operations, and possibly XOR.
Refer to the Bits, Bytes and Bases tutorial.
A search might find other bit access code.

As for the logic behind using the bitboards in evaluating chessboard positions, I would think there is a fair amount of reading to do, probably whole books on it. Not something that could be discussed effectively in detail on a forum.

[graham_ashe]

Originally Posted by passel

I'm not planning on trying to set up bitboards, but from the wikipedia description I would think that you would use, in VB6, a pair of Longs (32-bits each) to represent the 64-bit board. You would need a set of these for piece type and color. You might need several for targeted areas of the board, or perhaps those would be generated on the fly.
You would probably want to set up a few functions to implement bit set, clear and test functions, using an array of 32 preset masks with a single bit set in each bit position. You would normally use the And, Or and Not binary operations, and possibly XOR.
Refer to the Bits, Bytes and Bases tutorial.
A search might find other bit access code.

As for the logic behind using the bitboards in evaluating chessboard positions, I would think there is a fair amount of reading to do, probably whole books on it. Not something that could be discussed effectively in detail on a forum.

I'm quite familiar with the logic of bitboards. Unfortunately, much more time is wasted trying to figure out the VB6 syntax for what I need to do. That link looks useful. I'll go through that carefully. All I need really is a very simple example (declaration and actual method of comparison for the 64 bits). I can usually take it from there. Thanks for the information, though.

[passel]

Well, since there is not a native 64-bit type in VB that can be used for Logical operations you would have to create something. I know there are some hugh bit size examples on the board and they might be tailored to handle just 64 bits (one of the later threads). I haven't played with them so don't know how simply they would scale down. The advantage is that some of them are already designed to be used as a class object.

The following is a quick, non-class example, of using two Longs to get 64 bits, as I stated earlier. I just spent a few minutes, so it only shows the type declaration, a set sub, an And function, and a Disp (print) function, that only displays Hex for convenience. I guess if that can get you started, then so be it. This would seem to be an ideal case for creating a class module to handle these 64 bit types. I haven't coded any VB classes myself, so probably won't bother to at this point.

Option Explicit
Private Type Int64Type
  low As Long
  high As Long
End Type

Private Function Int64Set(high As Long, low As Long) As Int64Type
  Int64Set.low = low
  Int64Set.high = high
End Function

Private Function Int64And(a As Int64Type, b As Int64Type) As Int64Type
  Int64And.low = a.low And b.low
  Int64And.high = a.high And b.high
End Function

Private Function Int64Disp(a As Int64Type) As String
  Int64Disp = Hex$(a.high) & Right$("00000000" & Hex$(a.low), 8)
End Function

Private Sub Command1_Click()
  Dim a As Int64Type
  Dim b As Int64Type
  a = Int64Set(&H8000FF00, &HFF00000F)
  b = Int64Set(&H70003200, &H12333322)
  Debug.Print Int64Disp(Int64And(a, b))  'should print 320012000002
End Sub

[Rockoon]

The system Passel is demonstrating is the way to go...

Unfortunately, some of the bitboard "tricks" will become difficult under this system.. but there is no good solution when you are restricted to 32-bit variables and no carry flag.

[Rockoon]

You might want to look at the sourcecode for the chess engine named Crafty, which is freely available from the author Robert Hyatt

He also has some technical papers available here and some of them relate to bitboards.

[graham_ashe]

But how does one actually represent (in VB6) - let's just say one rank of the chessboard as 8 bits in the form of something like "00001111" and then "AND" that with something like "11111000" to know that the fifth bit represents a 'clash' (i.e 1 AND 1) between two pieces? Can this be done in any meaningful way? Is there a way to take apart the 8 bits one by one and somehow identify that the 5th bit is where the clash occurs?

[passel]

Sure. I'm not sure about the definition of "meaningful way".

Option Explicit
Private Type Int64Type
  low As Long
  high As Long
End Type

Private Function Int64Set(high As Long, low As Long) As Int64Type
  Int64Set.low = low
  Int64Set.high = high
End Function

Private Function Int64And(a As Int64Type, b As Int64Type) As Int64Type
  Int64And.low = a.low And b.low
  Int64And.high = a.high And b.high
End Function

Private Function Int64Disp(a As Int64Type) As String
  Int64Disp = Hex$(a.high) & Right$("00000000" & Hex$(a.low), 8)
End Function

Private Function Int64NotZero(a As Int64Type) As Boolean
  Int64NotZero = a.high <> 0 Or a.low <> 0
End Function

Private Sub Command1_Click()
  Dim a As Int64Type
  Dim b As Int64Type
  Dim c As Int64Type
  
  a = Int64Set(&H0&, &HF&)   '00001111' in the lowest rank
  b = Int64Set(&H0&, &HF8&)  '11111000' in the lowest rank
  c = Int64And(a, b)         '00001000' Result of the AND, in the lowest rank
  If Int64NotZero(c) Then
    Debug.Print "We have a clash"
  End If
End Sub

In the above, a and b are two bitboards with bits set in one rank of the board, as you've specified. c is the result of ANDing the two boards, and since the result is not zero, you have a 'clash', and which bits clash is in c.
How you use that information is the part I don't know (and don't feel like researching). Do you loop through the bits and test each one to find the clash (or clashes as there could be more than one bit set).

I assume, as I stated earlier, that you need to decide what functions are required to use bitboards (and you say your quite familiar with the logic of bitboards), and write those functions. As a minimum, I guessed you would need bit set, bit test, And, Or, etc.
But you might need higher functions like accessing by rank or file, shifts, rotates, etc.

Do you have a list of bitboard functions you expect to use and need to implement?

[graham_ashe]

The bitboard concept is pretty straightforward. For example, I can have a bitboard (64 bits) with all the possible moves for the white queen set to '1' and those not possible set to '0'. Similarly, I can have another bitboard (64 bits) for the black king with a '1' set for its location on the board and all other bits set to '0'. By 'AND-ing' the two bitboards, I can easily tell if the black king is being attacked by the white queen. Conceptually, it's pretty easy. Syntax is another story entirely. I suppose for simple 'yes/no' type board situations (like the preceding example), we don't need to actually locate which bit causes the clash, as you mentioned. Then again, knowing what the bit sequence is going to be in advance is not the same as automatically generating, storing and converting it to base-16 (for different pieces), which is another problem.

Personally, I'm thinking about using the traditional single-dimension array approach to represent the chessboard combined with maybe partial bitboards where a quick 'yes/no' answer might be needed. The program I'm writing won't actually play a full game of chess but instead does some specific analysis that involves tree-searching of a limited depth. That unfortunately, requires a functional chess-playing architecture all the same. You've actually been quite a big help. Thanks.

[passel]

Well, I understand the purpose of the bitboards, just not what functions you would want to help implement them.
For instance, as you said, each time the queen of one player was moved, then you would want to update a bitboard of the possible moves that queen could make.
So a high level function would be UpdateQueenMoves, and it would except the possition of the queen by rank and file. It might invoke other highlevel functions like the ClearBoard function, and then the SetAllBitsInRank, SetAllBitsInFile, SetAllBitsInDiagonals functions etc. You would have similar functions for other pieces. And there may be high level combination compare routines that I'm not aware of.

[graham_ashe]

Originally Posted by passel

Well, I understand the purpose of the bitboards, just not what functions you would want to help implement them.
For instance, as you said, each time the queen of one player was moved, then you would want to update a bitboard of the possible moves that queen could make.
So a high level function would be UpdateQueenMoves, and it would except the possition of the queen by rank and file. It might invoke other highlevel functions like the ClearBoard function, and then the SetAllBitsInRank, SetAllBitsInFile, SetAllBitsInDiagonals functions etc. You would have similar functions for other pieces. And there may be high level combination compare routines that I'm not aware of.

One of the main functions would have to be how to automatically 'create' a bit sequence and store it in a variable for use with bitwise operators. I'm not sure of the syntax needed to create a bit sequence. It seems as if you'd have to put them in an array to make the necessary 'switches' (to 0 or 1) and then line up the elements of that array somehow to form a bit sequence capable of being stored in a variable. Is this even possible? Only then could it be converted to base-16 as in your example.

[passel]

I'm not sure if I follow about automatically creating a bit sequence. It wouldn't be automatic, you have to code it.
The purpose of using base-16 is that it is human friendly way to look at binary numbers. The binary numbers map directly to base-4, 8, or 16 (or higher powers of 2) without involving math. VB supports Octal &O77 (that is the letter o) and Hexadecimal literals &HFF. Octal digits represent groups of 3 bits, Hexadecimal groups of 4 bits.
So you can map a binary number to hex, or hex to binary fairly easily in your head as you write the code.

Also, as stated earlier you would write code that allowed you to set and clear and test bits, either by linear index (0 to 63), or by rank and file (a matrix). You could then write code, using loops or just direct setting of bits to set combination of bits for whatever purpose you need.
This will probably be my last example, as I don't have any real interest in trying to solve chess problems using bitboards.

The added routines assumes the linear bits map to the rank and file as follows.

Rank
  7  56 57 58 59 60 61 62 63 

  6  48 49 50 51 52 53 54 55

  5  40 41 42 43 44 45 46 47   Linear Bits (0 to 63)

  4  32 33 34 35 36 37 38 39

  3  24 25 26 27 28 29 30 31

  2  16 17 18 19 20 21 22 23

  1   8  9 10 11 12 13 14 15

  0   0  1  2  3  4  5  6  7

      0  1  2  3  4  5  6  7 File

The lower left board coordinate being 0,0
I've added the various bit set, clr and tst routines, some preset bitboards for bits associated with the various ranks and files. A routine for setting the diagonal bits (only did the one for a given linear bit, the Rank and File version is easily done just as is done for the set and clear subs and tst function).
I also added a routine to display the bitboard as a matrix of 0's and 1's.

The example calls the CreateQueenMoveBoard sub and the BoardDisp routine, which tests most of the new subs and functions added.

Option Explicit
Private Type Int64Type
  low As Long
  high As Long
End Type

Dim Rank(0 To 7) As Int64Type  'All bits in a given rank
Dim File(0 To 7) As Int64Type  'All bits in a given file
Dim Bit(0 To 31) As Long        'a table of single bit set in each bit position of a Long

Dim BlackQueenMove As Int64Type  'a bitboard for the Black Queen's possible moves

Private Sub ClrBoard(a As Int64Type)
  a.low = 0: a.high = 0
End Sub

Private Function Int64Set(high As Long, low As Long) As Int64Type
  Int64Set.low = low
  Int64Set.high = high
End Function

Private Function Int64And(a As Int64Type, b As Int64Type) As Int64Type
  Int64And.low = a.low And b.low
  Int64And.high = a.high And b.high
End Function

Private Function Int64Or(a As Int64Type, b As Int64Type) As Int64Type
  Int64Or.low = a.low Or b.low
  Int64Or.high = a.high Or b.high
End Function

Private Function Int64BitTst(a As Int64Type, b As Long) As Boolean
  If b >= 0 And b <= 63 Then
    If b < 32 Then
      Int64BitTst = (a.low And Bit(b)) <> 0
    Else
      Int64BitTst = (a.high And Bit(b - 32)) <> 0
    End If
  End If
End Function

Private Sub Int64BitSet(a As Int64Type, b As Long)
  If b >= 0 And b <= 63 Then
    If b < 32 Then
      a.low = a.low Or Bit(b)
    Else
      a.high = a.high Or Bit(b - 32)
    End If
  End If
End Sub

Private Sub Int64BitSetRF(a As Int64Type, r As Long, f As Long)
  Dim b As Long
  If r >= 0 And r <= 7 And f >= 0 And f <= 7 Then  'if rank and file values valid
    b = r * 8 + f                                  ' computer linear bit
    Int64BitSet a, b                               ' and set it
  End If
End Sub

Private Sub Int64BitClrRF(a As Int64Type, r As Long, f As Long)
  Dim b As Long
  If r >= 0 And r <= 7 And f >= 0 And f <= 7 Then  'if rank and file values valid
    b = r * 8 + f                                  ' computer linear bit
    Int64BitClr a, b                               ' and clear it
  End If
End Sub

Private Sub Int64BitClr(a As Int64Type, b As Long)
  If b >= 0 And b <= 63 Then
    If b < 32 Then
      a.low = a.low And Not Bit(b)
    Else
      a.high = a.high And Not Bit(b - 32)
    End If
  End If
End Sub

Private Function Int64Disp(a As Int64Type) As String
  Int64Disp = Hex$(a.high) & Right$("00000000" & Hex$(a.low), 8)
End Function

Private Function BoardDisp(a As Int64Type) As String
  Dim s As String, i As Long, r As Long, f As Long, p As Long
  s = String(80, "0")
  For i = 9 To 80 Step 10
    Mid$(s, i, 2) = vbCrLf
  Next
  p = 1
  For r = 7 To 0 Step -1  'display board from top to bottom
    For f = 0 To 7
      If Int64BitTst(a, r * 8 + f) Then
        Mid$(s, p, 1) = "1"
      End If
      p = p + 1
    Next
    p = p + 2
  Next
  BoardDisp = s
End Function

Private Function Int64NotZero(a As Int64Type) As Boolean
  Int64NotZero = a.high <> 0 Or a.low <> 0
End Function

Private Sub SetDiagonalsRF(a As Int64Type, r As Long, f As Long)
  Dim lr As Long, lf As Long
  
  lr = r: lf = f
  Do While lr < 7 And lf < 7  'up right diagonal
    lr = lr + 1: lf = lf + 1
    Int64BitSetRF a, lr, lf
  Loop
  
  lr = r: lf = f
  Do While lr < 7 And lf > 0 'up left diagonal
    lr = lr + 1: lf = lf - 1
    Int64BitSetRF a, lr, lf
  Loop
  
  lr = r: lf = f
  Do While lr > 0 And lf > 0 'down left diagonal
    lr = lr - 1: lf = lf - 1
    Int64BitSetRF a, lr, lf
  Loop
  
  lr = r: lf = f
  Do While lr > 0 And lf < 7 ' down right diagonal
    lr = lr - 1: lf = lf + 1
    Int64BitSetRF a, lr, lf
  Loop
End Sub

Private Sub CreateQueenMoveBoard(a As Int64Type, r As Long, f As Long)
   ClrBoard a
   a = Int64Or(a, Rank(r)) 'Set all the bits in the Rank the queen is in
   a = Int64Or(a, File(f)) 'Set all the bits in the File the queen is in
   SetDiagonalsRF a, r, f  'Set all the bits on the diagonals
End Sub

Private Sub Command1_Click()
  CreateQueenMoveBoard BlackQueenMove, 2, 3
  Debug.Print BoardDisp(BlackQueenMove)
End Sub

Private Sub Form_Load()
  Dim i As Long
 'Initialize the bit masks for isolating bits in the bitboard
 'Bit(0) = 00000000000000000000000000000001 binary
 'Bit(1) = 00000000000000000000000000000010
 'Bit(2) = 00000000000000000000000000000100 etc...
  Bit(31) = &H80000000
  Bit(0) = 1
  For i = 1 To 30
    Bit(i) = Bit(i - 1) * 2
  Next
  
 'Initialize the bits for each rank (could set up a loop, but just as easy to set the patterns)
  Rank(7) = Int64Set(&HFF000000, &H0&)
  Rank(6) = Int64Set(&HFF0000, &H0&)
  Rank(5) = Int64Set(&HFF00&, &H0&)
  Rank(4) = Int64Set(&HFF&, &H0&)
  Rank(3) = Int64Set(&H0&, &HFF000000)
  Rank(2) = Int64Set(&H0&, &HFF0000)
  Rank(1) = Int64Set(&H0&, &HFF00&)
  Rank(0) = Int64Set(&H0&, &HFF&)
  
 'Initialize the bits for each file (could set up a loop, but just as easy to set the patterns)
  File(7) = Int64Set(&H80808080, &H80808080)
  File(6) = Int64Set(&H40404040, &H40404040)
  File(5) = Int64Set(&H20202020, &H20202020)
  File(4) = Int64Set(&H10101010, &H10101010)
  File(3) = Int64Set(&H8080808, &H8080808)
  File(2) = Int64Set(&H4040404, &H4040404)
  File(1) = Int64Set(&H2020202, &H2020202)
  File(0) = Int64Set(&H1010101, &H1010101)
End Sub

[graham_ashe]

Thanks for the example. I don't think bitboards are suitable for chess in VB6 but at least the technique is worth knowing. For the record, VB6 kicks major *** as far as arrays are concerned, which is what I'll probably use.

[Rockoon]

You might also be relieved to know that bitboards arent necessarily the most efficient method a chess engine can use.

While they are great for move list generation, they don't help at all with hashing and they are a detriment during actual position evaluation.

Conversely, the 8x8 (or even better, 10x10) array method works great for standard position evaluation methods (piece-square tables for example) and also helps with zobrist hashing.

[CostaM]

The huge speed advantage of bitboards (for some areas of the chess solving problem) is only achieved when each board is ONE 64 bit number. All the work of splitting, combining, and interpretting two 32 bits as 1 64 will likely negate any positive speed benefits.

[OnErr0r]

Originally Posted by CostaM

The huge speed advantage of bitboards (for some areas of the chess solving problem) is only achieved when each board is ONE 64 bit number. All the work of splitting, combining, and interpretting two 32 bits as 1 64 will likely negate any positive speed benefits.

On a 32bit processor, and using the "standard" integer instructions (MMX/SSE/SSE2 aside), there is no 64 bit number. Two registers or two 32bit variables are necessary.

[Rockoon]

Further, Hyatt (author of Crafty) concluded that there was only a slight advantage to using a 64-bit native integer rather than emulating a 64-bit integer with 32-bit ones. The reason for this is two fold:

A) 32-bit processors can often handle the kind of 64-bit operations required by bitboards in a single clock cycle due to multiple instruction executed simultaneously (the low and high portions of an emulated 64-bit word are independent of each other in most bitboard operations)

B) The performance of highly efficient (nodes per second) chess engines is often dominated by cache miss penalties (random access to the hash table is a worst case for the L0/L1/L2 caches)