Problem with bitboard knight attack generator

[ZirconiumX]

Lucas,

Your code is wonderful, thank you very much.

It is completely and utterly incompatible with my coding style, coding rules, function names, and assertion numbers, will confuse me as to why <whatever> and not <whatever> later on in life, and will probably not get used by Your Stubborness.

But thank you very much.

Matthew:out

[lucasart]

Perhaps you don't realise it yet, but writing a chess program from scratch is an enormous amount of work. Most people either: do a lot of copy/paste, or get discouraged before even having a search. THe point is that the King/Knight bitboard attack code that you have is not even 0.1% of a fully fledged chess program.

My advice (from two chess program that I wrote from scratch) would be to proceed as follows:

1/ bitboard: write the basic bitboard generation code. This is very simple and straight forward, don't waste your time in making useless optimizations there, as it's not performance sensitive (only done at run time). Add more bitboards only when you need them.

2/ Define a move structure, that is compact (no more than 32 bits, typically a bitfield struct). Write a Board class with methods Board::play and Board::undo, and start testing it manually especially with special moves (en passant, castling, promotions). You should also do functions to read/write from a FEN position, write moves into a string, read move from a string etc.

3/ Write all the move generation machinery. You'll find that this is already much more complicated than 1/ and 2/. This code must be tested thoroughly by perft. So of course you need to write a perft function, which is a trivial task (although some find it fun to optimize the perft itself and do "perft competitions" with perft hash tables etc. it's really useless for the purpose of doing a chess program). You should *never* attempt to skip this perft validation and go to step 4/ directly, or you'll regret it later, believe me, the pain of debugging will be much greater if done in the search than in perft testing.

4/ Write an SEE and test it. IMO the best SEE is the implementation of Tord Romstad, which has been slightly improved in StockFish, and that many other programmers have used to write their one.

5/ Write a quiescent search, yes a quiescent search, and not a search. This is where you should start. In particular the SEE is crucial for the quiescent search (cf. SEE pruning). For that you'll need an eval, just do a simplistic material + piece on square eval for now, you'll refine it *much* later when the search is efficient.

6/ Then write a search. You should start by the simplest alpha-beta search with SEE move ordering. After that you should add a Hash table, a PVS algorithm, and a Null move pruning. Make sure what you have is fully bug free and well tested before attempting to add anything else! And this is a general rule that applies everywhere in your program.

7/ Then start writing all the interfacing code. I *strongly* recommend that you use the UCI protocol, as it's easier and allows the programmer to really focus on the chess code, unlike the xboard protocol which is cluttered and outdated.

8/ Let's see if you haven't given up at this point, and I'll start filling the list

[brianr]

FWIW, I second all of these suggestions, except #7: Winboard is clearly the way to go, if you want to be in control of your engine (rather than the GUI).

[lucasart]

Lucas,

Your code is wonderful, thank you very much.

It is completely and utterly incompatible with my coding style, coding rules, function names, and assertion numbers, will confuse me as to why <whatever> and not <whatever> later on in life, and will probably not get used by Your Stubborness.

But thank you very much.

Matthew:out

Don't like it ? Write your own ! I bet you anything that you'll give up even before having a working move generation and playing code...
I can only help you if you want to be helped...

[ZirconiumX]

Lucas,

You make me feel stupid:

Rotated bitboards are quite simple to understand and to implement.

I understand how they work, for a rook you read along the rank avoiding wraparound, and enemy pieces (By ANDing with Empty off the top of my head). Then you look at the board but rotated 90 degrees and read again, and finally you OR the two together.

I understand how bishops are found.

But I have a dilemma, do I:

1. Use Magic Bitboards, but having a guilty conscience and absolutely no idea how they work.
2. Use Rotated Bitboards, but having to upgrade to the above at a later stage.
3. Use something else which is relatively fast and is understandable.
4. Give up and cry in a dark corner somewhere.

Matthew:out

[lucasart]

FWIW, I second all of these suggestions, except #7: Winboard is clearly the way to go, if you want to be in control of your engine (rather than the GUI).

The beauty of the UCI protocol is that it moves as much as possible code from the engine into the GUI. For example the opening book should be handl;ed by the GUI. UCI considers all moves independantly and asks your engine to think on a given position. So you don't bneed to "remember" all the moves that have been played, and when a new game command is issued you have nothing to do! Anyway, we could go on about the pros and cons of UCI and Xboard, but it's probably useless. Matthew will most likely have given up long berore step #7...

[ZirconiumX]

Perhaps you don't realise it yet, but writing a chess program from scratch is an enormous amount of work. Most people either: do a lot of copy/paste, or get discouraged before even having a search. THe point is that the King/Knight bitboard attack code that you have is not even 0.1% of a fully fledged chess program.

My advice (from two chess program that I wrote from scratch) would be to proceed as follows:

1/ bitboard: write the basic bitboard generation code. This is very simple and straight forward, don't waste your time in making useless optimizations there, as it's not performance sensitive (only done at run time). Add more bitboards only when you need them.

2/ Define a move structure, that is compact (no more than 32 bits, typically a bitfield struct). Write a Board class with methods Board::play and Board::undo, and start testing it manually especially with special moves (en passant, castling, promotions). You should also do functions to read/write from a FEN position, write moves into a string, read move from a string etc.

3/ Write all the move generation machinery. You'll find that this is already much more complicated than 1/ and 2/. This code must be tested thoroughly by perft. So of course you need to write a perft function, which is a trivial task (although some find it fun to optimize the perft itself and do "perft competitions" with perft hash tables etc. it's really useless for the purpose of doing a chess program). You should *never* attempt to skip this perft validation and go to step 4/ directly, or you'll regret it later, believe me, the pain of debugging will be much greater if done in the search than in perft testing.

4/ Write an SEE and test it. IMO the best SEE is the implementation of Tord Romstad, which has been slightly improved in StockFish, and that many other programmers have used to write their one.

5/ Write a quiescent search, yes a quiescent search, and not a search. This is where you should start. In particular the SEE is crucial for the quiescent search (cf. SEE pruning). For that you'll need an eval, just do a simplistic material + piece on square eval for now, you'll refine it *much* later when the search is efficient.

6/ Then write a search. You should start by the simplest alpha-beta search with SEE move ordering. After that you should add a Hash table, a PVS algorithm, and a Null move pruning. Make sure what you have is fully bug free and well tested before attempting to add anything else! And this is a general rule that applies everywhere in your program.

7/ Then start writing all the interfacing code. I *strongly* recommend that you use the UCI protocol, as it's easier and allows the programmer to really focus on the chess code, unlike the xboard protocol which is cluttered and outdated.

8/ Let's see if you haven't given up at this point, and I'll start filling the list

Most of my engines have been derivatives, so I didn't realise the amount of effort required.

Step 1 code:
See King Knight and Pawn (and borrowed slider code).

Matthew:out

[lucasart]

Perhaps you don't realise it yet, but writing a chess program from scratch is an enormous amount of work. Most people either: do a lot of copy/paste, or get discouraged before even having a search. THe point is that the King/Knight bitboard attack code that you have is not even 0.1% of a fully fledged chess program.

My advice (from two chess program that I wrote from scratch) would be to proceed as follows:

1/ bitboard: write the basic bitboard generation code. This is very simple and straight forward, don't waste your time in making useless optimizations there, as it's not performance sensitive (only done at run time). Add more bitboards only when you need them.

2/ Define a move structure, that is compact (no more than 32 bits, typically a bitfield struct). Write a Board class with methods Board::play and Board::undo, and start testing it manually especially with special moves (en passant, castling, promotions). You should also do functions to read/write from a FEN position, write moves into a string, read move from a string etc.

3/ Write all the move generation machinery. You'll find that this is already much more complicated than 1/ and 2/. This code must be tested thoroughly by perft. So of course you need to write a perft function, which is a trivial task (although some find it fun to optimize the perft itself and do "perft competitions" with perft hash tables etc. it's really useless for the purpose of doing a chess program). You should *never* attempt to skip this perft validation and go to step 4/ directly, or you'll regret it later, believe me, the pain of debugging will be much greater if done in the search than in perft testing.

4/ Write an SEE and test it. IMO the best SEE is the implementation of Tord Romstad, which has been slightly improved in StockFish, and that many other programmers have used to write their one.

5/ Write a quiescent search, yes a quiescent search, and not a search. This is where you should start. In particular the SEE is crucial for the quiescent search (cf. SEE pruning). For that you'll need an eval, just do a simplistic material + piece on square eval for now, you'll refine it *much* later when the search is efficient.

6/ Then write a search. You should start by the simplest alpha-beta search with SEE move ordering. After that you should add a Hash table, a PVS algorithm, and a Null move pruning. Make sure what you have is fully bug free and well tested before attempting to add anything else! And this is a general rule that applies everywhere in your program.

7/ Then start writing all the interfacing code. I *strongly* recommend that you use the UCI protocol, as it's easier and allows the programmer to really focus on the chess code, unlike the xboard protocol which is cluttered and outdated.

8/ Let's see if you haven't given up at this point, and I'll start filling the list

Most of my engines have been derivatives, so I didn't realise the amount of effort required.

Step 1 code:
See King Knight and Pawn (and borrowed slider code).

Matthew:out

Well, start doing step two now, and let us know how it goes

[lucasart]

Perhaps you don't realise it yet, but writing a chess program from scratch is an enormous amount of work. Most people either: do a lot of copy/paste, or get discouraged before even having a search. THe point is that the King/Knight bitboard attack code that you have is not even 0.1% of a fully fledged chess program.

My advice (from two chess program that I wrote from scratch) would be to proceed as follows:

1/ bitboard: write the basic bitboard generation code. This is very simple and straight forward, don't waste your time in making useless optimizations there, as it's not performance sensitive (only done at run time). Add more bitboards only when you need them.

2/ Define a move structure, that is compact (no more than 32 bits, typically a bitfield struct). Write a Board class with methods Board::play and Board::undo, and start testing it manually especially with special moves (en passant, castling, promotions). You should also do functions to read/write from a FEN position, write moves into a string, read move from a string etc.

3/ Write all the move generation machinery. You'll find that this is already much more complicated than 1/ and 2/. This code must be tested thoroughly by perft. So of course you need to write a perft function, which is a trivial task (although some find it fun to optimize the perft itself and do "perft competitions" with perft hash tables etc. it's really useless for the purpose of doing a chess program). You should *never* attempt to skip this perft validation and go to step 4/ directly, or you'll regret it later, believe me, the pain of debugging will be much greater if done in the search than in perft testing.

4/ Write an SEE and test it. IMO the best SEE is the implementation of Tord Romstad, which has been slightly improved in StockFish, and that many other programmers have used to write their one.

5/ Write a quiescent search, yes a quiescent search, and not a search. This is where you should start. In particular the SEE is crucial for the quiescent search (cf. SEE pruning). For that you'll need an eval, just do a simplistic material + piece on square eval for now, you'll refine it *much* later when the search is efficient.

6/ Then write a search. You should start by the simplest alpha-beta search with SEE move ordering. After that you should add a Hash table, a PVS algorithm, and a Null move pruning. Make sure what you have is fully bug free and well tested before attempting to add anything else! And this is a general rule that applies everywhere in your program.

7/ Then start writing all the interfacing code. I *strongly* recommend that you use the UCI protocol, as it's easier and allows the programmer to really focus on the chess code, unlike the xboard protocol which is cluttered and outdated.

8/ Let's see if you haven't given up at this point, and I'll start filling the list

Most of my engines have been derivatives, so I didn't realise the amount of effort required.

Step 1 code:
See King Knight and Pawn (and borrowed slider code).

Matthew:out

Well, start doing step two now, and let us know how it goes

Oh, I forgot, before step 2, you must make sure that step 1 code is 100% bugfree. So write a function that displayes a bitboard and run your bitboard code in debug to print them all, and only start step 2 at this point.

Here's an example of such a function:

Code: Select all

void print_bitboard(uint64_t b)
{
	int r, f;
	for (r = Rank8; r >= Rank1; r--) {
		for &#40;f = FileA; f <= FileH; f++) &#123;
			int sq = square&#40;r, f&#41;;
			char c = test_bit&#40;b, sq&#41; ? 'X' &#58; '.';
			printf&#40;" %c", c&#41;;
		&#125;
		printf&#40;"\n");
	&#125;
&#125;

which basically prints bitboards like this:

Code: Select all

 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 X . X . . . . .
 . . . X . . . .
 . . . . . . . .

[Sven]

Lucas,

You make me feel stupid:

Rotated bitboards are quite simple to understand and to implement.

I understand how they work, for a rook you read along the rank avoiding wraparound, and enemy pieces (By ANDing with Empty off the top of my head). Then you look at the board but rotated 90 degrees and read again, and finally you OR the two together.

I understand how bishops are found.

But I have a dilemma, do I:

1. Use Magic Bitboards, but having a guilty conscience and absolutely no idea how they work.
2. Use Rotated Bitboards, but having to upgrade to the above at a later stage.
3. Use something else which is relatively fast and is understandable.
4. Give up and cry in a dark corner somewhere.

Although you asked Lucas directly, may I suggest:

e. Cry in a dark corner somewhere if you really need to ... but then, don't give up, start with c. instead (where Dumb7Fill can be a good choice) to become familiar with bitboards, and only later on change the internal implementation of your attack getter functions by something more efficient like Magic Bitboards (which is not easy, I agree, but also not impossible to understand in the light of several well-written explanations). As Lucas said, I would not spend too much time here in the beginning.

Rotated instead of Magic Bitboards would be possible too, but it would be a choice that affects your board representation, as opposed to the other choices.

Sven