Checkmate evaluation functions

[hgm]

Well, that is what I mean by "something wrong". Even a fixed-depth alpha-beta search should not use much more time (or nodes) for the 20 ply search than for the 14-ply search. You searched 730M nodes that should not have been searched because they could not possibly change the score at the root.

A good search would not ignore unpromising lines, but would reduce them. I.e. not just postpone their search, but postpone the deepening of their search compared to the more promising lines. That way you find a mate quickly, not having wasted so much time on searching the unpromising nodes. But eventually they will be search to full depth. But if this is done after a mate has already been established, this will take far fewer nodes, because alpha-beta pruning gets much more efficient. If you increase depth until even the most-reduced line reaches the target depth, there is zero chance you would ever fail to find a checkmate.

As long as you cling to a fixed-depth search you can keep twiddling forever with move sorting and evaluation criteria, but you will never get anything competitive. It is like designing a car, and testing all kind of aerodynamic shapes to no avail, while stubbornly clinging that it should run on square wheels...

[Chessnut1071]

Well, that is what I mean by "something wrong". Even a fixed-depth alpha-beta search should not use much more time (or nodes) for the 20 ply search than for the 14-ply search. You searched 730M nodes that should not have been searched because they could not possibly change the score at the root.

A good search would not ignore unpromising lines, but would reduce them. I.e. not just postpone their search, but postpone the deepening of their search compared to the more promising lines. That way you find a mate quickly, not having wasted so much time on searching the unpromising nodes. But eventually they will be search to full depth. But if this is done after a mate has already been established, this will take far fewer nodes, because alpha-beta pruning gets much more efficient. If you increase depth until even the most-reduced line reaches the target depth, there is zero chance you would ever fail to find a checkmate.

As long as you cling to a fixed-depth search you can keep twiddling forever with move sorting and evaluation criteria, but you will never get anything competitive. It is like designing a car, and testing all kind of aerodynamic shapes to no avail, while stubbornly clinging that it should run on square wheels...

The FEN above has an approximate (30 x 20} ^ 6 = 23,328,000,000,000 moves in a 14-ply search tree with 1 checkmate move on white’s 7th move. With average luck, that’s about 23,328,000,000,000 move to find the solution. In an attempt to document the marginal effect of sorting optimized moves on solution speed, I tried to measure the nodes needed for three variables everybody uses:
1) Alpha/beta
2) TT Table
3) History by ply
The 14-ply solution tree needs over 32,000,000,000 nodes before I had to stop counting. Using previous move, check, enemy king moves, material gain/loss [not used 1st time], enemy king square, number of enemy moves and two other metrics on double sliders, I achieved the following results:

Nodes to checkmate = 3,157,122; time = 6.32 seconds

That is fairly consistent with Fairly-Max, except for time; however, Fairly-Max is using a more powerful 3.6 GHz I7 compared with my older 2.6 GHz i7.

My conclusion is if the optimization is done on the right variables and sorted efficiently, results are similar to the methods you describe as superior to my waste of time and spinning my wheels technique.

The difference between my earlier results. I didn’t include material gain/loss and double slider pieces in the optimization because of the time penalty to compute gain/loss.

[hgm]

Well, 23e12 is the size of the minimax tree; with alpha-beta pruning you expect to need only the square root of that, so ~5M. And that is without TT.

But one of my points was that the 20-ply search should not need much longer if a mate was already found at 14 ply.

BTW, Fairy-Max actually double-counts the nodes, as it counts the number of times it runs its move-generation loop, and in a QS node it actually does that twice: once to find the most-profitable capture, and then once to search all captures. Fairy-Max does not use history, and basically only material and (for some pieces) centralization.

[Chessnut1071]

Well, 23e12 is the size of the minimax tree; with alpha-beta pruning you expect to need only the square root of that, so ~5M. And that is without TT.

But one of my points was that the 20-ply search should not need much longer if a mate was already found at 14 ply.

BTW, Fairy-Max actually double-counts the nodes, as it counts the number of times it runs its move-generation loop, and in a QS node it actually does that twice: once to find the most-profitable capture, and then once to search all captures. Fairy-Max does not use history, and basically only material and (for some pieces) centralization.

Remember, Chess.com gave that FEN a 20=ply solution so I just used a 20-ply thread. If you step through the plys to 20, yes, you are right, you will find the 14-ply solution faster; however, it's a lot faster finding a 14-ply solution in a 14-ply tree than a 14-ply solution in a 20-ply tree.

I can't believe you're not using history and previous move. Those two metrics account for at least 1/2 of the speedup. Also, how do you handle sacrificial lines in a generic solution? I assume you take the hit on sacrificial lines where you give up a queen, or more, to find mate.

I'm still looking for a good description of PNS to see if it's an improvement, but so far, I haven't found anything that makes enough sese to program it.

PS: the sqrt(46,657,000,000,000,000) = 216,000,000

[hgm]

Remember, Chess.com gave that FEN a 20=ply solution so I just used a 20-ply thread. If you step through the plys to 20, yes, you are right, you will find the 14-ply solution faster; however, it's a lot faster finding a 14-ply solution in a 14-ply tree than a 14-ply solution in a 20-ply tree.

My point was that it shouldn't be. You should first encounter the 14-ply solution in the same time (namely when you have deepened to 14 ply), and after that no line can search deeper than 14 ply, because they should all be cut beyond that.

I can't believe you're not using history and previous move. Those two metrics account for at least 1/2 of the speedup.

That is because Fairy-Max (or more accurately, the program it is a derivative of, micro-Max) is a toy program, one of the most primitive engines in existense, designed to have minimal source-code size per Elo. The source code is thus less than 2K characters (about 100 lines). So the issue is not whether it would give a speedup, which it certainly will, but if that speedup is worth the number of characters for implementing it.

[Chessnut1071]

Remember, Chess.com gave that FEN a 20=ply solution so I just used a 20-ply thread. If you step through the plys to 20, yes, you are right, you will find the 14-ply solution faster; however, it's a lot faster finding a 14-ply solution in a 14-ply tree than a 14-ply solution in a 20-ply tree.

My point was that it shouldn't be. You should first encounter the 14-ply solution in the same time (namely when you have deepened to 14 ply), and after that no line can search deeper than 14 ply, because they should all be cut beyond that.

I can't believe you're not using history and previous move. Those two metrics account for at least 1/2 of the speedup.

That is because Fairy-Max (or more accurately, the program it is a derivative of, micro-Max) is a toy program, one of the most primitive engines in existense, designed to have minimal source-code size per Elo. The source code is thus less than 2K characters (about 100 lines). So the issue is not whether it would give a speedup, which it certainly will, but if that speedup is worth the number of characters for implementing it.

Now I'm really curious about your minimal code program. I understand that the speed gained without the overhead of computing all the variables; however, unless you get very lucky, you probably need to search a huge number of additional nodes, unless you're using some advance form of filtering I don't know about. So, what's the secret filter?

[Ras]

So, what's the secret filter?

You even quoted it. Just read the posting you quoted.

[Chessnut1071]

So, what's the secret filter?

You even quoted it. Just read the posting you quoted.

Now I see how he did it, He is using a Shogi, or near Shogi, to solve the problem. If I use skip on black king moves > 2, I get almost the exact same number of nodes searched, 2,871,584, and 5.25 seconds. Since his I7 is at least 2x my older I7, we get the about the same nodes and same time.

This is not a generic solution I'm looking for. this is a special case which only shows in puzzle mates.

I think the optimal generic solution may be a composite if at least 12 solutions where the optimum is a special function depending on the structure of the position. You can't have one generic for sacrificial and non-sacrificial lines along with Shogi and a host of special cases.

[Ras]

Now I see how he did it

He also wrote why finding a 14-ply solution in a 20-ply search can be a lot faster than finding a 20-ply solution in a 20-ply-search - though that's assuming that you use iterative deepening, which is not necessarily the case in a dedicated mate searcher. It is, however, easy to add in the regular search. CPW has that as mate distance pruning: https://www.chessprogramming.org/Mate_Distance_Pruning

The really nasty part is disproving that a mate exists in a given distance - either to refute the problem, or to prove that no double solutions exist, i.e. other mates in the required distance that have a different starting move. I don't see any other approach than a brute-force alpha-beta for that.

[Chessnut1071]

Now I see how he did it

He also wrote why finding a 14-ply solution in a 20-ply search can be a lot faster than finding a 20-ply solution in a 20-ply-search - though that's assuming that you use iterative deepening, which is not necessarily the case in a dedicated mate searcher. It is, however, easy to add in the regular search. CPW has that as mate distance pruning: https://www.chessprogramming.org/Mate_Distance_Pruning

The really nasty part is disproving that a mate exists in a given distance - either to refute the problem, or to prove that no double solutions exist, i.e. other mates in the required distance that have a different starting move. I don't see any other approach than a brute-force alpha-beta for that.

"I don't see any other approach than a brute-force alpha-beta for that."

Exactly my point. Also, iterative deepening works great for ELO opts and in cases where you have no idea how deep the mate is, but probably takes longer if you already know the mate distance.

I'm really perplexed at how Mr Genius mate finder developed a super fast generic mate finder over 25 years ago that's faster than anything I've seen today. I think he may have written code for ChessMaster, but it's all in machine language. Hans Berliner, CMU Prof and AI developer, wasn't very successful with his fast mate finder, however, he was more interested in OTB rating. It was unfortunate that his Korean student, a 1500 player, , who went on to develop Deep Blue never asked Hans, a 2450 player, for advice. I can just imagine what the tow of them could have done together.