Page 1 of 4
Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 12:55 am
by OliverBr
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...
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 3:46 am
by rvida
Try to exdend one ply only in pv nodes, half ply in non-pv nodes.
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 6:36 am
by bob
OliverBr wrote: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.
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 6:37 am
by bob
rvida wrote: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.
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 6:54 am
by Uri Blass
bob wrote:rvida wrote: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.
It may be harder to find a new best move in other cases but it is not clear that the other cases are more important.
I wonder if you tried to test extending single reply to checks only in pv nodes.
Uri
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 7:07 am
by bob
Uri Blass wrote:bob wrote:rvida wrote: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.
It may be harder to find a new best move in other cases but it is not clear that the other cases are more important.
I wonder if you tried to test extending single reply to checks only in pv nodes.
Uri
Yes I did. As well as other ideas such as the rather ridiculous "extend the PV just because it is the PV" idea. I found all extensions except for giving check to hurt. Although I did not test singular extensions (yet). But the one reply extension was no good, passed pawn extensions ditto, and the same for recapture extensions. And yes, I tried a bunch of values. 1/4 ply, 1/3 ply, 1/2 ply, 2/3 ply, 3/4 ply, etc. although nothing over 1.0
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 7:35 am
by Uri Blass
bob wrote:Uri Blass wrote:bob wrote:rvida wrote: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
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 8:19 am
by Gian-Carlo Pascutto
bob wrote:rvida wrote: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
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 8:38 am
by Uri Blass
Gian-Carlo Pascutto wrote:bob wrote:rvida wrote: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
Re: Problem with exploding tree because of extensions
Posted: Wed Jan 06, 2010 12:46 pm
by OliverBr
bob wrote:OliverBr wrote: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.