Piece List questions

[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(int i=0; i<board->plc[s][pce];++i)
    {
        if(board->pl[s][pce][i] == f)
        {
            board->pl[s][pce][i] = t; break;
        }
    }
}
extern inline void material_remove(SBoard *board, int pce, int s, int t)
{
    //plist
    for(int i=0; i<board->plc[s][pce];++i)
         {
           if(board->pl[s][pce][i] == t)
           {
           //piece at place i is dead - swap it with the piece on the end and reduce the count
            board->pl[s][pce][i] = board->pl[s][pce][board->plc[s][pce]-1];
            board->pl[s][pce][board->plc[s][pce]-1] = 0;
            board->plc[s][pce]--;
            break;
           }
         }
}
extern inline void material_add(SBoard *board, int pce, int s, int t)
{
       board->pl[s][pce][board->plc[s][pce]] = t;
       board->plc[s][pce]++;
}


extern inline void add_piece(SBoard *board, int pce, int s, int t)
{
       //plist
       board->pl[s][pce][board->plc[s][pce]] = t;
       board->plc[s][pce]++;
}

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