Search extensions at promising trajectories

[smrf]

It would be interesting to know, whether there are experiences on that attempt, and if working on that idea could make sense.

Reinhard.

[Volker Annuss]

What do you mean by promising trajectories?

In Hermann I use fractional extensions. When a move is made, that is unrelated to the previous move and does not trigger an extension itself, the fractional part of the remaining depth is set to 0.

A move is related to the previous one if
- The moving piece became attacked by another opponent piece
- The moving piece is no longer defended by another own piece
- The destination square becomes defended by another own piece
- The destination square is no longer attacked by another opponent piece
- A pawn moves twice (other pieces moving twice are covered by the conditions above when they change the defence state of their destination square, so two moves of the same slider are still unrelated, if they stay on the same file/line/diagonal)

In older versions of Hermann I just reduced the fractional part of the remaining depth by a small amount for every move that is not extended.

Edit: replaced extension by remaining depth in the last sentence.

[Tony]

What do you mean by promising trajectories?

In Hermann I use fractional extensions. When a move is made, that is unrelated to the previous move and does not trigger an extension itself, the fractional part of the remaining depth is set to 0.

A move is related to the previous one if
- The moving piece became attacked by another opponent piece
- The moving piece is no longer defended by another own piece
- The destination square becomes defended by another own piece
- The destination square is no longer attacked by another opponent piece
- A pawn moves twice (other pieces moving twice are covered by the conditions above when they change the defence state of their destination square, so two moves of the same slider are still unrelated, if they stay on the same file/line/diagonal)

In older versions of Hermann I just reduced the fractional part of the remaining depth by a small amount for every move that is not extended.

Edit: replaced extension by remaining depth in the last sentence.

Hi Volker,

So several interesting moves in a row could (together) trigger a full ply, but if there is a crappy move in between, you throw away the whole extra stuff.

Interesting. Do you do anything special with the hashtable ( depth) ?

Cheers,

Tony

[smrf]

Well, Volker, a trajectory is for me a possible beneficial combination.

Reading your answer I see a problem: because your evaluation is depending on the prior move, and an identical situation nevertheless could be reached by other preceding moves, the reuse of result evaluations stored in the cache might no longer be applicateable. How do you handle this problem?

Reinhard.

[Volker Annuss]

Interesting. Do you do anything special with the hashtable ( depth) ?

Hi Tony,

there is nothing special in the Hash table. I always store the full remaining depth in the hash table including the fractional part, but that has nothing to do with reducing the extensions away.

Greetings
Volker

[Volker Annuss]

Well, Volker, a trajectory is for me a possible beneficial combination.

Reading your answer I see a problem: because your evaluation is depending on the prior move, and an identical situation nevertheless could be reached by other preceding moves, the reuse of result evaluations stored in the cache might no longer be applicateable. How do you handle this problem?

The idea for handling the extensions like that is to follow forcing move sequences.

The evaluation depends only on positions, not on the path that leads to it. Nevertheless extensions and reductions are path dependent and so is the minimax score calculated for an inner node.

There is nothing special about this reduction. For instance sometimes you can reach the same position by a path that gives check and by another path without check. Sometimes you can reach the same position by a path with a recapture and by another path with a quiet move between the captures. LMR also depends on history moves (even if you don't use them directly) and killer moves that may not be the same when you reach the position by different paths.

My reduction depends on the last two plies and only takes a possibly path dependent extension away. So I see no reason to handle that in a special way.

Greetings
Volker

[hgm]

I have been considering adding a recapture extension. In early uMax versions such an extension had a benificial effect, despite the fact it wrecked hashing by introducing path dependence (a problem that was ignored).

I can mimic the effect of the recapture extension in a path-independent way by extending good captures, as recaptures are typically good captures (and if they aren't, the extension was probably a simple waste of time anyway). But then a basic flaw in the strategy becomes obvious as well: it makes little sense to extend good moves, as good moves for one side are bad for the other side. In particular, the reply to a really stupid capture (like Q x defended P) is a very good capture, and if you extend it, you end up extending many branches that started with very poor moves, which deserve to be reduced much more than to be extended!

This could be cured by reducing bad captures. A stupid capture, followed by the refuting good capture, would then cancel reduction with extension, and be searched at nominal depth. An eaqual capture followed by the recapture (which must be good for the original capture to be equal) would only have the extension for the latter. An 'initiating' good capture (i.e. which was not a recapture) followed by a recapture (e.g. BxR, PxB) would even get an extension of two ply. If captures originally seemed bad (by SEE) but turn out to score good on search, we could re-search with extension, similar to LMR.

Has such a thing ever been been tried? The recapture in uMax became detrimental after I implemented null-move pruning. Probably because its most important effect is to combat horizon effect, by extending likely delaying tactics. NMP serves a similar function. But perhaps in combination with bad-capture reductions it could become beneficial again.

[bob]

I have been considering adding a recapture extension. In early uMax versions such an extension had a benificial effect, despite the fact it wrecked hashing by introducing path dependence (a problem that was ignored).

I can mimic the effect of the recapture extension in a path-independent way by extending good captures, as recaptures are typically good captures (and if they aren't, the extension was probably a simple waste of time anyway). But then a basic flaw in the strategy becomes obvious as well: it makes little sense to extend good moves, as good moves for one side are bad for the other side. In particular, the reply to a really stupid capture (like Q x defended P) is a very good capture, and if you extend it, you end up extending many branches that started with very poor moves, which deserve to be reduced much more than to be extended!

This could be cured by reducing bad captures. A stupid capture, followed by the refuting good capture, would then cancel reduction with extension, and be searched at nominal depth. An eaqual capture followed by the recapture (which must be good for the original capture to be equal) would only have the extension for the latter. An 'initiating' good capture (i.e. which was not a recapture) followed by a recapture (e.g. BxR, PxB) would even get an extension of two ply. If captures originally seemed bad (by SEE) but turn out to score good on search, we could re-search with extension, similar to LMR.

Has such a thing ever been been tried? The recapture in uMax became detrimental after I implemented null-move pruning. Probably because its most important effect is to combat horizon effect, by extending likely delaying tactics. NMP serves a similar function. But perhaps in combination with bad-capture reductions it could become beneficial again.

I no longer use recapture, as testing showed it was ineffectual at the deeper depths we are seeing nowadays. But what kind of transposition table inconsistencies are you seeing? I can't see how recapture extensions would be any different than any other type of extension with respect to the hash table information...

[smrf]

If the evaluation is depending on the path through wich a current position has been reached, a reuse of cached evaluation values found after different paths would end in false results. The difference may be not that big, but noticeable. Especially at multithreaded engines this effect partially is reason for randomly raising different results for identical start positions.

[hgm]

But what kind of transposition table inconsistencies are you seeing? I can't see how recapture extensions would be any different than any other type of extension with respect to the hash table information...

If something is a recapture or not depends on the path to the node, in particular on the preding move. E.g.

[d]2kr4/4p3/5q2/4Q3/8/8/7P/4R1K1 w - - 0 1


after 1. Kh1, Rg8 2. Qxf6, then 2. ..., exf6 would be a recapture, but after 1. Qxf6, Rg8+ 2. Kh1, the same position would be reached without 2. ..., exf6 being a recapture. So there would be two distinc search trees for the position after white's second move, one extending exf6, the other not, competing for the same hash entry. As you would probably meant toe xtend here, the recapture extension could be made ineffective by trying the second branch first, and then getting a hash hit on it during the search of the first branch.