depth based extensions

[Uri Blass]

I wonder if you have extensions that are different for different remaining depth.

my function that calculate the extensions is dependent on the following factors:
1)alpha
2)remaining depth
3)position of the board.

I calculate today extensions after calling to alphabeta
I understood that for using hash tables in an efficient way it may be better to calculate extensions before calling alphabeta

I tried first to calculate extensions simply after making move but I found that it cannot be the same because after making move I can call alphabeta more than once with different depths and the extensions may be different.

I can calculate extensions simply before calling alphabeta when I know the remaining depth and know alpha but the question is if doing extensions that are dependent on these factors cannot increase problems of instability when I try to use hash for pruning.

What is your experience?

[H.G.Muller]

I am not sure I understand why it would matter where you take the decision, for instability. What is calling 'before alpha-beta' for one node, is still calling it within alpha-beta for the parent.

Based on theoretical considerations, I would think that the safest way to do it is this:

If you want to extend a certain branch, you take that decision within the first node on that branch, so that all moves in that node benifit from the extension. AlphaBeta(n) will than in fact do a common (n+1) ply search. (Or an n-ply search, depending on alpha.)

But you would store it in the hash with a draft of the search that was actually done (n+1 or n). If you then later retrieve the node, it really makes no difference if it is the result from an (n+1)-ply search because of an n-ply search request that was extended, or the result of a non-extended (n+1)-ply search request.

Depending on the new alpha, you take the extension decision again, before deciding if what you find in the hash suits you or not. If not, you have to do a re-search. If you needed the n-ply result, but the bound of the (n+1)-ply stored result is suitable, you will use the latter, of course.

This might still cause instabilities in the parent node, but I don't see that these instabilities would be any worse than the instabilities you normally get due to hashing: Sometimes re-searching gives you an unexpectedly different result, because some branches were based on hash-entries of deeper-than-necessary draft, and they might be different moves all the time.

[Daniel Mehrmann]

Hi !

This idea is very bad. Move based extensions are much better. The trick is to search good moves very deep and silly moves very short. Your idea just blow up the tree.

Best,
Daniel

[Uri Blass]

Hi !

This idea is very bad. Move based extensions are much better. The trick is to search good moves very deep and silly moves very short. Your idea just blow up the tree.

Best,
Daniel

I do not think depth based extensions is basically bad but maybe it is better to do it by other means.

The point is that when I simplify the position I want to extend because it is more easy to search and I want to extend more when the remaining depth is bigger.

transition to pawn endgame is an extreme example of this point.

Maybe better solution is simply to extend simple positions so it is not going to be easier to search them to big depth and it seems that yace does it for pawn endgames so it does not show big depth

for example

New game - Rybka 2.1o 32-bit
4k3/pppppppp/8/PPPPPPPP/4K3/8/8/8 w - - 0 1

Analysis by Yace 0.99.87:
1.d6 exd6 2.exd6 cxd6 3.b6 a6 4.cxd6 Kf8 5.Kf4 f6 6.g6 Kg8 7.Ke4 hxg6 8.hxg6 Kf8 9.Kd5 Ke8 10.Ke4 Kd8 11.Kd5 Ke8 12.Ke4 Kd8 13.Kd5 Ke8
+- (1.41) Depth: 9/30 00:01:46 106221kN

(, 05.10.2006)

Uri

[H.G.Muller]

Hi !

This idea is very bad. Move based extensions are much better. The trick is to search good moves very deep and silly moves very short. Your idea just blow up the tree.

Best,
Daniel

Not at all. My tree is exactly as big as your tree. The only thing that differs is where you take the decision, not what you base it on. Seen from the node where you take the decision, in your case you would take a decision for the move that you generate in the node itself, while I would take the decision based on characteristics of the position that the move created. This makes it a more objective decision, and reduces search instability.

[Chan Rasjid]

... The trick is to search good moves very deep and silly moves very short. .....
Best,
Daniel

The above has a catch. What is good for one side is bad for the other and so may be flawed. I once pointed this to Sergei that he should not extend (promotion) a good move and he agreed. He then indirectly pointed out that the (only) reason to extend is when there is a posssibility of instability in the search score; I have now basically taken this to be correct.

eg (mine) if we have a window of (v2Pawn, infi) and in check -
search to depth = n may be give a pv, but search to n+1 may indicate a minus-mate; a variation from about v2Pawn to -infi !

So high probablility of instability in the search score may be the only basis for extension.

Rasjid

[Fritz Grau]

I wonder if you have extensions that are different for different remaining depth.

That could only work with an extension concept that is more intelligent than the one I use: If I extend a node, I store its search depth in the hash table decremented by one, as if I had NOT extended it: Otherwise, the engine would use the hash value for the extended search in the next depth iteration step (but I would again intend an extended, so I would want to do a new extended search instead of using the hash value).[/quote]

[Peter Fendrich]

The point is that when I simplify the position I want to extend because it is more easy to search and I want to extend more when the remaining depth is bigger.
Uri

Uri, to extend when the position is simplified seems perfectly ok to me but why exted more when the remaining depth is bigger? Do you mean that the information given by the extension at that point is more valuable? I have been thinking of a method to extend as usual at any depth but further down the path extend more if it is still accurate to do so. The first extension is done for some reason and further down the tree, if that reason remain valid, extend more.
/Peter

[Uri Blass]

The point is that when I simplify the position I want to extend because it is more easy to search and I want to extend more when the remaining depth is bigger.
Uri

Uri, to extend when the position is simplified seems perfectly ok to me but why exted more when the remaining depth is bigger? Do you mean that the information given by the extension at that point is more valuable? I have been thinking of a method to extend as usual at any depth but further down the path extend more if it is still accurate to do so. The first extension is done for some reason and further down the tree, if that reason remain valid, extend more.
/Peter

I already suggested that it may be better in the last post that I used in this thread.

Note only that if I do it the term depth is totally losing it's meaning because the program extend every move in simple positions and I may search every line to depth 8 or bigger in pawn endgame inspite of having nominal depth of 6.

Uri

[H.G.Muller]

I am not sure it makes sense to search some moves much deeper than others just because you can do so (cheaply). So you get a very reliable score for that move... So what? If the score of the move you compare it with remains unreliable, the probability that you pick the wrong one won't go down much.

It does make sense to extend positions with only Pawns, or without Sliders. Because they need a much larger depth to get the same reliability. While Sliders can reach every square on the board in just a few moves, trivial things like the loss of an undefendable Pawn might show up only after 10 ply, just because of the time it takes to go there. With Sliders you will know if your Slider can reach an undefended piece before his Slider can defend it in 5 ply or so...

In Pawn endings, apart from extending it, I used to search moving the same Pawn as before even in QS, while standing pat in reply to a Pawn move was penalized by 6 Pawns or so...