Basic questions, move generation

[paulonio]

Hi all!
I'm new to chess-programming (experienced with chess and with programming separately ). I just read a lot of about it in last months and felt ready to start coding. After writing now some code, I have few basic question:
1. I started in C++ and I'm little confused how to organize my code. Should I use classes, structures or rather don't use any of them (what will give better performance)? For example when I have bitboards storing whole position:

Code: Select all

U64 wKing;
	U64 wQueens;
	(...)
        U64 wPieces;

	U64 bKing;
	(...)
	U64 bPieces;

	U64 allPieces;

Where will be better to keep all of that?
2. Another question connected with code organization: How to divide my code in to separated .cpp and .h files. What can I keep in header files and what rather not? For example I put every enumerations, typedefs constants and so on in to separated ".h" file and think it's ok. But I put also to another header file stuff like:

Code: Select all

U64 squaresMask[64];
U64 kingtAttacks[64];
void initMasks() {...}
void initAttacks()  {...}
etc.

and I'm not sure if it's the best solution.
3. Now some doubts in move generation. I decided to init all arrays of bitbords attacks in the start of the engine. But how fast should it be? Is there any better solution than looping through all squares (non-sliding pieces) like that:

Code: Select all

//King's attacks corners:
	kingAttacks[A1] = squaresMask[A2] | squaresMask[B1] | squaresMask[B2];
	kingAttacks[A8] = squaresMask[A7] | squaresMask[B8] | squaresMask[B7];
	kingAttacks[H1] = squaresMask[H2] | squaresMask[G1] | squaresMask[G2];
	kingAttacks[H8] = squaresMask[H7] | squaresMask[G8] | squaresMask[G7];

	//King's attacks first rank:
	for &#40;int i = 1; i < 8; ++i&#41;
	&#123;
		kingAttacks&#91;i&#93; = squaresMask&#91;i + DIR_N&#93; | squaresMask&#91;i + DIR_NE&#93; | squaresMask&#91;i + DIR_NW&#93; | squaresMask&#91;i + DIR_W&#93; | squaresMask&#91;i + DIR_E&#93;;
	&#125;
then last rank, first file, last file ...

//King's attacks rest of board&#58;
	for &#40;int i = 8; i <= 55; ++i&#41;
	&#123;
		if (&#40;i % 8 == 0&#41; && (&#40;i + 1&#41; % 8 == 0&#41;) &#123; continue; &#125;
		kingAttacks&#91;i&#93; = squaresMask&#91;i + DIR_N&#93; | squaresMask&#91;i + DIR_S&#93; | squaresMask&#91;i + DIR_W&#93; | squaresMask&#91;i + DIR_E&#93; | squaresMask&#91;i + DIR_NW&#93; | squaresMask&#91;i + DIR_NE&#93; | squaresMask&#91;i + DIR_SW&#93; | squaresMask&#91;i + DIR_SE&#93;;
	&#125;

Or in knights, shorter code, but much more comparisons (btw. how would you call/enumerate knight's directions?):

Code: Select all

//Knight's attacks
	for &#40;int i = 0; i < 63; ++i&#41;
	&#123;
		knightAttacks&#91;i&#93; = 0ULL;
		if &#40;i + 17 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 17&#93;; &#125;
		if &#40;i - 17 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 17&#93;; &#125;
		if &#40;i + 15 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 15&#93;; &#125;
		if &#40;i - 15 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 15&#93;; &#125;
		if &#40;i + 6 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 6&#93;; &#125;
		if &#40;i - 6 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 6&#93;; &#125;
		if &#40;i + 10 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 10&#93;; &#125;
		if &#40;i - 10 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 10&#93;; &#125;
	&#125;

4. Sliding pieces. If I understood correctly in solution I want to implement I should keep attacks in arrays like:

Code: Select all

U64 rookRankAttacks[64][64];
U64 rookFileAttacks[64][64];

Where one index is square and another occupancy of rank/file. Am I correct? What will be the best way to init that arrays?

Sorry if my post is too long or my questions are too basic I read a lot, but for sure I didn't find all articles in the internet, so every link will be appreciate.
Thanks for all answers.
Regards,
Paulo

[kbhearn]

Hi all!
I'm new to chess-programming (experienced with chess and with programming separately :) ). I just read a lot of about it in last months and felt ready to start coding. After writing now some code, I have few basic question:
1. I started in C++ and I'm little confused how to organize my code. Should I use classes, structures or rather don't use any of them (what will give better performance)? For example when I have bitboards storing whole position:

Code: Select all

U64 wKing;
	U64 wQueens;
	(...)
        U64 wPieces;

	U64 bKing;
	(...)
	U64 bPieces;

	U64 allPieces;

Where will be better to keep all of that?

Classes and structures in C++ are identical. Sometimes people use the keywords differently to distinguish between dumb classes that just hold datamembers and classes that have member functions but whether you call it a struct or a class has no functional difference. There also is no inherent overhead to a simple class with no virtual functions.

2. Another question connected with code organization: How to divide my code in to separated .cpp and .h files. What can I keep in header files and what rather not? For example I put every enumerations, typedefs constants and so on in to separated ".h" file and think it's ok. But I put also to another header file stuff like:

Code: Select all

U64 squaresMask[64];
U64 kingtAttacks[64];
void initMasks() {...}
void initAttacks()  {...}
etc.

and I'm not sure if it's the best solution.

If you're following the normal use of headers and .cpp files with multiple compilation units:

headers can contain : simple inline functions, class declarations, templates, constants, extern declarations so that storage declared in a different compilation unit can be referenced in all compilation units using the header(the actual storage declaration does have to be in exactly one of the compilation units come link-time).

the following must exist in only one compilation unit and thus should not be in a header: declarations of storage (variables), non-inline functions

3. Now some doubts in move generation. I decided to init all arrays of bitbords attacks in the start of the engine. But how fast should it be? Is there any better solution than looping through all squares (non-sliding pieces) like that:

Code: Select all

//King's attacks corners:
	kingAttacks[A1] = squaresMask[A2] | squaresMask[B1] | squaresMask[B2];
	kingAttacks[A8] = squaresMask[A7] | squaresMask[B8] | squaresMask[B7];
	kingAttacks[H1] = squaresMask[H2] | squaresMask[G1] | squaresMask[G2];
	kingAttacks[H8] = squaresMask[H7] | squaresMask[G8] | squaresMask[G7];

	//King's attacks first rank:
	for &#40;int i = 1; i < 8; ++i&#41;
	&#123;
		kingAttacks&#91;i&#93; = squaresMask&#91;i + DIR_N&#93; | squaresMask&#91;i + DIR_NE&#93; | squaresMask&#91;i + DIR_NW&#93; | squaresMask&#91;i + DIR_W&#93; | squaresMask&#91;i + DIR_E&#93;;
	&#125;
then last rank, first file, last file ...

//King's attacks rest of board&#58;
	for &#40;int i = 8; i <= 55; ++i&#41;
	&#123;
		if (&#40;i % 8 == 0&#41; && (&#40;i + 1&#41; % 8 == 0&#41;) &#123; continue; &#125;
		kingAttacks&#91;i&#93; = squaresMask&#91;i + DIR_N&#93; | squaresMask&#91;i + DIR_S&#93; | squaresMask&#91;i + DIR_W&#93; | squaresMask&#91;i + DIR_E&#93; | squaresMask&#91;i + DIR_NW&#93; | squaresMask&#91;i + DIR_NE&#93; | squaresMask&#91;i + DIR_SW&#93; | squaresMask&#91;i + DIR_SE&#93;;
	&#125;

Or in knights, shorter code, but much more comparisons (btw. how would you call/enumerate knight's directions?):

Code: Select all

//Knight's attacks
	for &#40;int i = 0; i < 63; ++i&#41;
	&#123;
		knightAttacks&#91;i&#93; = 0ULL;
		if &#40;i + 17 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 17&#93;; &#125;
		if &#40;i - 17 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 17&#93;; &#125;
		if &#40;i + 15 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 15&#93;; &#125;
		if &#40;i - 15 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 15&#93;; &#125;
		if &#40;i + 6 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 6&#93;; &#125;
		if &#40;i - 6 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 6&#93;; &#125;
		if &#40;i + 10 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 10&#93;; &#125;
		if &#40;i - 10 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 10&#93;; &#125;
	&#125;

Initialisation speed is not worth worrying about as you only do it once. If you need those bitmaps, building them in any straightforward manner is fine - yes there are shorter ways to do it, but it doesn't matter as long as what you're doing generates the correct result in this case.

4. Sliding pieces. If I understood correctly in solution I want to implement I should keep attacks in arrays like:

Code: Select all

U64 rookRankAttacks[64][64];
U64 rookFileAttacks[64][64];

Where one index is square and another occupancy of rank/file. Am I correct? What will be the best way to init that arrays?

Sorry if my post is too long or my questions are too basic :-) I read a lot, but for sure I didn't find all articles in the internet, so every link will be appreciate.
Thanks for all answers.
Regards,
Paulo

There are many ways to generate sliding piece attacks. The method used by top engines these days is magic bitboards. But that might give you a headache. What it appears you're looking to do is akin to kindergarten bitboards. Some information on optimisations to the method could be found at:

http://chessprogramming.wikispaces.com/ ... +Bitboards

That site is a great resource in general btw. As for initialising such arrays, you'd loop through each square in your array, and loop through each occupancy and calculate the moves a slow way, store the result, and then when your engine is searching, you can just look it up.

[elcabesa]

1) is useful to have all the bitboard inside a strcture or a class representing the whole position ( bitboard, color to move,ply count, castle right and so on)

2) as you want

3) you can do what you want, it will take few millisencond to init the attack arrays for knoght & king what is important is the speed of the code you use when generating moves.

4) I'm not maximum expert on magic bitboard but searching for magic bitboard on chessprogramming wiki or this forum should giver you the answers

Marco

[sje]

The main difference between a C++ struct and a C++ class is that in a struct, all member routines and variables are public by default where in a class they're all private by default.

http://www.cplusplus.com/

I respectfully suggest than using C++ for the first time to write a chess program for the first time may not be the best idea. A more reasonable approach would be to write your first non-trivial C++ program for a simpler game, like Reversi/Othello, Qubic (4x4x4 tic-tac-toe), Awari, or Nine Men's Morris. This will teach you a lot about C++ and also the basics of two-person, zero-sum game programming. With that knowledge in hand, you'll be much better prepared to write a C++ chess program -- and likely save on the total time and effort required.

[Henk]

Don't care. You have to rewrite your engine a few times anyhow unless you are very experienced. Maybe better produce as less code as possible so rewriting/reorganizing gets easier.

[cdani]

Just a side note. Here you have a bug because you ignore the sides of the board:

Code: Select all

//Knight's attacks
	for &#40;int i = 0; i < 63; ++i&#41;
	&#123;
		knightAttacks&#91;i&#93; = 0ULL;
		if &#40;i + 17 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 17&#93;; &#125;
		if &#40;i - 17 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 17&#93;; &#125;
		if &#40;i + 15 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 15&#93;; &#125;
		if &#40;i - 15 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 15&#93;; &#125;
		if &#40;i + 6 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 6&#93;; &#125;
		if &#40;i - 6 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 6&#93;; &#125;
		if &#40;i + 10 < 63&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i + 10&#93;; &#125;
		if &#40;i - 10 > 0&#41; &#123; knightAttacks&#91;i&#93; |= squaresMask&#91;i - 10&#93;; &#125;
	&#125;

[paulonio]

Thanks for all answers, it's very helpful.
After returning into C++ from C# and Java it was for me big surprise that classes and structures are pretty the same (the only difference is default access modifier ). I've always have in mind that classes are much more powerful and structs are "light".
According to 2.: So, if I understand it correctly now, I can keep in header file declarations like:

Code: Select all

extern U64 kingAttacks[64];
void initAttacks();

http://chessprogramming.wikispaces.com/ ... +Bitboards

That site is a great resource in general btw. As for initialising such arrays, you'd loop through each square in your array, and loop through each occupancy and calculate the moves a slow way, store the result, and then when your engine is searching, you can just look it up.

Yes I know that wiki. But it's sometimes hard to find something there when you don't know the proper keyword like "Kindergarten".

I respectfully suggest than using C++ for the first time to write a chess program for the first time may not be the best idea. A more reasonable approach would be to write your first non-trivial C++ program for a simpler game, like Reversi/Othello, Qubic (4x4x4 tic-tac-toe), Awari, or Nine Men's Morris. This will teach you a lot about C++ and also the basics of two-person, zero-sum game programming. With that knowledge in hand, you'll be much better prepared to write a C++ chess program -- and likely save on the total time and effort required.

It's not my first contact with C++, I just been out for some time. I wrote as a projects for university a Gomoku and 2048 (using Allegro) with some basic AI algorithms.

Don't care. You have to rewrite your engine a few times

It's so hopeful and motivating : )

Just a side note. Here you have a bug because you ignore the sides of the board

Thanks, first bug fixed.

[kbhearn]

Thanks for all answers, it's very helpful.
After returning into C++ from C# and Java it was for me big surprise that classes and structures are pretty the same (the only difference is default access modifier :o). I've always have in mind that classes are much more powerful and structs are "light".
According to 2.: So, if I understand it correctly now, I can keep in header file declarations like:

Code: Select all

extern U64 kingAttacks[64];
void initAttacks();

Yup, those would be normal sorts of entries for a header.