Some questions from a beginner

[The_Algebraist]

Hello everyone!

I'm new to the engine programming scene, I just started programming my own engine in C++ some time ago.

So far I've got a board data implementation. I chose to use bitboards, so this took some time. Next thing I'm planning is the move implementation.

Yet I have some questions. I read alot in the chess programming wikispaces, which is a great resource! This was how I also found this forum. But some points are a bit unclear to me.

First, as I said, I'm using bitboards. Then I had the problem of finding a piece on a given square. It seemed a little ineffective to me, to go through all bitboards (I use 8, as described in the 'dense method'). So, as recommended, I added a 64 square array that holds the information if there is a piece on a square.
But that stills leaves me with the question, how I transfer the information from the bitboards to the array or vice versa. Scanning through all boards and writing the result in the array wouldn't be much different than the first approach.
So I was wondering how you guys solve this problem? I had the idea to not really "synchronize" them (as in copying the information from one source to the other), but to just do all updates on both the bitboards and the array. What do you think about this approach? Will this be enough or am I running into problems in a later stage of the development?

Second, I want to try to test the code as good as possible. I already have experience in different programming languages and also some experience with C+ (although this is a loong time ago). So I was thinking to use unit-tests and try to have a very high code coverage.
Can you recommend a good unit-testing framework for C++? And a good tool to measure the code coverage (and possibly branch coverage) in C++?
How are you dealing with this subject? Are you implementing unit-tests or do you follow a different approach?

Well, I hope I didn't write too much in my first posting here! I'm glad I found this great place and I would appreciate some insights from you experts!

Tim

[Aleks Peshkov]

Your board representation is bitboards+array, so you do not synchronize them but update both independently each time your make move on the board. There are other data (like position hash key) you have to update incrementally during each move because it is faster to update then regenerate it again and again from scratch.

[Mincho Georgiev]

Hello Tim, nice to meet you!
I'm not 100% sure if I understood correctly, but I think you need to consider the following basic information. First, the board representation and second - the move generation. If you're going to use bitboards, you're going to need several bitboards to represent pieces. By doing so, you're not going to have a problem to find where a 'WHITE KNIGHT' stands for example, because you will have a bitboard which represents white knights with two set bits if you have pair of them. If you want to iterate trough knights, you're doing a bitscan/bitclear for each bit out of the WN (white knights) bitboard. Each bitscan gives you the SQUARE where each knight is on. This is just an example.
In my representation, I'm using an array of 16 bitboards (14 in use).
Bitboard 1-6 for white pieces by type, bitboard 9-14 for black pieces by type, bitboard 7 and 8 for ALL WHITES and ALL BLACKS. As for the move generation, you can choose between rotated or magic bitboards, there is plenty of information.
Regarding your "synchronizing" question, I'm not sure I understood, but the bitboards are set once when you set the position and then incrementally updated during a move_make. For example if knight captures a pawn, you update your knights board by removing the 'old' bit, then you get the new bit set for the new square, and then clearing the bit for the captured pawn from the pawns bitboard.
My point is, you don't want to scan anything when you use bitboards. You don't use arrays, only bitboards. You can use auxiliary information like piece_cout[] and such, but that's about it.
Since I mentioned bitscan, keep in mind that this has nothing to do with scanning an array or linked lists etc. The worst case you can have with bitboards is iterating trough the bitboards array and it's still better than updating and scanning a piece list or worse - the board itself like in a mailbox representation (on a new architecture that is)
I hope that's helpful.

[The_Algebraist]

Hello Aleks, hello Mincho,

thanks for your quick replies!

Your board representation is bitboards+array, so you do not synchronize them but update both independently each time your make move on the board. There are other data (like position hash key) you have to update incrementally during each move because it is faster to update then regenerate it again and again from scratch.

Great, thanks. So I'll do it this way and update everthing on making or unmaking a move.

Hello Tim, nice to meet you!
I'm not 100% sure if I understood correctly, but I think you need to consider the following basic information. First, the board representation and second - the move generation. If you're going to use bitboards, you're going to need several bitboards to represent pieces. By doing so, you're not going to have a problem to find where a 'WHITE KNIGHT' stands for example, because you will have a bitboard which represents white knights with two set bits if you have pair of them. If you want to iterate trough knights, you're doing a bitscan/bitclear for each bit out of the WN (white knights) bitboard. Each bitscan gives you the SQUARE where each knight is on. This is just an example.
In my representation, I'm using an array of 16 bitboards (14 in use).
Bitboard 1-6 for white pieces by type, bitboard 9-14 for black pieces by type, bitboard 7 and 8 for ALL WHITES and ALL BLACKS. As for the move generation, you can choose between rotated or magic bitboards, there is plenty of information.
Regarding your "synchronizing" question, I'm not sure I understood, but the bitboards are set once when you set the position and then incrementally updated during a move_make. For example if knight captures a pawn, you update your knights board by removing the 'old' bit, then you get the new bit set for the new square, and then clearing the bit for the captured pawn from the pawns bitboard.
My point is, you don't want to scan anything when you use bitboards. You don't use arrays, only bitboards. You can use auxiliary information like piece_cout[] and such, but that's about it.
Since I mentioned bitscan, keep in mind that this has nothing to do with scanning an array or linked lists etc. The worst case you can have with bitboards is iterating trough the bitboards array and it's still better than updating and scanning a piece list or worse - the board itself like in a mailbox representation (on a new architecture that is)
I hope that's helpful.

Thanks for all the information! I'm going with 8 bitboards, 1 for every piecetype, 1 for all the white pieces and 1 for all the black pieces (as suggested here in "denser board").

I just wasn't sure how to bring the information in my (redundant) board array, seems it is best to just update everything. I will have to make sure, that everything is set simultaneously, but then there is no need for synchronizing the bitboards with the board array (the two sources with the redundant information).


Do you have any suggestions for a unit-testing framework?

What do you use to test your code?

[Mincho Georgiev]

The 'board array' in bitboard representation is just an auxiliary data array, you're using it for square reference, but no scanning is involved like in a mailbox representation. You have to update it incrementally alongside with your bitboards and like Aleks said, alongside with your position hash and every other data (like piece count for example). A common thing between the two different representations (x88, etc and bitboards) is the UNDO stack. This is where you keep your move data in order to restore it when you UNDO a move. So: update the information when DO a move, restore it when UNDO from the undo stack.

[jdart]

Re unit test, depends on your language and platform. For Windows Visual C++ Professional has support for unit testing and coverage analysis. It is expensive but I think they have reduced pricing for students.

If you use gcc there is gcov.

boost has some test support but I haven't used it.

While I do have some unit testing mostly I have relied on asserts a lot. These do extensive runtime sanity checking during execution (in a debug build). I also recommend the "undefined behavior sanitizer" compiler options in GCC 5.x for avoiding bounds overflow, reference to undefined variables, etc.

--Jon

[Mincho Georgiev]

Re unit test, depends on your language and platform. For Windows Visual C++ Professional has support for unit testing and coverage analysis. It is expensive but I think they have reduced pricing for students.

If you use gcc there is gcov.

boost has some test support but I haven't used it.

While I do have some unit testing mostly I have relied on asserts a lot. These do extensive runtime sanity checking during execution (in a debug build). I also recommend the "undefined behavior sanitizer" compiler options in GCC 5.x for avoiding bounds overflow, reference to undefined variables, etc.

--Jon

Just on a side note, I admit, I was very skeptical 6-7 years ago about GCC reaching intel speeds, but I tried 4.8+ recently and my oh my, was I wrong. Great to see it developing, while Intel compiler keeps regressing past 11.0
Anyways, I don't want to derail the topic at hand.

[jdart]

GCC has made major architectural revisions over the past decade and is really now not the same compiler it was. I never had great results from Intel C++, but there are a lot of options. It is also very slow.

FYI this is the file of unit tests I have:

https://github.com/jdart1/arasan-chess/ ... c/unit.cpp.

Feel free to use the FENs if you want (code is MIT licensed). Some I got from Martin Sedlak & Steve Maugham.

--Jon

[The_Algebraist]

FYI this is the file of unit tests I have:

https://github.com/jdart1/arasan-chess/ ... c/unit.cpp.

Feel free to use the FENs if you want (code is MIT licensed). Some I got from Martin Sedlak & Steve Maugham.

--Jon

Thank you! That's great

I ended up with gtest as a unit testing framework for now. Looks good I guess.

Now I have to fix some bugs in the fen parser and then comes move generation

[The_Algebraist]

I need a little help again

Current status is that the move generation for pawns is working.

Then I started with the slider pieces. I read much about it the last days and decided to try my luck with magic bitboards.

I precomputed the arrays for bishops and rooks as described here: http://chessprogramming.wikispaces.com/ ... for+Magics

Then I used a lookup as suggested here: http://chessprogramming.wikispaces.com/ ... ions-Fancy

When I finally got it working, I tested it with this position I set up for the white bishop on D4:

Code: Select all

 8   r  n  b  .  k  .  .  r
 7   .  p  p  p  .  p  p  p
 6   p  q  .  .  .  n  .  .
 5   .  .  .  .  .  .  .  .
 4   .  .  .  B  .  .  .  .
 3   .  .  b  P  p  P  .  .
 2   P  P  P  .  P  .  P  P
 1   R  N  B  Q  K  .  N  R

     A  B  C  D  E  F  G  H

rnb1k2r/1ppp1ppp/pq3n2/8/3B4/2bPpP2/PPP1P1PP/RNBQK1NR w KQkq - 0 1

and then ran a test as follows:

Code: Select all

printBitboard(bishopAttacks(pos->allPieces(), SQ_D4));

with the result being:

Code: Select all

.  .  .  .  .  .  .  .
x  .  .  .  .  .  .  .
.  x  .  .  .  .  .  .
.  .  x  .  x  .  .  .
.  .  .  .  .  .  .  .
.  .  x  .  x  .  .  .
.  x  .  .  .  x  .  .
x  .  .  .  .  .  x  .

where allPieces returns the following bitboard

Code: Select all

x  x  x  .  x  .  .  x
.  x  x  x  .  x  x  x
x  x  .  .  .  x  .  .
.  .  .  .  .  .  .  .
.  .  .  x  .  .  .  .
.  .  x  x  x  x  .  .
x  x  x  .  x  .  x  x
x  x  x  x  x  .  x  x

For completeness:

Code: Select all

printBitboard(bishopAttacks(pos->allPieces(), SQ_D4) & ~pos->pieces(White));

leads to

Code: Select all

.  .  .  .  .  .  .  .
x  .  .  .  .  .  .  .
.  x  .  .  .  .  .  .
.  .  x  .  x  .  .  .
.  .  .  .  .  .  .  .
.  .  x  .  x  .  .  .
.  .  .  .  .  x  .  .
.  .  .  .  .  .  .  .

These results seem to be wrong. I expect the Squares A7, B2, A1, F2 and G1 to be empty, but have a target on F6.

Now I'm looking for my mistake for quite a while now, but I cannot find it.

Is there a way to test the precomputed magics? I used the function suggested in the cpw to generate them so I assume they are right, but you never know...


For referency (even if taken from the cpw) I paste my relevant code:

Code: Select all

struct SMagic {
   U64  mask;
   U64  magic;
   int  shift;
   U64* ptr;
};

// these are initialized with the precomputed values
extern SMagic bishopTbl[64];
extern SMagic rookTbl[64];

inline U64 bishopAttacks(U64 occ, Square sq) {
   U64* aptr = bishopTbl[sq].ptr;
   occ      &= bishopTbl[sq].mask;
   occ      *= bishopTbl[sq].magic;
   occ     >>= bishopTbl[sq].shift;
   return aptr[occ];
}
 
inline U64 rookAttacks(U64 occ, Square sq) {
   U64* aptr = rookTbl[sq].ptr;
   occ      &= rookTbl[sq].mask;
   occ      *= rookTbl[sq].magic;
   occ     >>= rookTbl[sq].shift;
   return aptr[occ];
}

Could you please have look over my code and give me a hint how I can best find the error?