Problem with exploding tree because of extensions

[bob]

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

I get an instant 4 ply search returning mate on the move...

[michiguel]

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.

Maybe this can be tried:
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#

[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

I get an instant 4 ply search returning mate on the move...

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!

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}

[bob]

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

Yes it will.

[bob]

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

I get an instant 4 ply search returning mate on the move...

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!

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}

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]

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

I get an instant 4 ply search returning mate on the move...

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!

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}

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.

That's the reason why every single strong open source chess engine uses practional plies, Glaurung, Crafty, Strelka, Toga, Stockfish ...

I guess Crafty hasn't always used fractional plies, when did you implement it?

[bob]

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

I get an instant 4 ply search returning mate on the move...

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!

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}

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.

That's the reason why every single strong open source chess engine uses practional plies, Glaurung, Crafty, Strelka, Toga, Stockfish ...

I guess Crafty hasn't always used fractional plies, when did you implement it?

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]

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

I get an instant 4 ply search returning mate on the move...

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!

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}

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.

That's the reason why every single strong open source chess engine uses practional plies, Glaurung, Crafty, Strelka, Toga, Stockfish ...

I guess Crafty hasn't always used fractional plies, when did you implement it?

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.

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

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

[Don]

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.

Bob,

Are you suggesting that there might be some gain extending less as you approach the leaf nodes of the search?

[JVMerlino]

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.

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.

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