Bitboard Engine

[John Digsby]

Hi,

I'm trying something a little new for chess programming in terms of how to make the computer evaluate positions. I previously wrote a move generator based on representing the board as two arrays of squares occupied by black and squares occupied by white, accompanied by a bog-standard 64-length array. I precomputed all valid moves for every piece on every square of an empty board, and loaded them into memeory at initialisation.

All this, just to try to make my code somewhat less verbose and easier for me to maintain!

As I reached the evaluation routines, and wanted to start looking at structures like outposted knights, etc. I found I was writing very complex code, which would produce a bit of a bottleneck during the tree search.

I have since poked around the source of Crafty and the same evaluations that I'm having to write into 30-40 line functions for are represented by simple boolean ifs because of the bitboard representation.

I understand how this works, but didn't implement it because it was so complicated. Since I'm mostly interested in the evaluation end, I wondered if there was some C++ source for a chessboard class (or somesuch) that implemented bitboards. I would convert Crafty happily, except that I don't understand exactly how ordinary C file structures work and can't seem to find the bit I'm after.

If anyone can help either finding an existing C++ solution, or in suggesting how to extract the one in Crafty I would be very appreciative, as I would rather get on with the "interesting" part than be bogged down in generation again!

[Dann Corbit]

Hi,

I'm trying something a little new for chess programming in terms of how to make the computer evaluate positions. I previously wrote a move generator based on representing the board as two arrays of squares occupied by black and squares occupied by white, accompanied by a bog-standard 64-length array. I precomputed all valid moves for every piece on every square of an empty board, and loaded them into memeory at initialisation.

All this, just to try to make my code somewhat less verbose and easier for me to maintain!

As I reached the evaluation routines, and wanted to start looking at structures like outposted knights, etc. I found I was writing very complex code, which would produce a bit of a bottleneck during the tree search.

I have since poked around the source of Crafty and the same evaluations that I'm having to write into 30-40 line functions for are represented by simple boolean ifs because of the bitboard representation.

I understand how this works, but didn't implement it because it was so complicated. Since I'm mostly interested in the evaluation end, I wondered if there was some C++ source for a chessboard class (or somesuch) that implemented bitboards. I would convert Crafty happily, except that I don't understand exactly how ordinary C file structures work and can't seem to find the bit I'm after.

If anyone can help either finding an existing C++ solution, or in suggesting how to extract the one in Crafty I would be very appreciative, as I would rather get on with the "interesting" part than be bogged down in generation again!

This is C and not C++, but it is well written and easy to understand:
http://www.prism.gatech.edu/~gtg365v/Buzz/

The author of Elephant has the most interesting C++ bitboard based move generator set I have ever seen. I guess he might let you have a copy if you asked him. He has implemented lots of fundamentally different bitboard techniques in his generators.

I think that the move generator for Adriano is very nice, and Olithink is a very good study also.

Any GPL C++ engine could be used as a base for your studies if your project is intended to be GPL as well.

[Tord Romstad]

I understand how this works, but didn't implement it because it was so complicated. Since I'm mostly interested in the evaluation end, I wondered if there was some C++ source for a chessboard class (or somesuch) that implemented bitboards.

Glaurung uses bitboards, is written in C++, and has a chessboard class (called 'Position'). But I should warn you that it is quite a big and messy program (more compact than Crafty, though), and written in quite strange and unidiomatic C++.

Tord

[Harald Lüßen]

The author of Elephant has the most interesting C++ bitboard based move generator set I have ever seen. I guess he might let you have a copy if you asked him. He has implemented lots of fundamentally different bitboard techniques in his generators.

Thank you. Yes I sometimes give the code away to people who ask for it,
tell me their email address and accept 3 easy things:
- Do not distribute it to others.
- Do not steal too much.
- Make comments on bugs or highlights.

Yes there are a few interesting bitboard techniques in it. It is not so much
about the move generator but about the methods to get the attack-bitboards.
I tried and compared a dozen different methods, each in an exchangeable
source module. Examples are rotated bitboards or magic bitboards.
The rest of the program is typical C++ style. I am not so happy with
some of my classes and I wish I had the time to change them a little.
The code is easy to read and hopefully to understand. Too much #if macros
make some parts of the code look like a little battlefield.

On the other side I wrote the program to improve my C++ skills.
I tried to implement the classes and functions in a very clean and
well dokumented way. And the whole program is written in the same
good style.

And Elephant has only about 2000 ELO points. Perhaps there are some bugs in it.

Harald

[Aleks Peshkov]

IMHO copy-paste design of any bitboard code implementation will not work, because data representation is a core of a chess engine, but not a common library.

I understand how this works, but didn't implement it because it was so complicated. Since I'm mostly interested in the evaluation end, I wondered if there was some C++ source for a chessboard class (or somesuch) that implemented bitboards.

Glaurung uses bitboards, is written in C++, and has a chessboard class (called 'Position'). But I should warn you that it is quite a big and messy program (more compact than Crafty, though), and written in quite strange and unidiomatic C++.

Glaurung 1 and Glaurung 2 are both ones of the very best (and my first personal favorites) examples of chess code architecture, chess-domain decisions and naming conventions.

But I will not recommend particular Glaurung's bitboard implementation as a start point of a new program. I think classical Crafty old-fashioned C-code can be understood and refactored into simpler C++ with more sucess.

[John Digsby]

But I will not recommend particular Glaurung's bitboard implementation as a start point of a new program. I think classical Crafty old-fashioned C-code can be understood and refactored into simpler C++ with more sucess.

I'm happy to refactor code, but in Crafty I've just had trouble tracking down all the code that only deals with the board representation so that I can quickly refactor it and have a working solution after a brief round of debugging. Can you offer any pointers as to which of the source files actually contain this code, because I'm really in a tangle trying to navigate it!

[bob]

Here's a rough run-down:

init.c initializes the stuff, including the magic numbers and such, as well as initializing the chess board, hash signature, etc.

make.c/unmake.c update the board by making/retracting moves.

If you are going to use magic move generation, then movgen.c has the move generators for generating captures, non-captures, and legal moves only when escaping check.

That covers the chess board data structure itself...

[Volker Pittlik]

Hi John,

there is a problem with the e-mail address in your profile. I get an error message for every reply. Please update the mail address or disable to be notified for every reply.

Volker

[John Digsby]

^^ Sorry about that - should be fixed now

I have spent a few hours today converting the code from Crafty into C++. Because I only wanted to make a chessboard class for representation and move generation, I have tried to be selective. I have, however, encountered a puzzler. The Bitboard is, as expected, an unsigned __int64. Yet, the following code appears:

Code: Select all

Bitboard temp;
...
Bitboard abit = temp & -temp;

This should always be 1, since the minus sign will do nothing to the unsigned variable. Or have I missed something

Crafty is very, very difficult to tear apart, but I have trouble understanding some of the other engines...oh dear - maybe I will have to write one from scratch after all

[delcacho]

It will be 1 only if the original variable is not 0 to start with.

[Gerd Isenberg]

Code: Select all

Bitboard temp;
...
Bitboard abit = temp & -temp;

This should always be 1, since the minus sign will do nothing to the unsigned variable. Or have I missed something

Yes, unary minus applies the two's complement:

Code: Select all

-x == ~x + 1


which is guaranteed with unsigned types in C/C++.
-temp is equivalent to 0-temp, which also is the way to suppress compiler warnings. Thus, temp & -temp isolates the least significant one bit.
For bitboard basics have a look to the chess programming wiki:
http://chessprogramming.wikispaces.com/Bitboards
http://chessprogramming.wikispaces.com/ ... ions#toc79

Gerd

[H.G.Muller]

This should always be 1, since the minus sign will do nothing to the unsigned variable. Or have I missed something

Yes, you missed how arithmetic with unsigned variables is done. With the exception of right shifts, this is exactly the same as how it is done on signed variables. It is only that the result is interpreted differently when you use compares on them.

So for an unsigned byte x=1, -x would be equal to 255.

Plus you missed that the & operator is not a logical, but a bitwise AND. So the result of (tmp & tmp) is not always 1, but always tmp.

[John Digsby]

Yes - I actually ran the code independently and now see how it works. Very intriguing - I think I was put off by the compiler warnings that resulted from this code.

I have decided that if I want a bitboard engine, I shall probably write one from scratch. It might take some time, but I think I generally understand how they work. What would people recommend, rotated or magic bitboards?

[Ilari Pihlajisto]

What would people recommend, rotated or magic bitboards?

Magic is a lot easier to use, and gives pretty much the same performance as rotated bitboards. I just grabbed Pradu's magic bitboard source code (http://www.prism.gatech.edu/~gtg365v/Buzz/) and used it in Sloppy without even trying to understand how exactly the magic works.

[Tord Romstad]

What would people recommend, rotated or magic bitboards?

It doesn't really matter much, and whatever you choose, it is easy to change from one to the other after you have a working program. The main disadvantages of magic bitboards are that they consume rather much memory, that it takes slightly more work to implement them, and that unless you find a very efficient way to generate the "magic numbers", you'll probably have to clutter your code with some big and very ugly constant arrays. The main disadvantage of rotated bitboards is that they make it a little more awkward to generate X-ray attacks.

None of these disadvantages are likely to be very important in practice. Both techniques are fine.

Tord

[John Digsby]

Thank you all very much - I have begun coding a rotated bitboard engine from scratch. I suspect there will be more questions, however...