Hash move in move ordering

[m24gstevens]

Hi all,

I'm struggling to understand the concept of scoring hash moves within move ordering. I've tried to implement it as follows:
- When writing to the transposition table in the alpha-beta search on a fail high or fail low, write with it the best move (Or at least a good enough move to fail high) into the hash entry.
- When probing the hash table, recover this best move
- When scoring the moves, if any move matches this best move, score it even higher than a PV move would be scored (So it is searched first)

Searching the Kiwipete position at depth 10, this dropped my node count from ~2770 kNodes to ~2620 kNodes, but I thought this technique would cause a much more significant drop in the number of nodes searched

Could someone explain the differences between this hash move scoring and PV move scoring?

(If anyone is so kind to check my source code for bugs, it is here: https://github.com/m24gstevens/Chess/tr ... m24gc/beta)

Thanks,
Matt

[clayt]

Typically, the transposition move gets used a lot in iterative deepening - this means that your transpositions would come from a previous search at depth 9. At a single search depth, the probability of finding a transposed node is much smaller, especially if you're not searching an endgame-type position where transposition is much more likely.

Additionally, some positions aren't very well suited to transposition. Try a number of positions and see if this result is consistent.

[hgm]

PV-move scoring is basically a poor-man's replacement for hash moves. Normally the PV would be in the hash table, so when you do the latter the former wouldn't give you anything extra.

BTW, many engines don't even score the hash move; they just search it even before move generation. After the move generation you can remove it from the list. Sometimes I do not even do that, and allow the duplicat to be searched: with a good hash table it would be a guaranteed hash hit plus hash cutoff, so searching it a second time is probably faster than running through the move list to compare every move against the hash move to see if you should delete it.

The decrease in nodes is indeed a bit disappointing. To know what goes on you can take statistics of how often the first move causes a beta cutoff, and how often this is the hash move. And how often you have a hash hit in the first place.

[algerbrex]

Hi all,

I'm struggling to understand the concept of scoring hash moves within move ordering. I've tried to implement it as follows:
- When writing to the transposition table in the alpha-beta search on a fail high or fail low, write with it the best move (Or at least a good enough move to fail high) into the hash entry.
- When probing the hash table, recover this best move
- When scoring the moves, if any move matches this best move, score it even higher than a PV move would be scored (So it is searched first)

Searching the Kiwipete position at depth 10, this dropped my node count from ~2770 kNodes to ~2620 kNodes, but I thought this technique would cause a much more significant drop in the number of nodes searched

Could someone explain the differences between this hash move scoring and PV move scoring?

(If anyone is so kind to check my source code for bugs, it is here: https://github.com/m24gstevens/Chess/tr ... m24gc/beta)

Thanks,
Matt

You're understanding sounds correct. In fact, as others have said, you really don't need both PV scoring and hash move scoring, since PV is just a less effective way of doing what using the hash move already does. You can just always take the hash move and score it first in the position.

The node count drop does sound a bit low. I would check on some other positions. A good position to test on would be the Lasker-Reichhelm Position: https://www.chessprogramming.org/Lasker ... m_Position. Almost all engines with a working transposition table should be able to find the only winning move, Kb1, after only a couple of seconds. If your engine isn't able to, you likely have a bug somewhere.

Also, double check you don't have any bugs in your Zobrist hashing scheme. It took me a long time to get transposition tables working for my engine, and a large source of bugs was problems in my Zobrist hashing. If you haven't already, although it looks like you had a function to do so, I would create a transposition table to use for perft, and run some test using it. Not only should you be getting a substantial reduction in the time it takes to reach higher depths, but all of the numbers should be correct.

[mvanthoor]

Also, double check you don't have any bugs in your Zobrist hashing scheme. It took me a long time to get transposition tables working for my engine, and a large source of bugs was problems in my Zobrist hashing. If you haven't already, although it looks like you had a function to do so, I would create a transposition table to use for perft, and run some test using it. Not only should you be getting a substantial reduction in the time it takes to reach higher depths, but all of the numbers should be correct.

This is of the utmost importance.

Assuming you keep the zobrist hash incrementally, also create a function that calculates it from scratch and compare that to the incrementally kept value. (When running in debug mode, obviously.) They should be the same. If they're not, you have an error somewhere, and your TT will never work correctly.

[hgm]

Just a thought: if you have a hash move, wouldn't it be better to sort all moves that normally would be sorted before the hash move (if the latter had not been one) behind all other moves? On the first visit to this node (when there was no hash move) all these moves must have been searched, and they were all worse than the move that eventually became hash move. Even if the hash move was later changed, the new one was only found after all moves ordered before it scored less.

For non-captures sorted by history this could be tricky, as the history order might have been different on a previous visit. For captures the MVV/LVA + SEE order would be the same always. So if a move that MVV/LVA-wise would come first (e.g. PxR), and the hash move, being a measly NxB does not cause a cutoff... Is it then really smart to try that PxR next? This move was already rejected at lower search depth. Why would higher depth make it better, if the hash move turns out to be poisoned, or not able to surpass a raised alpha?