generating mate trees

Discussion of anything and everything relating to chess playing software and machines.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Uri Blass
Posts: 8526
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

generating mate trees

Post by Uri Blass » Wed Sep 11, 2019 3: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.



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.

Dann Corbit
Posts: 9894
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: generating mate trees

Post by Dann Corbit » Wed Sep 11, 2019 9:40 pm

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#;
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.

MikeB
Posts: 3267
Joined: Thu Mar 09, 2006 5:34 am
Location: Pen Argyl, Pennsylvania

Re: generating mate trees

Post by MikeB » Wed Sep 11, 2019 10:57 pm

Uri Blass wrote:
Wed Sep 11, 2019 3: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.



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.
Honey-X5i - default mode single core no tb
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.

jp
Posts: 699
Joined: Mon Apr 23, 2018 5:54 am

Re: generating mate trees

Post by jp » Thu Sep 12, 2019 12:06 am

MikeB wrote:
Wed Sep 11, 2019 10:57 pm
I'm not following what you suggesting , but the tree is much bigger with Qxh7.
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.

Uri Blass
Posts: 8526
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: generating mate trees

Post by Uri Blass » Thu Sep 12, 2019 3:30 pm

jp wrote:
Thu Sep 12, 2019 12:06 am
MikeB wrote:
Wed Sep 11, 2019 10:57 pm
I'm not following what you suggesting , but the tree is much bigger with Qxh7.
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.
Yes

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.

Dann Corbit
Posts: 9894
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: generating mate trees

Post by Dann Corbit » Thu Sep 12, 2019 3:33 pm

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
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.

User avatar
hgm
Posts: 23451
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: generating mate trees

Post by hgm » Thu Sep 12, 2019 4:03 pm

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.

Dann Corbit
Posts: 9894
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: generating mate trees

Post by Dann Corbit » Fri Sep 13, 2019 3:27 am

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.

User avatar
MikeGL
Posts: 872
Joined: Thu Sep 01, 2011 12:49 pm

Re: generating mate trees

Post by MikeGL » Fri Sep 13, 2019 4:05 am

jp wrote:
Thu Sep 12, 2019 12:06 am
MikeB wrote:
Wed Sep 11, 2019 10:57 pm
I'm not following what you suggesting , but the tree is much bigger with Qxh7.
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.
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.
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.

jp
Posts: 699
Joined: Mon Apr 23, 2018 5:54 am

Re: generating mate trees

Post by jp » Fri Sep 13, 2019 12:18 pm

MikeGL wrote:
Fri Sep 13, 2019 4:05 am
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.
Yes, but it's only a subset of all positions with forced mate that have a single branch like that.

Post Reply