Dedicated mate finders

[sje]

Dedicated mate finders

As part of the Symbolic re-write, I have added a dedicated mate finder routine. It is single threaded and quite simple, but it's also useful for testing and benchmarking; also, for verification of mate-in-N positions.

For testing the mate finder, I have a set for four FEN files, each with 100,000 records with each record being a position with at least one mate-in-N solution and with no forced mates of lesser length.

The four files:
https://dl.dropboxusercontent.com/u/316 ... in1.fen.gz
https://dl.dropboxusercontent.com/u/316 ... in2.fen.gz
https://dl.dropboxusercontent.com/u/316 ... in3.fen.gz
https://dl.dropboxusercontent.com/u/316 ... in4.fen.gz

On an old and slow notebook with an Intel Atom CPU, the mate finder solves the matein3 file in about 20 minutes 29 seconds (ca. 161 Hz).

On a year 2006 Intel 2.66 GHz Xeon, the mate finder solves the matein4 file in about 2 hours (ca. 13.9 Hz). The same machine solves the matein1 file in about 4.4 seconds, which is essentially all I/O overhead.

One of the hardest (i.e., longest solution time) mate-in-4 positions is:
[d]1rb5/2pk3p/1p3Qpn/pP1pp1N1/3B4/1P1B4/3bK1PP/2R3NR w - - 8 42[/d]
The analysis for the above: [MateIn4/7/1.132/1,181,244] 42. Ne6 Bxc1 43. Ng7 Nf7 44. Qxf7+ Kd8 45. Qe8#
(Analysis format: [Score/Depth/Seconds/Nodes] PV)

[sje]

Inside Symbolic's mate finder

Symbolic's mate finder is implemented as a C++ class named MateFinder which has the public instance method

Code: Select all

  bool MateSearch(const ui fmd, const Position& fposition, Analysis& analysis);

Where fmd is the full move distance to mate, fposition is the root position to search, and analysis is the analytic result of the search containing the score, the processing time, the node count, and the predicted variation.

The method's return value is true if and only if a mate was found. If more than one mate is present, then only the first one found is returned. If a mate shorter that the full move distance is present, then it too is treated as a solution.

Inside the MateFinder class are two private instance methods which are called at alternating depths during the single iteration, full-width, depth-first ɑ/β search. At even plies, the method

Code: Select all

  SV MateAttack(const Window window, MoveList& PV);

tries to find a forced mate for the side to move and returns a score and a predicted variation. At odd plies, the method

Code: Select all

  SV MateDefend(const Window window, MoveList& PV);

tries to find a defense for the side to move. To save processing time, the position and some other variables are stored as instance variables and so are not passed as parameters.

The mate finder knows about stalemates, but not the other three kinds of draws. It doesn't use tablebase knowledge, although it would be easy to add this. It doesn't use transposition table assistance, although such could be useful for deep mates where the set-up time for a big table would be small compared to total search time.

Move ordering is done in the same way for both attack and defend nodes. When reaching each depth for the first time, the ordering is done by scoring each move by assigning a value equal to the negation of the number of replies available to the opponent after the move is made. At all other nodes, the history heuristic is used with a 12x64 entry popularity table indexed by FromMan/ToSquare.

At the penultimate depth, much time is saved by using Symbolic's checking move generator which generates only checking moves instead of generating all the moves and then selecting the checks. Also at the penultimate depth, instead of calling MateDefend(), the MateAttack() routine invokes the Position method IsCheckmated() which quickly determines (no move generation nor move counting) if the position is a checkmate.

[sje]

For testing the mate finder, I have a set for four FEN files, each with 100,000 records with each record being a position with at least one mate-in-N solution and with no forced mates of lesser length.

The four files:
https://dl.dropboxusercontent.com/u/316 ... in1.fen.gz
https://dl.dropboxusercontent.com/u/316 ... in2.fen.gz
https://dl.dropboxusercontent.com/u/316 ... in3.fen.gz
https://dl.dropboxusercontent.com/u/316 ... in4.fen.gz

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

[Vinvin]

On a year 2006 Intel 2.66 GHz Xeon, the mate finder solves the matein4 file in about 2 hours (ca. 13.9 Hz)...

And what's the results on a 2015 hardware ?

[hgm]

Do you use proof-number search for that?

[sje]

Do you use proof-number search for that?

It's just a simple single iteration, full-width, depth-first ɑ/β search.

I have since merged the MateAttack() and MateDefend() methods into the single MateNode() method. This make the code clearer and more general at a slight increase in average running time.

I might change the code to remove recursion which will increase the speed slightly. The search already uses a dynamically grown linked list of records for storing most per-ply variables, so it's most of the way there. The list already removes the need for a silly MAXPLY limit.

After that, the next obvious step would be to make the class multithreaded using the same technique used in Symbolic's deep split perft().

Here's the current MateNode() 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 (mywindow.IsOpen() && pickernodeptr->MovesRemain())
    {
      const Move move = pickernodeptr->Pick();
      Window subwindow(mywindow);
      MoveList subpv;
      SV subsv;

      ExecuteMove(move);
      subwindow.DownShift();
      subsv = CalcSvUpShift(MateNode(subwindow, subpv));
      if (subsv > mywindow.GetAlfa())
      {
        mywindow.PutAlfa(subsv);
        PV.Reset();
        PV.Append(new MoveNode(move));
        PV.AppendFromList(subpv);
      };
      RetractMove();
    };

    if (position.IsMated())
      mywindow.Update(position.IsChecked() ? SvCheckmated : SvEven);

    if (PV.GetCount() > 0)
      histtableptr->IncCounter(*PV.GetHead());
  };

  isftd = false;
  pickernodeptr = pickernodeptr->GetPrev();
  return mywindow.GetAlfa();
}

[hgm]

Last year I spent a lot of effort in solving the 224 historic mating problems of Chu Shogi, using a regular Chu Shogi engine. Even when I restricted the search tree to checks only (which is custom in Shogi mating problems), the engine often had a very hard time finding the solution. (I sometimes had to run it for days!)

From this I got the impression that depth-first alpha-beta was a quite inefficient way to find mates. In particular it had problems when lines existed where with wrong attack the King couldbe hunted into the open, and then chased all over the board with a Queen. This gave many checking possibilities for each move, but predictably led nowhere, as a lone Queen cannot force checkmate. The explosion of the branching factor then prevented that the lines of the good solution would reach the necessary depth to see the checkmate.

It could be that 'depth control' not measuring plies, but by a node budget that would then be equally divided over all daughter nodes (and then iteratively increased in the root, say by a factor 10 per iteration) would solve this problem.


White checkmates in 16 (checking) moves

[sje]

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#

[hgm]

Well, Fruit finds the solution to the 'hard' one in 0.03 sec, so I guess that 'hard' is a relative concept:

Code: Select all

  6	+99.93 	34923  	0:00.03	Qge4 Nf2 Qxf2 Rf3 Qexf3 Bf4 Q2xg2#
  5	+33.48 	14358  	0:00.02	Qge4 Nf2 Qxf2 Rf3 Qexf3
  5	+33.18 	12187  	0:00.02	Qgc2 Nf2 Qxf2 Bd2 Qxb3
  4	+33.18 	5051    	0:00.00	Qgc2 Nf2 Qxf2 Bd2 Qxb3
  3	+29.54 	1934    	0:00.00	Qgc2 Nf2 Qxb3
  2	+29.54 	1363    	0:00.00	Qgc2 Nf2 Qxb3
  2	+28.51 	1167    	0:00.00	Qge4 Nf2 Qxf2
  2	+27.88 	1008    	0:00.00	Rxh6 Rxb4
  1	+27.88 	3          	0:00.00	Rxh6 Rxb4

The mate in 16 above was not found by the engine after two days!

One problem was also that a normal engine goes (mostly) for material before it sees the mate. While the crux of these problems is often to first sacrifice a large amount of material to smoke out the King, and then to mate him with almost nothing left. (Traditionally the winning side only gets the material it strictly needs, in these Shogi problems.)

[zullil]

Well, Fruit finds the solution to the 'hard' one in 0.03 sec, so I guess that 'hard' is a relative concept:

Code: Select all

  6	+99.93 	34923  	0:00.03	Qge4 Nf2 Qxf2 Rf3 Qexf3 Bf4 Q2xg2#
  5	+33.48 	14358  	0:00.02	Qge4 Nf2 Qxf2 Rf3 Qexf3
  5	+33.18 	12187  	0:00.02	Qgc2 Nf2 Qxf2 Bd2 Qxb3
  4	+33.18 	5051    	0:00.00	Qgc2 Nf2 Qxf2 Bd2 Qxb3
  3	+29.54 	1934    	0:00.00	Qgc2 Nf2 Qxb3
  2	+29.54 	1363    	0:00.00	Qgc2 Nf2 Qxb3
  2	+28.51 	1167    	0:00.00	Qge4 Nf2 Qxf2
  2	+27.88 	1008    	0:00.00	Rxh6 Rxb4
  1	+27.88 	3          	0:00.00	Rxh6 Rxb4

And Stockfish finds a (different) mate-in-4 in .021 seconds:

Code: Select all

info depth 16 seldepth 12 multipv 1 score mate 4 nodes 18768 nps 893714 tbhits 0 time 21 pv g6c2 h6d2 c2d2 h1f2 e2f2 h2h1 f2g2