Iterative deepening and the principal variation

[Dann Corbit]

So it seems to me that if you already have hash-best-move implemented, that the only benefits of iterative deepening are:

(1) the ability to time-out with a good move at hand
(2) increased efficiency by filling up the hash table between iterations

Seems to me you don't have to bother with passing each iteration the previous iteration's PV, as the hash table gives you all that benefit already.

What IID gives you that a hash table does not is to provide an estimate if the move is not *already* in the hash table.

On the other hand, the only real benefit of IID is better move ordering. If you have perfect move ordering, then the benefit of IID is actually less than zero, since there is a cost to the shallower searches. If you have really good move ordering, then it is about break even. If you have bad move ordering then it is a huge win, as it will reduce your branching factor.

[Guetti]

Sorry, I'm completely confused now. Is this discussion about iterative deepening at the root or about IID (internal iterative deepening) in the search?
Some engines just collect the PV and insert the whole PV into the hashtable upon completion of each iteration. This ensures that the PV is always in the hashtable and was not overwritten.

[Dann Corbit]

Sorry, I'm completely confused now. Is this discussion about iterative deepening at the root or about IID (internal iterative deepening) in the search?

I did switch between the two meanings. I thought somewhere else IID was brought up.

Some engines just collect the PV and insert the whole PV into the hashtable upon completion of each iteration. This ensures that the PV is always in the hashtable and was not overwritten.

However, it does not ensure that the pv nodes are unique.

Consider the following search:

Code: Select all

1) c5; ID "Jon Dart: in 
    Searching move: c4-c5
    Best move (WildCat_8): Qd2-b2
    Not found in: 10:00
      2	00:00	         317	0	+1.24	Qd2c3 Qe7e5
      3	00:00	         473	0	+1.24	Qd2c3 Qe7e5
      4	00:00	         706	0	+0.93	Qd2c3 d5xc4 f3f4
      4	00:00	         750	0	+0.62	Qd2c3 d5xc4 f3f4
      4	00:00	         793	0	+0.31	Qd2c3 d5xc4 f3f4
      4	00:00	       2.317	0	+0.05	Qd2c3 d5xc4 Rf1d1 Nf6d5
      4	00:00	       3.500	350.000	+0.06	Ra3a4 Rc8b8 a7xb8Q+ Ra8xb8
      4	00:00	       4.562	456.200	+0.37	Ra3a4 Rc8b8 a7xb8Q+ Ra8xb8
      4	00:00	       5.450	545.000	+0.68	Ra3a4 Rc8b8 a7xb8Q+ Ra8xb8
      4	00:00	       7.185	718.500	+0.99	Ra3a4 Rc8b8 a7xb8Q+ Ra8xb8
      4	00:00	       8.451	845.100	+1.19	Ra3a4 d5xc4 Be2xc4 Qe7e5
      4	00:00	       9.230	923.000	+1.20	Ra3c3 f5f4
      4	00:00	      10.150	1.015.000	+1.20	Ra3c3 Kh8g8 Rf1d1 Qe7e5 c4xd5 Rc8xc3 Qd2xc3 Nf6xd5
      5	00:00	      14.654	1.465.400	+1.20	Ra3c3 Kh8g8 Rf1d1 Qe7e5 c4xd5 Rc8xc3 Qd2xc3 Nf6xd5
      6	00:00	      26.481	882.700	+1.15	Ra3c3 Qe7d6 h3h4 Ng5e6 Rf1b1 Ne6xd4 Qd2xd4
      6	00:00	      32.849	1.094.966	+1.16	Ra3a4 d5xc4 Be2xc4 Qe7e5 Ra4a5 h7h6
      6	00:00	      41.898	1.047.450	+1.23	Ra3a4 Qe7e8 Ra4b4 d5xc4 Rb4xc4 Nf6d5 Rc4xc8 Qe8xc8
      7	00:00	      94.063	1.045.144	+1.15	Ra3a4 Qe7d6 Qd2b4 Qd6e5 Qb4c3 Rc8e8
      7	00:00	     110.716	1.006.509	+1.16	Ra3c3 Qe7d6 h3h4 Ng5e6 Nd4xe6 Qd6xb6
      7	00:00	     128.277	1.068.975	+1.22	Ra3c3 Qe7d6 h3h4 Ng5f7 Rf1b1 Nf7e5
      8	00:00	     175.063	1.029.782	+0.91	Ra3c3 d5xc4 Rc3xc4 Rc8xc4 Be2xc4 Qe7c5 Rf1c1
      8	00:00	     197.650	1.098.055	+0.60	Ra3c3 Qe7b4 h3h4 Ng5f7 c4xd5 Rc8xc3 Kh2g2
      8	00:00	     200.579	1.002.895	+0.29	Ra3c3 Qe7b4 h3h4 Ng5f7 c4xd5 Rc8xc3 Kh2g2
      8	00:00	     208.392	1.041.960	-0.02	Ra3c3 Qe7b4 h3h4 Ng5f7 c4xd5 Rc8xc3 Kh2g2
      8	00:00	     213.784	971.745	-0.33	Ra3c3 Qe7b4 h3h4 Ng5f7 c4xd5 Rc8xc3 Kh2g2
      8	00:00	     227.417	988.769	-0.35	Ra3c3 Qe7b4 h3h4 Ng5f7 Nd4b5 d5xc4 Qd2d4 Qb4xb5 Qd4xf6+ Kh8g8
      8	00:00	     245.255	1.066.326	-0.34	Ra3a4 Qe7d6 Qd2b4 d5xc4 Qb4xd6 Ng5f7 Qd6xf6+ Kh8g8
      8	00:00	     285.064	1.096.400	-0.03	Ra3a4 Qe7d6 Qd2b4 Qd6e5 Qb4c3 Nf6g4+ f3xg4 d5xc4
      8	00:00	     335.047	1.155.334	+0.28	Ra3a4 Qe7d6 Qd2b4 Qd6e5 Qb4c3 Nf6g4+ f3xg4 d5xc4
      8	00:00	     376.027	1.175.084	+0.59	Ra3a4 Qe7d6 Qd2b4 Qd6e5 Qb4c3 Nf6g4+ f3xg4 d5xc4
      8	00:00	     423.363	1.176.008	+0.90	Ra3a4 Qe7d6 Qd2b4 Qd6e5 Qb4c3 Nf6g4+ f3xg4 d5xc4
      8	00:01	     533.265	1.185.033	+1.12	Ra3a4 Ng5f7 Rf1c1 Nf7e5 Kh2g2
      9	00:01	     718.801	1.178.362	+0.81	Ra3a4 Rc8e8 h3h4 Ng5f7
      9	00:01	     838.699	1.164.859	+0.56	Ra3a4 Rc8e8 h3h4 Ng5f7 Nd4c2 Nf7e5 Qd2d1 Kh8g8
     10	00:01	   1.187.138	1.152.561	+0.25	Ra3a4 d5xc4 Be2xc4 Nf6d7 Qd2b2 Qe7f6 Rf1b1 Nd7e5 Qb2c3 Ng5xf3+ Kh2g2
     10	00:01	   1.575.738	1.158.630	 0.00	Ra3a4 Qe7d7 Ra4b4 f5f4 g3xf4 Qd7xh3+ Kh2g1 Qh3g3+ Kg1h1 Qg3h3+ Kh1g1
     10	00:02	   1.921.801	1.164.727	+0.01	c4c5 Qe7xc5 Qd2b2 Qc5d6 Rf1d1 Ng5e6 Nd4xe6 f5f4
     10	00:02	   2.227.708	1.191.287	+0.26	c4c5 Rc8xc5 Qd2b2 Qe7f7 h3h4 Ng5e6 Rf1b1 Ne6xd4 Qb2xd4 Qf7e7
     11	00:03	   3.054.492	1.236.636	+0.27	c4c5 Rc8xc5 Qd2b2 Qe7f7 h3h4 Ng5e6 Rf1b1 Ne6xd4 Qb2xd4 Qf7e7 f3f4 Kh8g8
     12	00:04	   5.295.686	1.237.309	+0.26	c4c5 Rc8xc5 Qd2b2 Ng5e6 Be2d3 Rc5c8 Ra3c3 Rc8d8 Nd4xe6 Qe7xe6 Rf1e1 Rd8c8
     12	00:07	   8.586.691	1.195.917	+0.27	Qd2b2 d5xc4 Rf1c1 Bb7d5 h3h4 Ng5f7 Be2xc4 Rc8xc4 Rc1xc4 Bd5xc4 b6b7 Qe7d6 b7xa8Q+ Qd6f8
     12	00:08	  10.057.072	1.222.001	+0.58	Qd2b2 d5xc4 Rf1c1 Bb7d5 h3h4 Ng5f7 Be2xc4 Rc8xc4 Rc1xc4 Bd5xc4 b6b7 Kh8g8 b7xa8Q+ Qe7f8
     12	00:11	  13.385.100	1.231.379	+0.89	Qd2b2 d5xc4 Ra3c3 Bb7d5 h3h4 Ng5f7 Be2xc4 Rc8xc4 Rc3xc4 Bd5xc4 b6b7 Bc4xf1 b7xa8Q+ Qe7f8
     12	00:13	  16.522.528	1.246.983	+1.09	Qd2b2 d5xc4 Ra3c3 Nf6d7 h3h4 Ng5e6 Rc3xc4 Ne6c5 Rf1d1 Nd7e5 Rc4c3 Kh8g8
     13	00:15	  18.640.003	1.219.097	+0.78	Qd2b2 d5xc4 Ra3c3 Nf6d5 Rc3xc4 Qe7f6 Rc4xc8+ Ra8xc8 h3h4 Ng5f7 a7a8Q Rc8xa8 f3f4
     13	00:16	  18.919.612	1.218.262	+0.47	Qd2b2 d5xc4 Ra3c3 Nf6d5 Rc3xc4 Qe7f6 Rc4xc8+ Ra8xc8 h3h4 Ng5f7 a7a8Q Rc8xa8 f3f4
     13	00:18	  22.377.600	1.214.853	+0.30	Qd2b2 d5xc4 Ra3c3 Nf6d5 Rc3xc4 Kh8g8 Rc4xc8+ Ra8xc8 h3h4 Ng5f7 e3e4 f5xe4 f3xe4 Qe7xe4
     14	00:31	  36.421.476	1.180.216	+0.29	Qd2b2 d5xc4 Ra3c3 Nf6d5 Rc3xc4 Qe7f6 Rc4xc8+ Ra8xc8 h3h4 Ng5f7 Rf1b1 Nd5xe3 Qb2d2 Qf6e5 f3f4 Qe5e4
     15	00:58	  67.575.966	1.162.897	+0.29	Qd2b2 d5xc4 Ra3c3 Nf6d5 Rc3xc4 Qe7g7 Rc4xc8+ Ra8xc8 h3h4 Nd5xe3 Rf1b1 Ne3c4 Be2xc4 Rc8xc4 h4xg5 Qg7xd4 Qb2xd4+ Rc4xd4 Rb1b3 Kh8g7
     16	02:13	 152.086.596	1.142.820	+0.45	Qd2b2 d5xc4 Ra3c3 Nf6d5 h3h4 Ng5f7 Rc3xc4 Kh8g8
     17	05:46	 380.247.024	1.098.408	+0.28	Qd2b2 d5xc4 Ra3c3 Nf6d5 h3h4 Ng5f7 Rc3xc4 Kh8g8 Rc4xc8+ Ra8xc8 e3e4 f5xe4 f3xe4 Qe7xe4 Be2f3 Qe4e5 Bf3xd5 Qe5xd5 Qb2f2 Nf7e5
   3/10/2008 4:58:44 PM, Time for this analysis: 00:10:00, Rated time: 10:00

0 of 1 matching moves
3/10/2008 4:58:45 PM, Total time: 12:10:08 AM
Rated time: 10:00 = 600 Seconds

In this search, at the root, considering just the first ply, each of:
c4c5
Qd2b2
Qd2c3
Ra3a4
Ra3c3
was the pm at one time. If, on each iteration, we tagged the pv node in the hash table, then we could have 5 nodes tagged as pv[0] {unless we went through the effort of untagging all sibling nodes as pv nodes when we change a pv node}.

[AndrewShort]

I was talking about Iterative Deepening (ID), not Internal Iterative Deepining (IID). (I have not explored IID yet).

After hearing all your comments, seems you guys agree with me, that if you already have good move ordering with hash best-move, then ID does not benefit from the previous iteration's PV, as that is at best redundant and at worst diversionary.

[hgm]

On the other hand, the only real benefit of IID is better move ordering. If you have perfect move ordering, then the benefit of IID is actually less than zero, since there is a cost to the shallower searches.

This is hardly true if you have good hashing: if you have perfect move ordering, the first N levels of an N+1 ply search will already be in the hash table due to the ID at the root, so you will always hit on an entry that already has the node searched to one ply less than you need now. So the 'IID' actually only inolves one iteration, the one at full depth, which you would have had to do anyway.

It is only when you break new ground that IID really has to do extra iterations. And this is usually the case where they pay off very handsomely.

An additional question of phylosophical nature could be: what is actually "perfect move ordering"? Does it order the moves according to the score they would have in the current search (of depth N)? Or would it use the score of an infinite depth search? In the latter case the perfect move ordering could actually be very poor in any finite-depth search (if important things happen beyond the horizon). Would perfect move ordering require perfect evaluation?

[Guetti]

In this search, at the root, considering just the first ply, each of:
c4c5
Qd2b2
Qd2c3
Ra3a4
Ra3c3
was the pm at one time. If, on each iteration, we tagged the pv node in the hash table, then we could have 5 nodes tagged as pv[0] {unless we went through the effort of untagging all sibling nodes as pv nodes when we change a pv node}.

Why would you want to tag them as PV nodes? Just could just insert them into the TT at the current depth of the just completed search with the score you received for the search. Just to make sure you have at least a move to try first, in case the PV move was overwritten in the hash table.

[bob]

The problem is, you can't recognize a PV node...

But as you finish searching nodes and unmake moves and go back up to the parent, can you mark the "best child" with a flag? I.e. a flag that means, "The best move, or hash move, in some parent node led to this node".

Then replacement would just always prefer to replace non-flagged ones instead of flagged ones.

The problem is, with imperfect move ordering, you end up with a bunch of those kinds of nodes, and you don't want to keep a lot of junk just because you think they are PV nodes...

And if you change your mind on the best move at the root, you end up with 2x as many of those nodes, from the first and then the move that replaced the first as best...

[bob]

So it seems to me that if you already have hash-best-move implemented, that the only benefits of iterative deepening are:

(1) the ability to time-out with a good move at hand
(2) increased efficiency by filling up the hash table between iterations

Seems to me you don't have to bother with passing each iteration the previous iteration's PV, as the hash table gives you all that benefit already.

There is no guarantee that a PV move from the PV on iteration N survives in the hash table until we start iteration N+1. This is especially true the further from the root this PV move is...

Simplest idea is to just re-stuff the PV moves into the hash at the end of the iteration, to guarantee they are there for the next iteration. If they are already there, so what? Takes zero time to do this...

[hgm]

Ah, so 'zero' can mean 'a totally negligible small amount', rather than an exact mathematical zero, after all?

But why would you worry if, say, the last 7 ply of a 20-ply PV are missing? (The early PV moves being protected by their depth in the depth-preferred part of the table.) It will only take the time of a 7-ply search, starting from the end of the part of the PV that you do have, to reconstruct the full PV. That still seems quite negligible. The deepest part of the PV is more likely to change on deepening anyway.

In fact you could wonder if the overhead of carrying around a PV (e.g. in a tri-angular array) during the entire search would not be more time consuming than just redoing this part of the search. Stuffing the PV back into the hash table might take 'zero' time, but making sure you have the PV available might take orders of magnitude more time. Might still be negligible, of course, but it requires extra programming work compared to an alternative that also takes negligible time, so why do it?

[bob]

Ah, so 'zero' can mean 'a totally negligible small amount', rather than an exact mathematical zero, after all?

If the number is something like 0.000001% then yes, I call that zero.

But why would you worry if, say, the last 7 ply of a 20-ply PV are missing? (The early PV moves being protected by their depth in the depth-preferred part of the table.) It will only take the time of a 7-ply search, starting from the end of the part of the PV that you do have, to reconstruct the full PV. That still seems quite negligible. The deepest part of the PV is more likely to change on deepening anyway.

I worry because those last 7 plies are not free, and getting the ordering right makes a measurable difference. If you want to observe this, just turn hash move off for the last N plies in your search and measure the difference...

Here's crafty: No hash move in the last 7 plies of the PV. common middlegame position, searched to depth=17, just one cpu for consistency...

log.001: time=27.15 mat=0 n=56278033 fh=92% nps=2.1M
log.002: time=31.15 mat=0 n=59617831 fh=92% nps=1.9M

So, given some real data, would you be too concerned? I am...

In fact you could wonder if the overhead of carrying around a PV (e.g. in a tri-angular array) during the entire search would not be more time consuming than just redoing this part of the search. Stuffing the PV back into the hash table might take 'zero' time, but making sure you have the PV available might take orders of magnitude more time. Might still be negligible, of course, but it requires extra programming work compared to an alternative that also takes negligible time, so why do it?