Problem with exploding tree because of extensions

[Steve Maughan]

I remember a version of Monarch that had a similar problem. The tree explosion occurred because the checks and single were taking the search deep into the tree and then "stupid" moves were being tried as well as the check. I think I solved it by only extending close, or maybe even at, the tips.

Cheers,

Steve

[OliverBr]

Can you explain what are the "tips"?

[OliverBr]

I search this position with OliThink 5.2.7 and it even does not come back from the search at depth 1, I interrupted with the "?" command after 5 minutes:

Code: Select all

./olithink64 -sd 12 "6Q1/1p5Q/1qp2k2/4rP2/pP2p1b1/P7/1BP3B1/3R3K w - - 0 8"
go
?
 1 31997  27509 248576748  h7h8 f6f5
8. ... h7h8

kibitz W: 31997 Nodes: 232391905 QNodes: 16184843 Evals: 380680823 cs: 27509 knps: 903

[Steve Maughan]

You're at a "tips" or leaf when depth = 1 i.e. last full search before QSearch. Currently I do the one reply and check extension in the first ply of the QSearch.

Cheers,

Steve

[OliverBr]

You're at a "tips" or leaf when depth = 1 i.e. last full search before QSearch. Currently I do the one reply and check extension in the first ply of the QSearch.

Cheers,

Steve

Ah ok, thank you.

Unfortunately that wouldn't help here, as the SingReply-Check sequences expand the tree whereever.

I think, there are only three possibilities to stop that:

1) Skip the SingReply Extension (most simple, thats what I did now)
2) Stop the extension at one point, e.g. if Sum(extensions) > 10 dont extend anymore (not elegant)
3) Make fractional extensions and give either check or SingReply and extension smaller than OnePly (elegant)

[bob]

Try to exdend one ply only in pv nodes, half ply in non-pv nodes.

bad idea. Means it is harder to find a _new_ best move, which is not what you want.

It is not clear to me that the idea of extending more pv nodes is bad
and I suspect that the idea is good.
You can find a new best move in case that the pv is bad.

How? You are not extending as much. I see absolutely no logic or reason to search PV paths deeper than non-PV paths. This makes the final result depend too much on luck, because you hope the real best move is the first one searched, otherwise you will search the others less deeply and fail to see that they are better tactically.

No

I do not hope the real best move is in the first one.

The idea is about cases that the first move fail low and you can see the fail low fast enough to find a different move(you do not find a different move in case that the first move does not fail low).

I understand that it does not work based on your testing but the idea is not obviously wrong.

Uri

That's the "trivial case". Suppose you start at -1.0 for several iterations. But as you go deeper, there is a move that takes you back to +3.0.... You have _not_ failed low, you just couldn't see how good the move was. So you were winning, you had a ponder miss and had to start off at a shallow depth, and early searches could not spot the win and found a move that appears best at shallow depths, but which is losing. How do you change your mind?

The idea of treating PV and non-PV moves differently is simply and basically flawed. Unless you are so sure of your move ordering that you believe you always get the best move ordered first. In that case, why do a search in the first place, just order the moves and play the first one.

This is intuitively a bad idea, and giving special-case examples of where it works is not very useful, because we need something that works for _all_ cases, if it is going to be useful.

[bob]

Try to exdend one ply only in pv nodes, half ply in non-pv nodes.

bad idea. Means it is harder to find a _new_ best move, which is not what you want.

If the PV line is suspect the score for it will drop earlier, allowing another move to replace it. When attempting to replace it, that alternative move will be the new PV and get the same extensions.

The idea is sound, in Go they call it UCT

What if you haven't failed low. I gave a simple example that happens with reasonable frequency in games I watch on ICC.

Again, treating the PV differently is flawed unless you are so sure that you have the best move ordered first, in which case you ought to just order and play the first move and forget the search.

You also didn't mention the most common case. The PV is not "suspect" but there are significantly better moves to play, if you can find them with a shallower-than-usual search.

[bob]

Try to exdend one ply only in pv nodes, half ply in non-pv nodes.

bad idea. Means it is harder to find a _new_ best move, which is not what you want.

If the PV line is suspect the score for it will drop earlier, allowing another move to replace it. When attempting to replace it, that alternative move will be the new PV and get the same extensions.

The idea is sound, in Go they call it UCT

This is exactly what I meant.

Thinking about it
There is also another case that it can help.
The pv line is good but the program does not see deep enough so later it changed its mind to another move and has no time for another iteration.

pv extension cause the pv move to get a better score so the program does not change its mind and choose a better move.

Uri

If you live by writing code that only works for exceptions, you will die by the more frequent non-exception cases.

[OliverBr]

... you are so sure of your move ordering that you believe you always get the best move ordered first. In that case, why do a search in the first place, just order the moves and play the first one.

That is an awesome idea! I will try this in the next version, I guess I will save a lot of CPU Time.

[bob]

Hello together, OliThink has a simple extension politic:
If the move is a checking move or you have a singular reply move, extend by one ply:

Code: Select all

nch = attacked(kingpos[c^1], c^1);
if (nch) ext++; // Check Extension
else if (n == 1) ext++; //Singular reply extension

There is no further limitation of the extension and in most cases it's not necessary.
But there are sometimes positions where it is possible that check leads to singular reply, then again check and again singular reply and so it searches the tree very, very deep without any sense.
The tree explodes and search is stuck until timeout.

I have no good idea how to handle this problem in an elegant way. I was looking at the code of Glaurung and I didn't find anything there what would stop Glaurung's extensions, but Glaurung for sure, never has that explosion.

Any idea how to solve it elegantily?

Edit: I now saw that Glaurung extensions are mainly < One Ply, chess extension = 60/100 Ply, singular reply = 45/100 Ply... Is this the best solution? Then I would have to make fractions...

sounds like you are not doing repetitions correctly. But in any case, you probably don't want to extend too far. You can limit the extensions so that beyond a certain depth (a function of iteration depth is convenient here) you extend less.

No, it is not about repitition. It's about a position found deep in search where two queens can chase the king over the board.
The problem is that I don't have factional plies. I think if I could only extend either the check or the singular reply to a fractional ply, let's say 80/100, the problem wouldn't occur.

PS: That is the position deep in search, where the full-non limited extentension lead to the massive tree explosion:

[d] 6Q1/1p5Q/1qp2k2/4rP2/pP2p1b1/P7/1BP3B1/3R3K w - - 0 8

Even though it's a mate in 1, OliThink with full-ply extensions doesnt come back from search, because there is possible long line the two queens chasing the king in a check/singular-reply/check/singular-reply style like e.g:

Code: Select all

1. Qgh8+ Kg5 2. Q8g7+ Kf4 3. Qgh6+ Kg3 .... 

etc...And as white has more than 50 moves each turn, the tree exploded even more.

First, chasing the king is not so common because of repetitions. But as I mentioned, you probably do want to taper extensions off. I deal with it in a simpler way because I do not allow for the possibility of a non-ending search. Which is exactly what you get if you can extend on every ply. The only possible way I can see this is with the so-called "straight-jacket" positions where every move is a check, including the replies by the opponent. But those involve limiting captures and don't cause an issue and never occur in real games anyway.

If you just extend when giving check, that means that 99.9% of the time you only extend one ply of every two, which results in a terminating search. On occasion escaping check will be a checking move itself, but this won't happen for several consecutive moves in a path, except for the rare exception discussed first, above.