Problem with exploding tree because of extensions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
OliverBr
Posts: 240
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Contact:

Problem with exploding tree because of extensions

Post by OliverBr » Tue Jan 05, 2010 11:55 pm

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...

User avatar
rvida
Posts: 481
Joined: Thu Apr 16, 2009 10:00 am
Location: Slovakia, EU

Re: Problem with exploding tree because of extensions

Post by rvida » Wed Jan 06, 2010 2:46 am

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

bob
Posts: 20887
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Problem with exploding tree because of extensions

Post by bob » Wed Jan 06, 2010 5:36 am

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&#40;kingpos&#91;c^1&#93;, c^1&#41;;
if &#40;nch&#41; ext++; // Check Extension
else if &#40;n == 1&#41; 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.

bob
Posts: 20887
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Problem with exploding tree because of extensions

Post by bob » Wed Jan 06, 2010 5:37 am

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.

Uri Blass
Posts: 8752
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Problem with exploding tree because of extensions

Post by Uri Blass » Wed Jan 06, 2010 5:54 am

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

bob
Posts: 20887
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Problem with exploding tree because of extensions

Post by bob » Wed Jan 06, 2010 6:07 am

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

Uri Blass
Posts: 8752
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Problem with exploding tree because of extensions

Post by Uri Blass » Wed Jan 06, 2010 6:35 am

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

Gian-Carlo Pascutto
Posts: 1194
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: Problem with exploding tree because of extensions

Post by Gian-Carlo Pascutto » Wed Jan 06, 2010 7:19 am

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 :)

Uri Blass
Posts: 8752
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Problem with exploding tree because of extensions

Post by Uri Blass » Wed Jan 06, 2010 7:38 am

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

OliverBr
Posts: 240
Joined: Tue Dec 18, 2007 8:38 pm
Location: Munich, Germany
Contact:

Re: Problem with exploding tree because of extensions

Post by OliverBr » Wed Jan 06, 2010 11:46 am

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&#40;kingpos&#91;c^1&#93;, c^1&#41;;
if &#40;nch&#41; ext++; // Check Extension
else if &#40;n == 1&#41; 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.
Last edited by OliverBr on Wed Jan 06, 2010 11:55 am, edited 6 times in total.

Post Reply