Houdini 3 reducing the depth feature

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Rebel, chrisw

MM
Posts: 766
Joined: Sun Oct 16, 2011 11:25 am

Houdini 3 reducing the depth feature

Post by 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
MM
User avatar
Houdini
Posts: 1471
Joined: Tue Mar 16, 2010 12:00 am

Re: Houdini 3 reducing the depth feature

Post by Houdini »

MM wrote: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
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Houdini 3 reducing the depth feature

Post by bob »

Houdini wrote:
MM wrote: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.
User avatar
Houdini
Posts: 1471
Joined: Tue Mar 16, 2010 12:00 am

Re: Houdini 3 reducing the depth feature

Post by 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
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Houdini 3 reducing the depth feature

Post by bob »

Houdini wrote: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
Posts: 3574
Joined: Thu Jun 07, 2012 11:02 pm

Re: Houdini 3 reducing the depth feature

Post by Modern Times »

Let me see: Houdini 450-500 Elo stronger than Crafty. Advantage Robert.
Uri Blass
Posts: 10424
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: Houdini 3 reducing the depth feature

Post by Uri Blass »

bob wrote:
Houdini wrote: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).
User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 12:00 pm
Location: Slovakia, EU

Re: Houdini 3 reducing the depth feature

Post by rvida »

bob wrote: 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.
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 4:27 pm

Re: Houdini 3 reducing the depth feature

Post by Don »

Modern Times wrote:Let me see: Houdini 450-500 Elo stronger than Crafty. Advantage Robert.
Please show a little respect.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
Carotino
Posts: 222
Joined: Fri Jun 11, 2010 10:40 am
Location: Italy

Re: Houdini 3 reducing the depth feature

Post by 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.
Roberto