Winboard Forum

In an attempt to get more efficient search trees, I would like to remove any tactical exchanges that just delay the unavoidable (perhaps even at the cost of a sacrifice) from the ply-depth count. For capture-recapture tactics this is easy enough: both the capture and the recapture can be given an extension of 1 ply. This sounds expensive, but the exchange simplifies the situation, so that in all end-leaves of that branch the QS will be that much simpler. In fact it simply advances the moves that would have been condidered in QS anyway towards the root, which is not that bad.

Unfortunately, capture-recapture tactics is not the only way to stall for time. Threat-retreat (or other modes of dealing with the threat) are just as important. But unlike captures, there is no guarantee that threats ever run out, and usually they would not be looked at in QS. This makes awarding extensions for threat-evasion a dangerous thing, and in combination with awarding extensions for the threats themselves a recipe for disaster.

One way I am using to combat this problem is to use dual accounting of ply depth. Moves of one side can then never push moves of the other side over the horizon, and threats do not need an extension (just the threat evasions). This system is very difficult to combine with hashing, though. So I am wondering if there would not be a way to keep the threat+retreat extensions under control in a single-depth accounting scheme. Does anyone have any experience with this, perhaps in the context of check + check-evasion extensions?

I realize that a sequence of checks can potentially go on for a long time, or even forever. But if this possibility occurs in the tree, and if the ability to withdraw from the check determines on which side of the window the score ends up, it seems that there is no easy way out: any work you spend on expanding the tree elsewhere is very likely to be wasted. So making a wild guess as to how this King chase will end, and then generally deepening the search until the outcome comes within the horizon seems a really bad idea. You simply have to know the outcome of this branch first, and only then you know which remaining branches of the tree need deepening, and which can be pruned. Whatever many extensions it might take, better apply that extra depth only to this branch than to the tree in general...

Would it be a solution to be extremely selective in awarding the extension for the check-evasion? For example, rely on the ordinary search depth to find a way to a safe place, and only award the extension if the PV of the subtree from this move tells us that we can?

In an attempt to get more efficient search trees, I would like to remove any tactical exchanges that just delay the unavoidable (perhaps even at the cost of a sacrifice) from the ply-depth count. For capture-recapture tactics this is easy enough: both the capture and the recapture can be given an extension of 1 ply. This sounds expensive, but the exchange simplifies the situation, so that in all end-leaves of that branch the QS will be that much simpler. In fact it simply advances the moves that would have been condidered in QS anyway towards the root, which is not that bad.

I think that extending only recaptures is a good idea. If you extend any captures the tree will certainly explode. Even you have to limit the recapture to be on the same square as the capturer. Otherwise things
like exd5 Qxa2 dxe6 will all be extended. What is common is recaptures
of the same piece on the same square (BXN RxB), this steals 2ply of search. I extend on the recapture only and it seems to work ok for me.

Unfortunately, capture-recapture tactics is not the only way to stall for time. Threat-retreat (or other modes of dealing with the threat) are just as important. But unlike captures, there is no guarantee that threats ever run out, and usually they would not be looked at in QS. This makes awarding extensions for threat-evasion a dangerous thing, and in combination with awarding extensions for the threats themselves a recipe for disaster.

yes i was not happy with the threat extensions i tried even with fractional extensions becuase of that problem. What i prefered to do is to not extend nor reduce this moves when i detect a threat. Note that reduction is just a negative extension so to not reduce is a form of extension.
May be some special threat extensions might need real extension, but i haven't figured out a way that works for me.

One way I am using to combat this problem is to use dual accounting of ply depth. Moves of one side can then never push moves of the other side over the horizon, and threats do not need an extension (just the threat evasions). This system is very difficult to combine with hashing, though. So I am wondering if there would not be a way to keep the threat+retreat extensions under control in a single-depth accounting scheme. Does anyone have any experience with this, perhaps in the context of check + check-evasion extensions?

Most people do threat evasion extensions when a mate threat is detected.
And also when the king has only a few moves. I think extending on "threat/re-threat" could be overdoing it. Even it is hard to constrain Check + Single_respone kind of extension in my experience.

So making a wild guess as to how this King chase will end, and then generally deepening the search until the outcome comes within the horizon seems a really bad idea.

I think you can not guess efficiently what might happen. You might know the position is interesting in which case it is good to extend to have the feel of who is going to win. passed pawn extensions are good examples for this.

Would it be a solution to be extremely selective in awarding the extension for the check-evasion? For example, rely on the ordinary search depth to find a way to a safe place, and only award the extension if the PV of the subtree from this move tells us that we can?

I don't understand here. The first move is usually the one that needs the extension in case of threats, so you have to decide if to extend it before searching.

Daniel
[/code]

Daniel Shawul wrote:

Would it be a solution to be extremely selective in awarding the extension for the check-evasion? For example, rely on the ordinary search depth to find a way to a safe place, and only award the extension if the PV of the subtree from this move tells us that we can?

I don't understand here. The first move is usually the one that needs the extension in case of threats, so you have to decide if to extend it before searching.

What I meant is that you don't have to start immediately searching extended moves at full depth. First search all moves at the nominal depth, then decide which moves you want to extend, and search those one ply deeper. A bit in the spirit of IID. That way you postpone the decision to extend to the very last moment, when you have lots of information to base it on: from the move that refuted most other moves (and in particular the null move) you can deduce what the threat is you might be pushing over the horizon, and for a move that seems to help you know the reply (e.g. I checked his King with a Pawn, and he captured it). From this it should be possible to get an idea as to whether the apparent solution to the trouble that other moves encountered might just have been playing for time, rather than interfering with the threat itself, which therefore is likely to still exist behind the horizon.

This sounds like Singular extensions, where you have to prove all other moves are inferior to the first move by doing a reduced depth search with a lowered alpha. If all moves fail low , extend the "singular" move.
I think this was found out to be computationally expensive.

I guess it is indeed related to it. I would not apply it necessarily to a single move, though, if, for instance, you could recapture a Queen in two ways, both ways seem to deserve an extension.

If something is expensive or not, is always a difficult question. Doing an N-ply search with some moves extended to N+1 will no doubt significantly drive up the node count w.r.t. a simple N-ply search. But it will still be much cheaper than a full-width (N+1)-ply search. So if the extensions allowed you to see all tactics that otherwise would require N+1 ply, they still are a bargain even if the price was high...

I can imagine that you really have to implement this consistently for it to pay off. If you would only extend part of the moves that deserve an extension, you would have to search at N+1 ply anyway, to cover the blind spots that the unjustly non-extended moves would give you, and that would then defeat the entire purpose.

I have been experimenting with just such an extension for some time ...

Though, 'experimenting' might be too 'scientific' a word. More like, 'fooling around with' would be better


At times, it seems to be no worse than without it, so I think it has potential

Currently only doing the extension in nodes not predicted to fail low.

I call it Empty Threat Detection

H.G.Muller wrote:I guess it is indeed related to it. I would not apply it necessarily to a single move, though, if, for instance, you could recapture a Queen in two ways, both ways seem to deserve an extension.

If something is expensive or not, is always a difficult question. Doing an N-ply search with some moves extended to N+1 will no doubt significantly drive up the node count w.r.t. a simple N-ply search. But it will still be much cheaper than a full-width (N+1)-ply search. So if the extensions allowed you to see all tactics that otherwise would require N+1 ply, they still are a bargain even if the price was high...

I can imagine that you really have to implement this consistently for it to pay off. If you would only extend part of the moves that deserve an extension, you would have to search at N+1 ply anyway, to cover the blind spots that the unjustly non-extended moves would give you, and that would then defeat the entire purpose.

Hi Harm-Geert,

the Deep Blue way of handeling this was only calling a move forced when it would exceed beta, and giving the extension on research of this move.

There is some logic in it, and I'm using it in a few cases.

Tony