Desperado wrote:
My point is that this is not about "widening" the tree. ...
Well terminology is confusing of course. Because the tree itself to
a fixed depth is not widened, just explored more accurate,
but depending
on depth.
Depends on your definition of "widening" and "deepening". If deepening is top to bottom, and width is left-to-right, wouldn't you have to agree that the shape of the tree continually gets wider as it gets deeper? You can play games by reducing the widening near the tips via pruning, but all that does is delay the widening. For example, rather than the dot plot of the tree looking like a triangle with the vertex pointing up and representing the root, while with LMR it is more like a pair of triangles, bases touching, with one vertex at the root, and the other vertex at the deepest tip branch touched. But here's the key. The area of either has to be the same, because we have a fixed search space. One goes deeper but more speculatively. The other goes less deeply but highly accurately for what it can "see".
If you widen the tree how can you also go deeper?
imho, this is one point you miss.
we _are already_ deeper.
if you compare the given examples, ply 8 will be reached(finished) faster.
the more softly the transition over the plies is (compared to depth<n condition)
the more powerful the ratio between accuracy/gainOfPlies may be.
I am not talking iteration-by-iteration. I am talking about "drop-dead terminate the search we are out of time". I have always agreed that as we go deeper, we gain accuracy. If you talk purely about plies, the LMR/pruning plies are worth less than the full-width plies. But we can get so many more of those LMR/futility plies that there is a gain. So no argument. Deeper == more accurate. For _any_ tree search anyone is using in chess...
And the EBF is not growing as depth grows, or you would see a serious limit when your EBF reaches 5 or whatever. So if EBF is constant from depth 1 to depth 24 ...
here, my point is the following.
EBF is growing, but
not unlimited. it is getting closer and closer to the "real" EBF.
once again, above you can see that depth 5-8 has EBF < 2, from depth 9
on it is 2 (let s assume the searcher searchs with EBF of 2)
I have measured this many times, over thousands of positions, iteration by iteration. I do not see this change in EBF. It certainly goes haywire when changing our minds a lot, because move ordering is broken and than runs EBF up signicantly. It is sometimes much lower than expected, when move ordering is nearly perfect as in some endgames. But overall, for a given position, I don't see it start low and go high...
Here are some simple iteration-by-iteration times from a longish time control (60 10) game played on icc:
.37, .62, .84, 1.5, 3.61, 6.96,
8.06, 12.72, 38.56, 43.0,
0.29, 0.45, 1.93, 1.52, 7.03, 4.32, 8.9, 18.11, 48.0, 71.0
The EBF numbers for that last case work out like this:
1.5, 4.3, 0.79, 4.6, 0.6, 2.1, 2.0, 2.7, 1.47
Doesn't quite "start small and get bigger" to my cursory examination. If you want more data, I can email you the entire game. Might be better to play one long game with noise set to 0 so that all the iterations are displayed. The early EBFs are no real good because I only measure time to 0.01 second resolution and early iterations have a lot of 0.00 type times or very small times that are more noise than real...
The first move is a pretty shallow "find a move to ponder search". The last one is for depths 15-25. Those times are the times required to finish an iteration, defined as T = time(current) - time(previous) where the times are the cumulative times printed at the end of each iteration as in this:
Code: Select all
depth time score variation (1)
15 0.57 0.20 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. a5 Qe7 19. Rfc1 Bxe3 20. Qxe3 Rfb8
21. Rab1 Rxb1 22. Rxb1 Nc5
15-> 0.63 0.20 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. a5 Qe7 19. Rfc1 Bxe3 20. Qxe3 Rfb8
21. Rab1 Rxb1 22. Rxb1 Nc5
16 0.82 0.16 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qe1 Rc6 20. Bf4 Qc7
21. Qf1 a5 22. Bb5 Bxf3 23. gxf3
16-> 0.92 0.16 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qe1 Rc6 20. Bf4 Qc7
21. Qf1 a5 22. Bb5 Bxf3 23. gxf3
17 1.19 0.15 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qe1 Qc7 20. Bf4 a5
21. Bd3 Bxf3 22. gxf3 Rfd8 23. Qe4
Kf8
17-> 1.37 0.15 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qe1 Qc7 20. Bf4 a5
21. Bd3 Bxf3 22. gxf3 Rfd8 23. Qe4
Kf8
18 1.82 0.19 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qd3 Be7 20. Qxa6 Ra8
21. Qb5 Ra5 22. Qb2 Rxa4 23. Be3 Ra2
24. Qb5
18-> 3.30 0.19 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qd3 Be7 20. Qxa6 Ra8
21. Qb5 Ra5 22. Qb2 Rxa4 23. Be3 Ra2
24. Qb5 (s=3)
19 4.06 0.12 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qd3 Be7 20. Qxa6 Ra8
21. Qb5 Ra5 22. Qb2 Rxa4 23. Be3 Ra2
24. Qb5 Nc5 25. Bxc5 Bxc5 26. Qxc5
Rxe2 (s=2)
19-> 4.82 0.12 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qd3 Be7 20. Qxa6 Ra8
21. Qb5 Ra5 22. Qb2 Rxa4 23. Be3 Ra2
24. Qb5 Nc5 25. Bxc5 Bxc5 26. Qxc5
Rxe2 (s=2)
19-> 4.82 0.12 15. ... Bd5 16. Qxc3 Bxc5 17. Rb1 O-O
18. Rd1 Rc8 19. Qd3 Be7 20. Qxa6 Ra8
21. Qb5 Ra5 22. Qb2 Rxa4 23. Be3 Ra2
24. Qb5 Nc5 25. Bxc5 Bxc5 26. Qxc5
Rxe2
20 9.57 0.16 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rb8 24. a5 Kh8 25. Bc4
20-> 11.80 0.16 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rb8 24. a5 Kh8 25. Bc4
21 13.64 0.15 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rb8 24. a5 Kh8 25. Kg1 Kg8
21-> 16.12 0.15 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rb8 24. a5 Kh8 25. Kg1 Kg8
22 20.38 0.11 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rd8 24. a5 Rb8 25. h3 Be4 26. Bc4
22-> 25.02 0.11 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rd8 24. a5 Rb8 25. h3 Be4 26. Bc4
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rd8 24. a5 Kf8 25. h3 Rb8 26. Bf1 Kg8
27. Bc4
24-> 1:31 0.12 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rd8 24. a5 Kf8 25. h3 Rb8 26. Bf1 Kg8
27. Bc4 (s=4)
25 1:52 0.16 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rd8 24. a5 Kf8 25. h4 Rb8 26. h5 Kg8
27. Kh2 Kh8 (s=3)
25-> 2:42 0.16 15. ... Bd5 16. Qxc3 Bxc5 17. Be3 O-O
18. Rfc1 Bxe3 19. Qxe3 Qa5 20. Qc3
Qxc3 21. Rxc3 Ra7 22. Re1 Re8 23. Kh1
Rd8 24. a5 Kf8 25. h4 Rb8 26. h5 Kg8
27. Kh2 Kh8 (s=4)
I would characterize it as "getting more accurate with depth" which is actually the point.
that is definitely true, but certainly not all to say about this mechanism.
This can be also viewed as verifcation of the _inner tree_ , while we
already examine a more complex problem (search space).
Is that not true of _any_ tree, pruned or not, reduced or not? You add another layer of moves on top and the deeper you progress below the root, the more accurately you refine the root score and PV. So I don't see this "revolutionary widening" idea. Nothing is new. The shape of the tree is certainly different, bug going a ply deeper helps any tree search.
Michael