Piece List questions

[hMx]

Hi Andrew,

What you describe is nearly exactly how I do it in my problem solver "Chest".

The internal board could simply contain indeces into the piecelist array, so that when MakeMove moves a piece, you directly know which record in the piecelist to update. You move a pawn - easy - move the index in the interal board, and use that index to update the piecelist to reflect the new sq for the pawn. [side note: I am opting for now to use indeces rather than pointers, even though pointers are undoubtedly faster]

2 questions:

(1) how to handle captures? When undoing a capture move, how to know which index of the piecelist to use to restore the captured piece? My brain is fried, I can't think of an efficient way to do this...

I mark the entry as "unused" by storing a 0 as the position of the piece. I do NOT move down the other pieces in the piece list. That avoids changing the piecelist indexes stored in the board... and I have lots more of them than most everybody else.

It also avoids the problems with "undo" not exactly restoring the original piece list order (others explained that already).

(2) how to manage the piece list efficiently so that if side to move has only 3 pieces, you are looping 3 times in the piece list instead of 16?

thanks in advance...

I start with a compressed version (per side) and an additional (per side) number of initial slots used at most. You may compress your piece lists top level (between searches, not inside a search).

Scanning at most 15 unused slots does not sound THAT expensive to me.

[Steelman]

16-byte vector fits exactly in a SSE register.

I personally use two 16-byte vectors of piece squares as the primary board representation. I also need to keep redundant all_occupied_squares bitboard for Magic attack generation.

Regarding your questions:
1) I mark captured pieces as 0xff in piece-square vector. I do not undo, because it is cheaper to copy my 40-byte board representation. I do not have board-array at all. Piece-type information is handled separately, because it almost never changed (unless you have several queens or other non standard material after pawn promotion).

2) My attack tables return piece-vectors of pieces attacking a given square. When I need to enumerate piece-vector I mask off captured pieces with _mm_andnot SSE instruction then _mm_movemask instruction create a 16-bit set from my piece-vector register. Then I can bitscan the bitset.

So you do not have a board. You keep track of where the pieces are only. As a result you know where pieces are not. Yes. And getting attack info on any "square" gets cleaner.

A while back I was thinking of doing something similar. But move generation and positional score evaluation for me is a little easier if I have a board.

And you are a "bit player". I am not. Not sure I want to learn but I am interested. There would be a learning curve. Not sure I have time for it.

Thanks.

[Aleks Peshkov]

I suggested to use 16-byte piece-vectors for each separate side, because they are fast to update, to clone, and to iterate through, but only if you are ready to bother with SSE.

[AndrewShort]

well, I got the piece list implemented. my board array is now an array of indeces to a piece list array. Somewhat to my surprise, the engine is now only a litter faster, with regard to nps. I was hoping for a larger speed gain, since I used to blindly scan the board for pieces when generating moves.

would making it effectively an array of pointers give me substantially more speed? I suspect all the calls like PIECES(BOARD(sq)) are creating a lot of overhead... vb.net doesn't have pointers per se, but it has objects which are really pointers to chunks of memory.

[Laszlo Gaspar]

Hi all,

I rewrote my Java engine Timea to use piecelists. I thougth this is known theory but it was not mentioned so far so I share my solution with you. (It was also mentioned on CCC a few years ago, but I forgot the title of the referenced literature.)
I use a double linked list which is in fact an array of piece objects and the pointers (indeces) are bytes. These pointers are stored in the board[120] array and coded in the move structure as well. The Y piece have X = piece[Y].prev and Z = piece[Y].next indeces which show who are the previous and next pieces alive in the list (X and Z). When the Y piece is captured it is chained out from the list during a doMove() in the following way:

Code: Select all

piece[piece[Y].prev].next = piece[Y].next; // piece[X].next = Z 
piece[piece[Y].next].prev = piece[Y].prev; // piece[Z].prev = X

So now X and Z piece show to each other and Y is not in the list. Note that we didn't touch the Y piece object, so when the search returns back to this point to undo this move you still have the information in the Y piece object how to reconstruct the list (Y was stored int the move structure as captured piece):

Code: Select all

piece[piece[Y].prev].next = Y; // piece[X].next = Y 
piece[piece[Y].next].prev = Y; // piece[Z].prev = Y

The list is regenerated and Y is at the same place as it was earlier. This is possible because the list is in the same state as it was left at the time of deleting the Y piece from the list (and the board).

Is it a big overhead?

Best regards,
László

[smrf]

SMIRF does it in a comparable way, but internally more sophisticated. There is not necessary any overhead, e.g. see at:
http://www.talkchess.com/forum/viewtopi ... 54&t=20834

Nevertheless this is SMIRF's old approach and coming Octopus seems to become even more promising.

[Richard Allbert]

Hi,

Just read your post - I read Bob's paper also, and have just finished making Lime with rotated bitboards - it looks nothing like Crafty or any others, because I did it purely from the paper - a warning before you start...

it's ...
a. addictive
b. massively frustrating, especially getting the rotated parts correct - debugging is a minefield!

The currect version of Lime has an int board[144] structure - and the bitboard version is basically the same speed in perft and search, although I will add "gen_evasions" next, which will speed it up.

One slight disappointment was with evaluation - I expected the use of bitboard masks for pawns (e.g passed pawns) to be a lot faster, but it turns out to be the same as prefilling an array in the non bitboard version.

So I'm stuck with what to do - go ahead with the bitboard version or plod on with the standard array version....

Oh, and my piece lists at the moment look like this (non bitboard version):

Code: Select all

struct SBoard {
.........
 /*piece lists*/
      int pl[2][8][16];
      int plc[2][8];
.....
};

extern inline void material_move(SBoard *board, int pce, int s, int f, int t)
{
    //plist
    for&#40;int i=0; i<board->plc&#91;s&#93;&#91;pce&#93;;++i&#41;
    &#123;
        if&#40;board->pl&#91;s&#93;&#91;pce&#93;&#91;i&#93; == f&#41;
        &#123;
            board->pl&#91;s&#93;&#91;pce&#93;&#91;i&#93; = t; break;
        &#125;
    &#125;
&#125;
extern inline void material_remove&#40;SBoard *board, int pce, int s, int t&#41;
&#123;
    //plist
    for&#40;int i=0; i<board->plc&#91;s&#93;&#91;pce&#93;;++i&#41;
         &#123;
           if&#40;board->pl&#91;s&#93;&#91;pce&#93;&#91;i&#93; == t&#41;
           &#123;
           //piece at place i is dead - swap it with the piece on the end and reduce the count
            board->pl&#91;s&#93;&#91;pce&#93;&#91;i&#93; = board->pl&#91;s&#93;&#91;pce&#93;&#91;board->plc&#91;s&#93;&#91;pce&#93;-1&#93;;
            board->pl&#91;s&#93;&#91;pce&#93;&#91;board->plc&#91;s&#93;&#91;pce&#93;-1&#93; = 0;
            board->plc&#91;s&#93;&#91;pce&#93;--;
            break;
           &#125;
         &#125;
&#125;
extern inline void material_add&#40;SBoard *board, int pce, int s, int t&#41;
&#123;
       board->pl&#91;s&#93;&#91;pce&#93;&#91;board->plc&#91;s&#93;&#91;pce&#93;&#93; = t;
       board->plc&#91;s&#93;&#91;pce&#93;++;
&#125;


extern inline void add_piece&#40;SBoard *board, int pce, int s, int t&#41;
&#123;
       //plist
       board->pl&#91;s&#93;&#91;pce&#93;&#91;board->plc&#91;s&#93;&#91;pce&#93;&#93; = t;
       board->plc&#91;s&#93;&#91;pce&#93;++;
&#125;

This turned out faster than the current release which has all pieces in one list and sets dead pieces to 0.... counters are slao updated in the above functions as well.

Regards

Richard

[Richard Allbert]

Hi,

Just read your post - I read Bob's paper also, and have just finished making Lime with rotated bitboards - it looks nothing like Crafty or any others, because I did it purely from the paper - a warning before you start...

Regards

Richard

Of course, what I mean to add, was if you need the code from a complete beginner, just mail me

Richard