Winboard Forum

How do you handle mate scores in the hash table?
I've been having some problems with this for a while and wanted to see you guys do. What I've been doing is subtract depthleft to the (absolute) mate score int he hash table and subrtarce the (absolute) mate score by depth to root when accessed. This dosen't seem to work very well for me, so I'm looking for other methods to solve this problem.

Hi Pradu,
when stored, mate values are set to be relative to the current node, rather than to the root:

Code: Select all

        if( result > Score::MateHi )
            result += ply;
        else if( result < Score::MateLo )
            result -= ply;


then when you retrieve the value from the hash table you convert it to root-based again:

Code: Select all

        if( value < Score::MateLo )
            value += ply;
        else if( value > Score::MateHi )
            value -= ply;


This looks like what you're already doing though. In addition, if you get strange and incorrect mate scores there are a couple of things that have helped me:
- do not use null move if looking for mates (alpha is a mate score);
- do not store fail lows if looking for mates.
I'm trying the above since the last version and they seem to work. In earlier versions, I had to cleanup the hash table if the previous search returned a mate, which was inelegant but simple and effective!

I was up working on this problem last night. I decided to get around the issue by not storing precise mate scores in the trans table.

this way, if the search needs to know exactly what the distance to mate is. it's going to rely on the search, not the trans table. if i'm right this doesn't really happen very often except when the game is already won/lost.

however if alpha/beta is within a reasonable level. (ie, close game still) Then the trans table can still tell me that this position (which leads to mate) is WAY good or WAY bad.

I think (hope) that this solution gets rid of a few headaches for me without really downgrading performance.

here is the beginning of my modified proc for storing the values in the trans table.

Code: Select all

void trans_table_store(chessboard *board, int depth, transtableentrytype type, int value, chessmove move){

   
   //don't store scores close to mate
   if(value>=VALMATEIN(200) && (type==TRANSVALUEEXACTLY || type==TRANSVALUEATLEAST)){
      type=TRANSVALUEATLEAST;
      value=VALMATEIN(200);
   }else if(value<=-VALMATEIN(200) && (type==TRANSVALUEEXACTLY || type==TRANSVALUEATMOST)){
      type=TRANSVALUEATMOST;
      value=-VALMATEIN(200);
   }


I am not sure ho there can be any problem in connection with storing mate scores in the hash table. If there are positions that lead to a forced mate thy will get the high score that you assigned to mate, possibly discounted for the number of moves it takes to enforce this (possibly as part of a more general scheme to penalize postponment of gains). Why not simply store the position and the score it receives in the hash table?

I even 'upgrade' such an entry in the hash table, by listing it as being calculated to infinite depth; even if it is a 'mate in 3' that was discovered in a 6-ply search, nothing can be expected from deepening the search, since this can only lead to the discovery of slower mates that will have lower score. So if an evaluation at 12 ply is needed, the 6-ply evaluation foud in the hash table is still perfectly useable if it is a forced mate.

I am not sure ho there can be any problem in connection with storing mate scores in the hash table

The problem arises when the matescore used in search contains DTM from the root position, which is the most natural to do. In the hashtable you want to use DTM from the current position instead, so a conversion is needed.

A simpler method is to only store upper/lower bounds (as described by Bruce Moreland on his pages). Those are usually sufficient to cause cutoffs during search. Ofcourse a little slower to find the fastest mate, but that should not hurt performance in games (as games are usually decided by then ).

I also use the upgrade that you mentioned in the Baron. Also for scores that I retrieved from EGTB's.
Richard.

OK, I see. In my search DTM is effectively measured from the current positon, but the score gets progressively smaller as it is passed down towards the root because I give it an 'ageing' penalty. So if the current position is checkmate it recieves the corresponding ultimate score, no matter how deep in the tree it is, but seen from the root a mate far away looks less attractive than a mate close by.

So I guess I was just lucky that no problems occur this way.

H.G.Muller wrote:I even 'upgrade' such an entry in the hash table, by listing it as being calculated to infinite depth; even if it is a 'mate in 3' that was discovered in a 6-ply search, nothing can be expected from deepening the search, since this can only lead to the discovery of slower mates that will have lower score. So if an evaluation at 12 ply is needed, the 6-ply evaluation foud in the hash table is still perfectly useable if it is a forced mate.

Beware, though:

From playing a little bit with a hash-table extension to my minimalistic chess engine, I just came to realize the following: it is only save to do this when an n-ply search finds a mate in at most n+2 plies. If it finds a slower mate, there is no guarantee that there are no routes to mate at intermediate distances. For instances, in the archetypal pawn ending KPK (Ke1, Pe2; Ke8) with the aid of the hash table the first forced mate is found at a search depth of 26 ply, and it is a mate in 32.

It is interesting, by the way, that the search is much more efficient if I completely open the (alpha,beta) window on every ply (i.e. set it to (-inf,+inf)). On the first few plies this leads to more nodes being searched, but this is just an investment in the quality of the contents of hash table: the fact that every entry in there is always compatible with any window makes you catch up later.