Adding an Extension Results in Deeper General Search!

Discussion of chess software programming and technical issues.

Moderator: Ras

User avatar
Steve Maughan
Posts: 1315
Joined: Wed Mar 08, 2006 8:28 pm
Location: Florida, USA

Adding an Extension Results in Deeper General Search!

Post by Steve Maughan »

I've just implemented an extension for pawn pushes to the 7th and no reduction for pawn pushes to the 6th.

I used this position to test:
[d]2Q5/2pNp3/2k4p/p3P1P1/2P5/2pq4/1n6/6K1 w - -
Here is the search before added the extension...

Code: Select all

9/33   0:00   -2.42    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke4 
                       6.Qxe7 Qg3+ 7.Kf1 hxg5 8.Qh7+ Ke3 
                       9.Qf5 Nxc4 (1.485.496) 

10/40  0:01   -2.57    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke4 
                       6.Qxe7 Qd1+ 7.Kh2 Qh5+ 8.Kg3 hxg5 
                       9.Qc5 Qf3+ 10.Kh2 Qe2+ 11.Kg3 Nxc4 (3.179.438) 2679 

11/40  0:04   -2.96    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Qd7+ Kxc4 
                       6.Qc6+ Kb3 7.gxh6 Qe3+ 8.Kg2 Qg5+ 
                       9.Kh3 Qh5+ 10.Kg2 Qg4+ 11.Kf1 Qf4+ 
                       12.Kg1 Nd3 13.Qd5+ Kc2 (11.300.617) 2772 

12/46  0:12   -3.47    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qe3+ Kf6 
                       9.Nxc7 Nxc4 10.Qc3+ Kg6 11.Qg3+ Kh5 
                       12.Qh2+ Kg5 (35.327.161) 2855 

13/50  0:26   -4.21    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qc1 Nxc4 
                       9.Nxc7 Kd4 10.Kh2 Qe5+ 11.Kh3 Qxc7 
                       12.Qxc2 (75.593.943) 2884 

14/50  0:39   -4.21    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qc1 Nxc4 
                       9.Nxc7 Kd4 10.Kh2 Qe5+ 11.Kh3 Qxc7 
                       12.Qxc2 (113.001.928) 2847 

15/54  1:43   -4.54    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qd2 Qg4+ 
                       9.Kh2 Qh4+ 10.Kg2 Qe4+ 11.Kg3 Nxc4 
                       12.Qg5+ Kd4 13.h7 Qxh7 14.Nxc7 Qd3+ 
                       15.Kg4 (298.181.767) 2883 

15/54  2:01   -4.53++  3.Qa6+ (347.680.740) 2851 

15/54  2:02   -4.54    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qd2 Qg4+ 
                       9.Kh2 Qh4+ 10.Kg2 Qe4+ 11.Kg3 Nxc4 
                       12.Qg5+ Kd4 13.h7 Qxh7 14.Nxc7 Qd3+ 
                       15.Kg4 (350.071.225) 2852
Notice that after 2 minutes it has only search to a depth of 15 ply.

And here is the search after the extensions are added.

Code: Select all

13/40  0:00   -2.33    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke3 
                       6.Qb6+ Ke4 7.Nxe7 Qd1+ 8.Kg2 Qf3+ 
                       9.Kg1 Qg3+ 10.Kf1 Qd3+ 11.Kg1 Nxc4 (1.642.846) 

14/40  0:01   -2.33    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke3 
                       6.Qb6+ Ke4 7.Nxe7 Qd1+ 8.Kg2 Qf3+ 
                       9.Kg1 Qg3+ 10.Kf1 Qd3+ 11.Kg1 Nxc4 (2.678.710) 2473 

15/40  0:02   -2.70    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Qb6+ Kxe5 
                       6.Qxa5+ Kf4 7.Qc7+ Kxg5 8.Qxe7+ Kg4 
                       9.Qe6+ Qf5 10.Qe2+ Kf4 (6.278.271) 2512 

16/40  0:04   -2.91    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke3 
                       6.Nxe7 hxg5 7.Qxa5 Nxc4 8.Qc5+ Ke4 
                       9.e6 Qg3+ 10.Kh1 Qh3+ 11.Kg1 Qe3+ 
                       12.Qxe3+ Kxe3 (12.296.189) 2523 

17/44  0:09   -3.06    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Qd7+ Kxc4 
                       6.Qe6+ Qd5 7.Qa6+ Qb5 8.Qe6+ Kd3 
                       9.Qg6+ Kd2 10.gxh6 Qc5+ 11.Kh1 Qxe5 (24.636.998) 2552 

18/44  0:17   -3.51    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke4 
                       6.Nxe7 Qg3+ 7.Kf1 Qf4+ 8.Kg2 Qxg5+ 
                       9.Kh3 Qh5+ 10.Kg3 Qf3+ 11.Kh4 Qf4+ 
                       12.Kh3 Qf1+ 13.Kg4 Nxc4 (46.210.403) 2577 

19/48  0:55   -3.81    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qd7+ Kxe5 
                       6.Qxc7+ Kf5 7.gxh6 Nxc4 8.h7 c2 
                       9.Qc8+ Kf4 10.Qf8+ Qf5 11.Qh6+ Qg5+ 
                       12.Qxg5+ Kxg5 13.h8Q c1Q+ 14.Kg2 (148.990.133) 2689 

19/48  0:59   -3.80++  3.Qa6+ (159.443.383) 2680 

19/48  0:59   +5.32    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 Qxa8 7.g7 Qf3 8.g8Q+ Qf8 9.Qg2 Qf1+ 
                       10.Kxf1 Kf8 11.Qd5 Kg7 12.Qxa5 Nd1 
                       13.Qe5+ Kg6 14.Qxc7 (159.912.039) 2680 

20/48  1:01   +5.38    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 Qxa8 7.g7 Qf3 8.g8Q+ Qf8 9.Qg2 Qf2+ 
                       10.Kxf2 Kf8 11.Qf3+ Kg8 12.Qf7+ Kh8 
                       13.Qf8+ Kh7 14.Qxe7+ Kg6 15.Qxc7 (163.736.457) 2665 

21/48  1:07   +8.39    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 c2 7.Qc6+ Qd7 8.exd7+ Kd8 
                       9.Qa8+ Kxd7 10.Qd5+ Ke8 11.Qb5+ c6 
                       12.Qxb2 a4 13.Qxc2 a3 14.g7 Kf7 (176.493.006) 2618 

22/48  1:16   +8.67    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 c2 7.Qc6+ Qd7 8.exd7+ Kd8 
                       9.Qa8+ Kxd7 10.Qd5+ Ke8 11.Qb5+ c6 
                       12.Qxb2 a4 13.Qxc2 a3 14.g7 Kf7 
                       15.Qe4 (194.654.792) 2549
With the extension Maverick find the key move at depth 19 after 59 seconds. This means the extensions accelerated the search through the earlier plys. This seems counter intuitive to me. An extension normally slows down the search. I can only assume it was helpful at creating cutoffs for bad moves at lower depths.

Has anyone else see this behavior?

- Steve
http://www.chessprogramming.net - Juggernaut & Maverick Chess Engine
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Adding an Extension Results in Deeper General Search!

Post by bob »

Steve Maughan wrote:I've just implemented an extension for pawn pushes to the 7th and no reduction for pawn pushes to the 6th.

I used this position to test:
[d]2Q5/2pNp3/2k4p/p3P1P1/2P5/2pq4/1n6/6K1 w - -
Here is the search before added the extension...

Code: Select all

9/33   0:00   -2.42    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke4 
                       6.Qxe7 Qg3+ 7.Kf1 hxg5 8.Qh7+ Ke3 
                       9.Qf5 Nxc4 (1.485.496) 

10/40  0:01   -2.57    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke4 
                       6.Qxe7 Qd1+ 7.Kh2 Qh5+ 8.Kg3 hxg5 
                       9.Qc5 Qf3+ 10.Kh2 Qe2+ 11.Kg3 Nxc4 (3.179.438) 2679 

11/40  0:04   -2.96    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Qd7+ Kxc4 
                       6.Qc6+ Kb3 7.gxh6 Qe3+ 8.Kg2 Qg5+ 
                       9.Kh3 Qh5+ 10.Kg2 Qg4+ 11.Kf1 Qf4+ 
                       12.Kg1 Nd3 13.Qd5+ Kc2 (11.300.617) 2772 

12/46  0:12   -3.47    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qe3+ Kf6 
                       9.Nxc7 Nxc4 10.Qc3+ Kg6 11.Qg3+ Kh5 
                       12.Qh2+ Kg5 (35.327.161) 2855 

13/50  0:26   -4.21    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qc1 Nxc4 
                       9.Nxc7 Kd4 10.Kh2 Qe5+ 11.Kh3 Qxc7 
                       12.Qxc2 (75.593.943) 2884 

14/50  0:39   -4.21    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qc1 Nxc4 
                       9.Nxc7 Kd4 10.Kh2 Qe5+ 11.Kh3 Qxc7 
                       12.Qxc2 (113.001.928) 2847 

15/54  1:43   -4.54    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qd2 Qg4+ 
                       9.Kh2 Qh4+ 10.Kg2 Qe4+ 11.Kg3 Nxc4 
                       12.Qg5+ Kd4 13.h7 Qxh7 14.Nxc7 Qd3+ 
                       15.Kg4 (298.181.767) 2883 

15/54  2:01   -4.53++  3.Qa6+ (347.680.740) 2851 

15/54  2:02   -4.54    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qg4+ Kxe5 
                       6.gxh6 c2 7.Qg5+ Qf5 8.Qd2 Qg4+ 
                       9.Kh2 Qh4+ 10.Kg2 Qe4+ 11.Kg3 Nxc4 
                       12.Qg5+ Kd4 13.h7 Qxh7 14.Nxc7 Qd3+ 
                       15.Kg4 (350.071.225) 2852
Notice that after 2 minutes it has only search to a depth of 15 ply.

And here is the search after the extensions are added.

Code: Select all

13/40  0:00   -2.33    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke3 
                       6.Qb6+ Ke4 7.Nxe7 Qd1+ 8.Kg2 Qf3+ 
                       9.Kg1 Qg3+ 10.Kf1 Qd3+ 11.Kg1 Nxc4 (1.642.846) 

14/40  0:01   -2.33    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke3 
                       6.Qb6+ Ke4 7.Nxe7 Qd1+ 8.Kg2 Qf3+ 
                       9.Kg1 Qg3+ 10.Kf1 Qd3+ 11.Kg1 Nxc4 (2.678.710) 2473 

15/40  0:02   -2.70    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Qb6+ Kxe5 
                       6.Qxa5+ Kf4 7.Qc7+ Kxg5 8.Qxe7+ Kg4 
                       9.Qe6+ Qf5 10.Qe2+ Kf4 (6.278.271) 2512 

16/40  0:04   -2.91    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke3 
                       6.Nxe7 hxg5 7.Qxa5 Nxc4 8.Qc5+ Ke4 
                       9.e6 Qg3+ 10.Kh1 Qh3+ 11.Kg1 Qe3+ 
                       12.Qxe3+ Kxe3 (12.296.189) 2523 

17/44  0:09   -3.06    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Qd7+ Kxc4 
                       6.Qe6+ Qd5 7.Qa6+ Qb5 8.Qe6+ Kd3 
                       9.Qg6+ Kd2 10.gxh6 Qc5+ 11.Kh1 Qxe5 (24.636.998) 2552 

18/44  0:17   -3.51    3.Nb8+ Kc5 4.Qxc7+ Kd4 5.Nc6+ Ke4 
                       6.Nxe7 Qg3+ 7.Kf1 Qf4+ 8.Kg2 Qxg5+ 
                       9.Kh3 Qh5+ 10.Kg3 Qf3+ 11.Kh4 Qf4+ 
                       12.Kh3 Qf1+ 13.Kg4 Nxc4 (46.210.403) 2577 

19/48  0:55   -3.81    3.Nb8+ Kc5 4.Na6+ Kd4 5.Qd7+ Kxe5 
                       6.Qxc7+ Kf5 7.gxh6 Nxc4 8.h7 c2 
                       9.Qc8+ Kf4 10.Qf8+ Qf5 11.Qh6+ Qg5+ 
                       12.Qxg5+ Kxg5 13.h8Q c1Q+ 14.Kg2 (148.990.133) 2689 

19/48  0:59   -3.80++  3.Qa6+ (159.443.383) 2680 

19/48  0:59   +5.32    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 Qxa8 7.g7 Qf3 8.g8Q+ Qf8 9.Qg2 Qf1+ 
                       10.Kxf1 Kf8 11.Qd5 Kg7 12.Qxa5 Nd1 
                       13.Qe5+ Kg6 14.Qxc7 (159.912.039) 2680 

20/48  1:01   +5.38    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 Qxa8 7.g7 Qf3 8.g8Q+ Qf8 9.Qg2 Qf2+ 
                       10.Kxf2 Kf8 11.Qf3+ Kg8 12.Qf7+ Kh8 
                       13.Qf8+ Kh7 14.Qxe7+ Kg6 15.Qxc7 (163.736.457) 2665 

21/48  1:07   +8.39    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 c2 7.Qc6+ Qd7 8.exd7+ Kd8 
                       9.Qa8+ Kxd7 10.Qd5+ Ke8 11.Qb5+ c6 
                       12.Qxb2 a4 13.Qxc2 a3 14.g7 Kf7 (176.493.006) 2618 

22/48  1:16   +8.67    3.Qa6+ Kxd7 4.e6+ Ke8 5.Qa8+ Qd8 
                       6.g6 c2 7.Qc6+ Qd7 8.exd7+ Kd8 
                       9.Qa8+ Kxd7 10.Qd5+ Ke8 11.Qb5+ c6 
                       12.Qxb2 a4 13.Qxc2 a3 14.g7 Kf7 
                       15.Qe4 (194.654.792) 2549
With the extension Maverick find the key move at depth 19 after 59 seconds. This means the extensions accelerated the search through the earlier plys. This seems counter intuitive to me. An extension normally slows down the search. I can only assume it was helpful at creating cutoffs for bad moves at lower depths.

Has anyone else see this behavior?

- Steve
I assume that second number (following depth) is the max depth? If so it looks even stranger as you are not searching as deeply with the new extension as you were before it was added...

At least something worth investigating carefully.
Top
zd3nik
Posts: 193
Joined: Wed Mar 11, 2015 3:34 am
Location: United States

Re: Adding an Extension Results in Deeper General Search!

Post by zd3nik »

I have seen extensions cause similar behavior, but never to such an extreme. Have you tried any other positions? With and without pawns near the 6th and 7th ranks?

STC
Top
Henk
Posts: 7251
Joined: Mon May 27, 2013 10:31 am

Re: Adding an Extension Results in Deeper General Search!

Post by Henk »

Each time I found a spectacular improvement I was wrong. Something like a bug that increased search depth by accident. Also the total amount of nodes searched through will not change. So if you extend there you will search less deep somewhere else. Nothing for free unless you skip useless operations.
Top
User avatar
Steve Maughan
Posts: 1315
Joined: Wed Mar 08, 2006 8:28 pm
Location: Florida, USA

Re: Adding an Extension Results in Deeper General Search!

Post by Steve Maughan »

Bob, Shawn & Henk,

It looks like the reduction in tree size is real for this position. However, after 2000 games only the "extend pawn move to the 7th" added any strength, and only 5 ELO.

I think this position is quite rare but the reduction in tree size is spectacular.

- Steve
http://www.chessprogramming.net - Juggernaut & Maverick Chess Engine
Top
User avatar
hgm
Posts: 28461
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Adding an Extension Results in Deeper General Search!

Post by hgm »

The extension helps to discover promotions earlier, and you test it on a position where there are promotions. So it seems logical they should save you time, by not getting a completely wrong score first, adapting the tree to that, and discover the next iteration it was all in vain, and having to search a completely different tree.

The downside of such extensions is that in other positions, where promotions have no chance, you would spend a lot of time on extending the lines where they could occur, withut coming up with a viable one.

The rule that timing on one individual position doesn't mean a thing seems especially valid in such a case.
Top
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Adding an Extension Results in Deeper General Search!

Post by bob »

hgm wrote:The extension helps to discover promotions earlier, and you test it on a position where there are promotions. So it seems logical they should save you time, by not getting a completely wrong score first, adapting the tree to that, and discover the next iteration it was all in vain, and having to search a completely different tree.

The downside of such extensions is that in other positions, where promotions have no chance, you would spend a lot of time on extending the lines where they could occur, withut coming up with a viable one.

The rule that timing on one individual position doesn't mean a thing seems especially valid in such a case.
I did a bunch of testing last year and earlier this year on singular extensions and threat extensions, and your point was dead on... In what I would call "constrained tactical positions" which are those that are pretty deep but narrow along the critical paths, SE looks very good. But then in testing in normal positions against varied opponents, it is hard to make it "pay off" because most positions are not so deep and narrow. every time I have tested, the check extension is a positive gain. But that is (so far anyway) the ONLY extension I have found that works. Yes I suppose one could argue that backing off on reductions for a very small subset of moves (like pawn pushes to the 6th or 7th is something like an extension, perhaps.. and those do work in actual games although they are not spectacular gains.

Also, with SMP searches, there are a number of occasions where a parallel search will sniff out something a couple of plies earlier, and that makes for spectacular speedup numbers since a significant score jump offsets the alpha/beta window and tree size shrinks significantly...
Top
elcabesa
Posts: 858
Joined: Sun May 23, 2010 1:32 pm

Re: Adding an Extension Results in Deeper General Search!

Post by elcabesa »

extending some ply in search let the tree became bigger, bu it probably let you found better moves earlier and you have a better move ordering with a smaller tree.....

it's so difficult to write a chess engine :P
Top
Dann Corbit
Posts: 12818
Joined: Wed Mar 08, 2006 8:57 pm
Location: Redmond, WA USA

Re: Adding an Extension Results in Deeper General Search!

Post by Dann Corbit »

You mentioned in CCC general forum that you added Stockfish null move pruning.

It carves off more and more as you go deeper. If you changed two things at once (added extensions + new null move methodology), maybe that is what you are seeing.
Top
User avatar
Eelco de Groot
Posts: 4697
Joined: Sun Mar 12, 2006 2:40 am
Full name:   Eelco de Groot

Re: Adding an Extension Results in Deeper General Search!

Post by Eelco de Groot »

It may also be that you see the effect of search luck, at least for the first part before finding the move, which I take to be the solution move, Qa6+. The search is a little bit different and add to that random luck in the first instance it finds the move 4. Na6+ faster, and that may result in deeper PVs. I think you see that with that move 4. Na6+ there are higher maximum depths. In the second search the PVs are shorter with 4. Qxc7+. If the evals are also a bit lower (actually that does not seem to be the case because they are higher, still Qa6+ is found faster. Height of alpha is not always a factor because with higer alpha your search also becomes more optimistic, to borrow a term from Rybka 1.0 beta, which somehow I have not seen (does not mean much, I do not follow it since a long time) in all the Rybka discussions, the optimistic and pessimistic search of Rybka 1.0 beta were definitely really not from Fruit :!:), both this and the extensions help to find the keymove faster. Well anyway in this case the extensions probably did it. After finding, alpha is so high all the other moves are cut off faster. Then it depends on how much work is going into the new PV with Qa6+

But overall, the extension looks good here!
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
Top

Return to “Computer Chess Club: Programming and Technical Discussions”