Correct way to store and extract 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.
Post Reply
ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Correct way to store and extract mate scores

Post by ianm » Wed Jul 08, 2020 4:45 am

Hi All

I've confused myself with this (not surprising). So I'm wondering when extracting the mate score from the hash table does the score need to be adjusted by (+/- ply) or reset to the fixed mate value (+/- ply)?

Here's what I'm doing now:

Code: Select all

   if (ht[hi].key==hk && ht[hi].depth>=depth && (ht[hi].flag&FL_SIDE)==side)
   {
      int16_t s = ht[hi].score;
      if (s>MATE_VALUE) s -= ply; else if (s<-MATE_VALUE) s += ply;
      if (ht[hi].flag&HASH_EXACT) {stats.nhash++; return s;}
      else if ((ht[hi].flag&HASH_BETA) && s>=beta) {stats.nhash++; return beta;}
      else if ((ht[hi].flag&HASH_ALPHA) && s<=alpha) {stats.nhash++; return alpha;}
   }
but should it be:

Code: Select all

   if (ht[hi].key==hk && ht[hi].depth>=depth && (ht[hi].flag&FL_SIDE)==side)
   {
      int16_t s = ht[hi].score;
      if (s>MATE_VALUE) s = MAX_VALUE-ply; else if (s<-MATE_VALUE) s = -MAX_VALUE+ply;
      if (ht[hi].flag&HASH_EXACT) {stats.nhash++; return s;}
      else if ((ht[hi].flag&HASH_BETA) && s>=beta) {stats.nhash++; return beta;}
      else if ((ht[hi].flag&HASH_ALPHA) && s<=alpha) {stats.nhash++; return alpha;}
   }
In other words should the mate value from the hash table be adjusted to the current ply irrespective of the ply it was on when it was stored in the HT?

Many thanks, Ian

Sven
Posts: 3868
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Correct way to store and extract mate scores

Post by Sven » Wed Jul 08, 2020 8:43 am

The typical pattern applied in many engines is as follows:

- In the tree, mate scores are relative to the root node. When detecting a mate ("mated in 0") you return -(MATE_VALUE - ply). When seeing a mate score returned from a subtree you either see a negative score ("mated in N" with even N) or a positive score ("mate in N" with odd N) but both contain the distance from the root node to the "mated in 0" node where the mate was originally detected.

- In the hash table, mate scores are relative to the position they belong to.

- Therefore you retrieve mate scores from TT by inserting the distance between root and current node (which makes positive mate scores smaller and negative ones greater):

Code: Select all

int16_t scoreFromTT(int16_t s, int16_t ply) { return (s > MATE_VALUE) ? s - ply : (s < -MATE_VALUE) ? s + ply : s; }
//...
int16_t treeScore = scoreFromTT(ht[hi].score, ply);
and you store mate scores in the TT by removing that distance (which makes positive mate scores greater and negative ones smaller):

Code: Select all

int16_t scoreToTT(int16_t s, int16_t ply) { return (s > MATE_VALUE) ? s + ply : (s < -MATE_VALUE) ? s - ply : s; }
// ...
ht[hi].score = scoreToTT(treeScore, ply);
So your current code is correct if you also do the reverse when storing ...
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

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

Re: Correct way to store and extract mate scores

Post by hgm » Wed Jul 08, 2020 1:49 pm

For clarification: the same position in the TT can be probed at different distances from the root; even if there are no transpositions it will be probed such when it survives to the search for the next game move. So you cannot store any distance relative to the root in the TT, and must store absolute distance-to-mate there.

But if you retrieve a mate-in-7-ply from the TT at ply level 3 of your tree, you want it to show up as mated-in-10-ply in the root. If you don't adapt scores when propagating them to the root, you must make it such that the probe already delivers that score. (Except for the sign, which you do flip while propagating scores to the root.)

ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Re: Correct way to store and extract mate scores

Post by ianm » Wed Jul 08, 2020 11:50 pm

Excellent, thanks so much. I wasn't storing the value correctly. Interesting how it was working quite well though. Chess engines seem quite resilient until they play bad moves out of the blue!

Cheers, Ian

elcabesa
Posts: 830
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Correct way to store and extract mate scores

Post by elcabesa » Fri Jul 10, 2020 10:26 am

When saving to TT you have to store: "from this node it's a mate in 3"

When reading from TT you have to translate it to: "from root node it's a mate in 5"

ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Re: Correct way to store and extract mate scores

Post by ianm » Sat Jul 11, 2020 3:41 am

OK, I've modified the code to correctly store in the hash table and ran 100 games against TSCP. Plankton got a score of 83% which is the highest yet. But in game 6 where Plankton was clearly winning the game ended in a draw due to 3-fold repetition. Here is the game:



I set up the position from the command prompt and got a different outcome. The mate is discovered (great) and there is a bit of shuffling around but at least the outcome is mate:

Code: Select all

Ian's Low Memory Chess Program (plankton)
Version 8.7.6, 10/7/2020
Copyright 2020 Ian Mitchell
With late move reductions!
With history heuristic!
With evaluation cache!
With null moves!
With hash table!
With tapered eval!
With razoring!
With reverse pruning!
With futility pruning!

"help" displays a list of commands.

plankton> fen 8/8/4b3/5p2/5k2/7p/4K3/8 b - - 3 61
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . p 3
2 . . . . K . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Black to move.
plankton> st 60
Search time: 60000ms
plankton> go
ply  mv   time     nodes score pv
  1   0      0        15   761   1 h3h2
  2   0      0        53  1422   3 h3h2 e2d3 (h2h1q)
  3   0     16       116  1422   3 h3h2 e2d3 h2h1q
  4   0     16       187  1411   5 h3h2 e2d3 h2h1q d3d4
  5   0     16       324  1416   6 h3h2 e2d3 h2h1q d3d4 e6d5
  6   0     16       968  1438   8 h3h2 e2d3 h2h1q d3d4 h1h8 d4d3 (f4e5)
  7   0     16      3624  1446   9 h3h2 e2d3 h2h1q d3d4 h1d1 d4c3 f4e5 (c3b2)
  8   0     16      9621  1461  11 h3h2 e2d3 h2h1q d3d2 f4e5 d2c2 h1e4 c2c3 (f5f4)
  9   0     31     31375  1471  12 h3h2 e2d3 h2h1q d3d4 h1d1 d4c5 f4e5 c5b5 d1d5 (b5b4 f5f4)
 10   0     47     52354  1474  13 h3h2 e2d3 h2h1q d3d4 h1d1 d4c5 f4e5 c5b4 f5f4 b4c3 (f4f3)
 11   0    156    246491  1479  14 h3h2 e2d3 h2h1q d3c3 f4e5 c3d3 f5f4 d3d2 f4f3 d2e3 e6d5
 12   0    391    710645  1488  18 h3h2 e2d3 h2h1q d3d2 f4e5 d2e2 f5f4 e2f2
 13   0    656   1235803  2169  19 h3h2 e2d3 h2h1q d3d2 f4e5 d2e2 f5f4 e2f2 f4f3 f2e3 h1g1 e3d2 f3f2 (d2c2 f2f1q)
 14   0   1109   2058831  2169  19 h3h2 e2d3 h2h1q d3d2 f4e5 d2e2 f5f4 e2f2 f4f3 f2e3 h1g1 e3d2 f3f2 d2c2 (f2f1q)
 15   0   1281   2292098  2169  20 h3h2 e2d3 h2h1q d3d2 f4e5 d2e2 f5f4 e2f2 f4f3 f2e3 h1g1 e3d2 f3f2 d2c2 f2f1q (c2b2)
 16   0   3531   6322904  2169  23 h3h2 e2d3 h2h1q d3d2 f4e5 d2e2 f5f4 e2d3 f4f3 d3c3 h1g2 c3b4 g2g4 b4c3 f3f2 c3d2 (f2f1q)
 17   0  12594  22157818 19985  27 h3h2 e2d3 h2h1q d3d2 f4f3 d2c3 h1e1 c3c2 f3e4 c2b2 e1d2 b2b1 e4f4
nreps: 42106
nhash: 3509812
hashorder: 1157361
razor: 170721
prune: 3323597
hist: 57849
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . . . . K . . p 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: h3h2
plankton> e2d3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . p 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   2      0        18  1422   1 h2h1q
  2   2      0        43  1411   2 h2h1q d3d4
  3   2      0       116  1416   4 h2h1q d3d4 e6d5
  4   2      0       809  1481   6 h2h1q d3d4 h1b1
  5   2      0      2419 19981   7 h2h1q d3d4 h1d5 d4c3 d5b3
nreps: 3
nhash: 157
hashorder: 212
razor: 34
prune: 199
hist: 12
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . . 2
1 . . . . . . . q 1
  A B C D E F G H

Computer's move: h2h1q
plankton> d3d2
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . . . K . . . . 2
1 . . . . . . . q 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   4      0        36  1442   1 f4e5
  2   4      0       204  1442   3 h1d5 d2c2 (f4e5)
  3   4      0      2242  1461   5 f4e5 d2d3 f5f4
  4   4      0      2654  1461   5 f4e5 d2c2 f5f4 c2c3
  5   4      0      9753 19975   9 h1d5 d2e1 d5e4 e1d2 e4e3 (d2c2 e3b3)
nreps: 16
nhash: 569
hashorder: 683
razor: 79
prune: 345
hist: 20
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . q . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . . . K . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: h1d5, check!
plankton> d2c3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . q . p . . 5
4 . . . . . k . . 4
3 . . K . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   6      0        33  1438   2 f4e5
  2   6     16       263 19985   3 d5b3
nreps: 0
nhash: 4
hashorder: 15
razor: 3
prune: 9
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . q K . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: d5b3, check!
plankton> c3d2
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . q . . . . . . 3
2 . . . K . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   8      0        33  1442   1 f4e5
  2   8      0       119 19987   3 b3b2
nreps: 1
nhash: 10
hashorder: 7
razor: 0
prune: 4
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . q . K . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: b3b2, check!
plankton> d2d3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . q . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  10      0        37  1438   1 f4e5
  2  10      0       287  1442   3 b2a3 d3c2 (f4e5)
  3  10     16      1269  2177   5 b2b1 d3c3 b1c1
  4  10     16      1478 19979   6 b2b1 d3c3 b1e1 c3d3 (e1d1)
nreps: 11
nhash: 145
hashorder: 141
razor: 22
prune: 168
hist: 10
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . . 2
1 . q . . . . . . 1
  A B C D E F G H

Computer's move: b2b1, check!
plankton> d3d4
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . K . k . . 4
3 . . . . . . . . 3
2 . . . . . . . . 2
1 . q . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  12      0        32  1411   2 b1b6
  2  12      0        63 19983   1 b1b6
nreps: 0
nhash: 27
hashorder: 1
razor: 0
prune: 3
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . q . . b . . . 6
5 . . . . . p . . 5
4 . . . K . k . . 4
3 . . . . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: b1b6, check!
plankton> d4d3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . q . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  14      0        33  1438   1 f4e5
  2  14      0       352 19979   3 b6e3
nreps: 2
nhash: 11
hashorder: 13
razor: 1
prune: 6
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K q . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: b6e3, check!
plankton> d3c2
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . q . . . 3
2 . . K . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  16      0        34  1442   1 f4e5
  2  16      0       197  1446   3 f4e5 c2b2
  3  16      0      2094  1470   5 e3e2 c2b1 e2d2 (b1a1)
  4  16     15      3644  1486   7 e3e2 c2b1 e2d2 b1a1 (f4e5)
  5  16     15      6305 19979   9 e3e2 c2c3 e2c4
nreps: 13
nhash: 566
hashorder: 418
razor: 27
prune: 192
hist: 14
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . . K . q . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: e3e2, check!
plankton> c2c3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . K . . . . . 3
2 . . . . q . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  18      0        36  1438   2 f4e5
  2  18      0        72 19981   1 e2c4
nreps: 0
nhash: 31
hashorder: 1
razor: 0
prune: 4
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . q . . k . . 4
3 . . K . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: e2c4, check!
plankton> c3d2
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . q . . k . . 4
3 . . . . . . . . 3
2 . . . K . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  20      0        31  1442   1 f4e5
  2  20      0       167 19983   3 c4a2
nreps: 1
nhash: 5
hashorder: 12
razor: 3
prune: 6
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 q . . K . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: c4a2, check!
plankton> d2d3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 q . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  22      0        31  1438   1 f4e5
  2  22      0       149  1442   3 a2a3
  3  22      0      1388  1461   5 f4e5 d3c3 f5f4
  4  22      0      1832  1466   6 f4e5 d3e3 f5f4 e3f3 (e6d5)
  5  22      0      2854 19985   8 f4e5 d3e3 f5f4 e3d3 a2b3
nreps: 13
nhash: 243
hashorder: 244
razor: 38
prune: 168
hist: 12
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . k p . . 5
4 . . . . . . . . 4
3 . . . K . . . . 3
2 q . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: f4e5
plankton> d3c3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . k p . . 5
4 . . . . . . . . 4
3 . . K . . . . . 3
2 q . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  24     15        32  1461   2 f5f4
  2  24     15       115  1511   3 a2e2
  3  24     15       422 19995   3 e6c4 c3b4
nreps: 1
nhash: 153
hashorder: 32
razor: 0
prune: 82
hist: 9
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . . . . . 6
5 . . . . k p . . 5
4 . . b . . . . . 4
3 . . K . . . . . 3
2 q . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: e6c4
plankton> c3b4
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . . . . . 6
5 . . . . k p . . 5
4 . K b . . . . . 4
3 . . . . . . . . 3
2 q . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  26      0        35  1471   2 f5f4
  2  26      0       107 19997   2 a2b3
nreps: 0
nhash: 2
hashorder: 20
razor: 5
prune: 0
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . . . . . 6
5 . . . . k p . . 5
4 . K b . . . . . 4
3 . q . . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: a2b3, check!
plankton> b4a5
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . . . . . 6
5 K . . . k p . . 5
4 . . b . . . . . 4
3 . q . . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1  28      0        36  1479   2 f5f4
  2  28      0        80 19999   2 b3b5
nreps: 0
nhash: 14
hashorder: 5
razor: 1
prune: 2
hist: 0
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . . . . . 6
5 K q . . k p . . 5
4 . . b . . . . . 4
3 . . . . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: b3b5, check!
0-1 {Black mates}
plankton>
It seems like depending on what's in the HT it is struggling to make the fast mate. What can I do to avoid that?

Many thanks, Ian

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

Re: Correct way to store and extract mate scores

Post by hgm » Sat Jul 11, 2020 6:25 am

If I believe the opponent's scores, your mating distances are wrong. At least, I assume that your mate score is 200. When TSCP says -M4, you get 199.87 on the move afterter that. Which would mean mate (or King capture) in 13 ply = 6 moves, while it should have been in 4. This is suspect.

What is also suspect is that you reach a very low depth for these moves. You should iterate at least to the mating distance. It seems you stop iterating just when you reach any mate score, without the depth being large enough to guarantee it is the fastest mate.

ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Re: Correct way to store and extract mate scores

Post by ianm » Sat Jul 11, 2020 9:35 am

Yes of course! I've been exiting the iterative deepening search when a mate score is detected because that was in place before I added the HT. I didn't think of it because the HT can be enabled or disabled. Here is the result now:

Code: Select all

Ian's Low Memory Chess Program (plankton)
Version 8.7.7, 11/7/2020
Copyright 2020 Ian Mitchell
With late move reductions!
With history heuristic!
With evaluation cache!
With null moves!
With hash table!
With tapered eval!
With razoring!
With reverse pruning!
With futility pruning!

"help" displays a list of commands.

plankton> fen 8/8/4b3/5p2/5k2/7p/4K3/8 b - - 3 61
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . p 3
2 . . . . K . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Black to move.
plankton> st 20
Search time: 20000ms
plankton> go
ply  mv   time     nodes score pv
  1   0      0        15   761   1 h3h2
  2   0      0        53  1422   3 h3h2 e2d3 (h2h1q)
  3   0      0       116  1422   3 h3h2 e2d3 h2h1q
  4   0      0       188  1411   5 h3h2 e2d3 h2h1q d3d4
  5   0      0       327  1416   6 h3h2 e2d3 h2h1q d3d4 e6d5
  6   0      0       972  1438   8 h3h2 e2d3 h2h1q d3d4 h1h8 d4d3 (f4e5)
  7   0     16      3630  1446   9 h3h2 e2d3 h2h1q d3d4 h1d1 d4c3 f4e5 (c3b2)
  8   0     16      9559  1461  11 h3h2 e2d3 h2h1q d3d2 f4e5 d2c2 h1e4 c2c3 (f5f4)
  9   0     32     32095  1471  12 h3h2 e2d3 h2h1q d3d4 h1d1 d4c5 f4e5 c5b5 d1d5 (b5b4 f5f4)
 10   0     47     53045  1484  14 h3h2 e2d3 h2h1q d3d4 h1d1 d4c5 f4e5 c5b4 f5f4 b4c3 (f4f3)
 11   0    141    220660  1489  14 h3h2 e2d3 h2h1q d3c3 f4e5 c3d3 f5f4 d3d2 f4f3 d2e3 e6d5
 12   0    360    627872  1507  18 h3h2 e2d3 h2h1q d3c3 h1e1 c3c2 f4e5 c2d3 f5f4 d3c2 f4f3 c2d3 (f3f2)
 13   0    735   1328629  2169  20 h3h2 e2d3 h2h1q d3c3 h1e1 c3c2 f4e5 c2d3 f5f4 d3c2 f4f3 c2d3 f3f2 (d3c2 f2f1q)
 14   0   1141   2026125  2169  20 h3h2 e2d3 h2h1q d3c3 h1e1 c3c2 f4e5 c2d3 f5f4 d3c2 f4f3 c2d3 f3f2 d3c2 (f2f1q)
 15   0   2422   4127393 19983  22 h3h2 e2d3 h2h1q d3d2 h1e4 d2c3 e4e1
 16   0   7188  12753460 19983  24 h3h2 e2d3 h2h1q d3d2 h1b1 d2c3 b1e1
nreps: 78722
nhash: 6330725
hashorder: 2055357
razor: 295241
prune: 6583418
hist: 60000
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . . . . K . . p 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: h3h2
plankton> e2d3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . p 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   2      0        18  1422   1 h2h1q
  2   2      0        44  1411   2 h2h1q d3d4
  3   2      0       119  1416   4 h2h1q d3d4 e6d5
  4   2      0       663  1438   6 h2h1q d3d2 f4e5 d2c3
  5   2      0      2449  1461   7 h2h1q d3d2 f4e5 d2c3 f5f4
  6   2      0      4086  1461   7 h2h1q d3d2 f4e5 d2c2 h1e4 c2c3 (f5f4)
  7   2     16     13086  1827   9 h2h1q d3d2 e6b3 d2c3 h1f3
  8   2     16     23482  1827  13 h2h1q d3d2 e6b3 d2c3 h1f3
  9   2     16     25571  1827  13 h2h1q d3d2 e6b3 d2c3 h1f3
 10   2     31     27824  1827  14 h2h1q d3d2 e6b3 d2c3 h1f3
 11   2     31     41830  2170  14 h2h1q d3d2 h1e4 d2c3 e4e5 c3c2 e5e2
 12   2     78    101668 19973  18 h2h1q d3d2 h1b1 d2c3 b1c1 c3b4 c1b1
 13   2    188    258902 19983  19 h2h1q d3d2 h1a1 d2c2 a1e1 c2d3 f4f3
 14   2    344    493045 19987  20 h2h1q d3d2 h1a1 d2e2 a1c1 e2f2 c1e3 f2f1 e6c4 f1g2 e3g3 g2h1 c4d5
 15   2   1485   2531586 19989  24 h2h1q d3d2 h1a1 d2e2 a1c1 e2f2 e6d5 f2e2 d5c4 e2f2 c1f1
 16   2   8141  14235412 19989  24 h2h1q d3d2 h1a1 d2e2 a1c1 e2f2 e6d5 f2e2 d5c4 e2f2 c1f1
nreps: 97856
nhash: 7058963
hashorder: 2001621
razor: 316728
prune: 10697815
hist: 60000
curo: 0

hash table usage: 0%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . . 2
1 . . . . . . . q 1
  A B C D E F G H

Computer's move: h2h1q
plankton> d3d2
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . . . K . . . . 2
1 . . . . . . . q 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   4      0        36  1442   1 f4e5
  2   4     15       215  1438   3 f4e5 d2c3
  3   4     15      1827  1461   5 f4e5 d2c3 f5f4
  4   4     15      2733  1461   5 f4e5 d2c2 f5f4 c2c3
  5   4     15      4498  1484   7 f4e5 d2c2 f5f4 c2c3 f4f3
  6   4     15      8185  1827   8 e6b3 d2c3 h1f3
  7   4     15      9111  1827  10 e6b3 d2c3 h1f3
  8   4     15     10330  1827  12 e6b3 d2c3 h1f3
  9   4     15     14773  1827  14 e6b3 d2c3 h1f3
 10   4     47     49078 19985  16 h1b1 d2e2 b1b2 e2d1 e6b3 d1e1 b2c1 e1f2 c1e3
 11   4     62     72426 19989  16 h1b1 d2e2 b1c1 e2f2 c1e3 f2f1 e6c4 f1g2 e3g3 g2h1 c4d5
 12   4     93    114663 19989  16 h1b1 d2e2 b1c1 e2f2 c1e3 f2f1 e6c4 f1g2 e3g3 g2h1 c4d5
 13   4    187    229317 19989  18 h1b1 d2c3 b1c1
 14   4    359    462343 19991  17 h1c6 d2e2 c6c1 e2f2 e6d5 f2e2 d5c4
 15   4    906   1289007 19993  22 h1c6 d2e2 c6c2 e2f1 f4f3 f1e1 c2c1
 16   4   4047   6021092 19993  24 h1c6 d2e2 c6c2 e2f1 f4f3 f1e1 c2c1
 17   4  16859  24232235 19993  26 h1c6 d2e2 c6c2 e2f1 f4f3 f1e1 c2c1
nreps: 126776
nhash: 7091976
hashorder: 1796921
razor: 269342
prune: 13296087
hist: 60000
curo: 0

hash table usage: 1%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . q . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . . . . . . 3
2 . . . K . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: h1c6
plankton> d2d3
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . q . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   6      0        35  1438   1 f4e5
  2   6      0        91 19987   2 c6d6
  3   6      0       546 19987   4 c6d6
  4   6      0       581 19987   1 c6d6
  5   6      0       616 19987   1 c6d6
  6   6      0      2496 19989   6 c6b5 d3c3 b5b3 c3d2 b3b2
  7   6     16      3608 19989   8 c6b5 d3c3 b5b3 c3d2 b3b2
  8   6     16      5857 19989  10 c6b5 d3c3 b5b3 c3d2 b3b2
  9   6     16     10698 19989  12 c6b5 d3c3 b5b3 c3d2 b3b2
 10   6     31     22720 19995  15 c6c1 d3e2 e6c4 e2f2 c1f1
 11   6     47     33063 19995  13 c6c1 d3e2 e6c4 e2f2 c1f1
 12   6     63     59288 19995  16 c6c1 d3e2 e6c4 e2f2 c1f1
 13   6    109    118943 19995  14 c6c1 d3e2 e6c4 e2f2 c1f1
 14   6    188    226152 19995  16 c6c1 d3e2 e6c4 e2f2 c1f1
 15   6    344    452612 19995  17 c6c1 d3e2 e6c4 e2f2 c1f1
 16   6    953   1249294 19995  20 c6c1 d3e2 e6c4 e2f2 c1f1
 17   6   8391  12107207 19995  26 c6c1 d3e2 e6c4 e2f2 c1f1
nreps: 148754
nhash: 8220125
hashorder: 1609675
razor: 261340
prune: 14674128
hist: 60000
curo: 0

hash table usage: 1%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . . . k . . 4
3 . . . K . . . . 3
2 . . . . . . . . 2
1 . . q . . . . . 1
  A B C D E F G H

Computer's move: c6c1
plankton> d3d4
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . . K . k . . 4
3 . . . . . . . . 3
2 . . . . . . . . 2
1 . . q . . . . . 1
  A B C D E F G H

ply  mv   time     nodes score pv
  1   8      0        32  1411   2 c1b1
  2   8      0        74 19999   2 c1c4
  3   8      0       209 19999   3 c1c4
  4   8      0       240 19999   2 c1c4
  5   8      0       271 19999   2 c1c4
  6   8      0       406 19999   3 c1c4
  7   8      0       543 19999   3 c1c4
  8   8      0       680 19999   3 c1c4
  9   8      0       817 19999   3 c1c4
 10   8     16      2035 19999   8 c1c4
 11   8     16      3157 19999   6 c1c4
 12   8     16      4317 19999   6 c1c4
 13   8     16      6282 19999   9 c1c4
 14   8     16     13714 19999  10 c1c4
 15   8     32     27011 19999  12 c1c4
 16   8     47     53678 19999  15 c1c4
 17   8    141    187695 19999  17 c1c4
 18   8   2860   3933395 19999  24 c1c4
 19   8  15063  20773721 19999  26 c1c4
nreps: 122111
nhash: 8195027
hashorder: 1295315
razor: 288404
prune: 16433200
hist: 60000
curo: 0

hash table usage: 2%
  A B C D E F G H
8 . . . . . . . . 8
7 . . . . . . . . 7
6 . . . . b . . . 6
5 . . . . . p . . 5
4 . . q K . k . . 4
3 . . . . . . . . 3
2 . . . . . . . . 2
1 . . . . . . . . 1
  A B C D E F G H

Computer's move: c1c4, check!
0-1 {Black mates}
plankton>
is there a way now to exit the iterative deepening loop early when mate is detected?

Thanks again HG!

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

Re: Correct way to store and extract mate scores

Post by hgm » Sat Jul 11, 2020 11:01 am

Well, you could stop iterating when you reach the depth that corresponds to the mate score. If you do a lot of pruning, that still doesn't guarantee you have seen the fastest mate, though. A strongly reduced branch could lead to a quicker mate that it hasn't seen yet. So you can do a few ply extra to be sure.

It wouldn't give you any extra Elo, of course.

If you do mate-distance pruning, the tree stays so small when you approach the mate that the search deepends to the maximum depth in a flash anyway. I guess with the method you use (correcting the mate score with the ply depth in the leaves) you would have to explicitly implement that (e.g. fail low without searching any moves if even capture of a King cannot rise the score above alpha).

ianm
Posts: 11
Joined: Wed Apr 29, 2020 11:58 am
Location: Tasmania, Australia
Full name: Ian Mitchell

Re: Correct way to store and extract mate scores

Post by ianm » Sun Jul 12, 2020 5:56 am

I think I'll just have a check for mate-in-one. Not fussed about taking time to get to the fastest mate but when a mate in one is found better to stop now than waste time at that point.

Code: Select all

if (abs(score) >= (MAX_VALUE-1)) break;

Post Reply