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.

Code: Select all

long int chk_hash(int alpha, int beta, int depth, int *type, move_s *move) {

	/* see what info we can get from our hash tables for the current
	 position.  This could be a value we can return, a suggested move, or
	 even just a warning not to use null search in this position */

	hash_s *hash_p;
	long int score;
	s_int h_depth, flag;
	d_long hash;

	*type = no_info;
	*move = dummy;

	/* lookup our hash: */
	hash_p = hash_table + (hash_mask & cur_pos.x1);
	hash = hash_p->hash;
	if (hash.x1 == cur_pos.x1 && hash.x2 == cur_pos.x2) {
		/* get info from the hash: */
		*move = hash_p->move;
		score = hash_p->score;
		h_depth = hash_p->depth;
		flag = hash_p->flag;

		/* adjust our score if it is a mate score: */
		if (abs(score) > INF - 100) {
			if (score > 0)
				score -= (ply);
			else
				score += (ply);
		}

		/* see if we should avoid null moves: */
		if (h_depth >= depth - null_red && score < beta && flag == u_bound)
			*type = avoid_null;

		/* check what info we can get from our hash: */
		if (h_depth >= depth) {
			switch (flag) {
			case u_bound:
				if (score <= alpha) {
					*type = u_bound;
					return (alpha);
				}
				break;
			case l_bound:
				if (score >= beta) {
					*type = l_bound;
					return (beta);
				}
				break;
			case exact:
				*type = exact;
				return (score);
				break;
			}
		}
	}

	return (0);

}

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.

[Daniel Shawul]

I am not sure what your question is but you should check if you have a move from the tt all the time.
Whatever move you have in tt is the best so far, so no need for further checks. The score is checked
against current bounds (alpha & beta) because we don't want to prematurely stop search (hash cutoff)
for a suboptimal move searched with a lower bound. But the move is use for _move ordering_, so no severe penalties there.

Especially in IID where you do shallow depth search first, you need to search the best move first
otherwise the point of doing shallow depth search will be lost. I don't think you need to make any changes
to your hash table for IID to work. It will work even without the tt if you save the best move from the shallow
search elsewhere and search it first.

[outAtime]

hmmm... ok well the hash tables are checked in search:

Code: Select all

/* see what info we can get from our hash table: */
	h_score = chk_hash(alpha, beta, depth, &h_type, &h_move);
	if (h_type != no_info) {
		switch (h_type) {
		case exact:
			return (h_score);
		case u_bound:
			return (h_score);
		case l_bound:
			return (h_score);
		case avoid_null:
			do_null = FALSE;
			break;
		default:
			break;
		}
	}

	temp_hash = cur_pos;
	ep_temp = ep_square;
	i_alpha = alpha;

but you are mentioning saving the best move from the IID search so maybe I should do:

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);
        
    }
	 

still not sure about the (h_type == no_info) bit or if this is what you meant... this still dosen't look quite like anything else ive seen, not to say that is bad, but just not sure.

[outAtime]

This has to be wrong i get compiler errors:

Code: Select all

/* Internal iterative deepening */
    if (    depth >= 5
        &&  h_type == no_info
        &&  (pv_node || (!in_check())))
    {
	    int d;
		move_s moves[MOVE_BUFF], 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);
        
    }

in best_move = bestIID I get incompatable types in assignment error, so im missing something here..

[Daniel Shawul]

I think we are miscomunicating
First of all there shouldn't be a return in your IID implementation. The point of it is to get a move to search first, so once you do the shallow search you move along.
Second forget the hypothetical example I gave with doing IID without the hash table as that seems to cause more confusion.
All you have to do get the move from the tt, and check if it is good enough . Otherwise do a shallow depth IID.
So the only condition , if any, you should apply on the use of the hash move is check depth with which it was searched. Something like

Code: Select all

if(h_depth >= current_depth - 3)
*move = hash_p->move; 

You have that already without the depth check which is also fine.

[outAtime]

ok, so from what i can gather you are suggesting i do something so simple as:

Code: Select all

	/* Internal iterative deepening */
    {
	    int d;
				
        d = (pv_node ? depth - 2 : depth / 2);
        		
        do_null = FALSE;
        search(alpha, beta, d, FALSE, TRUE);
        do_null = TRUE;        
    }

seems almost too simple... what am I missing here? nothing? Is this the implementation you suggest? Maybe I still need something like what you mentioned about checking if the hash move is good enough... do I still need that? How would i check it? Thanks for your help.

[outAtime]

I still think I should be saving the result of this search in move_ordering or something otherwise... hmm, never mind ill wait for the reply. Thanks again.

[hgm]

Inmicro-Max I do bascally this:

Code: Select all

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

[outAtime]

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

Sloppy does:

Code: Select all

/* Get the best move from the hash table.
   If not successfull, return NULLMOVE.  */
U32
get_hash_move(U64 key)
{
	Hash *hash = &hash_table[key % settings.hash_size];

	if (hash->key == key)
		return hash->best;
	return NULLMOVE;
}

/* Probe the hash table for a score and the best move.
   If not successfull, return VAL_NONE.  */
int
probe_hash(int depth, int alpha, int beta, U64 key, U32 *best_move, int ply)
{
	Hash *hash;

	ASSERT(2, best_move != NULL);

	hash = &hash_table[key % settings.hash_size];
	if (hash->key == key) {
		*best_move = hash->best;
		if ((int)hash->depth >= depth) {
			int val = val_from_hash(hash->val, ply);

			if (hash->flag == H_EXACT)
				return val;
			if (hash->flag == H_ALPHA) {
				if (val <= alpha)
					return alpha;
				if (val < beta)
					return VAL_AVOID_NULL;
			} else if (hash->flag == H_BETA && val >= beta)
				return beta;
		}
	}

	return VAL_NONE;
}

so there is a separate function there to detect if hash has a best_move...
i was having difficulty trying to translate that idea so thought id post to see what else I could do, or if I was even on the right track... I can call h_type but cant call anything it seems from hash.c having to do with *move etc.. so im just tring to find out another way, or how to do it.
In my search PV has the highest move_ordering and seems alot of progams using IID order hash first so that may be another question. Thanks.

[Daniel Shawul]

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

Please stop the drama stanley.
You should try to comprehend what is posted if you are really here for that.
And don't insist on someone responding to your post. This is a public forum and you get help from anyone.
In the rare case that you really are a confused soul which needed help, I was referring to the bold faced text below. Anybody will tell you that is absurd.

Code: Select all

/* Internal iterative deepening */ 
    if (    depth >= 5 
        &&  h_type == no_info 
        &&  (pv_node || (!in_check()))) 
    { 
       int d; 
      move_s moves[MOVE_BUFF], 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]; 
       
        [b] return chk_hash(alpha, beta, depth, &h_type, &h_move); [/b] 
        
    } 

And no, I am not replying to your post again, so don't bother replying to this post.