Bitboards ?: C# vs C++

[hgm]

Above you wrote that KQRB is 64 x 2 x 9. But now you show tables that have 8 x 9 elements for each square. Did the 9 refer to the numbers on a single line? How did the 2 morph into an 8?

Anyway, it looks like the array would be indexed by starting square and direction. And then finds 9 numbers, the first the starting square (why would you do that, btw?), then the number of squares along the ray in that direction, and then the square numbers themselves (zero-padded).

"if the square > o the vector is terminated"; I suppose you refer to all_pieces[square] here. Now how would you know this is > 0 without looping to all squares in that direction? Say the east ray from b4, which has 6 element, 29, 28, 27, 26, 25, and 24. Now if 26 contained an enemy piece, how would you know that the capture you have to generate is 30 x 26, without first fetching the KQRB elements 29, 28, 27 and 26, and after that the all_pieces elements corrsponding to those square number, in a loop with 4 iterations and 2 memory accesses per iteration?

[Chessnut1071]

Above you wrote that KQRB is 64 x 2 x 9. But now you show tables that have 8 x 9 elements for each square. Did the 9 refer to the numbers on a single line? How did the 2 morph into an 8?

Anyway, it looks like the array would be indexed by starting square and direction. And then finds 9 numbers, the first the starting square (why would you do that, btw?), then the number of squares along the ray in that direction, and then the square numbers themselves (zero-padded).

"if the square > o the vector is terminated"; I suppose you refer to all_pieces[square] here. Now how would you know this is > 0 without looping to all squares in that direction? Say the east ray from b4, which has 6 element, 29, 28, 27, 26, 25, and 24. Now if 26 contained an enemy piece, how would you know that the capture you have to generate is 30 x 26, without first fetching the KQRB elements 29, 28, 27 and 26, and after that the all_pieces elements corrsponding to those square number, in a loop with 4 iterations and 2 memory accesses per iteration?

Now I can't understand your logic of loop searching. if you have a square [sq] KQRB[sq, 1, 20,0,0,0,0,0,0,0] you immediately have all_pieces[sq] and check_mask[sq], no searching , just an array lookup. The 1 indicates 1 move north. Each cell has 8 of those vectors with the number of possible moves indicated . The check_mask and all_pieces also shows discovered check. It may take a few more machine cycle than a bit shift; however, it take 6x more data at the same time. Also, you must have missed the corrigendum I put after my response to your message. I could use some help on bitboards, however, I don't have a bit shift forward command and have to rely on a gerry rigged substitute. I using Net 4.7.3.

[hgm]

Ah yes, I missed the corrigendum. So it is 64 x 8 x 2 x 9. So what is the '2' for?

Well, let's stick to the b4 example (sq = 30). Now all_pieces[sq] is indeed a number, which can be obtained by array lookup, and there will be a friendly piece there or you would not be interested in how it can move. So say there is a rook there, and you want to move it in direction 3 (b4->c4->d4->...->h4).

But what is check_mask[30]? That is a 64-byte array in itself, right? So not a simple array lookup. I is still totally unclear what you are doing with these data.

[Chessnut1071]

Ah yes, I missed the corrigendum. So it is 64 x 8 x 2 x 9. So what is the '2' for?

Well, let's stick to the b4 example (sq = 30). Now all_pieces[sq] is indeed a number, which can be obtained by array lookup, and there will be a friendly piece there or you would not be interested in how it can move. So say there is a rook there, and you want to move it in direction 3 (b4->c4->d4->...->h4).

But what is check_mask[30]? That is a 64-byte array in itself, right? So not a simple array lookup. I is still totally unclear what you are doing with these data.

Okay, one more time. Assume you are moving a bishop to capture a rook on square 30 (b4 on my board. mine starts 0 at h1 ,,,, 63 a8) and the enemy king is sitting on [51]. The enemy rook is sitting on a check vector [7] at square [30. The bishop is on move vector [5 or +9] and blocked by the enemy rook on [30] . So, the check mask shows vector [8 or -7] which is a bishop or queen check, a capture if it's an enemy piece along with the direction of check, and a blocker. If the enemy king happens to be on [39] instead, the enemy rook is pinned, the KQRB direction is opposite the check vector. All this information is obtained by 2 array lookup. the blocker stops the move list in that direction. If a friendly piece is sitting on [30) and the enemy king on [39] we find a discovered check for the rook. There's a lot of bytes in these tables, but, they're all pre-computed and the data is lightning fast. I used to have an engine similar to the one you first thought I was using. That engine searched about 80,000 nodes/sec. The method above is clocking about 20x that speed around 1.5 million.

Now, question on bit boards. Once you have the move how do you efficiently find the technical data associated with the move? Now comes your loops and if I assume.

[Chessnut1071]

Ah yes, I missed the corrigendum. So it is 64 x 8 x 2 x 9. So what is the '2' for?

Well, let's stick to the b4 example (sq = 30). Now all_pieces[sq] is indeed a number, which can be obtained by array lookup, and there will be a friendly piece there or you would not be interested in how it can move. So say there is a rook there, and you want to move it in direction 3 (b4->c4->d4->...->h4).

But what is check_mask[30]? That is a 64-byte array in itself, right? So not a simple array lookup. I is still totally unclear what you are doing with these data.

Okay, one more time. Assume you are moving a bishop to capture a rook on square 30 (b4 on my board. mine starts 0 at h1 ,,,, 63 a8) and the enemy king is sitting on [51]. The enemy rook is sitting on a check vector [7] at square [30. The bishop is on move vector [5 or +9] and blocked by the enemy rook on [30] . So, the check mask shows vector [8 or -7] which is a bishop or queen check, a capture if it's an enemy piece along with the direction of check, and a blocker. If the enemy king happens to be on [39] instead, the enemy rook is pinned, the KQRB direction is opposite the check vector. All this information is obtained by 2 array lookup. the blocker stops the move list in that direction. If a friendly piece is sitting on [30) and the enemy king on [39] we find a discovered check for the rook. There's a lot of bytes in these tables, but, they're all pre-computed and the data is lightning fast. I used to have an engine similar to the one you first thought I was using. That engine searched about 80,000 nodes/sec. The method above is clocking about 20x that speed around 1.5 million.

Now, question on bit boards. Once you have the move how do you efficiently find the technical data associated with the move? Now comes your loops and if I assume.

Whoops, corrigendum again: make that 35 x 1.5 million nodes, I use engine calls to to rate my engine and there's about 35 node per call.

[hgm]

Ah yes, I missed the corrigendum. So it is 64 x 8 x 2 x 9. So what is the '2' for?

Well, let's stick to the b4 example (sq = 30). Now all_pieces[sq] is indeed a number, which can be obtained by array lookup, and there will be a friendly piece there or you would not be interested in how it can move. So say there is a rook there, and you want to move it in direction 3 (b4->c4->d4->...->h4).

But what is check_mask[30]? That is a 64-byte array in itself, right? So not a simple array lookup. I is still totally unclear what you are doing with these data.

Okay, one more time. Assume you are moving a bishop to capture a rook on square 30 (b4 on my board. mine starts 0 at h1 ,,,, 63 a8) and the enemy king is sitting on [51]. The enemy rook is sitting on a check vector [7] at square [30. The bishop is on move vector [5 or +9] and blocked by the enemy rook on [30] . So, the check mask shows vector [8 or -7] which is a bishop or queen check, a capture if it's an enemy piece along with the direction of check, and a blocker. If the enemy king happens to be on [39] instead, the enemy rook is pinned, the KQRB direction is opposite the check vector. All this information is obtained by 2 array lookup. the blocker stops the move list in that direction. If a friendly piece is sitting on [30) and the enemy king on [39] we find a discovered check for the rook. There's a lot of bytes in these tables, but, they're all pre-computed and the data is lightning fast. I used to have an engine similar to the one you first thought I was using. That engine searched about 80,000 nodes/sec. The method above is clocking about 20x that speed around 1.5 million.

Now, question on bit boards. Once you have the move how do you efficiently find the technical data associated with the move? Now comes your loops and if I assume.

It seems we are talking about completely different things. You are describing how you determine whether a given move delivers a check, while I was talking on how to generate moves in the first place.

But let is turn to the way you detect checking moves. A Bishop moves to 30, and the opponent King is on 51. The check_mask table shows that you have 'alignment' in the 7 direction. So far, so good. My mailbox engines do a similar thing, except that I use 0x88 square numbering, so that I don't need a 64x64 array for the check mask, but just 256 bytes indexed by the difference of the square numbers. But that doesn't prove the Bishop delivers check. It would only do that when square 37 and 44 are both empty. You have to loop over the ray from Bishop to King to figure that out.

[dangi12012]

Ah yes, I missed the corrigendum. So it is 64 x 8 x 2 x 9. So what is the '2' for?

Well, let's stick to the b4 example (sq = 30). Now all_pieces[sq] is indeed a number, which can be obtained by array lookup, and there will be a friendly piece there or you would not be interested in how it can move. So say there is a rook there, and you want to move it in direction 3 (b4->c4->d4->...->h4).

But what is check_mask[30]? That is a 64-byte array in itself, right? So not a simple array lookup. I is still totally unclear what you are doing with these data.

Okay, one more time. Assume you are moving a bishop to capture a rook on square 30 (b4 on my board. mine starts 0 at h1 ,,,, 63 a8) and the enemy king is sitting on [51]. The enemy rook is sitting on a check vector [7] at square [30. The bishop is on move vector [5 or +9] and blocked by the enemy rook on [30] . So, the check mask shows vector [8 or -7] which is a bishop or queen check, a capture if it's an enemy piece along with the direction of check, and a blocker. If the enemy king happens to be on [39] instead, the enemy rook is pinned, the KQRB direction is opposite the check vector. All this information is obtained by 2 array lookup. the blocker stops the move list in that direction. If a friendly piece is sitting on [30) and the enemy king on [39] we find a discovered check for the rook. There's a lot of bytes in these tables, but, they're all pre-computed and the data is lightning fast. I used to have an engine similar to the one you first thought I was using. That engine searched about 80,000 nodes/sec. The method above is clocking about 20x that speed around 1.5 million.

Now, question on bit boards. Once you have the move how do you efficiently find the technical data associated with the move? Now comes your loops and if I assume.

It seems we are talking about completely different things. You are describing how you determine whether a given move delivers a check, while I was talking on how to generate moves in the first place.

But let is turn to the way you detect checking moves. A Bishop moves to 30, and the opponent King is on 51. The check_mask table shows that you have 'alignment' in the 7 direction. So far, so good. My mailbox engines do a similar thing, except that I use 0x88 square numbering, so that I don't need a 64x64 array for the check mask, but just 256 bytes indexed by the difference of the square numbers. But that doesn't prove the Bishop delivers check. It would only do that when square 37 and 44 are both empty. You have to loop over the ray from Bishop to King to figure that out.

Isnt it the fastest to just send out queen rays from a kings position after a move to check for legality?
But I want to add here that having a pinmask is also a good idea for mailslot so you know what piece is pinned and in which direction.

Thats all thats needed to go for a full legal movegenerator which is always faster since you dont do double work and make unmake a move + all memory overhead.

[Chessnut1071]

Ah yes, I missed the corrigendum. So it is 64 x 8 x 2 x 9. So what is the '2' for?

Well, let's stick to the b4 example (sq = 30). Now all_pieces[sq] is indeed a number, which can be obtained by array lookup, and there will be a friendly piece there or you would not be interested in how it can move. So say there is a rook there, and you want to move it in direction 3 (b4->c4->d4->...->h4).

But what is check_mask[30]? That is a 64-byte array in itself, right? So not a simple array lookup. I is still totally unclear what you are doing with these data.

Okay, one more time. Assume you are moving a bishop to capture a rook on square 30 (b4 on my board. mine starts 0 at h1 ,,,, 63 a8) and the enemy king is sitting on [51]. The enemy rook is sitting on a check vector [7] at square [30. The bishop is on move vector [5 or +9] and blocked by the enemy rook on [30] . So, the check mask shows vector [8 or -7] which is a bishop or queen check, a capture if it's an enemy piece along with the direction of check, and a blocker. If the enemy king happens to be on [39] instead, the enemy rook is pinned, the KQRB direction is opposite the check vector. All this information is obtained by 2 array lookup. the blocker stops the move list in that direction. If a friendly piece is sitting on [30) and the enemy king on [39] we find a discovered check for the rook. There's a lot of bytes in these tables, but, they're all pre-computed and the data is lightning fast. I used to have an engine similar to the one you first thought I was using. That engine searched about 80,000 nodes/sec. The method above is clocking about 20x that speed around 1.5 million.

Now, question on bit boards. Once you have the move how do you efficiently find the technical data associated with the move? Now comes your loops and if I assume.

It seems we are talking about completely different things. You are describing how you determine whether a given move delivers a check, whilevector is "pruned? I was talking on how to generate moves in the first place.

But let is turn to the way you detect checking moves. A Bishop moves to 30, and the opponent King is on 51. The check_mask table shows that you have 'alignment' in the 7 direction. So far, so good. My mailbox engines do a similar thing, except that I use 0x88 square numbering, so that I don't need a 64x64 array for the check mask, but just 256 bytes indexed by the difference of the square numbers. But that doesn't prove the Bishop delivers check. It would only do that when square 37 and 44 are both empty. You have to loop over the ray from Bishop to King to figure that out.

I agree, we need to get on the same page here. My check mask is adjusted for blockers first, if there's a piece along one of the "8" vectors the check vector is terminated at the first blocker. I assume you're doing the same thing, otherwise you will waste time searching for blockers.

Question: I'm still new to the bitboard and mail box systems. What the heck is a mail box? I'm still not fully informed on bit boards, but, I'm trying to work one out. Also, what's the big difference?

[hgm]

So the checkmask is not 'pre-computed', which I would understand as being computed at program start. You have to recompute it in every node. And especially when the king moves that is a lot of work, as it is an array with 64 elements. Even for blocking and unblocking you would have to loop over the downstream part of the ray, when you do it incrementally.

A mailbox structure is an array, where every element resides in a separate cell of the computer memory. The name was inspired by the analogy with mail boxes that you can rent in a post office, where you have an entire wall with small cupboards, each with their own door. A bitboard is a representation of the chess board that fits in a single memory cell, each bit corresponding to a different square.

[lithander]

Question: I'm still new to the bitboard and mail box systems. What the heck is a mail box? Also, what's the big difference?

https://www.chessprogramming.org/Mailbox

The big difference is that bitboard uses 64bit integers to encode features of the 64 squares on chess board. Each individual bit maps to a different square of the board. So you can store the placement of all black pieces in just one 64-bit integer for example.

In a mailbox engine you'd use an array of primitive types (byte or int) and a slot in that array maps to just one square on the board. That means you have all the bits of the primitive type (e.g. 8 bits in a byte) to encode that square's current occupation. More than enough for the 12 different pieces in chess. The most intuitive form of a mailbox engine would be a 8x8 board representation using an array of size 64.