generating mate trees

[Uri Blass]

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.

[Dann Corbit]

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

[MikeB]

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.

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]

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]

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]

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

[hgm]

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]

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

[MikeGL]

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.

[jp]

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.