Node counts at a given depth/iteration in search

[BB+]

If an iterative search is merely increasing "depth", then the profile of depths of opened nodes should look the same from one iteration to the next. For instance, in a uniform tree with branching factor 2, there are 50% of the nodes at depth X, 25% at depth X-1, etc., and this doesn't change from one iteration to the next. In perfectly ordered alpha-beta, there will be an odd/even effect. In practise, qsearch will modify this, as will transposition tables, IID, and more.

So I modified IvanHoe to count, for each iteration, the number of nodes opened at each depth. I counted null moves (this is one reason why I chose IvanHoe rather than Stockfish -- though IvanHoe has its own quirks with make_move in PV displays and the "top_analysis" code as opposed to gameplay).

Here are the raw depth counts from a depth 20 search with 256MB in the opening position.

Code: Select all

  Dp    Iter16   Iter17   Iter18   Iter19   Iter20
   0        45       22       23       43       22 
   1       209      239      303      249      146 
   2      1945     1843     1683     2289     1695 
   3      4901     5343     5121     5262     3204 
   4     21922    20244    21235    27347    18484 
   5     34551    39382    67607    63398    45608 
   6     85012   106860   160548   227442   184654 
   7    124170   135104   295477   333699   282654 
   8    169366   221123   410082   644275   608041 
   9    200970   256798   629915   764217   750276 
  10    187059   297808   697422  1075935  1023668 
  11    172671   278312   796728  1134349  1139478 
  12    145934   258857   738294  1230789  1245559 
  13    126882   227649   669976  1117824  1150965 
  14    102301   199457   576971  1000245  1028578 
  15     78317   174232   487356   844262   836121 
  16     57867   142300   398086   673770   661877 
  17     38967   115306   312304   530702   526115 
  18     26770    89250   236608   384870   384361 
  19     15806    68309   170661   275103   291216 
  20      9472    50356   117724   182858   199249 
  21      5198    33849    79783   119249   141855 
  22      3207    22429    53499    75284    94702 
  23      1577    13717    35301    47576    62354 
  24       891     7679    23937    30325    37694 
  25       340     3805    15869    19939    23258 
  26       206     1825    10809    13519    12652 
  27        64      792     6755     8559     6581 
  28        31      312     4092     5723     3289 
  29         7      122     2899     3525     1628 
  30         2       48     1659     2060      811 
  31         0       25     1097     1057      343 
  32         0        1      527      490      133 
  33         0        0      346      263       49 
  34         0        0      130      153       15 
  35         0        0       78       75        3 
  36         0        0       44       45        1 
  37         0        0       15       16        1 
  38         0        0        7        7        1 
  39         0        0        1        2        0 

Here are the percentages

Code: Select all

  Dp    Iter16   Iter17   Iter18   Iter19   Iter20
   0      0.00     0.00     0.00     0.00     0.00 
   1      0.01     0.01     0.00     0.00     0.00 
   2      0.12     0.07     0.02     0.02     0.02 
   3      0.30     0.19     0.07     0.05     0.03 
   4      1.36     0.73     0.30     0.25     0.17 
   5      2.14     1.42     0.96     0.58     0.42 
   6      5.26     3.85     2.28     2.10     1.71 
   7      7.68     4.87     4.20     3.08     2.63 
   8     10.48     7.97     5.83     5.94     5.65 
   9     12.43     9.26     8.96     7.05     6.97 
  10     11.57    10.74     9.92     9.92     9.51 
  11     10.68    10.04    11.33    10.46    10.58 
  12      9.03     9.33    10.50    11.35    11.57 
  13      7.85     8.21     9.53    10.31    10.69 
  14      6.33     7.19     8.21     9.22     9.55 
  15      4.84     6.28     6.93     7.78     7.77 
  16      3.58     5.13     5.66     6.21     6.15 
  17      2.41     4.16     4.44     4.89     4.89 
  18      1.66     3.22     3.37     3.55     3.57 
  19      0.98     2.46     2.43     2.54     2.70 
  20      0.59     1.82     1.67     1.69     1.85 
  21      0.32     1.22     1.13     1.10     1.32 
  22      0.20     0.81     0.76     0.69     0.88 
  23      0.10     0.49     0.50     0.44     0.58 
  24      0.06     0.28     0.34     0.28     0.35 
  25      0.02     0.14     0.23     0.18     0.22 
  26      0.01     0.07     0.15     0.12     0.12 
  27      0.00     0.03     0.10     0.08     0.06 
  28      0.00     0.01     0.06     0.05     0.03 
  29      0.00     0.00     0.04     0.03     0.02 
  30      0.00     0.00     0.02     0.02     0.01 
  31      0.00     0.00     0.02     0.01     0.00 
  32      0.00     0.00     0.01     0.00     0.00 

Here are the "moving" percentages, though I'd guess some of these are too near the root to be of much value.

Code: Select all

Iter16   Iter17   Iter18   Iter19   Iter20
X-15      0.01     0.07     0.07     0.25     0.42 
X-14      0.12     0.19     0.30     0.58     1.71 
X-13      0.30     0.73     0.96     2.10     2.63 
X-12      1.36     1.42     2.28     3.08     5.65 
X-11      2.14     3.85     4.20     5.94     6.97 
X-10      5.26     4.87     5.83     7.05     9.51 
X-9       7.68     7.97     8.96     9.92    10.58 
X-8      10.48     9.26     9.92    10.46    11.57 
X-7      12.43    10.74    11.33    11.35    10.69 
X-6      11.57    10.04    10.50    10.31     9.55 
X-5      10.68     9.33     9.53     9.22     7.77 
X-4       9.03     8.21     8.21     7.78     6.15 
X-3       7.85     7.19     6.93     6.21     4.89 
X-2       6.33     6.28     5.66     4.89     3.57 
X-1       4.84     5.13     4.44     3.55     2.70 
X-0       3.58     4.16     3.37     2.54     1.85 
X+1       2.41     3.22     2.43     1.69     1.32 
X+2       1.66     2.46     1.67     1.10     0.88 
X+3       0.98     1.82     1.13     0.69     0.58 
X+4       0.59     1.22     0.76     0.44     0.35 
X+5       0.32     0.81     0.50     0.28     0.22 

It is difficult to extrapolate from one position, and even more data for this one might be useful. One statistical measure is the "average depth" of an opened node, which behaves as

Code: Select all

16 10.77
17 12.08
18 12.53
19 12.76
20 12.94

In an ideal iterative depth-based search, this number should go up by 1 at each iteration. So the search at iteration 20 is really not that much "deeper" than that at iteration 19, at least in this example.

I did a few other positions, and the results still seemed to show an "average depth" gain of less than 1 as the iterations increase, though perhaps not as pronounced as above -- in the current TCEC position
"1n4k1/r1b2qp1/1p3p2/4pP1p/2PpN3/P2P2PP/1Q1B4/5RK1 b - - 0 32", I got this:

Code: Select all

14  8.21
15 11.09
16 11.24
17 10.46
18 11.59
19 13.90
20 14.93
21 15.25
22 15.67

Ideally, one would like to use such "statistical" information on the search profile to determine which nodes to extend, when to use more time, or the like, but that seems to be hard to realise in practise.

[hyatt]

I don't think this is "new ground." It has been obvious, for years, that going one additional ply deeper today is not the same as going one additional ply deeper 20 years ago. Reductions, forward pruning, all take a toll on the overall quality of the tree. Today,at 6M nodes per second, I can hit into the 23-24 ply range. 20 years ago, on a Cray T932, doing 7M NPS, I was hitting 11-12 plies deep. Clearly the 24 plies of today is better. But it is not _that_ much better, when you factor in 2x deeper. If one tries to conclude 50-70 elo per ply, that is 600+ and it is not reasonable. It is probably more like 1/2 of that. So the plies are not as "good." But then again, the same thing happened in the days of selective search. A ply was not as valuable as it was on a full-width program, because the full-width misses nothing within its search horizon, while the selective search program might miss a lot.

As far as "width goes". It seems intuitively obvious to me that as we go deeper, the tree gets "wider." It is a tree, after all. But the "widening" is still proportional to the depth, I don't believe the tree is getting "extra wider" as we go deeper.

[zwegner]

Number of nodes per ply as a ratio of the iteration 16 node count:

Code: Select all

 1     1.00    0.49    0.51    0.96    0.49
 2     1.00    1.14    1.45    1.19    0.70
 3     1.00    0.95    0.87    1.18    0.87
 4     1.00    1.09    1.04    1.07    0.65
 5     1.00    0.92    0.97    1.25    0.84
 6     1.00    1.14    1.96    1.83    1.32
 7     1.00    1.26    1.89    2.68    2.17
 8     1.00    1.09    2.38    2.69    2.28
 9     1.00    1.31    2.42    3.80    3.59
10     1.00    1.28    3.13    3.80    3.73
11     1.00    1.59    3.73    5.75    5.47
12     1.00    1.61    4.61    6.57    6.60
13     1.00    1.77    5.06    8.43    8.54
14     1.00    1.79    5.28    8.81    9.07
15     1.00    1.95    5.64    9.78   10.05
16     1.00    2.22    6.22   10.78   10.68
17     1.00    2.46    6.88   11.64   11.44
18     1.00    2.96    8.01   13.62   13.50
19     1.00    3.33    8.84   14.38   14.36
20     1.00    4.32   10.80   17.40   18.42
21     1.00    5.32   12.43   19.31   21.04
22     1.00    6.51   15.35   22.94   27.29
23     1.00    6.99   16.68   23.47   29.53
24     1.00    8.70   22.38   30.17   39.54
25     1.00    8.62   26.87   34.03   42.31
26     1.00   11.19   46.67   58.64   68.41
27     1.00    8.86   52.47   65.63   61.42
28     1.00   12.38  105.55  133.73  102.83
29     1.00   10.06  132.00  184.61  106.10
30     1.00   17.43  414.14  503.57  232.57
31     1.00   24.00  829.50 1030.00  405.50

[hyatt]

The question is, exactly _what_ do you believe that data shows?

Simplest measure I can think of is to count the number of moves searched from each individual node, then add all of those up and divide by the total number of nodes searched/counted. Do you think that number goes up as we go deeper? For a single ply, it might, because of the odd/even alpha/beta issue. In an even iteration, ignoring extensions and such, the last ply will average 1 move per position because those are all going to be CUT nodes. In an odd iteration, the last ply (9 for example) will be an ALL node. Since the last ply dominates all others in terms of counting, one iteration will see the count jump wildly, the next will see it drop wildly. That's just an artifact of alpha/beta.

It seems to me that this original "question" was about the following:

As we search deeper, are we also increasing the average width of the tree? If the answer is yes, then this implies that each iteration is proportionally harder to complete than the previous, because it represents extra work that would not be done if the EBF were uniform from iteration to iteration.

I believe the answer to the original question above is "no". So long as you ignore the tiny fact that we do pruning at the last 4 plies (for Crafty, anyway, others may use different numbers) and as you go deeper, those last 4 plies represent a smaller percentage of the total work done since all the other plies are full-width. I have not tried to do any math to quantify this and it might be completely irrelevant. But in any case, I've not seen anything that suggests that each iteration gets harder to do than the last, which would absolutely be the case if this "widening" talk had any substance to it. The only case of "getting harder" that I have seen deals with transposition table overloading. At some point, you over-saturate the table and begin to destroy useful information, and at that point, the iterations become harder. I've measured this effect many times, and it can turn into a 2x (or more) increase in effort required to reach the same depth when you search with a big table and then with a small one. But that is a different issue, and the "widening" effect is a result of crappy move ordering rather than being more "thorough" in the search.