Piece-list representation

[Alessandro Scotti]

Hi folks,
I'm trying to compare these two kinds of piece-list:
1) all pieces in a single list;
2) separate lists for each piece type (knight, bishop, etc.).
I've no experience with this (Kiwi uses bitboards) and currently tend to favor #1 (packed into an array) because it's simpler. However, many strong engines are using #2. After reading many old posts from the CCC forum I've still a couple of questions for you guys, regardless which representation you are using:
- do you sometimes miss something the other representation has?
- are there points in the program where you could really say: "aha! do that with the *other* representation!" ?

[Reinhard Scharnagl]

SMIRF has two sorted piece lists. But they do not exist separated from the board representation.

Reinhard.

[Tord Romstad]

Hi folks,
I'm trying to compare these two kinds of piece-list:
1) all pieces in a single list;
2) separate lists for each piece type (knight, bishop, etc.).
I've no experience with this (Kiwi uses bitboards) and currently tend to favor #1 (packed into an array) because it's simpler. However, many strong engines are using #2. After reading many old posts from the CCC forum I've still a couple of questions for you guys, regardless which representation you are using:
- do you sometimes miss something the other representation has?
- are there points in the program where you could really say: "aha! do that with the *other* representation!" ?

I use a hybrid approach: I have a single piece list for each side, but the pieces of the same type are stored in adjacent entries in the list. This makes it easy to loop through all squares occupied by white pieces, and equally easy to loop through only the squares occupied by white bishops. So far, I haven't found any disadvantages of this representation.

Tord

[Uri Blass]

Hi folks,
I'm trying to compare these two kinds of piece-list:
1) all pieces in a single list;
2) separate lists for each piece type (knight, bishop, etc.).
I've no experience with this (Kiwi uses bitboards) and currently tend to favor #1 (packed into an array) because it's simpler. However, many strong engines are using #2. After reading many old posts from the CCC forum I've still a couple of questions for you guys, regardless which representation you are using:
- do you sometimes miss something the other representation has?
- are there points in the program where you could really say: "aha! do that with the *other* representation!" ?

Movei is not a strong engine but it use seperate list for each piece type.
I thought that 2 is simpler.

[Anonymous]

How do you keep the piece lists sorted in case of promotion and in case or reinserting a captured piece when undoing the move? To me it looks, as this would need quite a bit of overhead (perhaps not so much in terms of processing power, but in program complexity).

Regards,
Dieter

[Pallav Nawani]

Hi folks,
I'm trying to compare these two kinds of piece-list:
1) all pieces in a single list;
2) separate lists for each piece type (knight, bishop, etc.).
I've no experience with this (Kiwi uses bitboards) and currently tend to favor #1 (packed into an array) because it's simpler. However, many strong engines are using #2. After reading many old posts from the CCC forum I've still a couple of questions for you guys, regardless which representation you are using:
- do you sometimes miss something the other representation has?
- are there points in the program where you could really say: "aha! do that with the *other* representation!" ?

In Current version (v0.12) of Natwarlal:
(a) I use an array of size 16 for for storing pieces, one for each side.

Advantages:
Faster and simpler make move/ unmake move. When a piece is captured, I let the array slot remain as it is, I just change the piece type to PNONE. when I unmake the move, I simply change the piece type back to what it originally was. Similarly, making & unmaking pawn promotions etc is easy.

Edit: Also, this method of storing pieces lead to deterministic move generation. Whatever be the order of piece captures/moves be, when you unmake the moves, they end up in exactly the same location in the array. (I recalled this after seeing Dieters post, he seems to have written his post even as I was typing mine).

Disadvantages:
I have to loop over the whole array to generate moves, and I have to do the same thing in evaluation. when evaluating pawns, I have to loop over the array (again) and separate out the pawns. Because of this, I believe this data structure is slower overall. Probably much slower.

I now think that having a separate piece list for different pieces would be better.

Pallav

[Reinhard Scharnagl]

To me it looks, as this would need quite a bit of overhead

Well, there is some overhead, but it is very performance enhancing e.g. to seperate pawns from other pieces types, or to be able to process each color separatedly.

In SMIRF every piece on the board simultaneously is a member of a double linked list, though being represented within a single int sized data element.

Reinhard.

[Sune Fischer]

Why not make a 2D array, won't that accomplish both?

Use the first index to loop the type of piece and the second index to loop pieces of that type.

Maybe even a 3D with first being the color?

BTW how does a piece list work, when a piece is captured is the list rearanged to close the hole?

-S[/code]

[Reinhard Scharnagl]

Why not make a 2D array, won't that accomplish both?

No that list is not to be used (iterated) continuosly with speed.

BTW how does a piece list work, when a piece is captured is the list rearanged to close the hole?

like usual in a double linked list.

Reinhard.

[Anonymous]

Why not make a 2D array, won't that accomplish both?

Use the first index to loop the type of piece and the second index to loop pieces of that type.

Maybe even a 3D with first being the color?

BTW how does a piece list work, when a piece is captured is the list rearanged to close the hole?

With a 2d array you have 2 loops instead of one loop at typical places, like movegeneration and evaluation. I never tried it, but I guess, it could be some significant overhead in late endgame.

With the typical piece_list a typical inner loop can look like

Code: Select all

   unsigned *pl = piece_list[stm][num_pieces[stm]];
   do
   {
     sq = *--pl;
     piece = board[sq];
    ...
   }
   while (piece != KING); /* Assume King is always at the start */


Note that very few variables will be needed. With a 2d array, you'd need quite a bit more code and variables. For my engine at the moment, the additional information available would not buy much. But this may well be, because much of the code is tuned around the data structures used. If I had that information availalbe, I'd probably code things a bit differently (and I am currently thinking about doing so).

To fill the gap left by a captured piece, just fill in the last piece of the list and decrement num_pieces[side].

Cheers,
Dieter

[Alessandro Scotti]

I'm now considering using a double linked list where each piece belongs to two lists: a list of pieces of same color, and a list of pieces of same color and type.
The latter allows me to easily iterate thru, say, all white knights. For what I could see in Kiwi, this is only useful during evaluation. When I tried switching from a series of separate loops for each piece type to one big loop over all pieces plus a switch statement, I got a huge slowdown. I suspect that jumping up and down over large pieces of code is not friendly to the CPU. Clearly, Fruit gets easily away with that. However, IIRC Fruit evaluates just one feature at a time, so the loops remain relatively short and tight... Just guesses, I'd like to hear from some CPU expert on this matter.
There is maybe another advantage in using double links, where it's possible to add another piece list in the future to "capture" some interesting property (e.g. the pieces that can attack the opponent king or who knows what else) by simply adding a couple of links to the piece structure. Probably useless, but who knows what kind of things one is going to try?

[Alessandro Scotti]

To fill the gap left by a captured piece, just fill in the last piece of the list and decrement num_pieces[side].

Hi Dieter,
that's how I would do it but I have a doubt... is it important to restore the exact list when undoing or is it enough to append the restored piece at the end of the list? I think there's no difference functionally, but maybe the "full restore" approach would be easier to debug...

[Anonymous]

Alessandro, I think we already discussed the "exact restore" vs. "functional equivalent restore" of the piece lists. I agree, that the later might make debugging a bit more difficult at places. Not so much for debugging move-generation and make/unmakemove functions (where for debugging easily some slow "check all datastructures from scratch" code can be plugged in); but perhaps because it can change the move ordering and therefor the search tree.

I am a bit surprised, that your switch slowed down the code considerably. But your explanation may well be correct, especially when the cases in the switch are very huge. Do you have contigous pieces (like pawn=1, knight = 2, bishop=3, ...) or rather pawn=1, knight=2, bishop=4, rook=8, ... ? The later will make switches less efficient.

For lager code chunks, I typically use function pointers, like

Code: Select all

typedef score_t (*score_func)(int, int);
static score_func score_func_array[8] =
{
  NULL,
  score_pawn,
  score_knight,
  score_bishop,
  score_rook,
  score_queen,
  score_king,
  NULL
};

   unsigned *pl = piece_list[stm][num_pieces[stm]];
   do
   {
     sq = *--pl;
     piece = board[sq];
     /* instead of switch */
     score += (score_func_array[piece])(stm, sq);
   }
   while (piece != KING); /* Assume King is always at the start */
   /* And a similar loop for the other side. Alternative would be an
       outer loop over color and a branch for the sign of the score. */


For move generation, however, I use the switch approach. There the cases have relatively little code, and the switch was faster, than the function pointer approach.

Cheers,
Dieter

[Sune Fischer]

With a 2d array you have 2 loops instead of one loop at typical places, like movegeneration and evaluation. I never tried it, but I guess, it could be some significant overhead in late endgame.

Well I wouldn't suggest to loop over the entire 6x10 array. With a counter for each type of piece one would need max 5 redundant tests if the king is all alone.
In return there is no need for a switch.

Note that very few variables will be needed. With a 2d array, you'd need quite a bit more code and variables. For my engine at the moment, the additional information available would not buy much. But this may well be, because much of the code is tuned around the data structures used. If I had that information availalbe, I'd probably code things a bit differently (and I am currently thinking about doing so).

To fill the gap left by a captured piece, just fill in the last piece of the list and decrement num_pieces[side].

Few variables may be needed, but then how do you quickly find e.g. the rooks if you need them for some eval or extension term?

I thought quickly locating the pieces was the main idea in using a piecelist. If it's a matter of reducing variables then the piece list can be discarded completely if there is already a "board".

Smart bookkeeping is quite a challenge

-S

[Tord Romstad]

With a 2d array you have 2 loops instead of one loop at typical places, like movegeneration and evaluation. I never tried it, but I guess, it could be some significant overhead in late endgame.

Well I wouldn't suggest to loop over the entire 6x10 array. With a counter for each type of piece one would need max 5 redundant tests if the king is all alone.

I still don't see what is wrong with a single list with pieces of the same type in adjacent entries, like in my program. The code is simple, the overhead is insignificant, and I can choose to loop through just a single piece type or all pieces of one colour, depending on what is most useful in the situation at hand. What would I gain by using a 2d array?

Tord

[Sune Fischer]

Hi Tord

I'm not a piecelist guy, but how do exactly do you mean, is it a list like

A="kqrbbnppp" or
B="k00000q00000r000000bb000000..." or
C="kpnbqppprb"?

I see it like
A compact and ordered. Quick to navigate and use but how do you keep it sorted when adding and removing pieces?

B is a 2D design, ordering is automatic but there are spaces and so jumps are required making it ideal for a double loop and no switch.

C is compact and unsorted. Needs a switch and a search every time.

Isn't those the 3 main choices?
Am I missing something?

-S

[Anonymous]

A="kqrbbnppp" or

A compact and ordered. Quick to navigate and use but how do you keep it sorted when adding and removing pieces?

I asked the same question. I can see two methods. Having pointers to the start of qs, rs, etc. When removing a piece, adjust the pointers and memmove everything after the removed piece one to the front. Or instead of pointers, keep track of the number of individual pieces.

Another method could be to use a linked list, again with some pointers to the individual piece list heads.

I guess I missed some more efficient methods.

I wonder why Reinhard is using doubly linked lists instead of single linked lists?

If code often needs to look for individual piece types, it might be worth to have them as bitboards instead. One would not need to have a bitboard movegenerator as well. My engine at the moment does this for pawns.

Dieter

[Reinhard Scharnagl]

I wonder why Reinhard is using doubly linked lists instead of single linked lists

Such a list could be easier sorted. Think e.g. of performing a promotion move. The lists also are used during tests for check threats and move generation. In some situation an inverse iterating through the pieces is helpful, too.

I do not use bitboards. Instead my pieces have bit encoded properties inside. You see, I might have an unusual board representation in SMIRF.

Having an sequential move generator demands to restore such lists 100% after undoing a capture or promotion move. Having an en-block generator merely demands to have always sorted lists.

Reinhard.

[Sune Fischer]

Yes that's the thing with bitboard piecelist, if you need all the pieces (as in move gen) then there is not much gain.
It's only if you are looking for a subset of pieces with some common property, ie. pawns on 7th...

Is it worth while to make a hybrid?
It probably is speedwise, but the complexity of it scares me some.

-S

[Tord Romstad]

Hi Tord

I'm not a piecelist guy, but how do exactly do you mean, is it a list like

A="kqrbbnppp" or
B="k00000q00000r000000bb000000..." or
C="kpnbqppprb"?

Like A, or at least almost. I have a "hole" in the piece list before each piece type, in order to facilitate inserting and removing pieces to the list. Theoretically this gives some extra overhead when looping through all pieces in positions with few pieces left on the board, but in practise I haven't found it to be noticable. And if I ever encounter some place in my code where this turns out to be a serious bottleneck, I can simply replace the loop through all pieces with one loop for each piece type.

Tord