Adaptative LMR and TT

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Adaptative LMR and TT

Post by Kempelen » Tue Dec 23, 2008 5:30 pm

A problem that came to me on the fly about LMR and TT, supposing an adaptative R for LMR, i.e. R=1 for top history and R=2 for the rest.

I mean, a position could be at a certain depth calculated with R=1 and if repeated in other iteration, could be with R=2, which make TT info unsafe. isn't it?

As LMR is move-order dependency, couldn't this be in conflict with with TT which is depth dependecy?
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Adaptative LMR and TT

Post by bob » Tue Dec 23, 2008 8:43 pm

Kempelen wrote:A problem that came to me on the fly about LMR and TT, supposing an adaptative R for LMR, i.e. R=1 for top history and R=2 for the rest.

I mean, a position could be at a certain depth calculated with R=1 and if repeated in other iteration, could be with R=2, which make TT info unsafe. isn't it?

As LMR is move-order dependency, couldn't this be in conflict with with TT which is depth dependecy?
If you store and lookup properly, this should not cause you any grief. I do a HashProbe() at the top of search, before I fiddle with the depth at all. Whenever I do a HashStore() inside the search, I always store using the _original_ depth value (which I never change for this reason). Doing it this way, whatever depth you have when you store is enough to use the entry when you probe. If you munge around with the depth before probing, or you change it before you store, then you can certainly introduce "issues".

User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Re: Adaptative LMR and TT

Post by Kempelen » Tue Dec 23, 2008 9:55 pm

bob wrote:
Kempelen wrote:A problem that came to me on the fly about LMR and TT, supposing an adaptative R for LMR, i.e. R=1 for top history and R=2 for the rest.

I mean, a position could be at a certain depth calculated with R=1 and if repeated in other iteration, could be with R=2, which make TT info unsafe. isn't it?

As LMR is move-order dependency, couldn't this be in conflict with with TT which is depth dependecy?
If you store and lookup properly, this should not cause you any grief. I do a HashProbe() at the top of search, before I fiddle with the depth at all. Whenever I do a HashStore() inside the search, I always store using the _original_ depth value (which I never change for this reason). Doing it this way, whatever depth you have when you store is enough to use the entry when you probe. If you munge around with the depth before probing, or you change it before you store, then you can certainly introduce "issues".
I am doing that way too, but I explained myself bad. What I was refering is thinking in the childs and the subtree of the node in question. One example:
node x at depth y has 10 child nodes, last 7 are with adaptative LMR. 3 first are with R=1 and 4 with R=2. Now you store the node in the TT for that depth.
Then you need again the node and you retrieve from the TT for that depth. You are supposing the whole subtree is the same but it is not. Continue with my example suppose you calculate againg the node. As you have a more accurate move ordering (because you have improve history and all move order variables during the whole search) in the example the child than before where R=2, now it is R=1. That change could make the value of the node be different. If there is a hidden tactic for that child thank to a lower R, the whole node and the value has a different value than what you have originaly in your TT.

what I see is that TT is ok for store nodes which depth is fix for all the subtree, but when you vary the subtree due to move ordering issues the TT cell is not valid, or at less you dont have enought confidence that the node, if calculated again, could have a better move or value.
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

bob
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Adaptative LMR and TT

Post by bob » Tue Dec 23, 2008 10:48 pm

Kempelen wrote:
bob wrote:
Kempelen wrote:A problem that came to me on the fly about LMR and TT, supposing an adaptative R for LMR, i.e. R=1 for top history and R=2 for the rest.

I mean, a position could be at a certain depth calculated with R=1 and if repeated in other iteration, could be with R=2, which make TT info unsafe. isn't it?

As LMR is move-order dependency, couldn't this be in conflict with with TT which is depth dependecy?
If you store and lookup properly, this should not cause you any grief. I do a HashProbe() at the top of search, before I fiddle with the depth at all. Whenever I do a HashStore() inside the search, I always store using the _original_ depth value (which I never change for this reason). Doing it this way, whatever depth you have when you store is enough to use the entry when you probe. If you munge around with the depth before probing, or you change it before you store, then you can certainly introduce "issues".
I am doing that way too, but I explained myself bad. What I was refering is thinking in the childs and the subtree of the node in question. One example:
node x at depth y has 10 child nodes, last 7 are with adaptative LMR. 3 first are with R=1 and 4 with R=2. Now you store the node in the TT for that depth.
Then you need again the node and you retrieve from the TT for that depth. You are supposing the whole subtree is the same but it is not. Continue with my example suppose you calculate againg the node. As you have a more accurate move ordering (because you have improve history and all move order variables during the whole search) in the example the child than before where R=2, now it is R=1. That change could make the value of the node be different. If there is a hidden tactic for that child thank to a lower R, the whole node and the value has a different value than what you have originaly in your TT.

what I see is that TT is ok for store nodes which depth is fix for all the subtree, but when you vary the subtree due to move ordering issues the TT cell is not valid, or at less you dont have enought confidence that the node, if calculated again, could have a better move or value.
Here's the issue: If you do _anything_ that is "path dependent" then the hash table will introduce problems, since the hash signature is position-derived, not path-derived. For example, in the simplest to understand case, say you add a recapture extension. You just introduced the potential for a hash table inconsistency, because the recapture is a ply N / ply N+1 event, while in the hash table, the capture could be anywhere, and the re-capture could be plies later, where the extension might not be triggered.

Bottom line, there is nothing you can do about it. If you hash the path, you lose the "transposition" part of "transposition/refutation table". So you generally accept the "issues" and move on...

Post Reply