Trouble with IID

[outAtime]

I'm having some difficulty because I'm not sure how to check if the hash contains a best move or not.



also after the IID search would I return chk_hash(alpha, beta, depth, &h_type, &h_move)? I have the feeling I should only be returning just the move, but again having difficulty with implementation. I can write (if h_type == no_info) but cant seem to figure out something for the _move. Thanks for any help.

so i was inquiring about the return, and obviously felt it was incorrect. I have seen many IID implementations which _do_ have a return, and so far not any which do not, thus my confusion at the start by the kind suggestion made. In the previous posts in this thread I have only been trying to understand the idea, and what i might be missing. I haven't insisted? anyone reply to anything; i did say i would wait for a reply rather ,and was only trying to avoid adding more questions at that point, waiting to see if anyone could clarify it before continuing. I apologize if I haven't immediately understood the posts of any other kind users, and hope that in i haven't appeared to be ridiculing? anyone's suggestion, as that would certainly be furthest from my intention. I apologize if i have unintentionally offended anyone by drama (what drama?). The intention of my quote was misinterpreted perhaps? I was only trying to understand it. Thanks.

[hgm]

ok, that looks more like the implementations im used to seeing. Im still waiting to find out Shawul's idea of IID with no return... he suggests I dont need to return anything or have any conditions... I guess I still dont know

Eventually you need to return from everything. But note that the return is basically the return of the normal Search, and not an extra return onlyused for IID. The while loop will eventually do the search at the full requested depth. But it might start at lower depth, depending on what you found in the hash. It might not be executaed at all if the depth found in the hash was larger or equal to what you need (meaning tuou return the hash score without seach.)

[Sven]

Inmicro-Max I do bascally this:

Code: Select all

Search(depth)
{
    d = 0;
    if(HashHit() == OK) {
        d = hash.depth;
        bestScore = hash.score;
    }
    while&#40;d < depth&#41; &#123;
        d = NextDepth&#40;d&#41;;
        bestScore = -INF;
        for&#40;ALL_MOVES&#41; &#123;
            score = -Search&#40;d-1&#41;;
            if&#40;score<bestScore&#41; bestScore = score;
        &#125;
    &#125;
    hash.depth = depth;
    hash.score=bestScore;
    return bestScore;
&#125;

"if(score<bestScore) bestScore = score;"
should read
"if(score>bestScore) bestScore = score;"
obviously.

Could you explain how this code is related to IID? I have difficulties to see where your "there is no best move in the hash table, and this is a PV node, and we are far enough away from QS" condition is buried.

Sven

[micron]

Here's how IID is commonly implemented.

Code: Select all

move_t  moveToTryFirst;
score = TTProbe( &moveToTryFirst );
if ( score > beta ) return score;

#if IID
if ( moveToTryFirst == NO_MOVE && depth > MIN_DEPTH_FOR_IID )
{
  int iidDepth = depth - 2; // or depth/2 or whatever
  (void)Search( iidDepth, alpha, beta, &moveToTryFirst );
}
#endif

InitMovePicker( moveToTryFirst );
ForEachMove
{
  ...
}

The IID block is a move-ordering optimization. It attempts to find a first move better than what your move picker would produce unaided.

Search() must be able to communicate the best move back to its caller. This essential requirement is missing from the code you have posted.
In the simplest implementation as above, the score returned by the reduced IID search is irrelevant.
There is no 'return' statement in the IID block.

I must confess that the name IID is puzzling. The IID code above looks more like "Internal Recursive Shallowing".
The pseudocode posted by hgm, on the other hand, certainly illustrates Iterative Deepening. But at first sight it shares little with conventional IID.

Robert P.

[hgm]

"if(score<bestScore) bestScore = score;"
should read
"if(score>bestScore) bestScore = score;"
obviously.

Oh sorry...

Could you explain how this code is related to IID? I have difficulties to see where your "there is no best move in the hash table, and this is a PV node, and we are far enough away from QS" condition is buried.

Sven

The conditions are buried in NextDepth, which could depend on whether there is a hash move, the initial depth and the target depth. So perhaps it would be better to write d=NextDepth(d, depth, hash.move);. In micro-Max this is just d++;, however. So you are never "too close" unless you are already done. And if there was a hash hit, there always will be a hash move.

[hgm]

I must confess that the name IID is puzzling. The IID code above looks more like "Internal Recursive Shallowing".
The pseudocode posted by hgm, on the other hand, certainly illustrates Iterative Deepening. But at first sight it shares little with conventional IID.

I think it s just a bit more efficient (iterative) implementation of the 'conventional' IID. The latter implements the iteration through a 'head recursion': Search(d) calls Search(d-2), which again calls Search(d-4), etc., until you reach the MIN_DEPTH_FOR_IID. Then you start to do all the real searches, (shallowest first) as you unwind the recursion

[Sven]

Code: Select all

/* Internal iterative deepening */
    if (    depth >= 5
        &&  h_type == no_info;
        &&  (pv_node || (!in_check())))
    {
	    int d;
		int best_move = dummy;
		int bestIID = -INF;
		
        d = (pv_node ? depth - 2 : depth / 2);

        do_null = FALSE;
        bestIID = search(alpha, beta, d, FALSE, TRUE);
        do_null = TRUE;
		
		best_move = bestIID;
		best_move = moves[i];
		
        return chk_hash(alpha, beta, depth, &h_type, &h_move);
        
    }

While it has already been clarified that returning would not make any sense here, and while it is also clear that the code above would not compile for at least two reasons (semicolon after "h_type == no_info", assignment of a value "bestIID" to a move "best_move"), I would like to add that the "original version" (see below) also does a couple of things better than your version:

a) It does not even define any "bestIID" variable, just because the goal of IID is only to find a "best move candidate" for the real search.

b) For non-PV nodes it also requires the static eval to be above a certain threshold, otherwise IID will not be used there. You only require not to be in check.

c) It stores the "best move from a shallow IID search" in a variable (ttMove) indicating that the IID search shall bring up a "move to be searched first" since initially there was no such move in the TT, while your version would already store that move in a "best_move" variable (although I miss how you retrieve it: "moves" ??) which could be confusing since the real search to find the best move has not started yet.

d) Its indentation is much better

Code: Select all

From Stockfish 2.0.1, search.cpp:
/*
...
  Copyright (C) 2004-2008 Tord Romstad (Glaurung author)
  Copyright (C) 2008-2010 Marco Costalba, Joona Kiiski, Tord Romstad
...
*/
...
// Step 9. Internal iterative deepening
    if (    depth >= IIDDepth[PvNode]
        &&  ttMove == MOVE_NONE
        && (PvNode || (!isCheck && ss->eval >= beta - IIDMargin)))
    {
        Depth d = (PvNode ? depth - 2 * ONE_PLY : depth / 2);

        ss->skipNullMove = true;
        search<PvNode>&#40;pos, ss, alpha, beta, d, ply&#41;;
        ss->skipNullMove = false;

        ttMove = ss->bestMove;
        tte = TT.retrieve&#40;posKey&#41;;
    &#125;

Sven

[Sven]

Here's how IID is commonly implemented.

Code: Select all

move_t  moveToTryFirst;
score = TTProbe( &moveToTryFirst );
if ( score > beta ) return score;

#if IID
if ( moveToTryFirst == NO_MOVE && depth > MIN_DEPTH_FOR_IID )
{
  int iidDepth = depth - 2; // or depth/2 or whatever
  (void)Search( iidDepth, alpha, beta, &moveToTryFirst );
}
#endif

InitMovePicker( moveToTryFirst );
ForEachMove
{
  ...
}

The IID block is a move-ordering optimization. It attempts to find a first move better than what your move picker would produce unaided.

Search() must be able to communicate the best move back to its caller. This essential requirement is missing from the code you have posted.
In the simplest implementation as above, the score returned by the reduced IID search is irrelevant.
There is no 'return' statement in the IID block.

I must confess that the name IID is puzzling. The IID code above looks more like "Internal Recursive Shallowing".
The pseudocode posted by hgm, on the other hand, certainly illustrates Iterative Deepening. But at first sight it shares little with conventional IID.

Robert P.

I agree completely, except for one tiny part of your pseudocode which is in fact not related to IID:

Code: Select all

score = TTProbe( &moveToTryFirst );
if ( score > beta ) return score;

Here the condition to return a value after TT probing is usually not just "score > beta" but something like "the info retrieved from TT is sufficient at the current node to prune the whole subtree and return the TT value instead". "score > beta" is an unnecessary restriction at this point since you don't make a beta cutoff here (the current node is not necessarily irrelevant for the minimax value of the root node).

Sven

[micron]

I agree completely, except for one tiny part of your pseudocode which is in fact not related to IID:

Code: Select all

score = TTProbe( &moveToTryFirst );
if ( score > beta ) return score;

Here the condition to return a value after TT probing is usually not just "score > beta" but something like "the info retrieved from TT is sufficient at the current node to prune the whole subtree and return the TT value instead".

Yes, of course. Thanks for the correction.
Robert P.