Hash tables and PV

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
outAtime
Posts: 226
Joined: Sun Mar 08, 2009 2:08 pm
Location: Canada

Hash tables and PV

Post by outAtime » Fri Jun 03, 2011 1:06 am

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 &#40;j = ply + 1; j < pv_length&#91;ply + 1&#93;; j++)
				pv&#91;ply&#93;&#91;j&#93; = pv&#91;ply + 1&#93;&#91;j&#93;;
			pv_length&#91;ply&#93; = pv_length&#91;ply + 1&#93;;
if &#40;score >= beta&#41;
return beta&#58;
************shouldn't I update the hash here? maybe separate Q_searches for PV/Null move etc?**************************

return alpha;
&#125;

Search &#123;

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&#123;
&#125;

if !depth &#123;
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  &#123;
if &#40;score > alpha&#41; &#123;
/* update the pv&#58; */
if &#40;score >= beta&#41;
store_hash lower_b
return alpha
&#125;
******also I do upper and exact&#40;i_alpha > alpha&#41; here... **********
&#125;

ROOT &#123;
if  if &#40;score > alpha&#41; &#123;
/* update the pv&#58; */

best_move = move;

store_hash exact_b

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

CALL_ROOT &#123;

// get PV from hash if PV is really short

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

*******hmmm... maybe I should always get PV from hash here? 
*****************************************************
&#125;

hash.c

/* check what info we can get from our hash&#58; */
if &#40;h_depth >= depth&#41; &#123;
******** is always replace better? I'm wondering what is the current
opinion or if this is OK **************************************
&#125;

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

outAtime
Posts: 226
Joined: Sun Mar 08, 2009 2:08 pm
Location: Canada

Re: Hash tables and PV

Post by outAtime » Fri Jun 03, 2011 1:18 am

Code: Select all

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

	if &#40;depth < hash_p->depth&#41; &#123;
		return;
	&#125;
maybe this is the one I'd consider removing... Thanks again :)
outAtime

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Hash tables and PV

Post by sje » Fri Jun 03, 2011 2:36 am

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.

User avatar
Desperado
Posts: 801
Joined: Mon Dec 15, 2008 10:45 am

Re: Hash tables and PV

Post by Desperado » Fri Jun 03, 2011 8:32 am

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
&#123;
 ui16_t size;
 ui16_t move&#91;LINE_MAXLEN&#93;;
&#125;;


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

extern __inline void lineClr&#40;line_t *lne&#41; &#123;lne->size=0;&#125;
extern __inline void lineCpy&#40;line_t *dst,line_t *src&#41;&#123;*dst=*src;&#125;
extern __inline void lineCat&#40;line_t *dst,line_t *src,mv_t mve&#41;
&#123;
 dst->move&#91;&#40;dst->size=0&#41;++&#93; = mve;
 for&#40;int i=0;i<src->size && i<LINE_MAXLEN-1;i++)
 &#123;dst->move&#91;dst->size++&#93; = src->move&#91;i&#93;;&#125;
&#125;


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


int ab&#40;int alpha,int beta,line_t *pv&#41;
&#123;
 line_t newPv&#91;1&#93;;

 /*...*/

 while&#40;moves&#41;
 &#123;
  
  lineClr&#40;newPv&#41;;
  domove&#40;)
  value = -ab&#40;)
  undoMove&#40;)

  if&#40;value<=bValue&#41; continue; bValue=value;
  if&#40;value<=alpha ) continue; alpha =value; lineCat&#40;pv,newPv,currentMove&#41;;
  if&#40;value>=beta  ) return&#40;value&#41;;
 &#125;

 return&#40;bValue&#41;;
&#125;
regards, Michael

User avatar
Desperado
Posts: 801
Joined: Mon Dec 15, 2008 10:45 am

Re: Hash tables and PV

Post by Desperado » Fri Jun 03, 2011 8:52 am

Desperado wrote: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
&#123;
 ui16_t size;
 ui16_t move&#91;LINE_MAXLEN&#93;;
&#125;;


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

extern __inline void lineClr&#40;line_t *lne&#41; &#123;lne->size=0;&#125;
extern __inline void lineCpy&#40;line_t *dst,line_t *src&#41;&#123;*dst=*src;&#125;
extern __inline void lineCat&#40;line_t *dst,line_t *src,mv_t mve&#41;
&#123;
 dst->move&#91;&#40;dst->size=0&#41;++&#93; = mve;
 for&#40;int i=0;i<src->size && i<LINE_MAXLEN-1;i++)
 &#123;dst->move&#91;dst->size++&#93; = src->move&#91;i&#93;;&#125;
&#125;


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


int ab&#40;int alpha,int beta,line_t *pv&#41;
&#123;
 line_t newPv&#91;1&#93;;

 /*...*/

 while&#40;moves&#41;
 &#123;
  
  lineClr&#40;newPv&#41;;
  domove&#40;)
  value = -ab&#40;)
  undoMove&#40;)

  if&#40;value<=bValue&#41; continue; bValue=value;
  if&#40;value<=alpha ) continue; alpha =value; lineCat&#40;pv,newPv,currentMove&#41;;
  if&#40;value>=beta  ) return&#40;value&#41;;
 &#125;

 return&#40;bValue&#41;;
&#125;
regards, Michael
a small (but important :!: ) edit...

Code: Select all

value = -ab&#40;-beta,-alpha,  newPv )
ahhhh, no time left :lol:

byebye

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hash tables and PV

Post by bob » Fri Jun 03, 2011 5:45 pm

outAtime wrote: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 &#123;

PV 1st
Hash, Caps, Killers, History, etc.. 
&#125;

Q_search &#123;

if &#40;score > alpha&#41;
/* update the pv&#58; */
			pv&#91;ply&#93;&#91;ply&#93; = moves&#91;i&#93;;
			for &#40;j = ply + 1; j < pv_length&#91;ply + 1&#93;; j++)
				pv&#91;ply&#93;&#91;j&#93; = pv&#91;ply + 1&#93;&#91;j&#93;;
			pv_length&#91;ply&#93; = pv_length&#91;ply + 1&#93;;
if &#40;score >= beta&#41;
return beta&#58;
************shouldn't I update the hash here? maybe separate Q_searches for PV/Null move etc?**************************

return alpha;
&#125;&#91;/quote&#93;

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.

&#91;quote&#93;

Search &#123;

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&#123;
&#125;

if !depth &#123;
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
*********************************************************&#91;/quote&#93;

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

&#91;quote&#93;

PVS  &#123;
if &#40;score > alpha&#41; &#123;
/* update the pv&#58; */
if &#40;score >= beta&#41;
store_hash lower_b
return alpha
&#125;
******also I do upper and exact&#40;i_alpha > alpha&#41; here... **********
&#125;


&#91;/quote&#93;
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.

&#91;quote&#93;


ROOT &#123;
if  if &#40;score > alpha&#41; &#123;
/* update the pv&#58; */

best_move = move;

store_hash exact_b

return best_move;
&#125;
**********this seems wrong to me... shouldn't I at least
update the hash if root_score >= beta? Maybe not... ********&#91;/quote&#93;

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


&#91;quote&#93;

CALL_ROOT &#123;

// get PV from hash if PV is really short

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

*******hmmm... maybe I should always get PV from hash here? 
*****************************************************
&#125;

hash.c

/* check what info we can get from our hash&#58; */
if &#40;h_depth >= depth&#41; &#123;
******** is always replace better? I'm wondering what is the current
opinion or if this is OK **************************************
&#125;&#91;/quote&#93;

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

&#91;quote&#93;

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!

Post Reply