Checkmate evaluation functions

[Chessnut1071]

I'm focused on finding fast solutions for checkmate at 20-ply and above. I have heard of a 25-year old program solving complicated problems in under a few minutes, problems which do not consist of all checks.

Computer chip:
Intel i-7 2.6 GHz, 1 core, 1 thread
Average speed 546,000 NPS [slow by most standards here, but I include 24-evaluation metrics in a 64-bit move]

Assuming white to mate
Two obvious strategies [mentioned earlier on a different thread] are: 1) no static evaluation on white's last move and check only moves consider on white's last move as well.

Another strategy that works on almost every puzzle if no more than 6 possible king moves on white's final move(although there are a few cases where this will fail by design).

My evaluation also includes:

Static evaluation [Shell Sort]:
White's 1st move,
White's 2nd - N-1 moves
All Black moves

Priority weights optimized by a modified Hooke-Jeeves nonlinear optimization function specifically written for chess

White Priority:
1) The previous successful mate move at the given ply - probably the most significant effect
2) History: successful move by ply in the past - about the same significance as a check move
3) Check: +, ++ , disc + very significant on most puzzle mates
4) Distance to enemy king (8 - distance) * Weight - slight by significant effect on most puzzles
5) Hit on an enemy king square - very slight effect on most puzzles
6) Material consequences (gain or loss) - this can be an issue if the problem was designed for sacrificial lines; otherwise, very significant on about 1/2 puzzle mates
7) Piece type[P,N,B,R,Q,K] - this is only reliable if optimized to specific problems and is not a good general strategy.

Black Priority
1) Previous successful move
2) History by ply
3) Check +, ++, disc +
4) Material consequences of move
4) Max enemy king moves

The genius who came up with quick mate over 20-years ago on an old, old computer had to have something besides the strategies I listed above. I suspect he used some sort of look ahead, like making 2 or 3 moves instead of one. When I tried this it tremendously increased the solution time and caused too many other issues.

Since the checkmate genius didn't have parallel processors back then, multi-cores and threads is not a solution.

Unfortunately, the mating genius never published how he did it before he died. If I find it, I will publish it here; however, I'm running out of gas on finding a general solution. Any suggestions are welcome.

[hgm]

Which program are you talking about? Chest UCI?

Dedicated mate finders often use other search techniques, like proof-number search. This can find deep mates very quickly, because it only searches lines not leading to that mate much less deep than the mating line. Once it finds a mate it only has to prove it is the fastest one, and this can be done much faster than finding a mate.

I guess problems with deep mates usually have a single forced line, rather than a very wide tree where you have very many ways to checkmate (but some slightly slower than others). Such as you would have in, say, the KBNK end-game. Then it becomes much harder to find the fastest mate.

[Chessnut1071]

Which program are you talking about? Chest UCI?

Dedicated mate finders often use other search techniques, like proof-number search. This can find deep mates very quickly, because it only searches lines not leading to that mate much less deep than the mating line. Once it finds a mate it only has to prove it is the fastest one, and this can be done much faster than finding a mate.

I guess problems with deep mates usually have a single forced line, rather than a very wide tree where you have very many ways to checkmate (but some slightly slower than others). Such as you would have in, say, the KBNK end-game. Then it becomes much harder to find the fastest mate.

FEN[222] = "k1r4r/2p3pp/BpN1pp2/3p4/Q2P1B2/P3P3/R6P/4K1qn w 0 1"; // Chess.com 1.Bf1 dsc + Kb7, Ka8, Ka7 2.Na5+ PxN 3. Qb5+ 2 Na5 dsc + Kb8 3. Qc6

Thanks for t. he reply.
My search is similar if not the same as PNS, it searches solutions N-ply deep where N is the given puzzle solution. My speed for the above FEN is 996,454 /nps. It take my solution 3617 seconds to find that mate for a generic mate function given the evaluation above. I can optimize the specific solution 1,000 times faster; however, that's not a solution, as Mr. Genius found it with a generic evaluation.

Given the FEN above, what are the fastest solutions by time and nodes searched. Then, what is in the evaluation function that's not listed above?
I assume the trick to fast deep ply mating solutions is in a very unique evaluation metric not generally known. If we can find it this may have significant consequences for ELO optimizations as well. tia

[Joerg Oster]

Which program are you talking about? Chest UCI?

Dedicated mate finders often use other search techniques, like proof-number search. This can find deep mates very quickly, because it only searches lines not leading to that mate much less deep than the mating line. Once it finds a mate it only has to prove it is the fastest one, and this can be done much faster than finding a mate.

I guess problems with deep mates usually have a single forced line, rather than a very wide tree where you have very many ways to checkmate (but some slightly slower than others). Such as you would have in, say, the KBNK end-game. Then it becomes much harder to find the fastest mate.

FEN[222] = "k1r4r/2p3pp/BpN1pp2/3p4/Q2P1B2/P3P3/R6P/4K1qn w 0 1"; // Chess.com 1.Bf1 dsc + Kb7, Ka8, Ka7 2.Na5+ PxN 3. Qb5+ 2 Na5 dsc + Kb8 3. Qc6

Thanks for t. he reply.
My search is similar if not the same as PNS, it searches solutions N-ply deep where N is the given puzzle solution. My speed for the above FEN is 996,454 /nps. It take my solution 3617 seconds to find that mate for a generic mate function given the evaluation above. I can optimize the specific solution 1,000 times faster; however, that's not a solution, as Mr. Genius found it with a generic evaluation.

Given the FEN above, what are the fastest solutions by time and nodes searched. Then, what is in the evaluation function that's not listed above?
I assume the trick to fast deep ply mating solutions is in a very unique evaluation metric not generally known. If we can find it this may have significant consequences for ELO optimizations as well. tia

The Huntsman 1 takes a bit more than a second for this mate in 7.

Code: Select all

info depth 40 seldepth 16 multipv 1 score mate 7 nodes 1433803 nps 1051946 hashfull 53 tbhits 0 time 1363 pv e1d2 g1f2 a6e2 a8b7 c6b4 b7b8 a4a6 f2e2 d2e2 h1g3 e2e1 e6e5 b4c6

Current Matefish Dev needs almost 6 seconds.

Code: Select all

info string Success! Mate in 7 found!
info time 5535 multipv 1 depth 13 seldepth 13 nodes 6482765 nps 1171231 tbhits 0 score mate 7 pv e1d2 g1h2 a6e2 a8b7 c6a5 b7b8 f4h2 b6a5 a4b5 b8a7 b5a6 a7b8 a2b2
bestmove e1d2 ponder g1h2

Both single-threaded.
Matefish also confirms there is no mate in 6.

Code: Select all

go mate 6
info time 1 multipv 1 depth 1 seldepth 1 nodes 1 nps 1000 tbhits 0 score cp 0 pv a6f1
info time 2 multipv 1 depth 3 seldepth 2 nodes 591 nps 295500 tbhits 0 score cp 0 pv a6f1
info time 2 multipv 1 depth 5 seldepth 11 nodes 1029 nps 514500 tbhits 0 score cp 0 pv a6f1
info time 24 multipv 1 depth 7 seldepth 11 nodes 24695 nps 1028958 tbhits 0 score cp 0 pv a6f1
info time 57 multipv 1 depth 9 seldepth 11 nodes 61846 nps 1085017 tbhits 0 score cp 0 pv a6f1
info currmove e1e2 currmovenumber 3
info string Failure! No mate found!
info time 462 multipv 1 depth 11 seldepth 11 nodes 468609 nps 1014305 tbhits 0 score cp 0 pv a6f1
bestmove a6f1

Huntsman is a modified Stockfish using only KingSafety part as eval. Plus some mods to move-ordering and search.
This works surprisingly well, in general.
Matefish, otoh, doesn't use any eval and the search (Alpha-Beta) has completely been rewritten.
Yet it is still far from the functionality and speed offered by ChestUCI or Gustav.

[hgm]

My search is similar if not the same as PNS, it searches solutions N-ply deep where N is the given puzzle solution.

That seems in total contradiction with what you described. PNS would not order moves by any of the criteria you use. It purely orders them by the number of 'loose ends' that would yet have to be resolved to prove mate.

[Chessnut1071]

Which program are you talking about? Chest UCI?

Dedicated mate finders often use other search techniques, like proof-number search. This can find deep mates very quickly, because it only searches lines not leading to that mate much less deep than the mating line. Once it finds a mate it only has to prove it is the fastest one, and this can be done much faster than finding a mate.

I guess problems with deep mates usually have a single forced line, rather than a very wide tree where you have very many ways to checkmate (but some slightly slower than others). Such as you would have in, say, the KBNK end-game. Then it becomes much harder to find the fastest mate.

FEN[222] = "k1r4r/2p3pp/BpN1pp2/3p4/Q2P1B2/P3P3/R6P/4K1qn w 0 1"; // Chess.com 1.Bf1 dsc + Kb7, Ka8, Ka7 2.Na5+ PxN 3. Qb5+ 2 Na5 dsc + Kb8 3. Qc6

Thanks for t. he reply.
My search is similar if not the same as PNS, it searches solutions N-ply deep where N is the given puzzle solution. My speed for the above FEN is 996,454 /nps. It take my solution 3617 seconds to find that mate for a generic mate function given the evaluation above. I can optimize the specific solution 1,000 times faster; however, that's not a solution, as Mr. Genius found it with a generic evaluation.

Given the FEN above, what are the fastest solutions by time and nodes searched. Then, what is in the evaluation function that's not listed above?
I assume the trick to fast deep ply mating solutions is in a very unique evaluation metric not generally known. If we can find it this may have significant consequences for ELO optimizations as well. tia

The Huntsman 1 takes a bit more than a second for this mate in 7.

Code: Select all

info depth 40 seldepth 16 multipv 1 score mate 7 nodes 1433803 nps 1051946 hashfull 53 tbhits 0 time 1363 pv e1d2 g1f2 a6e2 a8b7 c6b4 b7b8 a4a6 f2e2 d2e2 h1g3 e2e1 e6e5 b4c6

Current Matefish Dev needs almost 6 seconds.

Code: Select all

info string Success! Mate in 7 found!
info time 5535 multipv 1 depth 13 seldepth 13 nodes 6482765 nps 1171231 tbhits 0 score mate 7 pv e1d2 g1h2 a6e2 a8b7 c6a5 b7b8 f4h2 b6a5 a4b5 b8a7 b5a6 a7b8 a2b2
bestmove e1d2 ponder g1h2

Both single-threaded.
Matefish also confirms there is no mate in 6.

Code: Select all

go mate 6
info time 1 multipv 1 depth 1 seldepth 1 nodes 1 nps 1000 tbhits 0 score cp 0 pv a6f1
info time 2 multipv 1 depth 3 seldepth 2 nodes 591 nps 295500 tbhits 0 score cp 0 pv a6f1
info time 2 multipv 1 depth 5 seldepth 11 nodes 1029 nps 514500 tbhits 0 score cp 0 pv a6f1
info time 24 multipv 1 depth 7 seldepth 11 nodes 24695 nps 1028958 tbhits 0 score cp 0 pv a6f1
info time 57 multipv 1 depth 9 seldepth 11 nodes 61846 nps 1085017 tbhits 0 score cp 0 pv a6f1
info currmove e1e2 currmovenumber 3
info string Failure! No mate found!
info time 462 multipv 1 depth 11 seldepth 11 nodes 468609 nps 1014305 tbhits 0 score cp 0 pv a6f1
bestmove a6f1

Huntsman is a modified Stockfish using only KingSafety part as eval. Plus some mods to move-ordering and search.
This works surprisingly well, in general.
Matefish, otoh, doesn't use any eval and the search (Alpha-Beta) has completely been rewritten.
Yet it is still far from the functionality and speed offered by ChestUCI or Gustav.

Chess.com printed the solution as a 10-move mate. I never checked for a 7-move solution. I seems that many of the deep-ply mates on Chess,com have issues.

1) Are these programs using multi-core systems to achieve this speed?
2) Any information about what's in the evaluation function, assuming they have one?

[Chessnut1071]

My search is similar if not the same as PNS, it searches solutions N-ply deep where N is the given puzzle solution.

That seems in total contradiction with what you described. PNS would not order moves by any of the criteria you use. It purely orders them by the number of 'loose ends' that would yet have to be resolved to prove mate.

Any public code on this?

[Joerg Oster]

1) Are these programs using multi-core systems to achieve this speed?

No.

2) Any information about what's in the evaluation function, assuming they have one?

The main commit for Huntsman: https://github.com/joergoster/Stockfish ... a01829c490

[JVMerlino]

FEN[222] = "k1r4r/2p3pp/BpN1pp2/3p4/Q2P1B2/P3P3/R6P/4K1qn w 0 1"; // Chess.com 1.Bf1 dsc + Kb7, Ka8, Ka7 2.Na5+ PxN 3. Qb5+ 2 Na5 dsc + Kb8 3. Qc6

Given the FEN above, what are the fastest solutions by time and nodes searched. Then, what is in the evaluation function that's not listed above?
I assume the trick to fast deep ply mating solutions is in a very unique evaluation metric not generally known. If we can find it this may have significant consequences for ELO optimizations as well. tia

Myrddin, my mediocre engine, finds Mate in 7 in 2.4 seconds with one thread, searching 6.6M nodes. This should not be difficult for any engine.

[hgm]

Fairy-Max 4.8 takes 2.29sec to settle on mate in 7 (i7 3.2GHz, single core):

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 17	    #7 	22.8M  	0:15.00	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2e1 g7g5 a4a6 b7b8 b4c6
 16	    #7 	14.6M  	0:09.95	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 15	    #7 	9.90M  	0:06.97	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 14	    #7 	6.93M  	0:05.07	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 13	    #7 	5.01M  	0:03.80	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 12	    #7 	3.56M  	0:02.79	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #7 	2.85M  	0:02.29	e1d2 g1f2 a6e2 a8b7 c6b4 f2e2 d2e2 h1g3 e2d1 g7g5 a4a6 b7b8 b4c6
 11	    #8 	2.58M  	0:02.10	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a4c6 b8c8 c6c7
 10	+11.57 	2.14M  	0:01.76	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 a8b8 a5c6 b8c8 a4a8 c8d7 a8h8
  9	+9.19 	1.01M  	0:00.84	e1e2 g1g2 e2d1 g2g1 d1c2 g1f2 c2b3 f2e1 a6c8 e1a5 c6a5 h8c8 a4c6 a8b8 c6b6
  9	+9.10 	646678	0:00.54	a6f1 a8b7 c6b4 b7b8 a4a6 g1e3 f4e3 c7c5 a6b6 b8a8 b6a6 a8b8 d4c5
  8	+8.10 	428438	0:00.37	a6f1 a8b7 c6b4 b7b8 a4a6 g1f1 e1f1 h1g3 h2g3 e6e5 d4e5
  7	+5.95 	259062	0:00.23	a6f1 a8b7 c6b4 b7b8 a4a6 g1f2 a2f2 h1f2 e1f2
  6	+4.43 	120069	0:00.12	a6f1 a8b7 c6e7 b7b8 a2g2 g1g2 f1g2 c8e8 e7d5 e6d5 g2h1
  5	+3.45 	21191  	0:00.03	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  4	+3.45 	9862 	0:00.01	a6f1 a8b7 a2g2 c8a8 a4c2 g1g2 f1g2
  3	+0.97 	4301 	0:00.00	a6f1 a8b7 a4a6 b7c6 a2g2 g1g2 f1g2
  2	+0.14 	1122  	0:00.00	a6f1 a8b7 a2g2 b6b5 a4b5
  1	 -0.63 	158   	0:00.00	a6f1 a8b7 a2b2

That is with an evaluation that is little more than material and centralization. And a rudimentary move sorting that searches the hash move first, and then all other moves in move generation order.

Any public code on this?

Not in any Chess engine I know; for playing games it is not very useful. Unlike in Shogi, where it appears to be a worthwile method for finding very deep forced mates that one often has there, when there are many pieces in hand. I know SPEAR uses PNS for that, but I don't think that is public. But there must be other open-source Shogi programs.