Internal Iterative Deepening questions

Discussion of chess software programming and technical issues.

Moderators: Harvey Williamson, bob, hgm

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
sedicla
Posts: 149
Joined: Fri Jan 07, 2011 11:51 pm
Location: USA

Internal Iterative Deepening questions

Post by sedicla » Wed Sep 21, 2011 2:06 pm

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?

User avatar
hgm
Posts: 25056
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Internal Iterative Deepening questions

Post by hgm » Wed Sep 21, 2011 2:53 pm

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
Posts: 149
Joined: Fri Jan 07, 2011 11:51 pm
Location: USA

Re: Internal Iterative Deepening questions

Post by sedicla » Thu Sep 22, 2011 2:04 pm

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 !!!

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Internal Iterative Deepening questions

Post by Don » Thu Sep 22, 2011 5:39 pm

sedicla wrote: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.

User avatar
hgm
Posts: 25056
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Internal Iterative Deepening questions

Post by hgm » Thu Sep 22, 2011 5:52 pm

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.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Internal Iterative Deepening questions

Post by Don » Thu Sep 22, 2011 6:33 pm

hgm wrote: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.

User avatar
hgm
Posts: 25056
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Internal Iterative Deepening questions

Post by hgm » Thu Sep 22, 2011 6:54 pm

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
Posts: 149
Joined: Fri Jan 07, 2011 11:51 pm
Location: USA

Re: Internal Iterative Deepening questions

Post by sedicla » Tue Sep 27, 2011 1:50 pm

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.

User avatar
hgm
Posts: 25056
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Internal Iterative Deepening questions

Post by hgm » Tue Sep 27, 2011 3:43 pm

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
Posts: 149
Joined: Fri Jan 07, 2011 11:51 pm
Location: USA

Re: Internal Iterative Deepening questions

Post by sedicla » Tue Sep 27, 2011 4:15 pm

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 &#40;hash_move == MOVE_NONE && depth > 3&#41; 
    &#123; 
        if &#40;pv_node&#41; 
            // for pv_nodes look for a good hash_move. 
            score = search_ab&#40;incheck, alpha, beta, depth - 3, 0, 1&#41;;
        else 
            // for non pv_nodes try to dismiss bad moves from being searched first. 
            score = search_ab&#40;incheck, alpha, beta, 1, 0, 1&#41;; 
      hash_move = tt_move&#40;); 
   &#125; 

Post Reply