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.
-
outAtime
- Posts: 226
- Joined: Sun Mar 08, 2009 2:08 pm
- Location: Canada
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 (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
-
outAtime
- Posts: 226
- Joined: Sun Mar 08, 2009 2:08 pm
- Location: Canada
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: */
if (depth < hash_p->depth) {
return;
}
maybe this is the one I'd consider removing... Thanks again
outAtime
-
sje
- Posts: 4675
- Joined: Mon Mar 13, 2006 6:43 pm
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.
-
Desperado
- Posts: 801
- Joined: Mon Dec 15, 2008 10:45 am
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
{
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
- Posts: 801
- Joined: Mon Dec 15, 2008 10:45 am
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
{
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
- Posts: 20923
- Joined: Mon Feb 27, 2006 6:30 pm
- Location: Birmingham, AL
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 {
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!
