Houdini 3 reducing the depth feature

[MM]

Hi all,

i noticed, using the Shredder 12 gui, that in analysis Houdini 3 reduces suddenly the depth of the search when he finds a very good move (but i don't know basing on which criteria it decides to reduce or not)

I remember that Robert Houdart talked about this feature some months ago but honestly i don't remember the details.

My question is: does this feature work in games and not only in analysis and how exactly does it work?

Thank you in advance for a clarification.

Best Regards

[Houdini]

My question is: does this feature work in games and not only in analysis and how exactly does it work?

The "Smart Fail High" feature is active in analysis and game play.

The idea was to avoid the situation where an engine finds a significantly better move at high search depth, but then requires a lot of time to compute the exact score and the principal variation (PV) for this better move.
A typical example is that the engine sees a "fail high" after 10 minutes, but then needs another hour to produce the score and PV.

In this situation Houdini 3 will reduce the search depth so that the PV is found much faster - often 5 to 10 times faster.
This trick has worked so well that I've activated it even at fairly low search depth, for analysis and game play.

Robert

[bob]

My question is: does this feature work in games and not only in analysis and how exactly does it work?

The "Smart Fail High" feature is active in analysis and game play.

The idea was to avoid the situation where an engine finds a significantly better move at high search depth, but then requires a lot of time to compute the exact score and the principal variation (PV) for this better move.
A typical example is that the engine sees a "fail high" after 10 minutes, but then needs another hour to produce the score and PV.

In this situation Houdini 3 will reduce the search depth so that the PV is found much faster - often 5 to 10 times faster.
This trick has worked so well that I've activated it even at fairly low search depth, for analysis and game play.

Robert

But you don't find THE score and PV. It took until THIS depth to find the fail high. You won't necessarily find the REASON for the fail high with a shallower depth. The move most likely will just fail high due to the TT information, without any score or reliable PV...

A variation on this makes sense, when failing low. Because you zero in on PV moves quicker. But you won't see the REAL score until you get back to the current depth...

I fail to see the point myself, for dropping depth on a fail high, unless you just want to output SOMETHING, regardless of whether it is actually real or not.

[Houdini]

Houdini 3 finds THE score and PV.

The technical idea behind this is the difference in pruning and extensions between PV nodes and non-PV nodes.
If you find a fail-high for a non-PV node at depth 30, it's very likely that when it becomes a PV node the fail-high can be found at reduced depth.

Houdini 3 demonstrates how remarkably effective this idea is.

[bob]

Houdini 3 finds THE score and PV.

The technical idea behind this is the difference in pruning and extensions between PV nodes and non-PV nodes.
If you find a fail-high for a non-PV node at depth 30, it's very likely that when it becomes a PV node the fail-high can be found at reduced depth.

Houdini 3 demonstrates how remarkably effective this idea is.

How? A simple example. At depth 30, where the fail high occurs, you store TT entries for plies 1, 3, 5, ..., 29 that say "score >= beta". For plies 2, 4, ..., 30, you store TT entries that say "score <= alpha".

When you back up the depth a bit (I do not know how far you back it up, you can supply that number if you want, so I will use 6 for this discussion, to have a number to work with), when you search this particular move, you will see "> beta" but with a big draft. At depth=24, that big draft will swamp the basic search depth and the TT will cause you to fail high, but the search won't be able to relax beta and get a real score at only depth 24. I don't see how you are going to get a true score until you get back to depth=30. Unless you say you extend the PV itself for some reason, but not the other moves. Maybe every now and then you get lucky, but it is not going to produce a true score and PV every time. I'm not even convinced it will do so the majority of the time, although I will test this again.

It isn't a new idea. And there are many others that have been used in the past, both for fail highs and for fail lows. On a fail low, it sounds reasonable to back the depth up and find a new best move. And the TT should protect that fail-low entry to make the move continue to fail low even when you back the thing up. Unless something goes wrong. And when it does, your re-searches are totally wasted as you now find the same move to be best again, yet you already know it is bad.

I simply don't like the idea of reporting something that might be right some of the time, or even most of the time. Some programs have a badly broken multi-PV mode, for example, that can report a PV from a previous iteration as if it was from the current one.

[Modern Times]

Let me see: Houdini 450-500 Elo stronger than Crafty. Advantage Robert.

[Uri Blass]

Houdini 3 finds THE score and PV.

The technical idea behind this is the difference in pruning and extensions between PV nodes and non-PV nodes.
If you find a fail-high for a non-PV node at depth 30, it's very likely that when it becomes a PV node the fail-high can be found at reduced depth.

Houdini 3 demonstrates how remarkably effective this idea is.

How? A simple example. At depth 30, where the fail high occurs, you store TT entries for plies 1, 3, 5, ..., 29 that say "score >= beta". For plies 2, 4, ..., 30, you store TT entries that say "score <= alpha".

When you back up the depth a bit (I do not know how far you back it up, you can supply that number if you want, so I will use 6 for this discussion, to have a number to work with), when you search this particular move, you will see "> beta" but with a big draft. At depth=24, that big draft will swamp the basic search depth and the TT will cause you to fail high, but the search won't be able to relax beta and get a real score at only depth 24. I don't see how you are going to get a true score until you get back to depth=30. Unless you say you extend the PV itself for some reason, but not the other moves. Maybe every now and then you get lucky, but it is not going to produce a true score and PV every time. I'm not even convinced it will do so the majority of the time, although I will test this again.

It isn't a new idea. And there are many others that have been used in the past, both for fail highs and for fail lows. On a fail low, it sounds reasonable to back the depth up and find a new best move. And the TT should protect that fail-low entry to make the move continue to fail low even when you back the thing up. Unless something goes wrong. And when it does, your re-searches are totally wasted as you now find the same move to be best again, yet you already know it is bad.

I simply don't like the idea of reporting something that might be right some of the time, or even most of the time. Some programs have a badly broken multi-PV mode, for example, that can report a PV from a previous iteration as if it was from the current one.

I understand that Robert houdart does significant reductions of non pv moves.

He does not extend the pv move but reduce many non pv moves
and it often reduce non pv moves by 3 plies if you believe houdini's output(you do not have to believe houdini's output and I remember that rybka showed wrong output about depth and nodes per second but
I can say that the idea is not something that is obviously wrong).

[rvida]

How? A simple example. At depth 30, where the fail high occurs, you store TT entries for plies 1, 3, 5, ..., 29 that say "score >= beta". For plies 2, 4, ..., 30, you store TT entries that say "score <= alpha".

When you back up the depth a bit (I do not know how far you back it up, you can supply that number if you want, so I will use 6 for this discussion, to have a number to work with), when you search this particular move, you will see "> beta" but with a big draft. At depth=24, that big draft will swamp the basic search depth and the TT will cause you to fail high, but the search won't be able to relax beta and get a real score at only depth 24. I don't see how you are going to get a true score until you get back to depth=30.

Simply don't do hash cut-offs in pv-nodes and it will work just fine.

Unless you say you extend the PV itself for some reason, but not the other moves.

That is exactly what is happening in most modern engines. There is no pruning in PV nodes and reductions are more conservative. PV search to nominal depth N actually tends to be much deeper than a non-pv search to the same nominal depth N.

[Don]

Let me see: Houdini 450-500 Elo stronger than Crafty. Advantage Robert.

Please show a little respect.

[Carotino]

It works! I'm using a similar method in the new Vitruvius (less sophisticated than the one implemented by Robert) and results are surprising. For example, in this position:

FEN: r3b1k1/1rq1bppp/2n1p3/ppPpP3/2pP1P2/P1P1BB2/3Q2PP/1R2NRK1 w - - 0 1

Vitruvius 1.16 (in "Deep-Analysis" mode) finds, surprisingly quickly, the best move: 1.f5!
This without going too deep... I believe that this move is very difficult to find, for any engine ... Except, of course, Vitruvius 1.16 in "Deep-Analysis" mode and Houdini-3 in Tactical Mode.

Another example:

FEN: r1bq1rk1/ppp3b1/3p1nn1/P1PPp1Bp/1P2P3/1QNN1Pp1/4B1P1/R4RK1 b - - 0 1

Vitruvius 1.16 "Deep-Analysis" finds the best move (1.Bh6!) in only 4 minuts, on my computer. Depth: 21 plyes. At the same time Stockfish is at depth=27 plyes... And has not yet found the solution!

I do not own Houdini-3 and then I could not do the tests, but I think between the various engines is the only one who can find, such as Vitruvius 1.16, the solution in reasonable time...

P.S. I'm sorry, but I don't know how you post pictures.

Roberto.