crazyhouse promotions

[kbhearn]

small corrections to xor:
you don't need a key for 0 holding of each type (it can be chosen to be zero) so my numbers were a bit high there

addition/subtraction doesn't save ops because there's no need to xor off the key for holding 2 when you move to holding 3 (since you always move through 2 to get to 3 the 'true' key for 3 knights held by white can be key[white][holding1knight]^key[white][holding2knight]^key[white][holding3knight] which gives xor the same single operation for a drop or capture so addition/subtraction is only saving you the quantity of keys you need - but if you're already saving keys by using shifted/rotated versions of fewer keys it may not mix well that way.

[Evert]

I am not sure how a piece list comes in to this.

I figured promoted pieces would have their own index range.

So it would either have to be variable-length, or it would be on average half-empty, not much better than scanning a board that on average is 3/4 empty. Perhaps using white and black 'bitrank' occupancy variables might give a slight speedup. But that is only a micro-optimization.

Right, I had in mind a bitmask to indicate whether an entry is used or not.
I always use those, they also allow for neat bitboard-like tricks if you want to selictively do things with a subset of pieces.

[Evert]

or... you can do it with just one zobrist key for each piece type/color and addition/subtraction method instead which would save a few (possibly irrelevant) ops and keys (i.e. zobristHoldings = sum over all colorpieces(keyHoldings[colorpiece]*countHoldings[colorpiece]) which can be incrementally updated with a single addition/subtraction as a piece gets captured or dropped)

Note that one should not mix the two approaches: if you track holdings by addition, you should do the same for the board state. Unless youhave separate keys for those, which might be good anyway: it allows you to catch pseudo repeats, where the board position is the same but the hand material is not. If one side is leaking material to the other side, then you could simply fail low without examining this node (there's no way this node can be an improvement).

[hgm]

I always use additive Zobrist keys, to keep things simple. Then I don't have to do anything special for moves that start from a holdings square, and the incremental update of the key always is

key += Zobrist[toPiece][toSquare] - Zobrist[fromPiece][fromSquare] - Zobrist[victim][captureSquare];

and a similar expression for the PST evaluation.

Note that for repetition detection it is important to also detect pseudo-repeats, where the board is the same, but the hands are different. For this reason I keep the low 32 bits of the Zobrist keys of hand-squares zero,and use those bits of the total key for repetition detection. The table of visited positions then contains both this part of the hash key and the PST evaluation. When you find a key match you can then figure out from the PST eval if it is a true repeat or a pseudo-repeat, and take the appropriate action depending on that (e.g. return a draw score for a true repeat, and a loss score for a pseudo-repeat with fewer pieces in hand).

BTW, when the number of piece types gets large, I usually synthesize the Zobrist keys on the fly, as the product of a piece key and a square key:

Zobrist(pieceType, square) = pieceKey[pieceType]*squareKey[square]

To make the resulting keys more random, I initialize the pieceKeys and squareKeys as ~(rand()*rand()), to reduce the number of trailing zeros (which would concatenate on taking the product).

[hgm]

Right, I had in mind a bitmask to indicate whether an entry is used or not.
I always use those, they also allow for neat bitboard-like tricks if you want to selictively do things with a subset of pieces.

Indeed, that would be a possible solution. Extracting bits from a word is not a very cheap process, though (and you have to update the mask as well), and I am not sure that for a half-empty list it would save you anything. These kind of tricks start to pay off only for sparsely populated arrays,

[Evert]

a very cheap process, though (and you have to update the mask as well), and I am not sure that for a half-empty list it would save you anything. These kind of tricks start to pay off only for sparsely populated arrays,

Actually, you can avoid bitscan entirely if you just test if the current bit is set or not at the top of the loop. This is equivalent to testing if an entry is present in the list or not, but doesn't require a memory access. Updating the mask can probably be done in parallel to another instruction (for free), but I never checked this.
You can start at the lsb set by doing a single bitscan at the beginning of the loop, but wheter that's useful or not depends on ow you map piece types to indices (if the king is low in the list, this initial bitscan is pointless).
Whether it pays off or not depends on how sparse the list is versus how crowded the board is. I've never done a holdings-type game with mailbox; my only mailbox programs are for Grande-Acedrex and Xiangqi, which have sparsely populated boards.

[hgm]

Usually instructions can be executed in parallel with others anyway.

I wonder if an old-fashioned doubly-linked list couldn't be a good solution for this, if you don't care much about the order in which you generate moves. Updating the list is not terriby expensive: two loads and stores to unlink the captured piece. And when it gets dropped, just insert it at the start of the list, after saving the old pointer values. Stepping along the links is very brach-friendly. But it creates a very long dependency chain of 4-cycle-latency instructions, which could hurt if you don't need to do much per piece. (Move generation could be complex enough to keep it busy until the next piece in line is known, though.)

Actually the intermediate sparsity of the list can be avoided by re-creating a 'piece stack' before every search: assign new, contiguous numbers to the pieces of each side that are on the board. Add pieces that are dropped during the search at the end, and mark captured pieces as not present. The number of 'holes' in the list will never grow very large, due to the limited search depth, and the fact that not every move is a capture. You can then simply step through the list, and skip the few slots marked as captured. In fact, when you mark a piece as 'captured' by changing its type to a dummy type that has no moves, this does not even require an explicit branch.

You would have to assign a new piece number to every dropped piece, but even with 8-bit encoding you would probably have enough numbers available to still assign them in such a way that the number immediately reveals the color (e.g. white = 64-127, black = 128-191, off-board = 192-255). And it saves you the drudgery of remembering piece numbers for pieces that are in hand.

[zenpawn]

similarly the extra piece types are again just extra zobrist keys - technically you could get away with just 64 more zobrist keys (one per square) that says 'the piece on this square is a promoted pawn' - but maybe you want 8*64 for white-knight-promoted-from-pawn etc for simplicity's sake.

Since I'm currently going down the path of option #1 in my OP, I'm wondering if it would be sufficient to XOR in that bitboard versus having 64 different random numbers. If so, the reserves could likewise be converted into a single 64-bit # to XOR in.

[hgm]

It should be easy to represent the holdings by a single 64-bit quantity: just use a packed array of counters. (Whether that can be efficiently updated is another matter.) You ca at most have 16 P, 4 N,B or R and 2Q in hand, so three 3-bit counters, one 2-bit counter and one 5-bit counter per color would suffice. That is only 16-bits per color.

Note that you cannot simply XOR this quantity itselfinto the key if you are already doing that for the 'isPromoted' bitboard; the holdings patterns would often also occur as isPromoted patterns,for positions with few pieces in hand and few pieces promoted. So it would enormously drive up the number of key collisions.

You can multiply the isPromoted bitboard and the packedholdings with different constants before XOR'ing them into the key. I do something like that for the castling-rights and side-to-move state in CrazyWa:

index = hashKey + (stm + 9849 + castlingRights)*(epSqr + 51451) & hashMask;

where 'castlingRights' is a number 0-15 (one bit for each castling), and stmis 32 or 64.