Internal Iterative Deepening questions

[sedicla]

Usually IID is implemented like this:

if (hash_move == NONE && depth > 3 ...)
search (alpha, beta, depth - 3, ...

Has anyone tried searching with depth = 3 immediately, like:

if (hash_move == NONE && depth > 3 ...)
search (alpha, beta, 3, ...


I'm testing it now with 1000 games, 10sec+0.1sec. Doesn't it seems is going to make a big difference, let's see.

Also does it need to do IID when side to move is behind material, the best move probably would be a recapture, and maybe is not necessary a hash move anyways?

[hgm]

In Spartacus I only search at depth 1, before jumping to the requested depth if there is no hash move in non-PV nodes. In PV nodes I start at depth 1 or 2, and increment in steps of two.

In micro-Max I start at the hashDepth+1, incrementing in steps of 1 in any node, when there is a hash move and the bound is of the right type, and start at depth 0 (QS) otherwise.

[sedicla]

The first test didn't show any improvments. I think I'll keep the way it is. I guess if you are on depth = 10 and call IID with depth=3 you have a hash_move of depth = 3. But if you call with depth - 3, then you eventually have a hash_move of depth=7 which probably is a better move than of depth=3.

At this moment I'm working on evaluation, but sometimes you have some ideas for other parts.

It is such a challeging and exciting project to program a chess engine !!!

[Don]

Usually IID is implemented like this:

if (hash_move == NONE && depth > 3 ...)
search (alpha, beta, depth - 3, ...

Has anyone tried searching with depth = 3 immediately, like:

if (hash_move == NONE && depth > 3 ...)
search (alpha, beta, 3, ...


I'm testing it now with 1000 games, 10sec+0.1sec. Doesn't it seems is going to make a big difference, let's see.

Also does it need to do IID when side to move is behind material, the best move probably would be a recapture, and maybe is not necessary a hash move anyways?

It's not really iterative if you do it like that.

Also, you are interested in getting the best move with a fairly high probability so you don't want the actual depth you are about to search to be too ridiculously high compared to the IID search. Probably what you should experiment with is the amount of reduction.

[hgm]

In Spartacus the main importance of the IID is to protect you from investing a lot of time when searching a prospective cut-move, only to discover it is an obvious blunder. MVV/LVA is nice if you can capture a Queen of have PxR, but in many nodes close to the PV this will not be the case, and the first capture of your static ordering could be a meagre BxN. And although it looks like such a capture would at least be equal, the B could be soft-pinned on your Queen, or tight in defence to a Rook, so that this BxN would fail miserably low even when you start out above alpha. It also frequenty happens that all captures are bad.

When first searched at d=1, such pins or overloads would be detected, and you would then move on to the next move of your static ordering untill you found one that is at least is not trivially refuted, and then start the full-depth search on than one.

[Don]

In Spartacus the main importance of the IID is to protect you from investing a lot of time when searching a prospective cut-move, only to discover it is an obvious blunder. MVV/LVA is nice if you can capture a Queen of have PxR, but in many nodes close to the PV this will not be the case, and the first capture of your static ordering could be a meagre BxN. And although it looks like such a capture would at least be equal, the B could be soft-pinned on your Queen, or tight in defence to a Rook, so that this BxN would fail miserably low even when you start out above alpha. It also frequenty happens that all captures are bad.

When first searched at d=1, such pins or overloads would be detected, and you would then move on to the next move of your static ordering untill you found one that is at least is not trivially refuted, and then start the full-depth search on than one.

Good points. I'm sure 90% of the benefit is in the first 1 or 2 ply of searching and after than additional depths have diminishing returns. So it might turn out that your IID search in an ideal world would be the square root of the depth remaining or something like that.

[hgm]

Well, it might depend a little on whether you are just looking for convenient cut move, or whether you want to really find the best one (as in a PV node). I can imagine that the best at d=16 would not correlate very well with that at d=1 (or d=4), but that you really would benefit from first figurig outwhat isbest at d=14. For most cut nodes trying the d=1 is a good-enough filter though. In fact many engines don't use IID at all in cut nodes, but in my engines I found a single d=1 helpful (when the target depth >= 3).

[sedicla]

So, if I understood correctly I can use IID for non-pv in order to skip some bad moves to be searched, something like this:

Code: Select all

	
    // Internal Iterative Deepening.
    if (hash_move == MOVE_NONE && depth > 3)
    {
        if (pv_node)
        {
            // for pv_nodes look for a good hash_move.
            score = search_ab(incheck, alpha, beta, (depth > 10 ? depth / 2 : depth - 3), 0, 1);
            if &#40;score <= alpha&#41;
                score = search_ab&#40;incheck, -INFINITY, beta, &#40;depth > 10 ? depth / 2 &#58; depth - 3&#41;, 0, 1&#41;;
        &#125;
        else
            // for non pv_nodes try to dismiss bad moves from being searched first.
            score = search_ab&#40;incheck, -INFINITY, beta, 1, 0, 1&#41;;
		hash_move = tt_move&#40;);
	&#125;

I will make some tests later. Still working on other things.

[hgm]

Indeed. Not sure why you would open the window, though, when the search fails low. I would draw the conclusion in this case that the node is not a PV node but an all node, and assume a deeper search would not change that.

[sedicla]

Regarding opening the window, I was not saving any move in the hash table if I failed low. That's why I researched again with open window to force a best move.
However now I'm doing some tests to save the best move even if it fails low. In the end I think I really don't need to research. But from what I've learned is to test every single small change. At least 1000 games 10s+0.1s.
So I think my final code would be:

Code: Select all

// Internal Iterative Deepening. 
    if (hash_move == MOVE_NONE && depth > 3) 
    { 
        if (pv_node) 
            // for pv_nodes look for a good hash_move. 
            score = search_ab(incheck, alpha, beta, depth - 3, 0, 1);
        else 
            // for non pv_nodes try to dismiss bad moves from being searched first. 
            score = search_ab(incheck, alpha, beta, 1, 0, 1); 
      hash_move = tt_move(); 
   }