Hash tables and PV

[outAtime]

Hi all,

I have been looking into possibly changing the way I'm collecting PV.
Currently its like this:

Code: Select all

// search.c

move_ordering {

PV 1st
Hash, Caps, Killers, History, etc.. 
}

Q_search {

if (score > alpha)
/* update the pv: */
			pv[ply][ply] = moves[i];
			for (j = ply + 1; j < pv_length[ply + 1]; j++)
				pv[ply][j] = pv[ply + 1][j];
			pv_length[ply] = pv_length[ply + 1];
if (score >= beta)
return beta:
************shouldn't I update the hash here? maybe separate Q_searches for PV/Null move etc?**************************

return alpha;
}

Search {

check_hash
if exact return hash_score
if upper return hash_score
if lower return hash_score
if avoid_null FALSE
default break

null_search{
}

if !depth {
Q_search 
***********I was thinking this is not best - should go before null_search? Was thinking also of doing separate pv/non pv Q_search
*********************************************************

PVS  {
if (score > alpha) {
/* update the pv: */
if (score >= beta)
store_hash lower_b
return alpha
}
******also I do upper and exact(i_alpha > alpha) here... **********
}

ROOT {
if  if (score > alpha) {
/* update the pv: */

best_move = move;

store_hash exact_b

return best_move;
}
**********this seems wrong to me... shouldn't I at least
update the hash if root_score >= beta? Maybe not... ********

CALL_ROOT {

// get PV from hash if PV is really short

if (pv_length <= 2 && i_depth > 1 && abs(cur_score)
					< (INF - 100) && result != stalemate && result
					!= draw_by_fifty && result != draw_by_rep)
				hash_to_pv(i_depth); 

*******hmmm... maybe I should always get PV from hash here? 
*****************************************************
}

hash.c

/* check what info we can get from our hash: */
if (h_depth >= depth) {
******** is always replace better? I'm wondering what is the current
opinion or if this is OK **************************************
}

Thanks for any help on this topic, I'm already changing a few things
and trying some ideas and any good guidance would be very much
appreciated!

[outAtime]

Code: Select all

/* don't replace if the info in the hash table is more accurate than
	 what we have now: */

	if (depth < hash_p->depth) {
		return;
	}

maybe this is the one I'd consider removing... Thanks again

[sje]

A "real" predicted variation is only collected when the score is inside the A/B window. If a program collects PV moves every time a score is better than beta is moving a lot of data that might never be used.

[Desperado]

i am in hurry, though here is a simple alernative you may try...

Code: Select all

//******************************************************************************
//* pv/line
//******************************************************************************

#define LINE_MAXLEN 127

struct line_t
{
 ui16_t size;
 ui16_t move[LINE_MAXLEN];
};


//******************************************************************************
//* pv/line
//******************************************************************************

extern __inline void lineClr(line_t *lne) {lne->size=0;}
extern __inline void lineCpy(line_t *dst,line_t *src){*dst=*src;}
extern __inline void lineCat(line_t *dst,line_t *src,mv_t mve)
{
 dst->move[(dst->size=0)++] = mve;
 for(int i=0;i<src->size && i<LINE_MAXLEN-1;i++)
 {dst->move[dst->size++] = src->move[i];}
}


//******************************************************************************
//* collect - pseudo code
//******************************************************************************


int ab(int alpha,int beta,line_t *pv)
{
 line_t newPv[1];

 /*...*/

 while(moves)
 {
  
  lineClr(newPv);
  domove()
  value = -ab()
  undoMove()

  if(value<=bValue) continue; bValue=value;
  if(value<=alpha ) continue; alpha =value; lineCat(pv,newPv,currentMove);
  if(value>=beta  ) return(value);
 }

 return(bValue);
}

regards, Michael

[Desperado]

i am in hurry, though here is a simple alernative you may try...

Code: Select all

//******************************************************************************
//* pv/line
//******************************************************************************

#define LINE_MAXLEN 127

struct line_t
{
 ui16_t size;
 ui16_t move[LINE_MAXLEN];
};


//******************************************************************************
//* pv/line
//******************************************************************************

extern __inline void lineClr(line_t *lne) {lne->size=0;}
extern __inline void lineCpy(line_t *dst,line_t *src){*dst=*src;}
extern __inline void lineCat(line_t *dst,line_t *src,mv_t mve)
{
 dst->move[(dst->size=0)++] = mve;
 for(int i=0;i<src->size && i<LINE_MAXLEN-1;i++)
 {dst->move[dst->size++] = src->move[i];}
}


//******************************************************************************
//* collect - pseudo code
//******************************************************************************


int ab(int alpha,int beta,line_t *pv)
{
 line_t newPv[1];

 /*...*/

 while(moves)
 {
  
  lineClr(newPv);
  domove()
  value = -ab()
  undoMove()

  if(value<=bValue) continue; bValue=value;
  if(value<=alpha ) continue; alpha =value; lineCat(pv,newPv,currentMove);
  if(value>=beta  ) return(value);
 }

 return(bValue);
}

regards, Michael

a small (but important ) edit...

Code: Select all

value = -ab(-beta,-alpha,  newPv )

ahhhh, no time left

byebye

[bob]

Hi all,

I have been looking into possibly changing the way I'm collecting PV.
Currently its like this:

Code: Select all

// search.c

move_ordering {

PV 1st
Hash, Caps, Killers, History, etc.. 
}

Q_search {

if (score > alpha)
/* update the pv: */
			pv[ply][ply] = moves[i];
			for (j = ply + 1; j < pv_length[ply + 1]; j++)
				pv[ply][j] = pv[ply + 1][j];
			pv_length[ply] = pv_length[ply + 1];
if (score >= beta)
return beta:
************shouldn't I update the hash here? maybe separate Q_searches for PV/Null move etc?**************************

return alpha;
}[/quote]

You should only update the PV when score > alpha && score < beta.  On a "fail high" there is no PV.  If you want to update the hash in the q-search, which is ok to do, you would do it right before you return a result, because you would want to store any result you found, whether it be true score, or a bound.  I don't hash in the q-search as it increases memory traffic and stresses the hash table with lots of overwrites.  But it is pretty much break-even to hash or not hash there, so it is a choice one can make.

[quote]

Search {

check_hash
if exact return hash_score
if upper return hash_score
if lower return hash_score
if avoid_null FALSE
default break

null_search{
}

if !depth {
Q_search 
***********I was thinking this is not best - should go before null_search? Was thinking also of doing separate pv/non pv Q_search
*********************************************************[/quote]

It is a small speed optimization, you do a null-move search that will go right to the q-search anyway.

[quote]

PVS  {
if (score > alpha) {
/* update the pv: */
if (score >= beta)
store_hash lower_b
return alpha
}
******also I do upper and exact(i_alpha > alpha) here... **********
}


[/quote]
Same comment as above.  Don't update PV unless score is _inside_ the window.  Which means score > alpha && score < beta, otherwise you are generating lots of memory traffic fooling with a PV that is meaningless.

[quote]


ROOT {
if  if (score > alpha) {
/* update the pv: */

best_move = move;

store_hash exact_b

return best_move;
}
**********this seems wrong to me... shouldn't I at least
update the hash if root_score >= beta? Maybe not... ********[/quote]

The problem is you probably don't want to get a hash hit at the root.  You get nothing but a score.  You need a move to play.  So most don't hash at ply=1 to avoid that...


[quote]

CALL_ROOT {

// get PV from hash if PV is really short

if (pv_length <= 2 && i_depth > 1 && abs(cur_score)
					< (INF - 100) && result != stalemate && result
					!= draw_by_fifty && result != draw_by_rep)
				hash_to_pv(i_depth); 

*******hmmm... maybe I should always get PV from hash here? 
*****************************************************
}

hash.c

/* check what info we can get from our hash: */
if (h_depth >= depth) {
******** is always replace better? I'm wondering what is the current
opinion or if this is OK **************************************
}[/quote]

Most use some sort of priority scheme.  But always replace is critical as you must _never_ avoid storing a current entry.  What you overwrite is where all the choices are...

[quote]

Thanks for any help on this topic, I'm already changing a few things
and trying some ideas and any good guidance would be very much
appreciated!