I think that it may be interesting to have chess softwares that get a position with a forced mate and find the smallest tree to prove the mate.
Note that the mate does not have to be the shortest mate and mate in 3 with a forced line that means only 5 plies is better than mate in 2 when black has many legal moves in the first move so the tree is bigger.
For example Qxh7+ should be better than Qh6 based on size of the tree in the following position because the number of plies to calculate to prove the mate is smaller for Qxh7+ and it is only 5 plies in a single line.
[d]4qrk1/5p1p/4pBp1/8/8/R7/7Q/6K1 w - - 1 1
1)Is there a program to find not the shortest mate but the smallest tree that means Qxh7+ Kxh7 Rh3+ Kg8 Rh8#?
2)Is there a program that does not generate all black's moves to prove white has mate in 2 with Qh6 in the relevant position?
Note that humans do not need to consider all legal moves to be sure that black has no way to threat check and no way to protect g7?
They find that the black queen cannot help and cannot threat check against the opponent king but do not search all moves of the black queen like computers.
generating mate trees
Moderators: hgm, Rebel, chrisw
-
- Posts: 10300
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: generating mate trees
Brute force chest examines 116 nodes.
Q:\>chest319 -b -M 8000 -z9 MTREE.EPD
4qrk1/5p1p/4pBp1/8/8/R7/7Q/6K1 w - - acn 116; acs 0; bm Qh6; ce 32764; dm 2; pv Qh6 g5 Qg7#;
Q:\>chest319 -b -M 8000 -z9 MTREE.EPD
4qrk1/5p1p/4pBp1/8/8/R7/7Q/6K1 w - - acn 116; acs 0; bm Qh6; ce 32764; dm 2; pv Qh6 g5 Qg7#;
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 4889
- Joined: Thu Mar 09, 2006 6:34 am
- Location: Pen Argyl, Pennsylvania
Re: generating mate trees
Honey-X5i - default mode single core no tbUri Blass wrote: ↑Wed Sep 11, 2019 5:24 pm I think that it may be interesting to have chess softwares that get a position with a forced mate and find the smallest tree to prove the mate.
Note that the mate does not have to be the shortest mate and mate in 3 with a forced line that means only 5 plies is better than mate in 2 when black has many legal moves in the first move so the tree is bigger.
For example Qxh7+ should be better than Qh6 based on size of the tree in the following position because the number of plies to calculate to prove the mate is smaller for Qxh7+ and it is only 5 plies in a single line.
[d]4qrk1/5p1p/4pBp1/8/8/R7/7Q/6K1 w - - 1 1
1)Is there a program to find not the shortest mate but the smallest tree that means Qxh7+ Kxh7 Rh3+ Kg8 Rh8#?
2)Is there a program that does not generate all black's moves to prove white has mate in 2 with Qh6 in the relevant position?
Note that humans do not need to consider all legal moves to be sure that black has no way to threat check and no way to protect g7?
They find that the black queen cannot help and cannot threat check against the opponent king but do not search all moves of the black queen like computers.
info depth 2 seldepth 2 multipv 1 score mate 2 nodes 123 nps 61500 tbhits 0 time 2 pv h2h6 e6e5 h6g7
bestmove h2h6 ponder e6e5
I'm not following what you suggesting , but the tree is much bigger with Qxh7.
-
- Posts: 1470
- Joined: Mon Apr 23, 2018 7:54 am
Re: generating mate trees
I think Uri is taking the view from the player giving the mate, so the tree is the tree of possible defensive moves. To prove it really is a forced mate, you don't need to look at other moves that are possible for the mating side. The final tree will have only one move for the mater at each position, but all moves for the mated at each position.
-
- Posts: 10300
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: generating mate trees
Yesjp wrote: ↑Thu Sep 12, 2019 2:06 amI think Uri is taking the view from the player giving the mate, so the tree is the tree of possible defensive moves. To prove it really is a forced mate, you don't need to look at other moves that are possible for the mating side. The final tree will have only one move for the mater at each position, but all moves for the mated at each position.
It is exactly what I mean.
The engine may search more lines but I am interested in the smallest tree to prove a mate and not the shortest mate and if there is an engine that can find it.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: generating mate trees
Chest will output the proof tree (it is an option).
I do not know if the UCI version does it, but the command line version does
I do not know if the UCI version does it, but the command line version does
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: generating mate trees
A large tree doesn't always make it more difficult from a human perspective. Humans are very adept in grouping all irrelevant moves, and considering them as one.
-
- Posts: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: generating mate trees
Sample chest solution tree:
Code: Select all
chest319 -b -L < q:\dme.epd
4qrk1/5p1p/4pBp1/8/8/R7/7Q/6K1 w - - acn 116; acs 0; bm Qh6; ce 32764; dm 2; pv Qh6 g5 Qg7#;
Qh6 g5 Qg7#
Qxg5#
e5 Qg7#
Qd8 Qg7#
Qc8 Qg7#
Qb8 Qg7#
Qa8 Qg7#
Qe7 Qg7#
Qd7 Qg7#
Qc6 Qg7#
Qb5 Qg7#
Qa4 Qg7#
end of solution tree
Total Time (virt) = 0.227 sec
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
-
- Posts: 1010
- Joined: Thu Sep 01, 2011 2:49 pm
Re: generating mate trees
So logically, the attacking side always delivers checks until mate is delivered, and the defensive side has only one way to parry the check. Otherwise I can't imagine a smaller tree if it is not a check forcing the defensive side to move or defend its king.jp wrote: ↑Thu Sep 12, 2019 2:06 amI think Uri is taking the view from the player giving the mate, so the tree is the tree of possible defensive moves. To prove it really is a forced mate, you don't need to look at other moves that are possible for the mating side. The final tree will have only one move for the mater at each position, but all moves for the mated at each position.
I told my wife that a husband is like a fine wine; he gets better with age. The next day, she locked me in the cellar.
-
- Posts: 1470
- Joined: Mon Apr 23, 2018 7:54 am
Re: generating mate trees
Yes, but it's only a subset of all positions with forced mate that have a single branch like that.