Puzzle with mate scores in TT

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.
micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Puzzle with mate scores in TT

Post by micron » Fri Dec 10, 2010 12:21 pm

My engine has two compile-time options for treating mate scores in the TT.

1. Standard adjustments for ply.

Code: Select all

Reading from TT:
if ( score > MATESCORE - MAXPLIES ) 
  score -= ply; 
else if ( score < -MATESCORE + MAXPLIES ) 
  score += ply; 

Saving in TT&#58;
if ( score > MATESCORE - MAXPLIES ) 
  score += ply; 
else if ( score < -MATESCORE + MAXPLIES ) 
  score -= ply; 
... save score and scoreType in TT...
2. Mate scores converted to bounds.
http://web.archive.org/web/200404270147 ... tehash.htm

Code: Select all

Reading from TT&#58; 
No adjustment.

Saving in TT&#58;
if ( score > MATESCORE - MAXPLIES ) 
  &#123; 
    if ( scoreType == UPPERBOUND ) return; // don't save
    score = MATESCORE - MAXPLIES; 
    scoreType = LOWERBOUND; 
  &#125; 
  else if ( score < -MATESCORE + MAXPLIES ) 
  &#123; 
    if ( scoreType == LOWERBOUND ) return; // don't save
    score = -MATESCORE + MAXPLIES; 
    scoreType = UPPERBOUND; 
  &#125;
... save score and scoreType in TT...
The puzzle is that in my engine the nonstandard option #2 is much stronger (around 100 Elo) than #1.
It seems implausible that option #2 is "really" better, because in that case everyone would be using it.
More likely I have a bug (perhaps relating to scoreType for mate scores) that is rendered harmless by option #2. I am however, unable to see such a bug and would welcome ideas/suggestions how to proceed.

Robert P.

Daniel Shawul
Posts: 3757
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Puzzle with mate scores in TT

Post by Daniel Shawul » Fri Dec 10, 2010 11:08 pm

As you said, case (1) may have a bug with mate scoring which could make it prefer longer mates eg. mate in 20 over mate in 1. Look at the games and see if it has problems with finishing off mates... Your mate scoring seems to be a bit different from mine so I am not sure if it helps but here is what I do.

In search with 0 legal moves.

Code: Select all

          return   -MATE_SCORE + ply    .......... &#40;1&#41;
TT storing : neutralize the ply factor out (do the opposite of (1))

Code: Select all

 
 if&#40;score > MATE_SCORE&#41;                 .............&#40;2&#41;
 		score += &#40;ply + 1&#41;;
 else if&#40;score < -MATE_SCORE&#41; 
		score -=  &#40;ply + 1&#41;;
TT probe : bring back the ply factor (do the opposite of (2))

Code: Select all

      if&#40;score > MATE_SCORE&#41; 
				score -= &#40;ply + 1&#41;;
	  else if&#40;score < -MATE_SCORE&#41; 
				score += &#40;ply + 1&#41;;
regards
Daniel

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: Puzzle with mate scores in TT

Post by micron » Sat Dec 11, 2010 7:14 am

Daniel Shawul wrote:
Look at the games and see if it has problems with finishing off mates.
Thanks for the suggestion. Alas, it has so far proved frustrating instead of enlightening.
...here is what I do.
In search with 0 legal moves.

Code: Select all

return   -MATE_SCORE + ply    .......... &#40;1&#41;
Agreed.
TT storing : neutralize the ply factor out (do the opposite of (1))

Code: Select all

if&#40;score > MATE_SCORE&#41;                 .............&#40;2&#41;
 		score += &#40;ply + 1&#41;;
 else if&#40;score < -MATE_SCORE&#41; 
		score -=  &#40;ply + 1&#41;;
TT probe : bring back the ply factor (do the opposite of (2))

Code: Select all

      if&#40;score > MATE_SCORE&#41; 
				score -= &#40;ply + 1&#41;;
	  else if&#40;score < -MATE_SCORE&#41; 
				score += &#40;ply + 1&#41;;
Wouldn't that mean that you never adjust the score? The only value greater than MATE_SCORE is INFINITY, which won't be stored in the TT.

Also, why adjust by (ply + 1) instead of ply? The returned score, after storage and retrieval, would be the same in both cases.

Robert P.

Daniel Shawul
Posts: 3757
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Puzzle with mate scores in TT

Post by Daniel Shawul » Sat Dec 11, 2010 12:45 pm

Oops I messed up while trying to simplify the code for only the mating case...
See i do this adjustment for bitbase scores as well, which are scored much lower than mate ofcourse.
To prefer shorter wins, a lot of heuristic which considers material, position of pieces , and also the PLY etc..
The PLY factor is used is not 1 as is in the mating case, rather a weighted value(x40) is used for it not to be overwhelmed by other terms.
Existing scorpio code follows

Search with 0 legal:

Code: Select all

      score = -MATE_SCORE + WIN_PLY * &#40;ply + 1&#41;;
and for bitbases

Code: Select all

					if&#40;score > 0&#41;
						score -= WIN_PLY * &#40;ply + 1&#41;;
					else if&#40;score < 0&#41;
						score += WIN_PLY * &#40;ply + 1&#41;;
TT store:

Code: Select all

if&#40;score > WIN_SCORE&#41; 
				score += WIN_PLY * &#40;ply + 1&#41;;
			else if&#40;score < -WIN_SCORE&#41; 
				score -= WIN_PLY * &#40;ply + 1&#41;;
Here WIN_SCORE = 3000 and MATE_SCORE = 20000.
WIN_SCORE is the minimum winning score. WIN_PLY = 40 , if i use the standard factor 1 it will have difficulty detecting shorter bitbase wins..
The (ply + 1) could as well be (ply). I am kind of rusty after some time off :)

Well I hope I did not confuse you more.

regards,
Daniel

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: Puzzle with mate scores in TT

Post by micron » Sat Dec 11, 2010 11:15 pm

My engine has two compile-time options for treating mate scores in the TT.

1. Standard adjustments for ply.
2. Mate scores converted to bounds.
http://web.archive.org/web/200404270147 ... tehash.htm

The puzzle is that in my engine the nonstandard option #2 is much stronger (around 100 Elo) than #1.
It seems implausible that option #2 is "really" better, because in that case everyone would be using it.
I tracked this down to some evil effect of TT mate-scores from previous searches. With the standard adjustments #1 for ply, simply clearing the TT between moves removes the anomaly, giving 100+ Elo boost. Of course I don't want to do that; for one thing clearing a huge TT is so slow that matches are impossible at very short time control.

Instead I now test if a mate-score derives from an earlier search (easy because my TT struct has a moveClock field) and if so, ignore it.

User avatar
lucasart
Posts: 3040
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Puzzle with mate scores in TT

Post by lucasart » Sun Dec 12, 2010 2:47 pm

micron wrote:My engine has two compile-time options for treating mate scores in the TT.

1. Standard adjustments for ply.

Code: Select all

Reading from TT&#58;
if ( score > MATESCORE - MAXPLIES ) 
  score -= ply; 
else if ( score < -MATESCORE + MAXPLIES ) 
  score += ply; 

Saving in TT&#58;
if ( score > MATESCORE - MAXPLIES ) 
  score += ply; 
else if ( score < -MATESCORE + MAXPLIES ) 
  score -= ply; 
... save score and scoreType in TT...
2. Mate scores converted to bounds.
http://web.archive.org/web/200404270147 ... tehash.htm

Code: Select all

Reading from TT&#58; 
No adjustment.

Saving in TT&#58;
if ( score > MATESCORE - MAXPLIES ) 
  &#123; 
    if ( scoreType == UPPERBOUND ) return; // don't save
    score = MATESCORE - MAXPLIES; 
    scoreType = LOWERBOUND; 
  &#125; 
  else if ( score < -MATESCORE + MAXPLIES ) 
  &#123; 
    if ( scoreType == LOWERBOUND ) return; // don't save
    score = -MATESCORE + MAXPLIES; 
    scoreType = UPPERBOUND; 
  &#125;
... save score and scoreType in TT...
The puzzle is that in my engine the nonstandard option #2 is much stronger (around 100 Elo) than #1.
It seems implausible that option #2 is "really" better, because in that case everyone would be using it.
More likely I have a bug (perhaps relating to scoreType for mate scores) that is rendered harmless by option #2. I am however, unable to see such a bug and would welcome ideas/suggestions how to proceed.

Robert P.
TTable are subtile. I coded a chess engine, so I know the hurdles. After many failures, I realised that this is the right way to proceed:

* lookup the TT. At PV nodes only use it for move ordering, but don't return the TT score (because of draw by 3/50 move rules or mate situations).
* At non PV nodes, return the TT score if you know it creates a cutoff (using the info of score exact lboudn or ubound and the current window alpha,alpha+1=beta)
* when you've found the best move, save it in the TT, and put the info about whether the score is exact lbound or ubound.

Have a look at Fruit 2.1 source code for a good source code that is relatively simple to understand.

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: Puzzle with mate scores in TT

Post by micron » Sat Feb 19, 2011 10:41 pm

lucasart wrote:
My engine has two compile-time options for treating mate scores in the TT.

1. Standard adjustments for ply.

2. Mate scores converted to bounds.
http://web.archive.org/web/200404270147 ... tehash.htm


The puzzle is that in my engine the nonstandard option #2 is much stronger (around 100 Elo) than #1.
It seems implausible that option #2 is "really" better, because in that case everyone would be using it.
More likely I have a bug (perhaps relating to scoreType for mate scores) that is rendered harmless by option #2. I am however, unable to see such a bug and would welcome ideas/suggestions how to proceed.
TTable are subtile. I coded a chess engine, so I know the hurdles. After many failures, I realised that this is the right way to proceed:

* lookup the TT. At PV nodes only use it for move ordering, but don't return the TT score (because of draw by 3/50 move rules or mate situations).
* At non PV nodes, return the TT score if you know it creates a cutoff (using the info of score exact lboudn or ubound and the current window alpha,alpha+1=beta)
* when you've found the best move, save it in the TT, and put the info about whether the score is exact lbound or ubound.
Yes indeed, ignoring the score at PV nodes completely removes the anomaly. I can now use the standard adjustment for ply.
Robert P.

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

Re: Puzzle with mate scores in TT

Post by hgm » Sat Feb 19, 2011 11:39 pm

lucasart wrote:* lookup the TT. At PV nodes only use it for move ordering, but don't return the TT score (because of draw by 3/50 move rules or mate situations).
I have heard claims that this hurts the engine very much in positions like Fine #70. How long does it take your engine to solve that?

rjgibert
Posts: 308
Joined: Mon Jun 26, 2006 7:44 am

Re: Puzzle with mate scores in TT

Post by rjgibert » Sat Feb 19, 2011 11:51 pm

micron wrote: I tracked this down to some evil effect of TT mate-scores from previous searches. With the standard adjustments #1 for ply, simply clearing the TT between moves removes the anomaly, giving 100+ Elo boost. Of course I don't want to do that; for one thing clearing a huge TT is so slow that matches are impossible at very short time control.
Clearing the hash table between moves is not slow. At the beginning of a search, simply changing the 2 zobrist hash codes for turn to move effectively guarantees that nothing from a previous search gets used. There are others ways to accomplish the same thing very cheaply. This is just one.

But of course, you don't want to have to do this as you said.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Puzzle with mate scores in TT

Post by Evert » Sun Feb 20, 2011 12:41 am

lucasart wrote: * lookup the TT. At PV nodes only use it for move ordering, but don't return the TT score (because of draw by 3/50 move rules or mate situations).
I've seen that claim before and I've never understood why it would be necessary to ignore cut-offs from the transposition table in PV nodes (other than to get the complete PV).
For the three-fold repetition and the 50-move rule you have to be a little bit careful (I indeed don't allow cutoffs from the TT if the half-move counter is > 80 or so), but what's the problem with mate scores? I mean, they have to be corrected in some way for the distance to the root, but that's not too difficult.
What's the problem exactly?

Post Reply