finding where pieces are in eval()?

[cyberfish]

Hi,
I am having some difficulties improving my eval() in my new engine.

I used to only have material + piece square and everything was fine because I can do all that incrementally in making/unmaking functions. (~1e6 nps)

However, I am trying to improve it and am running into some difficulties - how do I find where the pieces are? Looping through the mailbox drags the performance down to ~2e5 (1/5 the original speed). At that speed it even loses against the old version due to reduced search depth, despite having a better eval(). Also, that would defeat the purpose of incrementally updating the material score I presume.

My engine has both bitboards and mailbox. Move generation is done by rotated bitboards and the mailbox is just for fast lookup.

Thanks.

[mjlef]

In NOW, I keep a list of indexes for each side. The indexes point to the location of each piece. It is a little work to update the indexes as pices are exchanged. When I do this I always keep the list as small as possible, and so move indexes into the open space of a deleted piece.

My current scheme is this:

windex [1..16]: integer; (sorry this is pascal code!}

it is arranged as follows:
windex[1][ always points to the king's location
windex[2]...windex[n] points to pieces
from windex[n+1]..windex[n2] points to pawns

so windex would in the opening point to pieces like this:
KQRRBBNNPPPPPPPP

if say a pawn is captured, it updates the indexes, and moves things around to keep the array small. I also have an index for the board that points back to the array element in windex. so for example the white pawn on e2 might point to windex[10]. This lets me quickly update the indexes.

some programs just maintain lists for each piece type, or use functions to get the piece location from the bitmaps (find first bit type functions).

I hope this helps.

Mark

[gladius]

There are a few different ways of doing it.

You can keep a piece-list incrementally, so you can do something like:

Code: Select all

for &#40;int i = 0; i < position.GetPieceCount&#40;Knight&#41;; i++) &#123;
   Square square = position.GetPieceSquare&#40;Knight, i&#41;;
   // do calculations for knight...
&#125;

The piece list can be updated quickly in the make/unmake.

Alternatively, if you have bitboards by piece type, you can do something very similar to move generation to get the squares of the pieces.

Code: Select all

Bitboard knightsBB = position.GetPieceBitboard(White, Knight);
while (knightsBB) {
 Square square = GetFirstSetBit(knightsBB);
 knightsBB &= knightsBB - 1;
 // do calculations for knight...
}

Either method is quite fast (although the piece list seems to be slightly faster for me - even including overhead for updating during make/unmake), and will certainly be faster than looping over all 64 squares of the board, using a switch at each square to determine the piece type there.

[Roman Hartmann]

Hi,
I had that problem too quite some time ago.

You could add a piece list and then you will only have to loop through the piece list instead of the whole board. The piece list can be updated incrementally when making/unmaking moves like you're already doing with material. To avoid looping through the piece list when deleting/restoring a piece I have a 2nd board where I store the array-adress of the piece.

best regards
Roman

[Dann Corbit]

Hi,
I am having some difficulties improving my eval() in my new engine.

I used to only have material + piece square and everything was fine because I can do all that incrementally in making/unmaking functions. (~1e6 nps)

However, I am trying to improve it and am running into some difficulties - how do I find where the pieces are? Looping through the mailbox drags the performance down to ~2e5 (1/5 the original speed). At that speed it even loses against the old version due to reduced search depth, despite having a better eval(). Also, that would defeat the purpose of incrementally updating the material score I presume.

My engine has both bitboards and mailbox. Move generation is done by rotated bitboards and the mailbox is just for fast lookup.

Thanks.

If you have bitboards, then you can find where your chessmen are by:
1. Make a copy of the bitboard of type <piece_type>
2. GetAndClearFirstBit() from your copy of the bitboard.
3. Repeat step 2 until the bitboard copy is empty.

[Guetti]

If you have bitboards, then you can find where your chessmen are by:
1. Make a copy of the bitboard of type <piece_type>
2. GetAndClearFirstBit() from your copy of the bitboard.
3. Repeat step 2 until the bitboard copy is empty.

I always thought Bitscanning is quite slow, so this would still be a time consuming operation, would it not?

- Andy

[Uri Blass]

If you have bitboards, then you can find where your chessmen are by:
1. Make a copy of the bitboard of type <piece_type>
2. GetAndClearFirstBit() from your copy of the bitboard.
3. Repeat step 2 until the bitboard copy is empty.

I always thought Bitscanning is quite slow, so this would still be a time consuming operation, would it not?

- Andy

I guess that it is not slow because strelka does it and strelka is a fast searcher.

Uri

[hgm]

Bitscanning is quite slow: it neads multiple instructions to extract the square number of the next piece. For a piece list this is just a single memory load from the list.

The disadvantage is that a list might have holes, because pieces get captured. So if you organize it as a table, you would have to test if the square number is valid, and occasionally it won't be valid. This might cause mispredictions. But as a piece that is captured will remain so for the entire subtree below it, in practice these branches are not so difficult to predict.

The alternative would be to make it a doubly-linked list, so that you can cheaply remove a piece (temporarily) in the search. (In any case you would squeeze out any holes in the root.) But this makes it more difficult to find a particular piece in the list: very often you want to do things with only Pawns, or only Sliders, and with linked lists it would be more difficult to find them in the list. So for me, a plain table (with occasional holes) worked best. Following links has a much longer critical (latency) path than scanning through an array, as you cannot start fetching the next link before you have completed fetching the previous one. And even for the L1 cache fetching for the purpose of generating a new address has a latency of 4 clocks (I think). Generating new addresses through increment only takes a single clock.

[Alessandro Scotti]

I use double linked lists in Hamsters, where every piece is linked both to a "by side" list (black, white) and to a "by type" list (pawn, knight, etc. of same color).
It's probably not the fastest way but it's good enough and at least I can understand it!

[hgm]

I got rid of the links when it turned out thet just slowed matters down. I had not expected this, but branch-prediction logic on modern CPUs is so good that it hardly hurts to put an "if(position[piece] < 0) continue;" everywhere you would like to to something with the piece.

(It was a pain, though, when I had to change position[] from being a (char) to being an (unsigned char), which I had to do when converting to a 10x8 board, as I needed the extra square numbers... Took me a long time before I had changed it everywhere to "if(position[piece] == 0xFF) continue;". And it invariably crashed sooner or later when I had overlooked even a single one.)

I effectively have 6 tables, organized as stacks, 3 for each color: leapers, sliders and pawns, where the King is always the first entry of the leaper list (and the rest are Knights).