Project help required: Bitboard Fruit 2.1

[Mincho Georgiev]

I've done this before, as I believe, many others here, not with fruit though. I second Bob. In my experience, the best, and the right way to do it is to follow the stages that you normally will when you writing a new program from scratch. Like: 1. you writing brand new move generator - rotated or magics based with OWN board structure and not necessarily the same members of it's representation, use bitboard related by taste and optimization requirements. Debug it completely and independently. 2. Write a VERY simple search module, and empty evaluation in order to drive on the search /which is only a skeleton too to avoid bugs until evaluation is complete/. 3. Translate the entire evaluation of the mailbox program regarding the new board representation and 3a. Do the latter the bitboard way - eliminate every mailbox approach in the evaluation if you make sure that the bitboard one is faster. After the evaluation is completely debugged, you can start writing the search to the stage, that allows testing. 4. Use testing and simultaneously completing the search until the program is ready - confirmed by the testing results and speedup.
Just my 5 cents, don't take it as an imposition of some kind.

[hgm]

HG, what happens if the blue queen checks both kings at the same time?

Same thing, I guess, as in any position where you check both kings at the same time: You are not allowed to go there. Moves leading to it would be illegal moves, because they apparently leave your own King in check.

[Sven]

My experience doing EXACTLY this project (Cray Blitz -> Crafty) says this is the wrong way to do it. You end up debugging code that is going to be thrown away. You first map from 0-63 to 0-127, and then you still have to change the eval and debug it. There are ways of testing the move generator without any eval or search whatsoever. First thing I wrote in Crafty was the move generator. I went no further until it was working correctly.

I suppose one can develop however they want, I'm old enough that I don't want to waste ANY time, for obvious reasons -- one is there is not that much time left to waste.

What is wrong for you is not necessarily wrong for others. In the given case, adding bitboard code to Fruit does not imply "debugging code that is going to be thrown away". Such code would be part of the original Fruit code (mailbox) which we certainly may assume to be sufficiently debugged.

The strategy chosen here is one of several valid ways in my opinion, whether you like it or not. Please be aware that this is an "experimental" and "learning" project, not necessarily a "writing a new world class engine" project. As soon as move generation, eval and search are changed such that they no longer use the mailbox board apart from looking up the piece type on an occupied square (which could be done with bitboards as well but is probably a tiny bit faster with a redundant mailbox board), the 16x16 mailbox board can be replaced by a simple 8x8 board, and a lot of unused original Fruit mailbox code can go away. Doing it step by step while keeping the whole program's functionality intact at any time is something I would always recommend, for virtually all kinds of software, when doing a "translation" or "port". Obviously you won't do it like that when you write something completely new, but that is not the given situation.

Most of this translation is merely technical. The interesting part, of course, is to rewrite the evaluation such that it really takes advantage of the bitboard data structures.

Finally, nobody wants you to waste your precious time for that. But in that case I propose not to say "that' wrong what you do" to someone else even though you appear to be not much interested in that project. The other option would be to let others make their own experiences.

Sven

[hgm]

Just wondering: is there any reason why 0-63 square numbering would be better than 0x88 numbering, when using bitboards? When I would do a project like this (where old and new structures have to coexist during a transient period) I would try to keep the original structure as much as possible. It seems the square numbers in the bitboard code are only used to index tables of bitboards, and the tables could be given size 128 as easily as size 64. If you are worried about the unused elements of the 0x88 boards spoiling cache efficiency (which I am not sure the Fruit mailbox code does to begin with), you can always interleave different tables (using a "#define table2 (table1+8)").

[Mincho Georgiev]

You will have to convert each and every single square masking for one.
Not to mention that you have to convert every square to table index, because you WILL use mask tables, otherwise, why would you need bitboards at all.

[Sven]

Just wondering: is there any reason why 0-63 square numbering would be better than 0x88 numbering, when using bitboards? When I would do a project like this (where old and new structures have to coexist during a transient period) I would try to keep the original structure as much as possible. It seems the square numbers in the bitboard code are only used to index tables of bitboards, and the tables could be given size 128 as easily as size 64. If you are worried about the unused elements of the 0x88 boards spoiling cache efficiency (which I am not sure the Fruit mailbox code does to begin with), you can always interleave different tables (using a "#define table2 (table1+8)").

It is much easier to use the position of a bit in a 64 bit number directly as the square number, than to map it to a 0..127 or (in case of Fruit which has a 16x16 mailbox board where valid file and rank numbers are in the range 0x4..0xB) to a 0..255 square number. So it is not all about table indexing only.

In the given project, the coexistence of 0..63 and 0..255 square numbers is probably only an intermediate state, at least that is my assumption (Matthew knows better of course).

Sven

[hgm]

It is much easier to use the position of a bit in a 64 bit number directly as the square number, than to map it to a 0..127 or (in case of Fruit which has a 16x16 mailbox board where valid file and rank numbers are in the range 0x4..0xB) to a 0..255 square number. So it is not all about table indexing only.

I don't get that. The square numbers come all from a table lookup, squareNr[bitboard*DEBRUIN>>58], don't they? And you could fill the table with anything you want.

[Sven]

It is much easier to use the position of a bit in a 64 bit number directly as the square number, than to map it to a 0..127 or (in case of Fruit which has a 16x16 mailbox board where valid file and rank numbers are in the range 0x4..0xB) to a 0..255 square number. So it is not all about table indexing only.

I don't get that. The square numbers come all from a table lookup, squareNr[bitboard*DEBRUIN>>58], don't they? And you could fill the table with anything you want.

No, in both move generator and evaluation it also happens frequently that you scan a bitboard to find all set bits, like in this example:

Code: Select all

uint64 bbMyRooks = board->bbRooks() & board->bbColour(me);
while (bbMyRooks) {
    int sq = popLSB(&bbMyRooks);
    GEN_ROOK_MOVES_FROM(sq, me, board->bbOccupied());
}

where popLSB() removes the LSB from the given non-zero bitboard passed as argument and returns its bit position. Here the origin of a square number is a bit position.

Sven

[hgm]

Code: Select all

int
popLSB(Bitboard *b)
{
  Bitboard s = *b & -*b;
  *b &= ~s;
  return squareNr[s*DEBRUIN>>58];
}

Right?

[Sven]

Code: Select all

int
popLSB(Bitboard *b)
{
  Bitboard s = *b & -*b;
  *b &= ~s;
  return squareNr[s*DEBRUIN>>58];
}

Right?

I see what you mean.

I have never tried to put something different from 0..63 into such a squareNr[] array, so I cannot say it would not work. You may be right.

But who would actually do so? And what if some other approach than using that squareNr[] array is in use?

Sven