Bitboards ?: C# vs C++

[Chessnut1071]

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.

Mail boxes sounds a lot like what I'm doing. In your opinion, are bit boards any faster?

[hgm]

In my opinion it depends much on how you organize your entire engine, and when you do that well, it doesn't matter much whether you use mailbox or bitboard. Simplistic mailboard implementations are probably a bit slower than bitboard, especially when you have complex evaluation.

About you method for determining whether a move delivers check: more important than whether this is fast or slow is why you would want to do this at all. In my engines I am only interested in this once it is decided that the move is going to be searched. In which case a new move generation will follow for the opponent. So for most generated moves I would not be interested in this info. That means it doesn't really pay to heavily invest in making testing moves for this easy (by preparing / updating thecheck mask), but that it gives a faster engine when I test individual moves through a method that would be slower when it had to be applied to all moves.

[dangi12012]

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.

Mail boxes sounds a lot like what I'm doing. In your opinion, are bit boards any faster?

Bitboards are faster but harder to implement. When you think of chess first its in terms of a 64 slot array. Thinking in terms of 12x 64bit variables is not intuitive - but its faster.

A lot of bitboard tricks are not explained properly in the wiki.
A whole board position even fits in a single AVX2 register and then you get access to the really good SIMD instructions.

You can even go another route entirely. By playing multiple games in parallel with simd. That is still unexplored and everyone seems to be doing chess in a very similar way today:
https://jim.sh/svn/jim/vendor/microwind ... /tuxchess/
https://github.com/olithink/OliThink
https://github.com/official-stockfish/Stockfish

So much is unexplored but I can say that bitboards are superiour to mailslot. They look similiar - But there are some optimisations with bitboards that cannot be done in an array.

[hgm]

Note however that there are other data structures than bitboards and mailbox boards, which can be used as principal game representation. In particular, an attack map that keep track (as a packed array of bit flags) which piece attacks or protects which other piece, might give you an engine that is far faster than pure bitboard or mailbox. So arguing which of the latter two is fastest somehow misses the point.

[lithander]

Mail boxes sounds a lot like what I'm doing. In your opinion, are bit boards any faster?

I also started with a simple mailbox engine. I believe that you learn basic chess programming principles faster if you don't worry about the performance too much. I also believe hgm is right that just chosing bitboard doesn't automatically make your engine fast or that mailbox engines are doomed to be too slow to be competitive. But personally I'm now looking into converting my simple mailbox engine to use bitboards hoping for a considerable speed increase. Frankly, making the mailbox approach fast seems harder to me than using bitboards.

[hgm]

That of course depends on how fast you want to make it. Conversion to bitboard is relatively easy, because you reach the end of the road pretty quickly.

[lithander]

That of course depends on how fast you want to make it. Conversion to bitboard is relatively easy, because you reach the end of the road pretty quickly.

Ideas like you present in mailbox trials are intriguing but I can barely follow. Wouldn't feel like my engine if I cant come up with the solutions myself and intuitively understand how all parts work together. So after simple 8x8 mailbox "relatively easy" sounds like a good next step.

[Chessnut1071]

In my opinion it depends much on how you organize your entire engine, and when you do that well, it doesn't matter much whether you use mailbox or bitboard. Simplistic mailboard implementations are probably a bit slower than bitboard, especially when you have complex evaluation.

About you method for determining whether a move delivers check: more important than whether this is fast or slow is why you would want to do this at all. In my engines I am only interested in this once it is decided that the move is going to be searched. In which case a new move generation will follow for the opponent. So for most generated moves I would not be interested in this info. That means it doesn't really pay to heavily invest in making testing moves for this easy (by preparing / updating thecheck mask), but that it gives a faster engine when I test individual moves through a method that would be slower when it had to be applied to all moves.

Ah, Herr Muller, the check is everything for my objective. My interest is minimum moves to mate at the highest ply possible. The last moves doesn't even look at anything but check. Also, the check feeds forward info for the constraints on the opposite side. Even maxing ELO needs check, discovered check and pin. I will agree; however, that many openings and middle games can ignore check, discovered check, but not pin. I can't because check is the single most important variable in optimized mate finding, followed closely history by ply. I need 30x(32x64) matrix for that little gimmick. but, it drops the engine calls by more than 50%. the 30 is for 30-ply which is my objective.

I think you are focused on some different type of approach than I'm actually using. I'd list the code, but, it's like going to work in your underwear right now.

I'm working on a bit board, but, I'm using an older version of C# in Net, Framework. I think you need to go to C++ to optimize a bitboard. I don't know many C# bitboards.

[dangi12012]

In my opinion it depends much on how you organize your entire engine, and when you do that well, it doesn't matter much whether you use mailbox or bitboard. Simplistic mailboard implementations are probably a bit slower than bitboard, especially when you have complex evaluation.

About you method for determining whether a move delivers check: more important than whether this is fast or slow is why you would want to do this at all. In my engines I am only interested in this once it is decided that the move is going to be searched. In which case a new move generation will follow for the opponent. So for most generated moves I would not be interested in this info. That means it doesn't really pay to heavily invest in making testing moves for this easy (by preparing / updating thecheck mask), but that it gives a faster engine when I test individual moves through a method that would be slower when it had to be applied to all moves.

Ah, Herr Muller, the check is everything for my objective. My interest is minimum moves to mate at the highest ply possible. The last moves doesn't even look at anything but check. Also, the check feeds forward info for the constraints on the opposite side. Even maxing ELO needs check, discovered check and pin. I will agree; however, that many openings and middle games can ignore check, discovered check, but not pin. I can't because check is the single most important variable in optimized mate finding, followed closely history by ply. I need 30x(32x64) matrix for that little gimmick. but, it drops the engine calls by more than 50%. the 30 is for 30-ply which is my objective.

I think you are focused on some different type of approach than I'm actually using. I'd list the code, but, it's like going to work in your underwear right now.

I'm working on a bit board, but, I'm using an older version of C# in Net, Framework. I think you need to go to C++ to optimize a bitboard. I don't know many C# bitboards.

Go for implementation first - and optimize later. Its 100x easier to write you engine in C# and translate to C++ when you need the performance.
I was hoping for the last 15 years that JIT languages will surpass precompiled binaries like C++ but this probably will not happen anytime soon.
So just implement first - optimize later. Or you will never have a reference finished product.

[hgm]

In my opinion it depends much on how you organize your entire engine, and when you do that well, it doesn't matter much whether you use mailbox or bitboard. Simplistic mailboard implementations are probably a bit slower than bitboard, especially when you have complex evaluation.

About you method for determining whether a move delivers check: more important than whether this is fast or slow is why you would want to do this at all. In my engines I am only interested in this once it is decided that the move is going to be searched. In which case a new move generation will follow for the opponent. So for most generated moves I would not be interested in this info. That means it doesn't really pay to heavily invest in making testing moves for this easy (by preparing / updating thecheck mask), but that it gives a faster engine when I test individual moves through a method that would be slower when it had to be applied to all moves.

Ah, Herr Muller, the check is everything for my objective. My interest is minimum moves to mate at the highest ply possible. The last moves doesn't even look at anything but check. Also, the check feeds forward info for the constraints on the opposite side. Even maxing ELO needs check, discovered check and pin. I will agree; however, that many openings and middle games can ignore check, discovered check, but not pin. I can't because check is the single most important variable in optimized mate finding, followed closely history by ply. I need 30x(32x64) matrix for that little gimmick. but, it drops the engine calls by more than 50%. the 30 is for 30-ply which is my objective.

I think you are focused on some different type of approach than I'm actually using. I'd list the code, but, it's like going to work in your underwear right now.

I'm working on a bit board, but, I'm using an older version of C# in Net, Framework. I think you need to go to C++ to optimize a bitboard. I don't know many C# bitboards.

OK, so you are building a mate finder rather than a chess player. Still, the basic principle remains valid: first examine what really has to be done, rather than just picking some method without analysis, and trying to make that as fast as possible. If you want to test all moves for delivering check, for the purpose of playing only those that do, that is a bad idea, even when the test can be made very fast. Because most moves do not deliver check, you would generate far more moves than needed. It would be much faster to use a special purpose move generator that selectively generates checking moves, and don't wastes any time on generating moves that don't. E.g. for knights you could have a pre-computed table indexed by knight square and opponent king square, which contains the (maximally 2) squares where that knight would deliver check. Most of the time knights would not be able to check at all, and you would be done with those almost instantly. That is a whole lot faster than generating all 8 moves for a knight, and subjecting each of those to a test to see whether they check.