Dedicated mate finders

[Dann Corbit]

Hello Dann:

How does your mate solver perform with this mate in 6:
[d]5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - -
It takes Chest "quite a while."

5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - - acd 13; acs 2514; bm Na4 Nc4 Nd1 Nd7 Ne8 Nxd3 Nxh5 Q1g1 Qaa3 Qbb4 Qbd4 Qd8 a8=Q a8=R b8=Q b8=R; ce 32756; dm 6; id "Leonid.391101"; pm Na4 Nc4 Nd1 Nd7 Ne8 Nxd3 Nxh5 Q1g1 Qaa3 Qbb4 Qbd4 Qd8 a8=Q a8=R b8=Q b8=R; pv b8=Q Bce8 Q8d6 Ne6 Qxf8+ Bhg8 Nd7+ Nd4 Qcxd4+ Kh7 Qfg7#;

JetChess solves it in less than 20 mintes in my PC of 9 years old! However, JetChess does not show pv.

There is a tragedy. Too bad that Aristarch came to a halt. I seem to remember that he was working on a new version, and then simply abandoned it.

JetChess 1.0.0.0 (single core, 32-bit). Hash = 1 GB. Intel Pentium D930 (3 GHz) of year 2006:

Code: Select all

5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - -

  1  Qb1-c2   0
  2  Qb1*d3   0
  3  Qb1-c1   0
  4  Qb1-d1   0
  5  Qb1-e1   0
  6  Qb1-f1   0
  7  Qb1-g1   Mate
  8  Qb1-h1   0
  9  Qa2-b3   0
 10  Qa2-c4   0
 11  Qa2-d5   0
 12  Qa2-e6   0
 13  Qa2*f7   0
 14  Qa2-a3   Mate
 15  Qa2-a4   0
 16  Qa2-a5   0
 17  Qa2-a6   0
 18  Qc3-b4   0
 19  Qc3-a5   0
 20  Qc3-d4   0
 21  Qc3-e5   0
 22  Qc3-d2   0
 23  Qc3-e1   0
 24  Qc3-c4   0
 25  Qc3-c5   0
 26  Qc3*c6   0
 27  Qc3*d3   0
 28  Qc3-b3   0
 29  Qc3-a3   0
 30  Qc3-c2   0
 31  Qc3-c1   0
 32  Qb6-c7   0
 33  Qb6-d8   Mate
 34  Qb6-c5   0
 35  Qb6-d4   Mate
 36  Qb6-e3   0
 37  Qb6-f2   0
 38  Qb6-g1   0
 39  Qb6-a5   0
 40  Qb6*c6   0
 41  Qb6-a6   0
 42  Qb6-b5   0
 43  Qb6-b4   Mate
 44  Qb6-b3   0
 45  Nb2-a4   Mate
 46  Nb2-c4   Mate
 47  Nb2*d3   Mate
 48  Nb2-d1   Mate
 49  Ne2-d4   0
 50  Ne2-g3   0
 51  Ne2-c1   0
 52  Ne2-g1   0
 53  Nf6-d7   Mate
 54  Nf6-e8   Mate
 55  Nf6-g8   0
 56  Nf6*h7   0
 57  Nf6-d5   0
 58  Nf6*e4   0
 59  Nf6-g4   0
 60  Nf6*h5   Mate
 61   f4-f5   0
 62   a7-a8Q  Mate
 63   a7-a8N  0
 64   a7-a8R  Mate
 65   a7-a8B  0
 66   b7-b8Q  Mate
 67   b7-b8N  0
 68   b7-b8R  Mate
 69   b7-b8B  0

Multiple Solutions (checkmate in 6).

Time: 1119.326 s (0:18:39.326)

Perft results:

Code: Select all

5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - -

perft(1) =             69
perft(2) =          2,722
perft(3) =        187,614
perft(4) =      7,223,934
perft(5) =    497,393,135
perft(6) = 18,912,611,910

Unique positions (en passant flag checked):

Code: Select all

5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - -

positions(1) =         69
positions(2) =      2,721
positions(3) =    103,763
positions(4) =  2,253,365
positions(5) = 58,386,326

It is the first time I see JetChess reporting perft(2) =/= positions(2). I hope it is not a bug.

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hi again:

There is a tragedy. Too bad that Aristarch came to a halt. I seem to remember that he was working on a new version, and then simply abandoned it.

I think that Aristarch and JetChess do not have the same authors:

- Aristarch chess engine by Stefan Zipproth.
- JetChess perft counter by Thomas Zipproth.

Although they share the http://www.zipproth.de site. Are they brothers or relatives? Who knows.

Thomas is member of Talkchess but he writes here very, very few. I have seen him contributing to SF testing framework in the past.

Regards from Spain.

Ajedrecista.

[Dann Corbit]

Hi again:

There is a tragedy. Too bad that Aristarch came to a halt. I seem to remember that he was working on a new version, and then simply abandoned it.

I think that Aristarch and JetChess do not have the same authors:

- Aristarch chess engine by Stefan Zipproth.
- JetChess perft counter by Thomas Zipproth.

Although they share the http://www.zipproth.de site. Are they brothers or relatives? Who knows.

Thomas is member of Talkchess but he writes here very, very few. I have seen him contributing to SF testing framework in the past.

Regards from Spain.

Ajedrecista.

Yes, I think you are right. I simply miss-remembered.

[bob]

Mate-in-4 sample extrema

Easy:
[d]7k/5K2/6qp/7P/8/8/8/8 w - - 8 13[/d]
[MateIn4/7/0.000/195] 135. hxg6 h5 136. g7+ Kh7 137. g8=Q+ Kh6 138. Qg6#

Hard:
[d]1n1k3r/r2bp3/2p3qB/7p/1p6/1R4P1/4q1BK/7N b - - 3 57[/d]
[MateIn4/7/1.071/1,297,242] 57... Qge4 58. Nf2 Qxf2 59. Rf3 Qexf3 60. Be3 Q2xg2#

The hard one is not so hard IMHO. takes Crafty 35K nodes to find:

6 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2# (s=2)
6-> 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
7 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
7-> 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
8 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
8-> 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
9 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
9-> 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
10 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
10-> 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
11 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
11-> 0.01 -Mat04 1. ... Qgc2 2. Bd2 Qexd2 3. Nf2 Qxf2
4. Rxb4 Qxg2#
time=0.01(100%) nodes=35403(35.4K) fh1=84% nps=3.5M
checks=591 qchecks=1.4K fp=19.6K mcp=201 reversible=0
LMReductions: 1/506 2/675 3/579 4/430 5/98
null-move (R): 3/1.3K 4/145
splits=15(1) aborts=0 joins=40 data=3%

The easy one only takes 2K nodes and a 4 ply search.

[bob]

How does your mate solver perform with this mate in 6:
[d]5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - -
It takes Chest "quite a while."

5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - - acd 13; acs 2514; bm Na4 Nc4 Nd1 Nd7 Ne8 Nxd3 Nxh5 Q1g1 Qaa3 Qbb4 Qbd4 Qd8 a8=Q a8=R b8=Q b8=R; ce 32756; dm 6; id "Leonid.391101"; pm Na4 Nc4 Nd1 Nd7 Ne8 Nxd3 Nxh5 Q1g1 Qaa3 Qbb4 Qbd4 Qd8 a8=Q a8=R b8=Q b8=R; pv b8=Q Bce8 Q8d6 Ne6 Qxf8+ Bhg8 Nd7+ Nd4 Qcxd4+ Kh7 Qfg7#;

[d]5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - - 0 1[/d]
One hour thirteen minutes seven seconds:

Code: Select all

[MateIn6/11/1:13:07.060/4,711,533,792] 1. Nxd3 Nf5 2. Ng4+ Kg8 3. Q1b2 Bxa2 4. Qh8+ Kf7 5. Qbf6+ Ke8 6. Qbd8#

This is a 1 second task. Crafty bails out after 15 plies total, 18M nodes total:

This on my office iMac with 4 threads.

[bob]

History table variants

For the dedicated mate finder, I've tried three different history table counter arrays for move ordering:

[FromMan][[FromSquare][ToSquare]
[FromMan][ToSquare]
[FromSquare][ToSquare]

It looks like [FromMan][[FromSquare][ToSquare] gives the least total node counts but [FromMan][ToSquare] gives the fastest times. Part of this is due to the time needed to reset the history table prior to each search, and part due to the extra time needed for three subscript access vs two subscript access.

A history counter is incremented only if the corresponding move beats alpha (including moves which cause a beta cutoff).

When a history counter hits 2^31, every counter in the table gets right shifted one bit to avoid overflow.

Code: Select all

class HistFmTsTable
{
public:  
  void Reset(void);
  
  ui FetchCounter(const Move move) const {return counters[move.GetFrMan()][move.GetToSq()];}
  void IncCounter(const Move move);
  
private:
  void DownShift(void);
  
  ui counters[ManRCLen][SqLen];
};

void HistFmTsTable::Reset(void)
{
  ForEachManRC(frman)
    ForEachSq(tosq)
      counters[frman][tosq] = 0;
}

void HistFmTsTable::DownShift(void)
{
  ForEachManRC(frman)
    ForEachSq(tosq)
      counters[frman][tosq] /= 2;
}

void HistFmTsTable::IncCounter(const Move move)
{
  if (++counters[move.GetFrMan()][move.GetToSq()] == 0x80000000)
    DownShift();
}

There's another variant I used a long time back and which I have been playing with again.

make a history counter 16 bits (or whatever you want.) Unsigned. For a 16 bit counter, 32768 is treated as zero, anything above is positive, anything below is negative.

To update, on a fail high, you add something to the counter. The only constraint is that what you add must be N * (65535 - current) where N is a number such that 0 <= N < 1.0. This counter can never overflow (sometimes called a saturating counter). To reduce a counter when a move addressing that counter fails low at a CUT node, you do the opposite, subtract a fraction of the distance from the current value to 0. Again, this stops the counter from wrapping in that direction either. I've been playing around with this again, and it eliminates the need for aging the counters when they get too large or small, and I am not even clearing them between searches...

[abulmo]

Also, the four EPD result files for the above:
https://dl.dropboxusercontent.com/u/316 ... in1.epd.gz
https://dl.dropboxusercontent.com/u/316 ... in2.epd.gz
https://dl.dropboxusercontent.com/u/316 ... in3.epd.gz
https://dl.dropboxusercontent.com/u/316 ... in4.epd.gz

The bm field is missing, it makes the files less usefull to me
Some positions are also drawn according to the fifty move rules. For example in the matein2.epd file:
2K5/8/k7/2R5/8/8/8/8 w - - 100 240 ad 3; nc 35; pt 0.000; pv Kc7 Ka7 Ra5#; ss MateIn2;
I know the fifty move rule draws need to be claimed, but I have little doubt it will be claimed by the mated side before the irremediable loss occurs.

[sje]

Some limitations of Symbolic's current dedicated mate finder:

1) It's single threaded.
2) It returns as soon as a mating PV is found; it doesn't look for possible further mates.
3) It doesn't promise that the returned mating PV is the shortest one available.
4) It doesn't use an iteration approach; instead it does just one search with a fixed depth limit.
5) Its move ordering is very simple.
6) Only stalemate draws are recognized.
7) It doesn't use transposition table assistance.
8) It doesn't use tablebase table assistance.

[Dann Corbit]

Some limitations of Symbolic's current dedicated mate finder:

1) It's single threaded.
2) It returns as soon as a mating PV is found; it doesn't look for possible further mates.
3) It doesn't promise that the returned mating PV is the shortest one available.
4) It doesn't use an iteration approach; instead it does just one search with a fixed depth limit.
5) Its move ordering is very simple.
6) Only stalemate draws are recognized.
7) It doesn't use transposition table assistance.
8) It doesn't use tablebase table assistance.

Do you use alpha-beta or proof search?
It seems to me that proof search would be a natural for checkmate recognition.

[sje]

Do you use alpha-beta or proof search?
It seems to me that proof search would be a natural for checkmate recognition.

Simple &#593;/&#946;. Here's the core routine:

Code: Select all

SV MateFinder::MateNode(const Window window, MoveList& PV)
{
  Window mywindow(window);

  if (pickerlist.GetCount() == ply)
  {
    pickerlist.Append(new MatePickerNode());
    pickernodeptr = pickerlist.GetTail();
  }
  else
    pickernodeptr = pickernodeptr->GetNext();

  PV.Reset();

  if (draft == 0)
    mywindow.Update(position.IsCheckmated() ? SvCheckmated : SvEven);
  else
  {
    Move move;
    MatePickMode mpmode;

    if (draft == 1)
      mpmode = MatePickModeFinal;
    else
      mpmode = (ply & 1) ? MatePickModeDefend : MatePickModeAttack;

    pickernodeptr->Preset(mpmode, position, isftd, histtableptr);
    while &#40;mywindow.IsOpen&#40;) && &#40;mywindow.GetAlfa&#40;) < SvMateIn1&#41; && pickernodeptr->MovesRemain&#40;))
    &#123;
      const Move move = pickernodeptr->Pick&#40;);
      Window subwindow&#40;mywindow&#41;;
      MoveList subpv;
      SV subsv;

      ExecuteMove&#40;move&#41;;
      subwindow.DownShift&#40;);
      subsv = CalcSvUpShift&#40;MateNode&#40;subwindow, subpv&#41;);
      if &#40;subsv > mywindow.GetAlfa&#40;))
      &#123;
        mywindow.PutAlfa&#40;subsv&#41;;
        PV.BuildFromMoveAndList&#40;move, subpv&#41;;
      &#125;;
      RetractMove&#40;);
    &#125;;

    if (&#40;pickernodeptr->GetGenCount&#40;) == 0&#41; && position.IsMated&#40;))
      mywindow.Update&#40;position.IsChecked&#40;) ? SvCheckmated &#58; SvEven&#41;;

    if &#40;PV.GetCount&#40;) > 0&#41;
      histtableptr->IncCounter&#40;*PV.GetHead&#40;));
  &#125;;

  isftd = false;
  pickernodeptr = pickernodeptr->GetPrev&#40;);
  return mywindow.GetAlfa&#40;);
&#125;