Move structure and hash tables

[dangi12012]

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

Go into their discord and look it up - or ask them.

[Ras]

I see a lot of effort going towards packing a move in 16 bits to save space in the hash table

Yes, I'm doing that because in my microcontroller version with 8192 entries in total, that saves 16kB, which is a lot. I'm also using that compressed move format e.g. for tracking PVs in positions because that saves stack.

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.

Rather not. I store from and to which are 6 bits each for a 0-63 board index. Actually, I'm using a 10x12 mailbox board, but have conversion tables from and to 8x8 notation. That leaves 4 bits free which I'm using to indicate piece or pawn move, or promotion piece (implying a pawn move). I could encode that more efficiently, e.g. I store black and white promotion pieces as separate numbers. I could get away with only 3 bits here, but that one free bit wouldn't help me so that I rather went for quicker table-based conversion that doesn't need the board state to convert the move.

The main thing I lose from my usual 32 bit move format is the MVV-LVA info, but that's no big deal because when retrieving the hash move, that gets a fixed MVV-LVA override anyway. Castling and EP don't need to be stored in the hash table because that is already in the board state, provided that the move is legal - I'm checking for pseudo-legality when looking up a hash move and discard the hash hit if the hash move fails that check.

I don't think this is actually worth Elo if you're not in such a tight memory sitiuation where you fight for mere kilobytes because it doesn't allow hash tables with more entries unless you allow non-powers of two in terms of entries.

[hgm]

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.

That would make decoding very slow, as you would have to generate the entire move list to do it.

Not sure what you mean by 'extracting a move'. We were talking about extracting data required for updating the game state from a move as one of the possible ways for obtaining that data.

[Ras]

Just the move can be done in 8 bits as the offset in your movelist from any position.

The drawback is that this requires you to have a movelist at that point - so you can't try the hash move and only generate the movelist if the hash move doesn't lead to a beta cut. If you have a hash move, you have like 90% probability of a beta cut.

[Karlo Bala]

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?

Don't bother, just use as many bits as you need. The size of a move structure is probably the last thing you want to optimize in the engine.

[Daniel Shawul]

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?

I use 32-bit move representation because that is more convenient. But when size really matters, such as in an MCTS search where the tree is stored in RAM, I encode and decode the move into 16 bit representation. For the hashtable, if you need that extra space to double your hash size it may matter but probably not worth a lot of elo.

[Henk]

Yes I regret storing move in 16 bits. Just make debugging as easy as possible. At least annoying.
Why all these tricks for a few elo. If you can't invent something better than just resign.

[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

Go into their discord and look it up - or ask them.

You once again have nothing to back up your claims. Your number is for perft, which no one cares about. You're not better than a troll at this point, I hope moderation takes some action.

[hgm]

You mean like warning people who call posters names just because these have an opinion they don't agree with?

[chrisw]

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?

It makes little difference to performance.
Another disadvantage of 16-bit, apart from having to write more fiddly code for determining the characteristics of the move, is that you also start running into problems between finding move character before MakeMove() and after it, because you’re dependent on board state (after MakeMove, the moving piece type had to be got from sq-to, not sq-from and so on and so on). Or maybe for example you need to know something about the move at nply-1, or nply-2, well, you’ll also need a boardstate history, not just a move history.
For an engine in development where you probably can’t predict all possible move informations you might need, then 32 bit with OTT info would seem desirable. After the engine is fully complete, then think about cutting back to 16-bit, but I’ld predict it would by way down the list of important things to try and optimize.