Checkmate evaluation functions

[Ras]

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

No, completely not your point. Your point was how to faster find a mate if a mate does exist - not proving that there is no mate.

[hgm]

Once you have established the mate, and can limit the depth of all other branches with mate-distance pruning, the only way left to reduce the size of the tree is to pick cut-moves for the defending side that lead to minimal branching of the attacking side. Picking the capture of the most-valuable piece seems a good way to do that. Or, perhaps even better, capturing the most mobile piece. (Although valuable pieces with low mobility because of unfavorable placement might be able to acquire high mobility later in the tree. So you might want to weigh in future mobility as well, or value as a poor-man's estimate for that.)

Of course you want to prevent picking defensive moves that in the end turn out not to be cut moves at all, because they defend so poorly that you do get checkmated faster than in the main line. That would be a pure waste of time. So you should not completely discard the defender's King Safety; if the King position is very awkward you might want to give priority to moves that relieve it, to at least have a chance that the move will be a cut move, rather than focusing on reducing the branching ratio.

But most attacker moves will be completely pointless. After eliminating one or two pieces that were dangerous for the King in those lines all hope for a checkmate will probably have gone, and you can focus on decimating the opponen't forces.

[Chessnut1071]

Once you have established the mate, and can limit the depth of all other branches with mate-distance pruning, the only way left to reduce the size of the tree is to pick cut-moves for the defending side that lead to minimal branching of the attacking side. Picking the capture of the most-valuable piece seems a good way to do that. Or, perhaps even better, capturing the most mobile piece. (Although valuable pieces with low mobility because of unfavorable placement might be able to acquire high mobility later in the tree. So you might want to weigh in future mobility as well, or value as a poor-man's estimate for that.)

Of course you want to prevent picking defensive moves that in the end turn out not to be cut moves at all, because they defend so poorly that you do get checkmated faster than in the main line. That would be a pure waste of time. So you should not completely discard the defender's King Safety; if the King position is very awkward you might want to give priority to moves that relieve it, to at least have a chance that the move will be a cut move, rather than focusing on reducing the branching ratio.

But most attacker moves will be completely pointless. After eliminating one or two pieces that were dangerous for the King in those lines all hope for a checkmate will probably have gone, and you can focus on decimating the opponen't forces.

The best generic variables I found for defense were 1) check 2) history & previous move 3) slider captures (B,R,Q). They work for offensive as well. Anything else has marginal significance in comparison. The other offensive significant variable, in some forced line, the number of enemy king moves. With Shogi and near Shogi this is number 1.

I think you mentioned before that history, although important, took too many resources in Fairly-Max. I use the following for history:

where pm = piece*100 + square; History[33,3264]
++History[ply, pm] increments when an attack line, or defensive line, fails. History[ply,0] = pm for previous move. This takes almost no time, but does require storage space, which is not a problem on most system today.

I think you mentioned that you don't waste time sorting; however, how do you avoid going down unlikely lines without the sort?

Also, I don't use iterative deepening, although I have an option for that, because the puzzle mates I'm working with give the mate depth. I only use ID when I can't find the mate at the specified ply. btw, after you fixed my TT I never missed a mate up to 22-ply that I know of. thx.

[Joerg Oster]

Once you have established the mate, and can limit the depth of all other branches with mate-distance pruning, the only way left to reduce the size of the tree is to pick cut-moves for the defending side that lead to minimal branching of the attacking side. Picking the capture of the most-valuable piece seems a good way to do that. Or, perhaps even better, capturing the most mobile piece. (Although valuable pieces with low mobility because of unfavorable placement might be able to acquire high mobility later in the tree. So you might want to weigh in future mobility as well, or value as a poor-man's estimate for that.)

Of course you want to prevent picking defensive moves that in the end turn out not to be cut moves at all, because they defend so poorly that you do get checkmated faster than in the main line. That would be a pure waste of time. So you should not completely discard the defender's King Safety; if the King position is very awkward you might want to give priority to moves that relieve it, to at least have a chance that the move will be a cut move, rather than focusing on reducing the branching ratio.

But most attacker moves will be completely pointless. After eliminating one or two pieces that were dangerous for the King in those lines all hope for a checkmate will probably have gone, and you can focus on decimating the opponen't forces.

The best generic variables I found for defense were 1) check 2) history & previous move 3) slider captures (B,R,Q). They work for offensive as well. Anything else has marginal significance in comparison. The other offensive significant variable, in some forced line, the number of enemy king moves. With Shogi and near Shogi this is number 1.

I think you mentioned before that history, although important, took too many resources in Fairly-Max. I use the following for history:

where pm = piece*100 + square; History[33,3264]
++History[ply, pm] increments when an attack line, or defensive line, fails. History[ply,0] = pm for previous move. This takes almost no time, but does require storage space, which is not a problem on most system today.

I think you mentioned that you don't waste time sorting; however, how do you avoid going down unlikely lines without the sort?

Also, I don't use iterative deepening, although I have an option for that, because the puzzle mates I'm working with give the mate depth. I only use ID when I can't find the mate at the specified ply. btw, after you fixed my TT I never missed a mate up to 22-ply that I know of. thx.

I give a big bonus for checking moves, for both sides.
Captures are ranked by MVV.
If the defending side is in check, I give a bonus for capturing the checking piece, and a smaller one for intercepting the check.

For the side to mate:
Bonus for knight checks, and for queen/rook contact checks.
A bonus for pieces freeing a potential promotion square,
and a small bonus for advanced pawn pushes.
I also give a bonus for pieces attacking square(s) close to the opponent's king.
Plus a bonus for pieces able to eventually give check on the next move.

I'm also doing this for the root moves!
Together with some improvements to the search, this helped a lot!

This mate in 6 position initially took more than 90 seconds to solve. [d]1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - - Now, Matefish solves it in less than a second.

Code: Select all

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
info time 2 multipv 1 depth 1 seldepth 1 nodes 2 nps 1000 tbhits 0 score cp 0 pv f4f6
info time 6 multipv 1 depth 3 seldepth 8 nodes 4408 nps 734666 tbhits 0 score cp 0 pv f4f6
info time 6 multipv 1 depth 5 seldepth 4 nodes 4420 nps 736666 tbhits 0 score cp 0 pv f4f6
info time 6 multipv 1 depth 7 seldepth 11 nodes 4800 nps 800000 tbhits 0 score cp 0 pv f4f6
info string Success! Mate in 6 found!
info time 282 multipv 1 depth 9 seldepth 11 nodes 257722 nps 913907 tbhits 0 score mate 6 pv b8d7 d5d4 f4f6 e6d5 a7a8b a5a8 e5b8 b1f5 g5f5 e7e5 f5e5
bestmove b8d7 ponder d5d4

Dedicated mate solvers like Chest and Gustav probably do and know a LOT more!
And I really mean a LOT ...

[Chessnut1071]

Once you have established the mate, and can limit the depth of all other branches with mate-distance pruning, the only way left to reduce the size of the tree is to pick cut-moves for the defending side that lead to minimal branching of the attacking side. Picking the capture of the most-valuable piece seems a good way to do that. Or, perhaps even better, capturing the most mobile piece. (Although valuable pieces with low mobility because of unfavorable placement might be able to acquire high mobility later in the tree. So you might want to weigh in future mobility as well, or value as a poor-man's estimate for that.)

Of course you want to prevent picking defensive moves that in the end turn out not to be cut moves at all, because they defend so poorly that you do get checkmated faster than in the main line. That would be a pure waste of time. So you should not completely discard the defender's King Safety; if the King position is very awkward you might want to give priority to moves that relieve it, to at least have a chance that the move will be a cut move, rather than focusing on reducing the branching ratio.

But most attacker moves will be completely pointless. After eliminating one or two pieces that were dangerous for the King in those lines all hope for a checkmate will probably have gone, and you can focus on decimating the opponen't forces.

The best generic variables I found for defense were 1) check 2) history & previous move 3) slider captures (B,R,Q). They work for offensive as well. Anything else has marginal significance in comparison. The other offensive significant variable, in some forced line, the number of enemy king moves. With Shogi and near Shogi this is number 1.

I think you mentioned before that history, although important, took too many resources in Fairly-Max. I use the following for history:

where pm = piece*100 + square; History[33,3264]
++History[ply, pm] increments when an attack line, or defensive line, fails. History[ply,0] = pm for previous move. This takes almost no time, but does require storage space, which is not a problem on most system today.

I think you mentioned that you don't waste time sorting; however, how do you avoid going down unlikely lines without the sort?

Also, I don't use iterative deepening, although I have an option for that, because the puzzle mates I'm working with give the mate depth. I only use ID when I can't find the mate at the specified ply. btw, after you fixed my TT I never missed a mate up to 22-ply that I know of. thx.

I give a big bonus for checking moves, for both sides.
Captures are ranked by MVV.
If the defending side is in check, I give a bonus for capturing the checking piece, and a smaller one for intercepting the check.

For the side to mate:
Bonus for knight checks, and for queen/rook contact checks.
A bonus for pieces freeing a potential promotion square,
and a small bonus for advanced pawn pushes.
I also give a bonus for pieces attacking square(s) close to the opponent's king.
Plus a bonus for pieces able to eventually give check on the next move.

I'm also doing this for the root moves!
Together with some improvements to the search, this helped a lot!

This mate in 6 position initially took more than 90 seconds to solve. [d]1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - - Now, Matefish solves it in less than a second.

Code: Select all

position fen 1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - -
go mate 6
info time 2 multipv 1 depth 1 seldepth 1 nodes 2 nps 1000 tbhits 0 score cp 0 pv f4f6
info time 6 multipv 1 depth 3 seldepth 8 nodes 4408 nps 734666 tbhits 0 score cp 0 pv f4f6
info time 6 multipv 1 depth 5 seldepth 4 nodes 4420 nps 736666 tbhits 0 score cp 0 pv f4f6
info time 6 multipv 1 depth 7 seldepth 11 nodes 4800 nps 800000 tbhits 0 score cp 0 pv f4f6
info string Success! Mate in 6 found!
info time 282 multipv 1 depth 9 seldepth 11 nodes 257722 nps 913907 tbhits 0 score mate 6 pv b8d7 d5d4 f4f6 e6d5 a7a8b a5a8 e5b8 b1f5 g5f5 e7e5 f5e5
bestmove b8d7 ponder d5d4

Dedicated mate solvers like Chest and Gustav probably do and know a LOT more!
And I really mean a LOT ...

My program found the solution in 8,430,340 nodes; 56 sec.
We were probably victims of the same variable, check on the 1st move, which are dead ends for this particular position.

Since we can't tell whether the chip is faster or the program is more efficient, it's probably better to state the nodes searched as a way to compare.

I suspect the best mate finders probably aren't using our approach and may have a more sophisticated way to solve for mate. So far, I have not found any other approach, like PNS, explained well enough to program it.

[Joerg Oster]

...

I suspect the best mate finders probably aren't using our approach and may have a more sophisticated way to solve for mate. So far, I have not found any other approach, like PNS, explained well enough to program it.

For a very basic PNS implementation, you may take a look here: https://github.com/joergoster/Stockfish/tree/matefish2

[hgm]

I think you mentioned that you don't waste time sorting; however, how do you avoid going down unlikely lines without the sort?

Also, I don't use iterative deepening, although I have an option for that, because the puzzle mates I'm working with give the mate depth. I only use ID when I can't find the mate at the specified ply. btw, after you fixed my TT I never missed a mate up to 22-ply that I know of. thx.

It is not so much time that would be wasted, as characters source code.

Iterative Deepening is used to refute poor lines at low depth, and the refutation is remembered in the TT, so that in the next iteration little time is wasted in trying moves that failed to refute lines that could have been refuted by another move. In most cases the move that refutes a line would still refute it when you search one ply deeper, so that you would get a cutoff on the first (TT) move that you try.

I think it is a mistake to not do ID. Static criteria for how close you are to checkmating are bound to be very inaccurate if you are still far from the mate, but if you immediately do a maximum-depth search, they are the only guidence you have for refuting incorrect moves at, say, the first ply. If you would do a (much faster) pilot search of (say) half the intended depth, the leaves of that search would be much closer to the expected checkmate (in the branches that do lead to such a mate), so that the move choice for how to achieve the mate or prevent it closer to the root is much more realistic than any static criteria could give you for a mate that is still so far away. And the maximum depth should profit from that.

[JVMerlino]

This mate in 6 position initially took more than 90 seconds to solve. [d]1N1K1b1r/P3pPp1/4k1P1/rp1pB1RN/q4RP1/8/p2pB1p1/1b6 w - - Now, Matefish solves it in less than a second.

Well, that's a position that absolutely embarrasses Myrddin. With 8 cores it took just under 59 MINUTES to find the move and announce mate in 6.

[hgm]

KingSlayer needs 155M nodes to first see the mate (at 13 ply, 1:20 min). After that it only takes 22 sec to deepen to 16 ply (186M nodes).