Move structure and hash tables

[gaard]

I see a lot of effort going towards packing a move in 16 bits to save space in the hash table or even for general use. But then you need special functions to determine, with the board state, whether a move is castling (although this one may be as simple as abs(orig - dest) == 2), en passant, capturing, promotion piece, etc. I suppose some of those can be encoded in the remaining 4 bits of a 16-bit move, but usually not all of them. An extra 16 bits also leaves room for flags like direct check, reveal check, etc. Has anyone every measured performance between the two schemes, that is, 16-bit move versus 32-bit. Is there any reason to believe the difference is worth more than a couple of Elo?

[Brunetti]

Has anyone every measured performance between the two schemes, that is, 16-bit move versus 32-bit. Is there any reason to believe the difference is worth more than a couple of Elo?

Hardly someone will measure this difference, I think, because this is not a matter of simply changing a setting: your move generator changes much and when you do such a rewrite probably you're updating other parts of the engine.

Anyway, at the cost of halving your hash size, you gain in code readability and maintainability. While the hash size shouldn't be a problem nowadays with all the big memories, fast instructions, prefetch and so on, the gains worth that loss, I think. There's also the consideration that in 64-bit architecture, 16-bit variables management should be slower than 32/64 bit ones'.

In my (weak) engine I use a 32-bit integer, where I store, besides the standard info, the move type and there's also a nice 8-bit remain for a move order value, which helps much in the search. But my search is really messy so the results are not very good

Alex

[dangi12012]

I measured the difference and 16 bits is faster. Cache pressure is bigger and arithmetic is dirt cheap. Faster % can be translated into elo via an empirical formula specific to your engine.

you can build a movegen that does not need a make unmake move. So in a sense you can get away with 0 bits too if you look at my Signature URL you will see what i mean.

You need to store the hash + eval in a TT and not how you got there. Just the move can be done in 8 bits as the offset in your movelist from any position.

[Mergi]

This very much depends on the engine architecture as well. By changing the move size, the compiler might introduce some extra padding in your TT entry. I'm using 8 bytes per TT entry and if i changed the size of the move to 32 bits, the TT entry would suddenly become 50% larger (12 bytes) because of the extra padding.

[gaard]

I measured the difference and 16 bits is faster. Cache pressure is bigger and arithmetic is dirt cheap. Faster % can be translated into elo via an empirical formula specific to your engine.

you can build a movegen that does not need a make unmake move. So in a sense you can get away with 0 bits too if you look at my Signature URL you will see what i mean.

You need to store the hash + eval in a TT and not how you got there. Just the move can be done in 8 bits as the offset in your movelist from any position.

My understanding is that your perft app, which I haven't looked at in great detail, doesn't use a move list or a hash table. I haven't done any specific measurements, but I assumed the cache pressure would come from double the move list size (maybe 32k max stack space over 50 recursive search calls) and hash retrieval cache misses. So, how did you measure the change?

10 years ago, the rule of thumb I remember reading is that double the hash size lent ~5 Elo. Surely that has to have diminished since then, which begs the question, is a 25% difference even measurable in under 100,000 games?

[hgm]

Apart from the from- and to-squares you only need a single bit to encode all moves of orthodox chess in a very convenient way. The extra bit is a flag that indicates whether the move is 'special', i.e. has effects in addition to simply moving between the mentioned squares. (So in orthodox Chess these are castlings, promotions, e.p. captures and double pushes. The latter because these have to set the e.p. flag.)

As special moves are rare in the tree, the amount of work you have to do to decode those has virtually zero impact on speed. So the only thing that matters is how much time it takes to verify the move is not special. Which is limited to testing that extra bit, which is as fast as you can get. In the common (= predicted) case you can then just perform the move like special moves do not exist.

The way I usually encode the special moves is by storing a 'move code' in the bits that for normal moves would contain the to-square. This move code is then used as the index in a table that contains the true to-square, and all other info needed to perform the special move. To economize on index range you can encode the true to-square relative to the from-square (so all double pushes for white can use the same move code, and there are only two white e.p. captures, to the left or to the right).

As the simplest and still relatively common special move is a double push, you could first test for that in the code path that treats the special moves. I usually put the 'special' flag in the same byte as the to-square number (so that you can also consider this encoding through off-board to-squares). E.g. if the on-board to-squares are numbered 0 to 63, you could use the '64' bit as flag, and the '128' bit (the byte's sign bit) to indicate the move is a double push. After testing the to-square with a 0xC0 mask (and continuing to use it for normal moving when (toSqr & 0xC0) == 0), you can then immediately branch on the sign bit to code for performing the double push. (I.e. calculate the e.p. square and to-square from the from-square, and then continue with the code for normal moves.) The to-square range 64-127 is then still available for more complex special moves, indexing a table with move info.

[Harald]

Do not forget the under promotions (R, B, N) as special moves.

Or consider this: If you have a current board state with all the pieces then a move needs
only from (6 bit), to (6 bit) and promotion (2 bit) = 14 bit.

Without the board you need more bits to describe the move and its features.
When you already exceeded 16 bit anyway it is convenient to have the moving piece (3 bit),
a double pawn push flag, an en passant flag, a castle flag, a capture flag, the captured piece (3 bit),
a checking flag, a mate flag, sorting values, ...

[hgm]

Extracting the moving piece and captured piece from bit fields in the move encoding takes more time than just reading it from the board. I would never recommend that, even when you have all the bits in the world available.

[dangi12012]

Extracting the moving piece and captured piece from bit fields in the move encoding takes more time than just reading it from the board. I would never recommend that, even when you have all the bits in the world available.

Extracting a special move takes no amount of time if its a C++ template. Also any move can be encoded in 8 bits - as the offset in the movelist.
Maybe stockfish will use my approach according to their discord since its faster - and they currently use 30% of time for the movegeneration.

[Sopel]

Maybe stockfish will use my approach according to their discord since its faster - and they currently use 30% of time for the movegeneration.

This number is wrong by about an order of magnitude