Hash size changes best move?

[Sam Hull]

A version of this question was posted elsewhere but nobody seemed able to offer much of an explanation, and a request was made to submit it to the experts here.

- - - - - - - - - -
Why do many (all?) chess engines change their evaluation (more importantly the single selected move) based purely on different hash sizes at equivalent base depths in infinite analysis. Is a larger hash size inherently better beyond improving search efficiency; if so why?

I assumed it was merely cache to speed the search and not part of the evaluation mechanism itself. I understand how the scoring of possible moves can be relative to a particular search path, but given enough time why wouldn't the final result be the same?
- - - - - - - - - -

Thanks,
-Sam-

[Daniel Shawul]

It affects move ordering and hence the shape of the tree. Bigger hash tables more tb hits which gives better move ordering.
I recently replaced my initial move ordering at iteration 0 that was a qsearch, by adding a random term to it. And that alone gave me 6 different moves from 6 tries ! So I belivee a slight change in move ordering elsewhere should significantly affect the final move selected as well.
Using different random numbers for the hashkey gives some unpredictablity but not that much. The nodes searched differ but not the final move selected.

[gordonr]

On a related note, what happens after the hashtable becomes full? I realise this will vary between engines, but is it typical to use some form of entry replacement algorithm?

Consider the position arrived at after the initial moves 1. f3 e5 2. g4 d6
So, White has a subset of moves that avoid mate in 1 and the rest allow mate in 1. As expected, during their initial analysis, the bad moves are "immediately" skipped by engines.

But here's my surprise, why is it that after prolonged analysis - probably after filling the hashtable - when iterating through the list of current legal moves, the "allow mate in 1" moves are paused on for a noticable period? Ok, it may only be a few seconds, but the GUI is showing these moves for longer. e.g. why is it even considering a4 for any length of time?

I'm sure there's a good reason for this but I don't know why. Any insight? I think this is relevant for Houdini, Zappa Mexico II and Critter as a sample set I tried.

[Daniel Shawul]

They shouldn't My engine's output is like this

f1g2 1264554
d2d3 810919
c2c3 604619
f1h3 220064
e1f2 174190
h2h4 187844
b1a3 108287
d2d4 27849
g4g5 22957
f3f4 29327
b1c3 179
a2a3 106
b2b3 106
h2h3 106
b2b4 96
a2a4 96
c2c4 96
18 -40 840 15458858 g1h3 h7h5 h3f2 c8e6 b1c3 b8c6 e2e4 h5g4 f3g4 g8f6 f1d3 f8e7
h2h3 f6d7 c3d5 d7c5 d3b5 a7a6

As you can see moves like a2a4 are almost never considered as you can see from the amount effort spent on them (nodes count).

If I have to guess they are probably using the score of the move for move ordering. And if you use alpha-beta you can not know the score of all moves but the first one. But still I doubt if that will cause them to spend too much time on a2a4.

[gordonr]

They shouldn't My engine's output is like this

If I have to guess they are probably using the score of the move for move ordering. And if you use alpha-beta you can not know the score of all moves but the first one. But still I doubt if that will cause them to spend too much time on a2a4.

Thanks for the reply.

But why isn't it the case when searching at a low depth (as part of iterative deepening) that the position after a4 is stored in the hashtable with Qh4# being the best move, and thereafter this entry causes a4 to be always skipped fast enough that it's not really seen in the GUI?

I'm not saying these "allow mate in 1" moves are considered for any great length of time, but they are considered for longer than I'd expect. And I don't regard it as a bug; just a limitation in my understanding.

[Daniel Shawul]

You have got a point there. If a move will result in a loss in 1, it doesn't matter whether it is searched to depth= 2 or depth = 20. Deeper search is not going to change the outcome. But the hash table usually does not give
a cutoff if the move is not searched to equal or greater depth than what is asked for. Mates are different and one can add a special code to handle that.. I think some engines do a 'mate distance pruning' to help in this kind of situation.

[bob]

A version of this question was posted elsewhere but nobody seemed able to offer much of an explanation, and a request was made to submit it to the experts here.

- - - - - - - - - -
Why do many (all?) chess engines change their evaluation (more importantly the single selected move) based purely on different hash sizes at equivalent base depths in infinite analysis. Is a larger hash size inherently better beyond improving search efficiency; if so why?

I assumed it was merely cache to speed the search and not part of the evaluation mechanism itself. I understand how the scoring of possible moves can be relative to a particular search path, but given enough time why wouldn't the final result be the same?
- - - - - - - - - -

Thanks,
-Sam-

The problem is called "sub-tree grafting". If you don't overwrite any entries, this event becomes more probable. What happens is that when you search one part of the tree, the information used can terminate the search on another part of the tree. That is the obvious part. But if the first sub-tree occurs near the root, so that the table entry represents a significantly deep search, you can reach that same position later in the search and the hit will give you a score that represents a deeper-than-intended search depth... You actually get a deeper search than intended, with a more accurate (and different score).

Different sizes will result in different overwrite events, which can change this.