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.
Dedicated mate finders
Moderators: hgm, Rebel, chrisw
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
History table variants
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.
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();
}
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Mate-in-4 sample extrema
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.
[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
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Mate-in-4 sample extrema
[d]k1b5/brb3PP/2R2b2/bQ6/2Pb4/4bQ2/3R2RQ/6QK w - - 0 1[/d]
Single thread mate search:
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#
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Mate-in-4 sample extrema
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.
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.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Mate-in-4 sample extrema
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."
[d]5b1k/PP3bnb/1Qb2N2/7b/4bP2/2Qb4/QN2N3/KQ6 w - -
It takes Chest "quite a while."
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Mate-in-4 sample extrema
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 wrote: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."
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Mate-in-4 sample extrema
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#;
[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#;
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
18 MateIn4 in 16.824 seconds, single thread
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;
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Mate-in-4 sample extrema
Symbolic says: Position is not reachable from the starting array.Dann Corbit wrote: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#;