Question for Bob Hyatt

[bob]

From my experience in correspondence games
I have many examples when rybka changed her mind after hours but in most of them it was only afrer the score of the pv move went down
something like:
1.xx 1.02/20
1.xx 0.94/21
1.yy 1.04/21

This suggest the following idea to add stability:

Every time that the score of the pv move does not go down in a new iteration reduce the depth of other root moves by one ply.

It means that in the first iteration when the score does not go down you can practically skip the rest of the moves becaue of hash tables.

Example:
Suppose you have the following scores
1.e4 0.10/11
1.e4 0.06/12(score went down so you search 1.d4 and other moves also to depth 12 and suppose you find nothing better than 1.e4)
1.e4 0.07/13

score did not go down
other moves are searched only to depth 12 so they are pruned based on hash tables.


When you get depth 14 you may have
1.e4 0.07/14
again score did not go down but now you cannot prune based on hash so you search other moves to depth 13

If a move fail high at depth 13 you make a research to depth 14 and only if it also fail high at depth 14 you change the main choice.

Uri

I don't like this idea very much. Suppose you have a position with some good quiet positional moves and a tactical shot leadiung to immediate win. In the first iterations, one of the positional moves is the best, so it is a PV. In the next iterations a pretty accurate score for it is calculated. Then it is left to chance in which iteration you will find the tactical shot. For example, if depth 12 is needed to find the move:

1. Positional (+0.20/10)
1. Positional (+0.25/11)
1. Positional (+0.31/12)
1. Positional (+0.38/13)
1. Tactical (+4.48/13)

The assumption 'if I don't get a lower score, the PV is probably the best move' is not fulfilled in tactical positions!

I know that is not always correct
Every reduction can be wrong in part of the cases.

The point is that it may be more important in games to find better positional moves and not to find tactical wins.

The program may go one ply deeper so the score goes down and it may be enough for it to find a better positional move.

Uri

There's a significant risk here of making the tree blow up so that you know you are in trouble, but can do nothing about it. Suppose you use your idea and search the PV and reduce the rest. Which will let you reach a significant depth. Then the PV drops, and now when you start searching for a best move, all your stuff is worthless for ordering. hash table entries are too shallow to use outright. You searched those trees to a reduced depth. Etc. I am still convinced that searching the PV deeper, just because it is the PV, is wrong.

LMR is doing enough of this already...

[hgm]

LMR is doing enough of this already...

Exactly. This idea sounded very much like LMR to me from the beginning. If you do it on top of LMR, and it would work, this suggests that the reduction you apply in LMR is not large enough to start with.

I can add that advanced time management often also does this: you search the PV move, and when its value has not dropped, and your time is running out (which it usually is; as searching the PV move takes such a large fraction of the iteration, the timeout is likely to occur during it), you play the PV move without proving that the others were worse at the same depth. Which effectively does mean that you search them one less deep than the root PV move.

[Michael Sherwin]

LMR is doing enough of this already...

Exactly. This idea sounded very much like LMR to me from the beginning. If you do it on top of LMR, and it would work, this suggests that the reduction you apply in LMR is not large enough to start with.

I can add that advanced time management often also does this: you search the PV move, and when its value has not dropped, and your time is running out (which it usually is; as searching the PV move takes such a large fraction of the iteration, the timeout is likely to occur during it), you play the PV move without proving that the others were worse at the same depth. Which effectively does mean that you search them one less deep than the root PV move.

Now that that is settled, what about my suggestion of strengthening the PST entry for the root move that came in best?

[lkaufman]

We're actually testing Uri's idea now. So far it's testing slightly but not significantly positive. So while I cannot say that it is a benefit, I can at least say that it appears not to be a bad idea.

[diep]

From my experience in correspondence games
I have many examples when rybka changed her mind after hours but in most of them it was only afrer the score of the pv move went down
something like:
1.xx 1.02/20
1.xx 0.94/21
1.yy 1.04/21

This suggest the following idea to add stability:

Every time that the score of the pv move does not go down in a new iteration reduce the depth of other root moves by one ply.

Assuming binary logics you suggest to NOT reduce when score does go down.

From the entire search depth of say 21 ply you fix it now
for 1 out of 21 ply. So that's not a real interesting solution.

The generic problem is that of course total nonsense move yy has been reduced bigtime in search and stored like that in hashtable. Now if pv score goes down of course, it is easier for search to deny it has a bad position and pick the nonsense move as new bestmove. A generic problem of reductions. The more you reduce the bigger this problem is of course and bigger search depths do not solve it.

Nullmove doesn't suffer from this problem, despite reducing search a lot more as its reduction assumption is far more powerful.

So basically you suppose to lose search depth meanwhile not fixing the problem (if you reduce in PV nodes that is, which majority doesn't do) .

If you look back in CCC archives you will see i mentionned the above weakness of LMR already a decade ago, around 1999 when i did reduce a lot in diep. More than i do now.

It means that in the first iteration when the score does not go down you can practically skip the rest of the moves becaue of hash tables.

Example:
Suppose you have the following scores
1.e4 0.10/11
1.e4 0.06/12(score went down so you search 1.d4 and other moves also to depth 12 and suppose you find nothing better than 1.e4)
1.e4 0.07/13

score did not go down
other moves are searched only to depth 12 so they are pruned based on hash tables.


When you get depth 14 you may have
1.e4 0.07/14
again score did not go down but now you cannot prune based on hash so you search other moves to depth 13

If a move fail high at depth 13 you make a research to depth 14 and only if it also fail high at depth 14 you change the main choice.

Uri

[hgm]

Search is like water flowing through the landscape of strategic hills. When you go down-slope, you run as fast as you can in a narrow stream. It doesn't matter much if you don't take the steepest decent always, you will get to the botom anyway, without probing all of the slope.

But surrounded by hills, the flow stagnates, and it forms a lake, that probes in every direction to the same level, until it finds the lowes mountain pass to escape.

I just came back from a hiking holiday on Gran Canaria, and I noticed that when you follow the barrancos that cut through the mountains upstream (because that is he least steep climb), they often bring you to a place where to get out of the valley you have to cross over much taller mountain ranges then when you would have climbed out of them early on...

[Michael Sherwin]

We're actually testing Uri's idea now. So far it's testing slightly but not significantly positive. So while I cannot say that it is a benefit, I can at least say that it appears not to be a bad idea.

I am testing the PST idea starting with a rather extreme -10fs/+10ts adjustment. I will test down from there. So far, it is doing very well!

[metax]

I am testing the PST idea starting with a rather extreme -10fs/+10ts adjustment. I will test down from there. So far, it is doing very well!

What is fs/ts supposed to mean?

[Michael Sherwin]

I am testing the PST idea starting with a rather extreme -10fs/+10ts adjustment. I will test down from there. So far, it is doing very well!

What is fs/ts supposed to mean?

fs = from square

ts = to square

[Michael Sherwin]

I am testing the PST idea starting with a rather extreme -10fs/+10ts adjustment. I will test down from there. So far, it is doing very well!

What is fs/ts supposed to mean?

fs = from square

ts = to square

I'm getting pulled in about a dozen different directions so, forgive me if I am a bit terse.

I will give an example of the idea.

Example: lets say that the engine has just finished iteration depth 12 with Ng1f3 returned as the best move. The idea is to modify the PST for the knight by subtracting a small amount from knightTbl[fs] and adding a small amount to knightTbl[ts] before iteration depth 13 is started. If Ng1f3 would have proven before to be about equal with some other moves and therefore caused the pv to change, now the extra bonus added to the knight move may be enough to prevent the pv from changing. On the other hand if another move order that also gets the knight to the prefered square is better, it will not be over looked.