Dedicated mate finders

[sje]

Performance changes with every change to the code; for the latest MateIn4 run, see: https://dl.dropboxusercontent.com/u/316 ... in4.epd.gz

All 100,000 problems in the MateIn4 set were correctly solved with minimum length mates in just under 5,400 seconds total using only a single calculation thread. This includes time for set-up and reporting for each position. The speed is about 18.5 problems per second or about 54 ms per problem.

The speed for the 100,000 problem MateIn3 set was about twenty six times faster (ca. 211 seconds total, 474 problems per second, 2.1 ms per problem).

The inescapable overhead for I/O and set-up is about 0.1 ms per problem.

[sje]

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();
}

[Dann Corbit]

This mate in 4:
[d]k1b5/brb3PP/2R2b2/bQ6/2Pb4/4bQ2/3R2RQ/6QK w - -
Took Stockfish an entire 1/5 of a second to solve for mate in 4.

Code: Select all

bench 4096 9 60000 X:\users\dcorbit\hrd4.epd time

Position: 1/1
info depth 1 seldepth 1 multipv 1 score cp 4212 nodes 837 nps 5042 tbhits 0 time 166 pv h7h8q
info depth 2 seldepth 2 multipv 1 score cp 4954 nodes 1079 nps 6422 tbhits 0 time 168 pv h7h8q a5b6 h8c8 c7b8 c6f6
info depth 3 seldepth 4 multipv 1 score cp 5059 nodes 1280 nps 7485 tbhits 0 time 171 pv h7h8q a5b6 c6c7
info depth 4 seldepth 5 multipv 1 score cp 5563 nodes 1634 nps 9445 tbhits 0 time 173 pv h7h8q a5b6 h8c8 c7b8 c8b7 a8b7
info depth 5 seldepth 6 multipv 1 score cp 5608 nodes 3515 nps 19747 tbhits 0 time 178 pv h7h8q c7b8 h8c8 d4b6 c8b7 a8b7
info depth 6 seldepth 7 multipv 1 score cp 5547 nodes 4661 nps 25751 tbhits 0 time 181 pv h7h8q a8b8 b5b7 b8b7 c6c7 b7a6 h2d6 a5b6 h8c8 a6a5 g7g8q
info depth 7 seldepth 8 multipv 1 score cp 5665 nodes 6764 nps 36365 tbhits 0 time 186 pv h7h8q f6d8 h8d8 c7b8 d8c8 a5b6 c6b6
info depth 8 seldepth 10 multipv 1 score cp 6353 nodes 10348 nps 54178 tbhits 0 time 191 pv h7h8q f6d8 h8d8 a7b6 d8c8 a8a7 g7g8q c7d8 c6b6
info depth 9 seldepth 10 multipv 1 score mate 6 nodes 17593 nps 87965 tbhits 0 time 200 pv h7h8q f6d8 h8d8 a7b6 d8c8 a8a7 g7g8q c7d8 c6b6 e3g1
info depth 10 seldepth 12 multipv 1 score mate 4 nodes 49867 nps 235221 tbhits 0 time 212 pv c6c7 a5c7 h2c7 e3g1 c7c8 a7b8 c8b7

[sje]

[d]k1b5/brb3PP/2R2b2/bQ6/2Pb4/4bQ2/3R2RQ/6QK w - - 0 1[/d]
Single thread mate search:

Code: Select all

[] sf k1b5/brb3PP/2R2b2/bQ6/2Pb4/4bQ2/3R2RQ/6QK w - - 0 1
[] mate 4
[MateIn4/7/1.085/1,036,813] 1. Rxc7 Bxc7 2. Qxc7 Bd8 3. Qfxb7+ Bxb7 4. Qbxb7#

[Dann Corbit]

This is a collection of mates in 4 that took chest 1 second to solve. (150K 4 ply mates from my last run all solved in under a second).

1q4qk/3r2rq/4Bq2/2pB4/B7/2r2B2/BRB3pp/K1B5 b - -
5b1k/PP2Rbrb/2b5/7b/2Q1bP2/2Qb4/QR2R3/KQ6 w - -
5b1k/PP3brb/2b2R2/6Qb/4bP2/2Qb4/QR2R3/KQ6 w - -
5b1k/PP3brb/2b2R2/7b/4bP2/2Qb4/QR2R3/KQ4Q1 w - -
5b1k/PPQ2brb/2b2R2/7b/4bP2/2Qb4/QR2R3/KQ6 w - -
5b1k/PPR2brb/2b5/7b/2Q1bP2/2Qb4/QR2R3/KQ6 w - -
6qk/3r2rq/4Bq2/2pB1q2/B7/5B2/BRB2rpp/K1B5 b - -
6qk/3r2rq/4Bq2/2pB1q2/B7/5B2/BRBr2pp/K1B5 b - -
6qk/3r2rq/4Bq2/2pB4/Bq6/2r2B2/BRB3pp/K1B5 b - -
k1b5/brb2QPP/2R2b2/b7/2Pb4/4bQ2/3R2RQ/6QK w - -
k1b5/brb2RPP/5b2/b7/2Pb1Q2/4bQ2/3R2RQ/6QK w - -
k1b5/brb3PP/2R2b2/b7/2Pb4/4bQ2/3R2RQ/1Q4QK w - -
k1b5/brb3PP/2R2b2/bQ6/2Pb4/4bQ2/3R2RQ/6QK w - -
k1b5/brbR2PP/5b2/b7/2Pb1Q2/4bQ2/3R2RQ/6QK w - -
kq4q1/qr2r3/2qB4/4Bp2/7B/2B2r2/pp3BRB/5B1K b - -
kq6/qr2r3/2qB4/2q1Bp2/7B/2B5/pp2rBRB/5B1K b - -
kq6/qr2r3/2qB4/2q1Bp2/7B/2B5/ppr2BRB/5B1K b - -
kq6/qr2r3/2qB4/4Bp2/6qB/2B2r2/pp3BRB/5B1K b - -

Chest took around a million nodes or so to prove these as mates in 4.
Since Chest is a prover, it cannot take the same sort of pruning shortcuts that chess playing engines can.

[Dann Corbit]

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."

[Dann Corbit]

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#;

[Dann Corbit]

Here is the slowest one with a single solution for a mate in 6:
[d]3qkrbn/1p1nq1qp/2n2rr1/1q2p3/q4P2/2B5/PPN1N2P/NB2KRBN b - - acd 13; acs 1056; bm exf4; ce 32756; dm 6; id "Leonid.388012"; pm exf4; pv exf4 Nhg3 fxg3 Be5 Rxf1+ Kd2 Ndxe5+ Ncd4 Nf3+ Kc3 Qec5#;

[sje]

18 MateIn4 in 16.824 seconds, single thread:

Code: Select all

1q4qk/3r2rq/4Bq2/2pB4/B7/2r2B2/BRB3pp/K1B5 b - - 0 1 ad 7; nc 893244; pt 0.930; pv Rxc2 B2b3 Rxc1+ Ka2 Qc2 Bd1 Qcxb2#; ss MateIn4;
5b1k/PP2Rbrb/2b5/7b/2Q1bP2/2Qb4/QR2R3/KQ6 w - - 0 1 ad 7; nc 806421; pt 0.849; pv Qxf7 Bxf7 Qxf7 Bxb1 Qcxg7+ Bxg7 Qxg7#; ss MateIn4;
5b1k/PP3brb/2b2R2/6Qb/4bP2/2Qb4/QR2R3/KQ6 w - - 0 1 ad 7; nc 982485; pt 1.122; pv Rxf7 Bxf7 Qxf7 Bg8 Qcxg7+ Bxg7 Qgxg7#; ss MateIn4;
5b1k/PP3brb/2b2R2/7b/4bP2/2Qb4/QR2R3/KQ4Q1 w - - 0 1 ad 7; nc 957400; pt 1.098; pv Rxf7 B7g6 Rxf8+ Kh7 Qf7 Be8 Qcxg7#; ss MateIn4;
5b1k/PPQ2brb/2b2R2/7b/4bP2/2Qb4/QR2R3/KQ6 w - - 0 1 ad 7; nc 722390; pt 0.716; pv Rxf7 Bxf7 Qcxf7 Bxb1 Qxf8+ Bg8 Qcxg7#; ss MateIn4;
5b1k/PPR2brb/2b5/7b/2Q1bP2/2Qb4/QR2R3/KQ6 w - - 0 1 ad 7; nc 852240; pt 0.920; pv Qxf7 Bxf7 Qxf7 Be8 Qcxg7+ Bxg7 Qxg7#; ss MateIn4;
6qk/3r2rq/4Bq2/2pB1q2/B7/5B2/BRB2rpp/K1B5 b - - 0 1 ad 7; nc 961373; pt 1.016; pv Qxc2 Bxc2 Qxc2 Bxg8 Qcxb2+ Bxb2 Qxb2#; ss MateIn4;
6qk/3r2rq/4Bq2/2pB1q2/B7/5B2/BRBr2pp/K1B5 b - - 0 1 ad 7; nc 748911; pt 0.704; pv Qxc2 Bxc2 Qxc2 Bxg8 Qcxb2+ Bxb2 Qxb2#; ss MateIn4;
6qk/3r2rq/4Bq2/2pB4/Bq6/2r2B2/BRB3pp/K1B5 b - - 0 1 ad 7; nc 930493; pt 0.960; pv Rxc2 Bxc2 Qxc2 Bab3 Qxc1+ Ka2 Qcxb2#; ss MateIn4;
k1b5/brb2QPP/2R2b2/b7/2Pb4/4bQ2/3R2RQ/6QK w - - 0 1 ad 7; nc 833086; pt 0.888; pv Rxc7 Bxc7 Qfxc7 Bde5 Qxc8+ Beb8 Qfxb7#; ss MateIn4;
k1b5/brb2RPP/5b2/b7/2Pb1Q2/4bQ2/3R2RQ/6QK w - - 0 1 ad 7; nc 862331; pt 0.892; pv Qxc7 Bxc7 Qxc7 Ba1 Qfxb7+ Bxb7 Qxb7#; ss MateIn4;
k1b5/brb3PP/2R2b2/b7/2Pb4/4bQ2/3R2RQ/1Q4QK w - - 0 1 ad 7; nc 989590; pt 1.049; pv Rxc7 Bxc7 Qxc7 Bb8 Qbxb7+ Bxb7 Qfxb7#; ss MateIn4;
k1b5/brb3PP/2R2b2/bQ6/2Pb4/4bQ2/3R2RQ/6QK w - - 0 1 ad 7; nc 1036813; pt 1.083; pv Rxc7 Bxc7 Qxc7 Bd8 Qfxb7+ Bxb7 Qbxb7#; ss MateIn4;
k1b5/brbR2PP/5b2/b7/2Pb1Q2/4bQ2/3R2RQ/6QK w - - 0 1 ad 7; nc 798131; pt 0.825; pv Qxc7 Bxc7 Qxc7 Ba1 Qfxb7+ Bxb7 Qxb7#; ss MateIn4;
kq4q1/qr2r3/2qB4/4Bp2/7B/2B2r2/pp3BRB/5B1K b - - 0 1 ad 7; nc 941664; pt 0.994; pv Rxf2 Bxf2 Qxf2 Bg1 Qfxg2+ Bxg2 Qcxg2#; ss MateIn4;
kq6/qr2r3/2qB4/2q1Bp2/7B/2B5/pp2rBRB/5B1K b - - 0 1 ad 7; nc 776025; pt 0.786; pv Qxf2 Bxf2 Qxf2 Be1 Qfxg2+ Bxg2 Qxg2#; ss MateIn4;
kq6/qr2r3/2qB4/2q1Bp2/7B/2B5/ppr2BRB/5B1K b - - 0 1 ad 7; nc 898226; pt 0.959; pv Qxf2 Bxf2 Qxf2 Bc5 Qfxg2+ Bxg2 Qxg2#; ss MateIn4;
kq6/qr2r3/2qB4/4Bp2/6qB/2B2r2/pp3BRB/5B1K b - - 0 1 ad 7; nc 968762; pt 1.020; pv Rxf2 Bxf2 Qxf2 Bg1 Qfxg2+ Bxg2 Qgxg2#; ss MateIn4;

[sje]

Here is the slowest one with a single solution for a mate in 6:
[d]3qkrbn/1p1nq1qp/2n2rr1/1q2p3/q4P2/2B5/PPN1N2P/NB2KRBN b - - acd 13; acs 1056; bm exf4; ce 32756; dm 6; id "Leonid.388012"; pm exf4; pv exf4 Nhg3 fxg3 Be5 Rxf1+ Kd2 Ndxe5+ Ncd4 Nf3+ Kc3 Qec5#;

Symbolic says: Position is not reachable from the starting array.