Hashing and mate scores

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Hashing and mate scores

Post by Chan Rasjid » Sat Sep 29, 2007 10:32 pm

There is a straightforward way to treat mate scores and to hash such scores in the transposition table. My understanding is that there is probably no alternative and correct way for this unless it masquerades in a similar but degenerate manner. It is the way Dr Hyatt used to mention, hashing simply the distance to mate.

If the current exchanges between Muller and Dr Hyatt is about this and Muller proposes any better alternative, I think he must have simply missed something or has some misunderstanding.

Long time ago, Bruce Moreland mentioned how he treated mate scores and I was surprised of how he did it. I mentioned that there was a simple way and that there seemed no need to do it in any other manner. He did no reply to my post.

The way is this:-

Code: Select all

#define  infi 10000
#define max_height  128
#define  loss_mate  -10000 + 127
#define  win_mate   10000 - 127

int search(int depth,...){
gen_moves();
if (in_check && no_valid_move){
  score = -infi + ply;
  hash_mate(EXACT,MAX_DEPTH, score - ply);/* adjust ply*/
  return score;  
}

if (probehash == true){
 score = get_hash_score();
 if &#40;score <= loss_mate&#41;
 score += ply;/*adjust ply*/
 if &#40;score >= win_mate&#41;
 score -= ply;/*adjust ply*/
 ...etc
&#125; 


for moves&#123;
make&#40;);
++ply;
score = -search&#40;depth - 1, ...);
unmake&#40;);
--ply;
&#125;

/*hash with ply adjust for mate scores */
 if &#40;score <= loss_mate&#41;&#123;
  assert&#40;ply & 1&#41;;
  assert&#40;score - ply >= -infi&#41;;
  hash_mate&#40;EXACT,MAX_DEPTH, score - ply&#41;;
 &#125;
 if &#40;score >= win_mate&#41;&#123;
  assert&#40;!&#40;ply & 1&#41;);
  assert&#40;score + ply <= infi&#41;;
  hash_mate&#40;EXACT,MAX_DEPTH, score + ply&#41;;
 &#125;


return score;
&#125;

I don't seem to be able to find the alternative method by Muller. If he put it here and IF it is not too complicated, I may try to understand it although I am averse to think about anything that don't seem to help.

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

Tony

Re: Hashing and mate scores

Post by Tony » Sun Sep 30, 2007 7:39 am

Most hashtables already use an AT_MOST, AT_LEAST and EXACT flag. Why not add a CHECKMATE flag ?

That way you also have an easy test, wether you are overwriting an existing checkmate score with a smaller one (because of not playing the fastest mate)

Tony

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Hashing and mate scores

Post by Chan Rasjid » Sun Sep 30, 2007 4:14 pm

Hello,

van Roon-Werten wrote:-
Most hashtables already use an AT_MOST, AT_LEAST and EXACT flag. Why not add a CHECKMATE flag ?

That way you also have an easy test, wether you are overwriting an existing checkmate score with a smaller one (because of not playing the fastest mate)
I have an extra bit that may add a CHEKMATE flag.
I could call if (!(flag & CHEKMATE)){}else instead of
if (score >=loss_mate && score <= win_mate){}else. But this may not be what you mean.

I don't search for the shortest mate until it propagates to the root when I call mate_search(). I use EXACT for convenience but my mate scores are always MAX_DEPTH, but may be exact/upper/lower.For the first search with -infi, +infi, it will return on a win-mate as lower and this may propagate few plies down and hash as best loss-mate/upper, etc..

My hashing do have an overwriting scheme that always overwrite nodes of earlier game-move searches even if they be exact mate-scores. I do know know yet of any problem with overwriting of shorter checkmate as my overwriting due to multi-probe rehashing or otherwise also have a natural priority based on depth+ exact > upper> lower, etc.

As an aside, I also don't know why a program do not return on mate scores and look for the shortest mate
only if mate scores propagate to the root. Most mate scores end up being refuted if our program is strong.

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
hgm
Posts: 24740
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Hashing and mate scores

Post by hgm » Mon Oct 01, 2007 10:09 am

Chan Rasjid wrote:I don't seem to be able to find the alternative method by Muller. If he put it here and IF it is not too complicated, I may try to understand it although I am averse to think about anything that don't seem to help.
It was in two other threads, but it is short enough to repeat it once more (tailored to checkmates only, rather than for taking the shortest path to any gain):

Code: Select all

int Search&#40;Depth, Alpha, Beta&#41; 
&#123; 
    int BestScore = Dept>0 ? -INFINITY &#58; Eval&#40;); 

    if&#40;NO_MOVES&#41; return&#40;CHECKMATED ? -INFINITY &#58; 0&#41;;

    HASH_PROBE; // might lead to pruning on OK hit

    // Have to search
    if&#40;Alpha <= -MATESCORES&#41; Alpha = Alpha - 1; 
    if&#40;Beta < -MATESCORES&#41; Beta = Beta - 1; 

    for&#40;ALL_MOVES_TO_BE_SEARCHED&#41;
    &#123;
        if&#40;BestScore >= Beta&#41; goto cutoff;

        Score = -Search&#40;Depth-1, ...);
        if&#40;Score > BestScore&#41; &#123; BestScore = Score; ... /* alpha-beta stuff */&#125;
    &#125;
  cutoff&#58;
    if&#40;BestScore < -MATESCORES&#41; BestScore = BestScore + 1; 

    HASH_STORE&#40;BestScore&#41;; 
    return&#40;BestScore&#41;; 
&#125; 

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Hashing and mate scores

Post by Chan Rasjid » Mon Oct 01, 2007 2:26 pm

Hello Muller,

You give me problems. I don't like to think and now I must.OK, the pseudo codes are just few lines but on first reading, it does not seem straightforward so I may take some time or just give up! I will try but I think others can just add a comment if they know if it works and I may try harder.

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Hashing and mate scores

Post by Chan Rasjid » Mon Oct 01, 2007 2:56 pm

Code: Select all

/*these added to clear any misunderstanding*/
#define INFINITY  10000
#define MAX_HEIGHT  128
#define MATESCORES 10000 - 127

int Search&#40;Depth, Alpha, Beta&#41;
&#123;
    int BestScore = Dept>0 ? -INFINITY &#58; Eval&#40;);

    if&#40;NO_MOVES&#41; return&#40;CHECKMATED ? -INFINITY &#58; 0&#41;;

    HASH_PROBE; // might lead to pruning on OK hit

    // Have to search
    if&#40;Alpha <= -MATESCORES&#41; Alpha = Alpha - 1;
    if&#40;Beta < -MATESCORES&#41; Beta = Beta - 1;

    for&#40;ALL_MOVES_TO_BE_SEARCHED&#41;
    &#123;
/*
I need to move this line down
        if&#40;BestScore >= Beta&#41; goto cutoff;
*/

        Score = -Search&#40;Depth-1, ...);
        if&#40;Score > BestScore&#41; &#123; BestScore = Score; ... /* alpha-beta stuff */
         if&#40;BestScore >= Beta&#41; goto cutoff;
&#125;
    &#125;
  cutoff&#58;
    if&#40;BestScore < -MATESCORES&#41; BestScore = BestScore + 1;

    HASH_STORE&#40;BestScore&#41;;
    return&#40;BestScore&#41;;
&#125;
My first minor question is:-
for first call to search() from root with Alpha = -infi, the line
if(Alpha <= -MATESCORES) Alpha = Alpha - 1;
would be satisfied and Alpha = -INFINITY - 1 ???
I'll see if it's OK.

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
hgm
Posts: 24740
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Hashing and mate scores

Post by hgm » Mon Oct 01, 2007 3:21 pm

Chan Rasjid wrote: My first minor question is:-
for first call to search() from root with Alpha = -infi, the line
if(Alpha <= -MATESCORES) Alpha = Alpha - 1;
would be satisfied and Alpha = -INFINITY - 1 ???
I'll see if it's OK.
Yes, that doesn't hurt. It just makes the search window a bit larger, but there will never be any score that falls in the expanded range.

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: Hashing and mate scores

Post by Chan Rasjid » Mon Oct 01, 2007 6:13 pm

Hello Muller,

I think your codes work. But this is the month of Ramadan when my thinking is not too reliable and so my analysis is tentative unless confirmed by others.

Some small changes to your codes with my comments added:-

Code: Select all

#define INFINITY  10000
#define MAX_HEIGHT  128
#define MATESCORES 10000 - 63

int Search&#40;Depth, Alpha, Beta&#41;
&#123;
    int BestScore = Dept>0 ? -INFINITY &#58; Eval&#40;);

    if&#40;NO_MOVES&#41; return&#40;CHECKMATED ? -INFINITY &#58; 0&#41;;

    HASH_PROBE; // might lead to pruning on OK hit

    // Have to search
    /* 
my comments - 
1&#41;this bounds shifting needed only when node below is searching for a better wining mate.
2&#41; ensures beta-cutoff return if next better winning mate found
*/
    if&#40;Alpha <= -MATESCORES&#41; Alpha = Alpha - 1;
    if&#40;Beta < -MATESCORES&#41; Beta = Beta - 1;

    for&#40;ALL_MOVES_TO_BE_SEARCHED&#41;
    &#123;
        Score = -Search&#40;Depth-1, ...);
        if&#40;Score > BestScore&#41; &#123; BestScore = Score; ... /* alpha-beta stuff */
         if&#40;BestScore >= Beta&#41; goto cutoff;
&#125;
    &#125;
  cutoff&#58;
  /* my comments - this seems ok as it affects only losing best mate-scores*/  
  if&#40;BestScore < -MATESCORES&#41; BestScore =  BestScore + 1;

    HASH_STORE&#40;BestScore&#41;;
    return&#40;BestScore&#41;;
&#125;
1) MATESCORES is 10000 - 63 and not 10000 - 127
as now mate in 1/2/3 is -1/-2/-3 ..../ -63

2) Assume a certain node A deep in the tree and the first move searched to a sufficient depth that returns a winning mate in 3, the plies being relative :-

node / ply / mate-scores
==============
F 5 -infi ,checkmate
E 4 infi ,mate_in_1
D 3 -infi + 1 ,mate_in_2
C 2 infi - 1 ,mate_in_2
B 1 -infi + 2 ,mate_in_3
A 0 infi - 2 ,mate_in_3

When A searches for a better mate with the next move, (Alpha, Beta) of B will be shifted left by 1 to
(-inf -1, -inf + 1 ) and seems ok (see comments within codes)

3) Hashing -inf/inf, -inf+1/ inf+1, -inf+2/ inf+2,...
and probe hash retrieves of such scores and setting such as bestscore etc.. seems ok. It seems the scheme does not cause any hashing problem.

4) If this scheme works, I think it is much cleaner. I cannot yet incorporate it in my program as I am making fairly extensive changes to it.

5) the unusual stuffs in the pseudo codes affect only mate scores. ok?

6) who invented this?
Has this being used in any open source program?

7)final- my analysis is TENTATIVE!!!

Rasjid
Don't believe when you're told "There's no free lunch!" There is Linux.

Pradu
Posts: 287
Joined: Sat Mar 11, 2006 2:19 am
Location: Atlanta, GA
Contact:

Re: Hashing and mate scores

Post by Pradu » Mon Oct 01, 2007 7:46 pm

Chan Rasjid wrote:6) who invented this?
Has this being used in any open source program?
I guess it is not clear who came up with the technique but I know a similar technique exists in atleast two opensource programs. The bounds updating for pruning out lines that cannot possibly lead to shorter mates can be found in Fruit where Fabien calls it "mate-distance pruning". I have also been using the bounds updating technique for cutting out bad mate lines in Buzz since the beginning.

Code: Select all

#ifdef MATE_DISTANCE_PRUNING
&#123;
	//dfr=depth from root

	//The maximum mate score that can be attained by 
	//the current player
	//MATE-&#40;dfr+1&#41;
	int mate_score_bound=MATE-&#40;dfr+1&#41;;
	if&#40;alpha>=mate_score_bound&#41; return mate_score_bound;
	if&#40;beta>mate_score_bound&#41; beta=mate_score_bound;

	//The maximum mate score that the opponent can
	//have &#40;mate right now&#41;
	mate_score_bound=-&#40;MATE-dfr&#41;;
	if&#40;mate_score_bound>=beta&#41; return mate_score_bound;
	if&#40;mate_score_bound>alpha&#41; alpha=mate_score_bound;
&#125;
#endif
H.G. wants to extend the concept to not just mates but all moves in general I think.

Gerd Isenberg
Posts: 2177
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Hashing and mate scores

Post by Gerd Isenberg » Mon Oct 01, 2007 9:15 pm

Chan Rasjid wrote:Hello Muller,
I think your codes work. But this is the month of Ramadan when my thinking is not too reliable and so my analysis is tentative unless confirmed by others.
I guess there are some more programs keeping ply-independent mate scores - adjusted in zero direction while backing them up the tree. Iirr there was a similar discussion about this topic some time ago, where Ed explained how it works in Rebel or Pro Deo. I think one scheme is as good as the other and a matter of taste, customization or even own invention in pre internet times. Often the first understanding of things manifest thinking paradigms.

I assume HG's delayed-loss-bonus concept in conditionally adjusting alpha, beta and best score on mate bounds quite smart. It avoids unnecessary searches with mate bounds - even if it is negligible for normal play. Ply-dependend mate score programs may try some extra conditions at the start of the search-routine to gain the same effect:

Code: Select all

   score = ply - VALUE_MATE; // initial worst case score if mated
   if ( score >= beta&#41;	
      return score;	 // worst case score is already a beta-cutoff
   if (-score - 1 <= alpha&#41;	
      return -score - 1; // already mate in n-ply 
Since ply-dependend mate score programs only adjust mate scores while probing/storing hash - but Bob does not hash in qsearch - he obviously has shorter qsearch code, which might be an issue in a high speed program like Crafty with separate search/qsearch code. HG - probably using one recursive search-routine for both search and qsearch - needs the additional conditions always - even if cheap and almost 100% predictable none taken.

Gerd

Post Reply