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.Chessnut1071 wrote: ↑Sun Sep 17, 2023 5:37 pm"I don't see any other approach than a brute-force alpha-beta for that."
Exactly my point.
Checkmate evaluation functions
Moderator: Ras
-
- Posts: 2695
- Joined: Tue Aug 30, 2016 8:19 pm
- Full name: Rasmus Althoff
Re: Checkmate evaluation functions
Rasmus Althoff
https://www.ct800.net
https://www.ct800.net
-
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Checkmate evaluation functions
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.
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.
-
- Posts: 313
- Joined: Tue Aug 03, 2021 2:41 pm
- Full name: Bill Beame
Re: Checkmate evaluation functions
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.hgm wrote: ↑Sun Sep 17, 2023 9:08 pm 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.
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.
-
- Posts: 969
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
- Full name: Jörg Oster
Re: Checkmate evaluation functions
I give a big bonus for checking moves, for both sides.Chessnut1071 wrote: ↑Mon Sep 18, 2023 6:15 amThe 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.hgm wrote: ↑Sun Sep 17, 2023 9:08 pm 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.
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.
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
And I really mean a LOT ...
Jörg Oster
-
- Posts: 313
- Joined: Tue Aug 03, 2021 2:41 pm
- Full name: Bill Beame
Re: Checkmate evaluation functions
My program found the solution in 8,430,340 nodes; 56 sec.Joerg Oster wrote: ↑Mon Sep 18, 2023 11:37 amI give a big bonus for checking moves, for both sides.Chessnut1071 wrote: ↑Mon Sep 18, 2023 6:15 amThe 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.hgm wrote: ↑Sun Sep 17, 2023 9:08 pm 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.
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.
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.Dedicated mate solvers like Chest and Gustav probably do and know a LOT more!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
And I really mean a LOT ...
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.
-
- Posts: 969
- Joined: Fri Mar 10, 2006 4:29 pm
- Location: Germany
- Full name: Jörg Oster
Re: Checkmate evaluation functions
For a very basic PNS implementation, you may take a look here: https://github.com/joergoster/Stockfish/tree/matefish2Chessnut1071 wrote: ↑Tue Sep 19, 2023 12:43 am ...
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.
Jörg Oster
-
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Checkmate evaluation functions
It is not so much time that would be wasted, as characters source code.Chessnut1071 wrote: ↑Mon Sep 18, 2023 6:15 am 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.
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.
-
- Posts: 1396
- Joined: Wed Mar 08, 2006 10:15 pm
- Location: San Francisco, California
Re: Checkmate evaluation functions
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.Joerg Oster wrote: ↑Mon Sep 18, 2023 11:37 am 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.


-
- Posts: 28353
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Checkmate evaluation functions
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).