Houdini 3 reducing the depth feature

[syzygy]

There are two things in the discussion, IMHO.

(1) how to quickly resolve a fail high or fail low so that the search can get past that point. FH and FL are really different animals that most of us currently handle the same way, something I think needs to be looked at quite a bit in fact... Back in the late 90's, John Stanback and I had a long discussion about this issue on r.g.c.c... he proposed the idea that on a fail low, start back over at iteration one, because the fail high is missing a lot of move ordering information, and the previous search of this move did not fail high, so any remembered ordering (HT moves) will likely be wrong. If you do that, the HT entry for the fail low has a really big draft, so starting back over at depth 1 should find some other move, and as you progress through the iterations, you improve move ordering as in a normal search. Unless you lose that fail high. I've thought about this and played with it, but have not made a decision and it sits on my "further testing/thinking is required" list.

(2) producing a score / PV quickly to let the user know what is going on. If you search a FH move to a reduced depth to get a score quicker, that score must be at best maybe a rough approximation of the score that comes from a deeper search. Displaying it might be more confusing, as it is possible that score is actually worse than the scores for previous best moves you displayed Until you get deep enough.

I'm guessing that H3 resolves the FH first at the (reduced) depth at which it was originally searched, and at which it originally failed high (after which it failed high again at unreduced depth, assuming H3 uses a form of LMR at the root similar to that of other programs). So normally it should again score better than the previous moves at this reduced depth, and therefore (quickly) produce a PV.

So I can see that (2) works. Whether (1) is achieved is less clear, but it might very well give a little benefit (in addition to the quick PV).

Maybe my guess is not entirely correct, and H3 reduces the new PV move more than what LMR at the root did, the idea being that the original (non-PV) search reduced depth also at other points further down the tree, whereas in the PV search those reductions will not take place. If that's the case then I can see your point (but of course, if it works for H3, it works for H3...).

[bob]

I understand the idea, although I do not buy "all in" that it is correct. Why would one do things so differently in the PV, that you make it very hard for a non-PV move to fail high in the first place??? I don't personally assume that this is the way things have to be done, it's just the way some do it at the moment. From a theoretical perspective, it seems wrong, however.

I am not sure how an idea that produces elo can be wrong. About a year of ten ago I added (what I called) the PVS extension as described here. It's (still) good for 20-30 elo. When I would reduce the depth at a fail-high it still could produce the good score and mainline since the hash-table has all the best moves right resulting in several to many extensions.

This is similar to the tt-singular idea in robolito and friends. I've tried several variations, but not your "4 tt moves in a row to trigger an extension." Won't work for me, period, because I use the speed optimization of whenever I have no best move to store (ALL node, for example) I store the FIRST move I searched. Since I search the TT move without generating moves, it can occasionally save time. It is a performance enhancement, rather than a search improvement (I search the same tree if I don't do this, but I have to generate moves first, and occasionally an ALL node becomes a CUT node and this "pseudo-best-move" will cause a fail high with less effort (no move generation). But this means I would be extending way too much using your idea, since every hash entry has a "best move" even though they are often not a "best move" at all, just "a legal move".

The question was if reducing the depth at a fail-high can produce the real score and the answer is yes. I noticed Richard told you the same thing.

"yes" is not helpful. "How" would be. If you back up several iterations, how can you hope to get the same score you will get from several iterations deeper???

Until you get to the same depth, anyway...

I get the point of backing up a bit, because move ordering is now broken, and backing up a few plies gives you easier searches to establish some move ordering for the new move. But "the score"? Can't see how it can be correct until you get to the depth where it fails high, otherwise it would have failed high at earlier depths, don't you think???

So maybe you get "a score" when you back up, and by the time you get back to the right depth you get "the score". That I would buy.

I think you are underestimating what others have inside:
[d] 8/8/8/3k4/8/8/8/1NN1KNN1 w - -

Code: Select all

ProDeo 1.81
 00:00:41  18.00  13.87  1.Nc3 Kd6 2.Nd3 Kc7 3.Ne3 Kb6 4.Ncd5 Kb5
 00:00:49  18.03  13.87  1.Nf3 
 00:00:50  18.03  14.02  1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kb5 4.Nc3 Kb6 
 00:01:04  19.00  14.07  1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kb5 4.Nc3 Kb6 
 00:02:26  20.00  M 17   1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kd5 4.Nc3 Kd6 5.Nb5 

And now I let it run from the well ordered hash table by taking back 1.Nf3 and then the mate is found 2 plies earlier because of the PVS extension.

Code: Select all

 00:00:05  16.00  13.77  1.Nc3 Kc4 2.Kd2 Kc5 3.Ne3 Kd6 4.Nd3 Kc6 5.Nf3 
 00:00:14  17.00  13.77  1.Nc3 Ke5 2.Nf3 Kf4 3.N1d2 Kg4 4.Ne5 Kf5 5.Nc6 
 00:00:39  18.00  M 17   1.Nc3 Ke5 2.Nf3 Kf4 3.Ke2 Kf5 4.Ne3 Ke6 5.Nd4 

Known behavior. It is how we solve fine 70 in under 26 plies, when it takes 26 non-capturing moves before the first pawn is actually captured (won). If you actually do perfect move ordering, it takes you 26 plies. Taking less than 26 plies requires a sub-optimal move ordering.

Not sure what this has to do with the TT extension, however... The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

[Rebel]

I understand the idea, although I do not buy "all in" that it is correct. Why would one do things so differently in the PV, that you make it very hard for a non-PV move to fail high in the first place??? I don't personally assume that this is the way things have to be done, it's just the way some do it at the moment. From a theoretical perspective, it seems wrong, however.

I am not sure how an idea that produces elo can be wrong. About a year of ten ago I added (what I called) the PVS extension as described here. It's (still) good for 20-30 elo. When I would reduce the depth at a fail-high it still could produce the good score and mainline since the hash-table has all the best moves right resulting in several to many extensions.

This is similar to the tt-singular idea in robolito and friends. I've tried several variations, but not your "4 tt moves in a row to trigger an extension." Won't work for me, period, because I use the speed optimization of whenever I have no best move to store (ALL node, for example) I store the FIRST move I searched. Since I search the TT move without generating moves, it can occasionally save time. It is a performance enhancement, rather than a search improvement (I search the same tree if I don't do this, but I have to generate moves first, and occasionally an ALL node becomes a CUT node and this "pseudo-best-move" will cause a fail high with less effort (no move generation). But this means I would be extending way too much using your idea, since every hash entry has a "best move" even though they are often not a "best move" at all, just "a legal move".

The question was if reducing the depth at a fail-high can produce the real score and the answer is yes. I noticed Richard told you the same thing.

"yes" is not helpful. "How" would be. If you back up several iterations, how can you hope to get the same score you will get from several iterations deeper???

Until you get to the same depth, anyway...

I get the point of backing up a bit, because move ordering is now broken, and backing up a few plies gives you easier searches to establish some move ordering for the new move. But "the score"? Can't see how it can be correct until you get to the depth where it fails high, otherwise it would have failed high at earlier depths, don't you think???

So maybe you get "a score" when you back up, and by the time you get back to the right depth you get "the score". That I would buy.

I think you are underestimating what others have inside:
[d] 8/8/8/3k4/8/8/8/1NN1KNN1 w - -

Code: Select all

ProDeo 1.81
 00:00:41  18.00  13.87  1.Nc3 Kd6 2.Nd3 Kc7 3.Ne3 Kb6 4.Ncd5 Kb5
 00:00:49  18.03  13.87  1.Nf3 
 00:00:50  18.03  14.02  1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kb5 4.Nc3 Kb6 
 00:01:04  19.00  14.07  1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kb5 4.Nc3 Kb6 
 00:02:26  20.00  M 17   1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kd5 4.Nc3 Kd6 5.Nb5 

And now I let it run from the well ordered hash table by taking back 1.Nf3 and then the mate is found 2 plies earlier because of the PVS extension.

Code: Select all

 00:00:05  16.00  13.77  1.Nc3 Kc4 2.Kd2 Kc5 3.Ne3 Kd6 4.Nd3 Kc6 5.Nf3 
 00:00:14  17.00  13.77  1.Nc3 Ke5 2.Nf3 Kf4 3.N1d2 Kg4 4.Ne5 Kf5 5.Nc6 
 00:00:39  18.00  M 17   1.Nc3 Ke5 2.Nf3 Kf4 3.Ke2 Kf5 4.Ne3 Ke6 5.Nd4 

Known behavior. It is how we solve fine 70 in under 26 plies, when it takes 26 non-capturing moves before the first pawn is actually captured (won). If you actually do perfect move ordering, it takes you 26 plies. Taking less than 26 plies requires a sub-optimal move ordering.

Not sure what this has to do with the TT extension, however... The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

We are not in your class room here and I am not one of your 18 year old inexperienced students. The above position was checked WITH and WITHOUT the PVS extension. I can give you hundreds of similar examples but you prefer to scoff and doubt the work of others anyway. Robert's smart-fail-high can easily work by various search mechanisms you are unaware of, my PVS extension is just a demonstration of one of the possibilities.

[bob]

I understand the idea, although I do not buy "all in" that it is correct. Why would one do things so differently in the PV, that you make it very hard for a non-PV move to fail high in the first place??? I don't personally assume that this is the way things have to be done, it's just the way some do it at the moment. From a theoretical perspective, it seems wrong, however.

I am not sure how an idea that produces elo can be wrong. About a year of ten ago I added (what I called) the PVS extension as described here. It's (still) good for 20-30 elo. When I would reduce the depth at a fail-high it still could produce the good score and mainline since the hash-table has all the best moves right resulting in several to many extensions.

This is similar to the tt-singular idea in robolito and friends. I've tried several variations, but not your "4 tt moves in a row to trigger an extension." Won't work for me, period, because I use the speed optimization of whenever I have no best move to store (ALL node, for example) I store the FIRST move I searched. Since I search the TT move without generating moves, it can occasionally save time. It is a performance enhancement, rather than a search improvement (I search the same tree if I don't do this, but I have to generate moves first, and occasionally an ALL node becomes a CUT node and this "pseudo-best-move" will cause a fail high with less effort (no move generation). But this means I would be extending way too much using your idea, since every hash entry has a "best move" even though they are often not a "best move" at all, just "a legal move".

The question was if reducing the depth at a fail-high can produce the real score and the answer is yes. I noticed Richard told you the same thing.

"yes" is not helpful. "How" would be. If you back up several iterations, how can you hope to get the same score you will get from several iterations deeper???

Until you get to the same depth, anyway...

I get the point of backing up a bit, because move ordering is now broken, and backing up a few plies gives you easier searches to establish some move ordering for the new move. But "the score"? Can't see how it can be correct until you get to the depth where it fails high, otherwise it would have failed high at earlier depths, don't you think???

So maybe you get "a score" when you back up, and by the time you get back to the right depth you get "the score". That I would buy.

I think you are underestimating what others have inside:
[d] 8/8/8/3k4/8/8/8/1NN1KNN1 w - -

Code: Select all

ProDeo 1.81
 00:00:41  18.00  13.87  1.Nc3 Kd6 2.Nd3 Kc7 3.Ne3 Kb6 4.Ncd5 Kb5
 00:00:49  18.03  13.87  1.Nf3 
 00:00:50  18.03  14.02  1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kb5 4.Nc3 Kb6 
 00:01:04  19.00  14.07  1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kb5 4.Nc3 Kb6 
 00:02:26  20.00  M 17   1.Nf3 Kc5 2.Nd3 Kc4 3.Ke2 Kd5 4.Nc3 Kd6 5.Nb5 

And now I let it run from the well ordered hash table by taking back 1.Nf3 and then the mate is found 2 plies earlier because of the PVS extension.

Code: Select all

 00:00:05  16.00  13.77  1.Nc3 Kc4 2.Kd2 Kc5 3.Ne3 Kd6 4.Nd3 Kc6 5.Nf3 
 00:00:14  17.00  13.77  1.Nc3 Ke5 2.Nf3 Kf4 3.N1d2 Kg4 4.Ne5 Kf5 5.Nc6 
 00:00:39  18.00  M 17   1.Nc3 Ke5 2.Nf3 Kf4 3.Ke2 Kf5 4.Ne3 Ke6 5.Nd4 

Known behavior. It is how we solve fine 70 in under 26 plies, when it takes 26 non-capturing moves before the first pawn is actually captured (won). If you actually do perfect move ordering, it takes you 26 plies. Taking less than 26 plies requires a sub-optimal move ordering.

Not sure what this has to do with the TT extension, however... The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

We are not in your class room here and I am not one of your 18 year old inexperienced students. The above position was checked WITH and WITHOUT the PVS extension. I can give you hundreds of similar examples but you prefer to scoff and doubt the work of others anyway. Robert's smart-fail-high can easily work by various search mechanisms you are unaware of, my PVS extension is just a demonstration of one of the possibilities.

Did you read this:

The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

See all those "mights" in there. Your "PVS" extension is hardly new. As I said, variations have been around forever. None have really passed the "big testing" validation however. Have you tested it with 20-30K games to see how it really works? Or is this based on your 1990-era testing where you played 40 long games and decided whether something was good or bad???

I can certainly test it easily enough, it is simple to code... I am just not big on extending the PV artificially, while ignoring the non-PV moves. It has some upsides, but also a big cost on the downside...

And also, this really has nothing to do with Houdini either...

[Rebel]

Not sure what this has to do with the TT extension, however... The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

We are not in your class room here and I am not one of your 18 year old inexperienced students. The above position was checked WITH and WITHOUT the PVS extension. I can give you hundreds of similar examples but you prefer to scoff and doubt the work of others anyway. Robert's smart-fail-high can easily work by various search mechanisms you are unaware of, my PVS extension is just a demonstration of one of the possibilities.

Did you read this:

The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

[Class in]

Apologies master Bob, your humble student (even after 32 years) is still unware of such side effects.

See all those "mights" in there. Your "PVS" extension is hardly new. As I said, variations have been around forever. None have really passed the "big testing" validation however. Have you tested it with 20-30K games to see how it really works? Or is this based on your 1990-era testing where you played 40 long games and decided whether something was good or bad???

Yes master Bob, none of us worthy to claim an elo improvement without your approval.

[/Class out]

[bob]

Not sure what this has to do with the TT extension, however... The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

We are not in your class room here and I am not one of your 18 year old inexperienced students. The above position was checked WITH and WITHOUT the PVS extension. I can give you hundreds of similar examples but you prefer to scoff and doubt the work of others anyway. Robert's smart-fail-high can easily work by various search mechanisms you are unaware of, my PVS extension is just a demonstration of one of the possibilities.

Did you read this:

The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

[Class in]

Apologies master Bob, your humble student (even after 32 years) is still unware of such side effects.

See all those "mights" in there. Your "PVS" extension is hardly new. As I said, variations have been around forever. None have really passed the "big testing" validation however. Have you tested it with 20-30K games to see how it really works? Or is this based on your 1990-era testing where you played 40 long games and decided whether something was good or bad???

Yes master Bob, none of us worthy to claim an elo improvement without your approval.

[/Class out]

Take your extra jerk pill this morning or something. I simply said "might be". If you are unaware of something, figure it out. You've made WAY too many incorrect statements in the past for my tastes. Particularly when dealing with testing changes. If I question how you arrived at some conclusion, it is with good reason. So, again, did you test PROPERLY or did you come to your conclusions years ago when you came up with your PVS extension idea, where you were testing in what everyone now knows is "random noise"???

[Rebel]

Not sure what this has to do with the TT extension, however... The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

We are not in your class room here and I am not one of your 18 year old inexperienced students. The above position was checked WITH and WITHOUT the PVS extension. I can give you hundreds of similar examples but you prefer to scoff and doubt the work of others anyway. Robert's smart-fail-high can easily work by various search mechanisms you are unaware of, my PVS extension is just a demonstration of one of the possibilities.

Did you read this:

The mate you give might NOT be found 2 plies earlier because of the extension, it might also be found due to a lucky TT hit that gives you a more accurate search the second time around...

[Class in]

Apologies master Bob, your humble student (even after 32 years) is still unware of such side effects.

See all those "mights" in there. Your "PVS" extension is hardly new. As I said, variations have been around forever. None have really passed the "big testing" validation however. Have you tested it with 20-30K games to see how it really works? Or is this based on your 1990-era testing where you played 40 long games and decided whether something was good or bad???

Yes master Bob, none of us worthy to claim an elo improvement without your approval.

[/Class out]

Take your extra jerk pill this morning or something. I simply said "might be". If you are unaware of something, figure it out. You've made WAY too many incorrect statements in the past for my tastes. Particularly when dealing with testing changes. If I question how you arrived at some conclusion, it is with good reason. So, again, did you test PROPERLY or did you come to your conclusions years ago when you came up with your PVS extension idea, where you were testing in what everyone now knows is "random noise"???

Patronizing the work of others seems to be your trademark nowadays.

Re-read what I initially stated: It's (still) good for 20-30 elo.

But test it yourself, the parameter to turn off the PVS extension is:

Code: Select all

[M37_COUNT = 100]               * cancel PVS extension

[ZirconiumX]

Bob,

Ed is a 70-odd year old man.

He is retired.

He does not have the hyperfast testing facilities that you have.

He does not have a 10 node cluster.

He does not have a crappy IBRIX filesystem.

He does not have a Cray supercomputer lying around, etc. etc.

He is not the richest person in the world.

He is not able to afford your facilities.

So, unless you want to test every last change since REBEL 1, let him be.

Matthew:out

[Rebel]

Ed is a 70-odd year old man.

2 mistakes in a 7 word sentence

Lemme rephrase:

Ed is a 62 year nice guy

[mcostalba]

Bob,

Ed is a 70-odd year old man.

He is retired.

He does not have the hyperfast testing facilities that you have.

He does not have a 10 node cluster.

He does not have a crappy IBRIX filesystem.

He does not have a Cray supercomputer lying around, etc. etc.

He is not the richest person in the world.

He is not able to afford your facilities.

So, unless you want to test every last change since REBEL 1, let him be.

Matthew:out

Matthew, I am not sure you have understood the danger you are heading to full stream These 2 guys were already enjoying fighting each other well before you were borne.

P.S: In Italy we say "Who has the bread doesn't have the teeth, who has the teeth doesn't have the bread".