I get an instant 4 ply search returning mate on the move...OliverBr wrote: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
Problem with exploding tree because of extensions
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Problem with exploding tree because of extensions
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: Problem with exploding tree because of extensions
Maybe this can be tried:OliverBr wrote: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.bob wrote: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.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:
There is no further limitation of the extension and in most cases it's not necessary.Code: Select all
nch = attacked(kingpos[c^1], c^1); if (nch) ext++; // Check Extension else if (n == 1) ext++; //Singular reply extension
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...
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:
etc...And as white has more than 50 moves each turn, the tree exploded even more.Code: Select all
1. Qgh8+ Kg5 2. Q8g7+ Kf4 3. Qgh6+ Kg3 ....
1) Do not extend when you are winning (maybe based on eval)
2) Keep track of the extension it took each ply. Do not allow to have more than x number of extensions in the last x+y plies. (it works as a fractional plies, which I believe are not needed)
Miguel
PS: This position is funny for Gaviota, it finds mate in one node. I wish it has the same move ordering all the time
1 1 0.0 +Mat_1 5.Rd6#
70 2 0.0 +Mat_1 5.Rd6#
139 3 0.0 +Mat_1 5.Rd6#
Last edited by michiguel on Wed Jan 06, 2010 4:40 pm, edited 1 time in total.
-
- Posts: 725
- Joined: Tue Dec 18, 2007 9:38 pm
- Location: Munich, Germany
- Full name: Dr. Oliver Brausch
Re: Problem with exploding tree because of extensions
Of course, me too, when I do not extend *ALL* singular replys and checks with a full OnePly and then immediately with only searching 18 nodes and 2 evals!bob wrote:I get an instant 4 ply search returning mate on the move...OliverBr wrote: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
Code: Select all
./olithink -sd 12 "6Q1/1p5Q/1qp2k2/4rP2/pP2p1b1/P7/1BP3B1/3R3K w - - 0 8"
go
1 31999 0 20 d1d6
8. ... d1d6
kibitz W: 31999 Nodes: 18 QNodes: 2 Evals: 2 cs: 0 knps: 20
1-0 {White mates}
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Problem with exploding tree because of extensions
Yes it will.OliverBr wrote:That is an awesome idea! I will try this in the next version, I guess I will save a lot of CPU Time.bob wrote:... 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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Problem with exploding tree because of extensions
You have to be very careful with extensions. If you allow more than 1 full extension per ply, you are guaranteed to hang up at times. If you allow exactly 1 full extension per ply, you will reach positions where you again hang for a long time. If you limit this to less than 1 full extension per ply, the problem disappears, although there will always be issues if you do _any_ extensions at all, since that can greatly increase the size of a single branch compared to the rest.OliverBr wrote:Of course, me too, when I do not extend *ALL* singular replys and checks with a full OnePly and then immediately with only searching 18 nodes and 2 evals!bob wrote:I get an instant 4 ply search returning mate on the move...OliverBr wrote: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
Code: Select all
./olithink -sd 12 "6Q1/1p5Q/1qp2k2/4rP2/pP2p1b1/P7/1BP3B1/3R3K w - - 0 8" go 1 31999 0 20 d1d6 8. ... d1d6 kibitz W: 31999 Nodes: 18 QNodes: 2 Evals: 2 cs: 0 knps: 20 1-0 {White mates}
-
- Posts: 725
- Joined: Tue Dec 18, 2007 9:38 pm
- Location: Munich, Germany
- Full name: Dr. Oliver Brausch
Re: Problem with exploding tree because of extensions
That's the reason why every single strong open source chess engine uses practional plies, Glaurung, Crafty, Strelka, Toga, Stockfish ...bob wrote:You have to be very careful with extensions. If you allow more than 1 full extension per ply, you are guaranteed to hang up at times. If you allow exactly 1 full extension per ply, you will reach positions where you again hang for a long time. If you limit this to less than 1 full extension per ply, the problem disappears, although there will always be issues if you do _any_ extensions at all, since that can greatly increase the size of a single branch compared to the rest.OliverBr wrote:Of course, me too, when I do not extend *ALL* singular replys and checks with a full OnePly and then immediately with only searching 18 nodes and 2 evals!bob wrote:I get an instant 4 ply search returning mate on the move...OliverBr wrote: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
Code: Select all
./olithink -sd 12 "6Q1/1p5Q/1qp2k2/4rP2/pP2p1b1/P7/1BP3B1/3R3K w - - 0 8" go 1 31999 0 20 d1d6 8. ... d1d6 kibitz W: 31999 Nodes: 18 QNodes: 2 Evals: 2 cs: 0 knps: 20 1-0 {White mates}
I guess Crafty hasn't always used fractional plies, when did you implement it?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Problem with exploding tree because of extensions
I don't use 'em any more. I started using them pretty early, probably 1995 or so when Crafty came out. But as recent testing proved that most of the extensions were slightly worse with than without, I removed them. And without them, fractional plies were unnecessary and I removed that as well.OliverBr wrote:That's the reason why every single strong open source chess engine uses practional plies, Glaurung, Crafty, Strelka, Toga, Stockfish ...bob wrote:You have to be very careful with extensions. If you allow more than 1 full extension per ply, you are guaranteed to hang up at times. If you allow exactly 1 full extension per ply, you will reach positions where you again hang for a long time. If you limit this to less than 1 full extension per ply, the problem disappears, although there will always be issues if you do _any_ extensions at all, since that can greatly increase the size of a single branch compared to the rest.OliverBr wrote:Of course, me too, when I do not extend *ALL* singular replys and checks with a full OnePly and then immediately with only searching 18 nodes and 2 evals!bob wrote:I get an instant 4 ply search returning mate on the move...OliverBr wrote: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
Code: Select all
./olithink -sd 12 "6Q1/1p5Q/1qp2k2/4rP2/pP2p1b1/P7/1BP3B1/3R3K w - - 0 8" go 1 31999 0 20 d1d6 8. ... d1d6 kibitz W: 31999 Nodes: 18 QNodes: 2 Evals: 2 cs: 0 knps: 20 1-0 {White mates}
I guess Crafty hasn't always used fractional plies, when did you implement it?
-
- Posts: 725
- Joined: Tue Dec 18, 2007 9:38 pm
- Location: Munich, Germany
- Full name: Dr. Oliver Brausch
Re: Problem with exploding tree because of extensions
That's funny as I am hesitating to implement them. But on the other hand all those strong engines use them. Glaurung is the master of fracional plies. This must have a reason. ...bob wrote:I don't use 'em any more. I started using them pretty early, probably 1995 or so when Crafty came out. But as recent testing proved that most of the extensions were slightly worse with than without, I removed them. And without them, fractional plies were unnecessary and I removed that as well.OliverBr wrote:That's the reason why every single strong open source chess engine uses practional plies, Glaurung, Crafty, Strelka, Toga, Stockfish ...bob wrote:You have to be very careful with extensions. If you allow more than 1 full extension per ply, you are guaranteed to hang up at times. If you allow exactly 1 full extension per ply, you will reach positions where you again hang for a long time. If you limit this to less than 1 full extension per ply, the problem disappears, although there will always be issues if you do _any_ extensions at all, since that can greatly increase the size of a single branch compared to the rest.OliverBr wrote:Of course, me too, when I do not extend *ALL* singular replys and checks with a full OnePly and then immediately with only searching 18 nodes and 2 evals!bob wrote:I get an instant 4 ply search returning mate on the move...OliverBr wrote: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
Code: Select all
./olithink -sd 12 "6Q1/1p5Q/1qp2k2/4rP2/pP2p1b1/P7/1BP3B1/3R3K w - - 0 8" go 1 31999 0 20 d1d6 8. ... d1d6 kibitz W: 31999 Nodes: 18 QNodes: 2 Evals: 2 cs: 0 knps: 20 1-0 {White mates}
I guess Crafty hasn't always used fractional plies, when did you implement it?
What about the idea that instead of extending certain "interesting" moves, just reduce all the other moves, those who are not "interesting".
The result would be similar, but you don't have the danger of running into a tree explosion.. ?!
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: Problem with exploding tree because of extensions
Bob,bob wrote: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.OliverBr wrote: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.bob wrote: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.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:
There is no further limitation of the extension and in most cases it's not necessary.Code: Select all
nch = attacked(kingpos[c^1], c^1); if (nch) ext++; // Check Extension else if (n == 1) ext++; //Singular reply extension
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...
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:
etc...And as white has more than 50 moves each turn, the tree exploded even more.Code: Select all
1. Qgh8+ Kg5 2. Q8g7+ Kf4 3. Qgh6+ Kg3 ....
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.
Are you suggesting that there might be some gain extending less as you approach the leaf nodes of the search?
-
- Posts: 1357
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Problem with exploding tree because of extensions
My engine also only has extensions for check and singular reply, and they are also full ply extensions because I have not implemented fractional extensions.OliverBr wrote: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:
etc...And as white has more than 50 moves each turn, the tree exploded even more.Code: Select all
1. Qgh8+ Kg5 2. Q8g7+ Kf4 3. Qgh6+ Kg3 ....
However, I do put a limit on the amount of extensions I allow for any one branch of the tree (it is currently set at 10), and Myrddin finds the Mate instantly at depth 1.
I believe some other engines put a limit on extensions (and reductions), and I did that to specifically avoid these kinds of potential search explosions.
jm