Piece List questions

[AndrewShort]

My internal board is a 1d array of 120 elements (the classic border square array), but when I generate moves for the side to move, I would like to loop over a separate piece list of at most 16 pieces, and less as the game goes on.

Seems one could implement a piece list as a single 1d array of 32 records, the first 16 records reserved for White and the last 16 records reserved for Black. In fact the 1st element could always be White's King, and the 17th element always Black's King, as they are never removed. A record would contain the piece (which, in my case, is an unsigned integer containing bits for color and piece type), and the square (which, in my case, would be an integer ranging from 21 to 98).

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...

(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...

[plattyaj]

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...

(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...

In Schola I store the index and the captured piece in the structure used to undo a move. Perhaps there's a more efficient way but it seems fine to me.

I keep the number of active pieces in the board position but I don't update that when making / unmaking a move (except when doing the final move update). I simply mark the piece as DEAD when I make a capture move. Obviously if you have a long sequence of captures as you search this will become less efficient but it's simpler and probably as efficient as re-sorting the piece index each time you make or unmake a capture.

The code's on my website if you want to take a quick look - see moves.c.

Andy.

[bob]

My internal board is a 1d array of 120 elements (the classic border square array), but when I generate moves for the side to move, I would like to loop over a separate piece list of at most 16 pieces, and less as the game goes on.

Seems one could implement a piece list as a single 1d array of 32 records, the first 16 records reserved for White and the last 16 records reserved for Black. In fact the 1st element could always be White's King, and the 17th element always Black's King, as they are never removed. A record would contain the piece (which, in my case, is an unsigned integer containing bits for color and piece type), and the square (which, in my case, would be an integer ranging from 21 to 98).

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...

(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...

We did a similar approach in Cray Blitz. When you zap an entry when capturing, use two arrays that behave like stacks. Push the list index on one, and the entry being removed on the other. then it is easy to undo the removal since you have both the index and the value that should go there.

At the beginning of the search, "collapse" the list. During the search, you will have to step over the 0 entries, but after making a real move on the board, collapse the list and have some sort of counter that tells you how many entries are in the list.

[sje]

Be careful with piece lists. Unless every capture is reversible with respect to piece vector indices, the program can undo a variation and come up with a piece vector with differently ordered entries. This can lead to a bit of determinism as it influences the order of generated moves.

[Steelman]

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...

(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...

In Schola I store the index and the captured piece in the structure used to undo a move. Perhaps there's a more efficient way but it seems fine to me.

I keep the number of active pieces in the board position but I don't update that when making / unmaking a move (except when doing the final move update). I simply mark the piece as DEAD when I make a capture move. Obviously if you have a long sequence of captures as you search this will become less efficient but it's simpler and probably as efficient as re-sorting the piece index each time you make or unmake a capture.

The code's on my website if you want to take a quick look - see moves.c.

Andy.

Interesting you had the very same question I had when I re-wrote my program last year. My board is a array of 120 structure pointers. I have 2 piece lists, one for the white pieces and one for the black. These piece structures are a single linked list of 16 elements. And the kings are stored at the start of both lists. Actually on the start up of a game or maybe a test position these two lists are initilized to the exact quantity of pieces in the position. I can handle up to a total of 64 pieces total if I needed to?

My first thought was as a piece was exchanged in makemove I would delete the piece from the list and store the piece pointer in the move tree. But to remove the piece pointer from the single linked list I would need the previous piece pointer as well as the next piece pointer. But a single linked list does not have the previous pointer available. I would then need to store that previous pointer value somewhere. Thats the first problem!
Then in undomove I could simply put the piece pointer back into the list of piece after the king location in the list. But as Steven indicates in his reply that may cause a problem because the piece list order is being changed at every exchange. That could be another problem?! What seemed to be simple at first was getting complicated!

Ok - How about a double linked list approch. Well the previous pointer problem is solved but now I have more links to break and reconnect. More overhead! And I still have the piece list order being changed.

Well I ended up doing very close to what Andy and Bob indicates. Zero the piece value in the list and when the time comes to undo it put the piece value back in the piece list. Then when my program makes the best move then delete the piece pointer link from the list.

Does anyone actually delete pieces from piece lists and put them back during the main search? How? Seemed to me the extra overhead negated the advantage of having a shorter piece list. But I never did experiment with that approach so I really am not sure.

PS: Bob Hyatt's paper on "Chess program board representations" is very good and you should look it up. Thanks Bob. Very helpful to me!
The next giant step would be to go the "bitboard" approach. At my age (54) learning bitboards is something I am not sure I want to get into. But it is the way to go if you get serious about chess programming.

[Aleks Peshkov]

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.

[Daniel Shawul]

Exactly. I had the same problem which took me a day of debugging to find out that my make-unmake does not actually restore the previous board position. After that I fixed the unmake to output the pieces and pawns in the same order as they were before the capture/promotion.

Daniel

[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.