BertTuyt wrote:Joost, maybe I missed the explanation in a previous post, but how are you able to include the whole move in 44 bits (only)?
One of the things I (related to different move format) I still want to test, is to include the move into 64 bits, by combing the new position Bitboards into 1 Bitboard ( so bbMove = bbWhitePiece | bbBlackPiece ).
With (to my knowledge) 2 disadvantages if in a capture the from and to square are the same (but that is also the case in my current implementation, where I only store bitboards) you can not extract the info from the Bitboards, and you still need to check on promotions (in general).
Think we also disussed this some years ago, but I never tested it.
Disadvantage is that a move is not a simple pointer update operation, but you need to calculate the new position based upon the (64bit) MoveInfo and the previous position.
Regarding the Hash-table entry I only store the Move-Index.
Maybe a disadvantage is that I need to call the MoveGenerator() first to get the real move (and I do a check if the Move-Index does not exceed the number of moves, basically an extra collision detection).
In your case it would be beneficial if the Hash-table entry creates an immediate cutoff.
If not, you need to call the MoveGenerator() anyway.
Bert
IIRC, Fabien uses a clever trick by storing all changed bits of a move in a single bitboard. I think he has the squares running from bits 1 through 54 (not 0 through 53) and then he uses bits 0...5 for the from square, and bits 58...63 for the dest square. These from/dest bits can never overlap with the bits of captured squares (because bits 1...5 are edge squares). It does require some masking to extract them again. Of course, you can easily encapsulate this by wrapping the bitboard in a class and defining from() and dest() member functions that do the masking in the implementation.
In fact, you could use this trick for any board that fits within 64 bits since even the first square on the 2nd row and last square on the second but last row are edge squares that cannot be captured. You don't need to use the fact that you have extra ghost bits at the end.
64-bit moves are also more compact to store in the move list, and for 10x10 boards with duplicate capture detection you never need more than 128 moves, so 128 * 8 = 1024 bytes for an entire move list. Just 16 cache lines.
I think Fabien's format is really interesting. Another interesting format is from Gerard, who uses a "delta" board with 1 bits for every bit that changes in the position. For circular captures, from == dest, and these bits cancel each (just initialize them with bitwise-xor). That will still allow to do make_move() on a position, but it will prevent printing the move when from == dest.
Also, for Thai and Russian draughts, Gerard's format is not suitable. For Thai draughts, you can land on a square where you also captured a piece (because Thai draughts immediately removes pieces after you jumped them). For Russian draughts, you can promote during a circular capture.