Draw 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.
smatovic
Posts: 909
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Draw scores in TT

Post by smatovic » Sat Apr 14, 2018 8:32 am

How do you handle draw scores by repetition and fifty move rule in TT?

I use zero as draw score, and simply prevent to load such an value from TT,
i guess there are better techniques to prevent an mix up with an eval score of zero.

--
Srdja

edit: assuming i wish to use an 16 bit signed integer as tt score with centi pawn based eval.

User avatar
xr_a_y
Posts: 766
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Draw scores in TT

Post by xr_a_y » Sat Apr 14, 2018 8:50 am

Hello,

using a reversible 16bit hash for move in TT (I store this move hash in a TT entry), I can simply check afterward if the move is leading to a draw and eventually use the contempt factor or just skip the TT advice and search for a best move.

smatovic
Posts: 909
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Draw scores in TT

Post by smatovic » Sat Apr 14, 2018 10:33 am

using a reversible 16bit hash for move in TT
Are 16 bit sufficient for a move? Hash collisions?

--
Srdja

flok

Re: Draw scores in TT

Post by flok » Sat Apr 14, 2018 11:42 am

Just curious but why would you want to prevent those scores in the TT?
They're valid for the position, aren't they?

User avatar
xr_a_y
Posts: 766
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Draw scores in TT

Post by xr_a_y » Sat Apr 14, 2018 12:04 pm

Yes I just store starting square, landing square and a move type.

Something like this :

Code: Select all

class Move{
public :
  [...]
  typedef unsigned short int HashType;

  static inline Square::LightSquare     Hash2From(HashType h) { return (h >> 10) & 0x3F ;}
  static inline Square::LightSquare     Hash2To  (HashType h) { return (h >>  4) & 0x3F ;}
  static inline UtilMove::eSpecialMove  Hash2Type(HashType h) { return UtilMove::eSpecialMove( (h & 0xF)+UtilMove::sm_mini);}
  static inline HashType                ToHash(Square::LightSquare     from,
                                               Square::LightSquare     to,
                                               UtilMove::eSpecialMove  type){
          if (type == UtilMove::sm_invalide) {
                  from = 0;
                  to = 0;
          }
          return &#40;from << 10&#41; | &#40;to << 4&#41; | &#40;type-UtilMove&#58;&#58;sm_mini&#41;;
  &#125;
  static inline MiniMove                HashToMini&#40;HashType h&#41; &#123; return &#123; Hash2From&#40;h&#41;, Hash2To&#40;h&#41;, Hash2Type&#40;h&#41; &#125;; &#125;

  explicit Move&#40;const MiniMove & mini&#41;;
  &#91;...&#93;
&#125;;

smatovic
Posts: 909
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Draw scores in TT

Post by smatovic » Sat Apr 14, 2018 12:37 pm

Just curious but why would you want to prevent those scores in the TT?
They're valid for the position, aren't they?
Hmm, maybe i am just chasing rabbits here,
but I think they are actual not valid for transpositions.

Repetition and fifty move rule are history based,
a transposition may have another history,
so the drawscore may be invalid.

I had recently some issues with Kaufmann pos 12

6k1/p3q2p/1nr3pB/8/3Q1P2/6P1/PP5P/3R2K1 b - - bm Rd6; id "position 12";

But now i can't reproduce the behavior anymore,
and storing and loading TT draw scores turns out to be an speedup.

--
Srdja

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Draw scores in TT

Post by syzygy » Sat Apr 14, 2018 1:13 pm

smatovic wrote:How do you handle draw scores by repetition and fifty move rule in TT?

I use zero as draw score, and simply prevent to load such an value from TT,
i guess there are better techniques to prevent an mix up with an eval score of zero.
There is no way to do it right (without encoding the history of the position into the hashkey, which will heavily impact Elo), so "everybody" just accepts the problems.

Not using draw scores from the TT, or not using special "draw-by-repetition" scores from the TT, does not help much since the path-dependent draw anyway has to be backed up to parent nodes whose scores can then be non-zero but still be influenced by the path-dependent draw. So not using draw scores is a "fake" solution.

This is called the Graph History Interaction problem. If you google it, you find an article titled "a general solution to the graph history interaction problem", but the title is severely misleading.


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

Re: Draw scores in TT

Post by hgm » Sat Apr 14, 2018 5:26 pm

If you really want to make a carreer out of this, you could keep track of which nodes are 'contaminated' by repetition scores. Unfortunately this is not very easy to detect. If a node has a move that is a repetition, and the repetion turns out to be best, it is obviously contaminated. But if the draw score is not best, it could still be contaminated, for when the move had not lead to a repetition its score might actually have been best. But nodes can only be repetitions if their position occurred on the branch closer to the root. (For repeating game positions there is no path dependence, and these are hard draws.) And that means they are currently being searched, at several ply higher depth than in their repetition. Which means a previous depth higher than what you need now should be available as an IID result or from their hash hit. From that score you can see how the draw score compares to their intrinsic score, and how the intrinsic score compares to the score of the best move in the current node, and thus if the repeat has contaminated the node. If it did, you could pass the uncontaminated score to the parent node, so that it can decide whether substituting the actual score for the uncontaminated score has contaminated it as well.

smatovic
Posts: 909
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Draw scores in TT

Post by smatovic » Sat Apr 14, 2018 5:41 pm

If you really want to make a carreer out of this
nevermind, KISS.

--
Srdja

Post Reply