storing a move, for undoing and other operation to see what was the last move

[spirch]

hello

this should be language agnostic, hopefully.

I store a lot of information in a long (64 bit) with bitwise operation
I use a fixed array length large enough so I know I have enough space so it wont go out of bound and i wont need to resize it

actual move from/to
MoveFrom (7 bits)
MoveTo (7 bits)
ExtraMoveFrom (7 bits) in a case of castle or enpassant
ExtraMoveTo (7 bits) in a case of castle or enpassant
(total 28 bits)

piece information from/to (which kind, color and can it do a "special move" like castle or enpassant)
PieceFrom (6 bits)
PieceTo (6 bits)
ExtraPieceFrom (6 bits) in a case of castle or enpassant
ExtraPieceTo (6 bits) in a case of castle or enpassant
PromotedTo (6 bits)
(total 30 bits)

give me some information about what could be inside that move
IsEnPassant(1 bit)
IsCapture (1 bit)
IsPromotion (1 bit)
IsCastle (1 bit)
isPawnDoubleMove (1 bit), this help me for enpassant tracking
(total 5 bits)

so i'm using so far 63 bits.

my undo move just read that long and extract the information in it and apply it

what are you using or doing to keep internal list of move?

do you think what i do is unnecessary ?

[spirch]

code wise, this is what it look like;
(language is c#)

actual move from/to
MoveFrom = history & bit.Move;
MoveTo = history >> bit.MoveToShift & bit.Move
ExtraMoveFrom = history >> bit.ExtraMoveFromShift & bit.Move;
ExtraMoveTo = history >> bit.ExtraMoveToShift & bit.Move;
(total 28 bits)

piece information from/to (which kind, color and can it do a "special move" like castle or enpassant)
PieceFrom = history >> bit.PieceFromShift & bit.Piece;
PieceTo = history >> bit.PieceToShift & bit.Piece;
ExtraPieceFrom = history >> bit.ExtraPieceFromShift & bit.Piece;
ExtraPieceTo = history >> bit.ExtraPieceToShift & bit.Piece;
PromotedTo = history >> bit.PromotedToShift & bit.Piece;
(total 30 bits)

give me some information about what could be inside that move
IsEnPassant = (history & bit.IsEnPassant) == bit.IsEnPassant
IsCapture = (history & bit.IsCaptureBit) == bit.IsCaptureBit
IsPromotion = (history & bit.IsPromotionBit) == bit.IsPromotionBit;
IsCastle = (history & bit.IsCastleBit) == bit.IsCastleBit
isPawnDoubleMove = (history & bit.IsPawnDoubleMoveBit) == bit.IsPawnDoubleMoveBit
(total 5 bits)

[Joost Buijs]

I use the following format:

6 bit from
6 bit to
8 bit flags: quiet_move, pawn_move, double pawn_move, king_move, castling, capture, en_passant, promotion
4 bit info: basically to store the promotion piece type or castling type.

This is 24 bit total, and sits inside a struct so it will take 32 bit anyway.

For my engine this is enough info, but it all depends upon how your move_make and unmake is organized.

[hgm]

Packing unrelated variables into one machine word causes extra overhead compared to keeping them in separate words. So why would you want to do that? It is not like the size of the info needed for unmaking the move is a critical issue.

When making a move I typically remember the square of origin and destination, the piece that moved (i.e. was on the square of origin), the piece that was captured (i.e. that as on the destination), an extra square that could be captured (for e.p.) and what was captured there. (The latter could also be used to remove the Rook on castling). But I keep those as different variables, for easy access.

But for encoding the move in the Transposition Table I only use the origin and destination squares, plus a single bit to flag whether it is a special move. If that bit is set the 'destination square' is actually an index in a table that tells what the true destination square is, plus anything else that would be relevant for making the move. (But not for unmaking it! That info (like what piece was captured) would be collected while making the move). You have to get it from somewhere, and reading it from the board itself is not any slower than reading it from the move.) This because the size of a TT entry is critical, as there will be billions of such entries. The number of moves I have to remember how to unmake is only as large as the search depth, perhaps 256 max.

In the move list, which stores moves between their generation and there search, I store the moves as a 32-bit integer, packed as four 8-bit fields. (These can be 'extracted' by simply reading the corresponding bytes from memory; the packing then doesn't give any overhead.) The move will be in the two low-order bytes, in the same format as in the TT, and the high-order byte can be used for the sort key. (So the move list can be sorted as if it consisted of 32-bit unsigned integers.) In KingSlayer I use the additional byte to indicate a promotion or e.p. square, to make it more capable w.r.t. encoding promotions or double captures, for pieces like the Chu Shogi Lion.

[Joost Buijs]

Packing unrelated variables into one machine word causes extra overhead compared to keeping them in separate words. So why would you want to do that? It is not like the size of the info needed for unmaking the move is a critical issue.

In the past I used 8 bit from and 8 bit to as well, the scheme I use now gives me some extra bits to play with for future extensions. And it doesn't make any difference in speed on modern hardware with a modern compiler, at least I can't measure it. Al this speed stuff is nonsense anyway, it really doesn't matter if your engine is 1% slower or faster. All that matters is evaluation, this is where you can gain hundreds of Elo points.

It was different in the 80's when computers were too slow to be tactically sufficient, but the times of the 2 MHz. Intel 8080 are long gone.

[emadsen]

what are you using or doing to keep internal list of move?
do you think what i do is unnecessary ?

Yes, I think some of your encoded move data is unnecessary. Such as PieceFrom and PieceTo. I just look up the piece type from Board.CurrentPosition (at square Move.From).

Rather than encoding ExtraPieceFrom and ExtraPieceTo into the move, I prefer to handle en passant and castling in the Board.PlayMove function. In other words, knowledge of how to handle those complex moves is placed in code that plays moves rather than code that generates moves. This frees up bits in the move for history heuristic score.

I pack move characteristics and move scoring (history heuristic) into a 64 bit ulong such that I can sort the ulong[] Moves array and get moves in priority order: best move from cache, captures by MVV / LVA, pawn promotions, killer moves, then history score. All the move characteristics (that define how to play the move on the board) are in the lower bits (From square, To square, etc) so they don't affect move priority order- except in the unlikely case two moves have identical history scores.

See my explanation in code comments in the Move.cs class.

[hgm]

In the past I used 8 bit from and 8 bit to as well, the scheme I use now gives me some extra bits to play with for future extensions. And it doesn't make any difference in speed on modern hardware with a modern compiler, at least I can't measure it. Al this speed stuff is nonsense anyway, it really doesn't matter if your engine is 1% slower or faster. All that matters is evaluation, this is where you can gain hundreds of Elo points.

It was different in the 80's when computers were too slow to be tactically sufficient, but the times of the 2 MHz. Intel 8080 are long gone.

All very true. But it is also a matter of code simplicity. Your posting really pre-empted mine, which I was writing in reply to the OP. But to comment on your format: if the struct thakes 32 bit anyway, why not just take 8 bits for the from- and to-square each, and put the 4 info bits in the 4th byte? Then you can keep the bit-twiddling out of the code. Even if it matters only an utterly irrelevant 1%, why do the slower thing if it is just as easy (if not easier) to do the faster thing.

What has always bothered me is that because iof the issue of endienness I cannot define a union { int all, struct { char from, to, flags, key;} } and rely on it that the key ends up in the high byte, so I can justs ort the moves as int. I still have to write ugly things like from = move >> 8 & 255 to access the byte that holds the from-square, even if the compiler completely optimizes that away.

The decoding of the moves in my format goes very natural:

Code: Select all

to = move & 255;
if(to & 64) { // is special move
  // rarely executed code
  switch(moveDecode[to-64].type) {
    case DOUBLEPUSH:
    case CASTLING:
    case EP:
    case PROMOTION:
  }
  to = from + moveDecode[to-64].step; // true destination
}

[emadsen]

Such as PieceFrom and PieceTo

I take back what I said. I do encode PieceFrom and PieceTo as CapA and CapV for MVV / LVA move ordering. But I don't encode anything about extra pieces for castling or en passant. That can be inferred from the current board position.

[spirch]

i think i wasnt clear enough, sorry about that

this long is to unmake move only and if needed, to know what happened last move

this is not used for actual move which is something completely different, i do bitwise but i store way less information


i should do some actual profiling to see if "packing" all this into a long is better than a class or a struct with different field for each information

my feeling (which is why profiling is key, feeling can be wrong) is that one 8 bytes, same memory address, is faster to scan/access than many small one

the code is sure uglier with all these bitwise operation

also, my board is 0x88 which might affect how i do my packing, max position is 119 which need 7 bits to store

[spirch]

Such as PieceFrom and PieceTo

I take back what I said. I do encode PieceFrom and PieceTo as CapA and CapV for MVV / LVA move ordering. But I don't encode anything about extra pieces for castling or en passant. That can be inferred from the current board position.

(just a reminder this is to unmake only)

is it "faster" to infer by looking at the board or is it "faster" to just take the value as it was stored without looking at the board?

for castling, you need to figure out which rook was used
for en passant you need to figure out where was the pawn

both can be inferred but in my mind if i store it, i dont need to figure it out, it's right there. the processing was done when the move was done