Actually I'm not proposing anything - I'm wondering how much worse such an approach would be.xmas79 wrote: You are essentially proposing an hash table only for storing exact entries.
It's not quite the same as storing only "exact" entries, since you do store the entire path in the entry. If I can retrieve a PV of length N, I don't care if some entry N-k gets trashed.
I guess it's true that for efficiency you can't beat the triangular array. However, you would only need to know two things from the ply+1 search: whether it is a PV node (which you can tell from the score) and the hash key where the full path was stored.(1) Performance: at a given (PV) node at depth D you get the PV by searching its best move deep, and store it in the related bucket. But when you have already searched the best move in this node, how do you retrieve the PV coming from the best move node? You should make (again) the best move, probe the hash path, unmake, then stick the best move in front of the retrieved PV, and store again in the hash. Everything starts by simply putting one move on the tips, so the back-up keeps adding moves in front of it, eventually reaching the root.
Sure, nothing beats a triangular array for accuracy. Again, I wasn't trying to do that, I was wondering how much worse it would be.(2) Robustness: how many entries you should have? And what assures you that your probe will get a PV that is what you was really looking for? Indeed you cannot have such guarantee, since the best move is searched first (and stored first), then in the other part of the tree you could overwrite that entry, defating the purpose. So you could even have truncated PV during a backup.