mate search in QS for drop games

[hgm]

A standard capture search for drop games is not reliable, because in the proces of capturing the hands get filled. So often capturing a piece gives you the piece in hand that you were still lacking for performing a checkmate with drops. This means your opponent now has to defend against that mate, and thus cannot afford to recapture you, even if the piece that made the original capture is now hanging.

Testing if you have a forced mate, even if it is through check-drops only, in all QS nodes, is very expensive, though. Some Shogi engines therefore only test for the most obvious mates, e.g. mate by two consecutive drops (with one evasion in between), and will miss any deepr ones. To find arbitraily deep mates, you could use a proof-number search, but that is also very expensive. (From what I understand this is more like a minimax search than like alpha-beta.)

I wonder if the following would work to search for checkmates: iteratively deepen an alpha-beta search of checking moves plus evasions, which ends in a check. Evaluate the in-check node as MATED + 100*NrOfEvasions. Search with a null window at MATED + 350 (say). That is MATE - 350 for the checking side. This fails high if against any defense you can create (after nN moves) a position where the opponent is still in check, and has at most 3 evasions. This keeps your hope of checkmating him alive, and you do another iteration. If he can defend such that he can always end up in a position with 4 or more evasions you will fail low. In that case you assume he escapes, and give up.

You could require a smaller and smaller number of evasions as the search deepens, so that it must be really promising in order to continue when it gets very expensive. And stop at some (generous) maximum depth.

[Evert]

Might be worth a try.

I've been meaning to give proof-number search a try, but so far did not get around to it. I suspect it might be interesting for answering a yes/no question about whether the current position is a fortress draw or not as well.

What I do in SjaakII is a fairly straight-forward mate search with a few tweaks to keep the cost down.

The first of these is a cache to remember whether I tried this position before. This is separate from the main transposition table, although I do store any mate I find there too.

I use a staged move generator for his part of the code, which helps a lot.

I also limit the depth of the mate I'm looking for, based on the remaining depth, so at depth 1 or 2 I may look for mate-in-two, but I only look for mate-in-three at depth 3 or 4. I haven't tested whether this is particularly useful though (you need longer time-control games to test whether this works or not).

I do a separate test near the root (so at large remaining depth), mainly to check that I'm not going to be drop-mated suddenly. Again, I increase the depth of the mate with the remaining depth.

My philosophy was that I cared more about avoiding sudden death drops by my opponent than about inflicting them (so loss-avoiding rather than win-seeking), but I'm not sure if this is particularly successful in that regard.

I should close off by saying what this was worth in testing, but I don't remember. I don't think it was spectacular though (I do remember that not limiting it fairly aggressively makes it too expensive though).

EDIT: apparently this was about +15 Elo. Not limiting it sufficiently was about -140, but I terminated that one early.

[hgm]

Proof-number search seems ideal for tsume problems, where you either checkmate or run out of checks. But I don't see any good reasons for not being interested in mates through a quiet move. And then 'disproof' is usually not possible. Yet some Shogi engines seem to do it. (Haven't really figured out yet for which purpose exactly.)

I don't really understand what you are saying. If the remaining depth is N, you should automatically find all tsume mates in N, due to the check extension. So there seems to be no need for a separate mate search.

BTW, in my first post, the window should of course have been {MATE-250, MATE} when searching the check drops, and not a null window. Otherwise you would not know when to stop iterating, and not work hard enough to find an actual mate.

The problem with these kind of searches is that it is very easy to succumb to paranoia, spending huge effort on mate attempts that stand no chance of succeeding. When a King is inside its own safe area, controlled by his own pieces, even with a large number of pieces in hand all you could do is drop them one by one to be gobbled up for no purpose. OTOH, it is very common tsume attacks start with an unsafe contact check, on a square only protected by King. When the King then withdraws he is next to a square where a safe check drop can take place. This might not be a problem if he is fleeing into a direction that is safe, hiding amongst his own pieces with no enemies there. But usually it means he will be driven against the edge or in the arms of a lurking opponent, so then he is sort of forced to capture the checker. This can draw him out into the open, or towards an opponent infestation.

So I guess it is really important to have a heuristic to determine which check drops are worth trying in a mate search. In any case safe check drops should be tried. They might even be worth an extension, in a depth-limited mate search. But unsafe check drops on squares protected only by the King are worth trying if they border a square you already attack, so that after capture you could drop something there (provided you have something left to drop). By pruning unsafe check drops that can be gobbled up by the King without bringing the latter closer to peril, you prevent pointless solo suicide attacks on a completely safe King fortress, which otherwise would take a lot of nodes to refute, if many pieces build up in hand during QS.

[Evert]

Proof-number search seems ideal for tsume problems, where you either checkmate or run out of checks. But I don't see any good reasons for not being interested in mates through a quiet move. And then 'disproof' is usually not possible. Yet some Shogi engines seem to do it. (Haven't really figured out yet for which purpose exactly.)

From what I remember reading (in the context of chess), PN search tends to meander a bit when a mate sequence involves quiet moves. I'll see if I can find the paper again.

I don't really understand what you are saying. If the remaining depth is N, you should automatically find all tsume mates in N, due to the check extension. So there seems to be no need for a separate mate search.

Hmm... you're right. I guess the issue is that I prune most drop moves near the tips, before checking if they are checking moves. That may account for the issue, but it suggests that there is more to be had here by being a bit more clever about it.
That means the Elo gain I see probably comes from not overlooking quick mates near the root of the search (which used to happen somewhat regularly).

The problem with these kind of searches is that it is very easy to succumb to paranoia, spending huge effort on mate attempts that stand no chance of succeeding. When a King is inside its own safe area, controlled by his own pieces, even with a large number of pieces in hand all you could do is drop them one by one to be gobbled up for no purpose. OTOH, it is very common tsume attacks start with an unsafe contact check, on a square only protected by King. When the King then withdraws he is next to a square where a safe check drop can take place. This might not be a problem if he is fleeing into a direction that is safe, hiding amongst his own pieces with no enemies there. But usually it means he will be driven against the edge or in the arms of a lurking opponent, so then he is sort of forced to capture the checker. This can draw him out into the open, or towards an opponent infestation.

So I guess it is really important to have a heuristic to determine which check drops are worth trying in a mate search. In any case safe check drops should be tried. They might even be worth an extension, in a depth-limited mate search. But unsafe check drops on squares protected only by the King are worth trying if they border a square you already attack, so that after capture you could drop something there (provided you have something left to drop). By pruning unsafe check drops that can be gobbled up by the King without bringing the latter closer to peril, you prevent pointless solo suicide attacks on a completely safe King fortress, which otherwise would take a lot of nodes to refute, if many pieces build up in hand during QS.

Sounds reasonable. It also depends on what you want from the code: do you quickly want to find some mates that you would otherwise miss, or do you want to reliably detect mates? In the first case you can cut more corners and not worry too much about catching everything - as long as it helps some it's good.
Obviously it's better if you can do the second for the same price.

I don't do any sort of extensions, by the way, because I want to keep this as cheap as possible. In a sense you might say that I do a crude form of iterative deepening in the sense that if I searched the position for a mate-in-N now, it will be searched for a mate-in-N+1 on the next iteration of the iterative deepening loop at the root. It seemed like a good idea at the time, I'm less sure now.

[hgm]

In Shokidoki I selectively generate check-drops, by testing all squares adjacent to King for emptiness, and then test all the piece types that could check from there for being in hand. And if a slider is in hand, also try dropping it along the rays through the King. But I only do that for depth >= 1. Trying it in QS always gave me search explosion.

My guess is that trying to be exhaustive would be so expensive that it backfires. So I aim to only do what is cheap and sufficiently dangerous. After all, the current search already does a pretty good job.

When I keep a 'protection board' in each node that records all to-squares of board moves, and the neighbors of to-squares that are also neighbors of King, I could use that to filter the check drops: do not drop on squares adjacent to King where you are not protected (because the King attacks those), unless you lure the King next to a protected square by this. Shokidoki is mailbox, but the intersection of King neighborhood and to-square neighborhood can be cheaply obtained by listing the steps from King to such intersection squares in a null-terminated list, as as function of the King - toSquare step.

The only problem is distant check-drops. These are not attacked by King, so they might not be attacked at all, in which case you would want to try those even if they are not protected. And it is more difficult to know what the opponent attacked. You could try to use the 'protection board' from the parent node, but it is no longer up to date, as one of the pieces was just moved. You could explicitly test for each distant drop on an unprotected square whether the last-moved piece attacks it, to prevent you would make an unsafe check drop. But you might refrain from making a perfectly safe check drop because you imagine the square is still under attack, while the piece doing that has just been moved away. You could explicitly test whether the moved piece attacked the drop square,( and no longer attacks it now), but that still would not guarantee there is no other piece that also attacked it.

Of course you could just forget about distant checks, justifying this by the assumption they are on average less dangerous, as they can be evaded by interposing something. That would of course make you miss a lot of mates, but there would be plenty of mates by contact checks only, and even detecting only those should be an improvement. Interposition evasions are very troublesome with regard to search explosion, as it is always possible to 'renew' the check by capturing the interposed piece, and this gives the checker more piece in hand to continue his attack. So perhaps mates by distant check drops should just be classified as 'too difficult/expensive to detect beyond the normal search horizon'. My expectation is that it would already buy you a lot to foresee mates of the type where you have, say, Pc6 and the opponent Kc9, where you play 1. S@c8 {next to c7 attacked by the Pawn} 1... Kxc8 (1... Kd8 2. G@d7 Ke9 3. G@e8#) 2. G@c7 Kb9/c9/d9 3. G@b8/c8/d8#. This motif is so common, and when you are taken completely by surprise when the opponent 'sacrifices' a Rook by RxG to complete the material for this plan which you had counted on recapturing, it makes your QS very unreliable.

[Evert]

In Shokidoki I selectively generate check-drops, by testing all squares adjacent to King for emptiness, and then test all the piece types that could check from there for being in hand.

The funny thing is that I do the same thing for SjaakII, but only in the mate search.

The reason for this is that I first wrote a normal search, with the full move generator. However, the move generator is flexible in that the worker function can be told very easily to restrict what it generates using bitmasks (one for from-squares, one for to-squares, one for drop-pieces and one for promotion choices). This is used for capture generation in QS and for evasion generation while in check. When I added the mate search I wrote the staged move generator using the existing worker.

It wouldn't be hard to make the main search use the staged generator as well, but I didn't get round to that yet. It's on the TODO list.

And if a slider is in hand, also try dropping it along the rays through the King. But I only do that for depth >= 1. Trying it in QS always gave me search explosion.

Also if you only do it at depth=0? I would not bother with larger QS depths, since mate scores in QS cannot be trusted in general.

My guess is that trying to be exhaustive would be so expensive that it backfires. So I aim to only do what is cheap and sufficiently dangerous. After all, the current search already does a pretty good job.

Quite.

The only problem is distant check-drops. These are not attacked by King, so they might not be attacked at all, in which case you would want to try those even if they are not protected. And it is more difficult to know what the opponent attacked. You could try to use the 'protection board' from the parent node, but it is no longer up to date, as one of the pieces was just moved. You could explicitly test for each distant drop on an unprotected square whether the last-moved piece attacks it, to prevent you would make an unsafe check drop. But you might refrain from making a perfectly safe check drop because you imagine the square is still under attack, while the piece doing that has just been moved away. You could explicitly test whether the moved piece attacked the drop square,( and no longer attacks it now), but that still would not guarantee there is no other piece that also attacked it.

Of course you could just forget about distant checks, justifying this by the assumption they are on average less dangerous, as they can be evaded by interposing something. That would of course make you miss a lot of mates, but there would be plenty of mates by contact checks only, and even detecting only those should be an improvement.

I include distant drops, but I have no idea about cost/benefit. Even if you don't include drop checks in the mate search though the normal search (with help of the check extension) should help it find mates that start with one.

[hgm]

Also if you only do it at depth=0? I would not bother with larger QS depths, since mate scores in QS cannot be trusted in general.

Currently all QS nodes have d=0 in Shokidoki, because the depth that is passed to the daughter is derived from the IID loop counter, (which starts at 1), and not from the depth argument. This could be changed, of course. But this is not completely trivial, as it also affects hashing.

But the aim is not to have QS return a reliable mate score, but to prevent QS counts itself rich (or poor) by counting on captures that are punished by mate. The mate detetion is solely for the purpose of making such captures fail low. E.g. my King is on g1, facing an opponent Silver on g3. When he gets a Gold in hand he will play G@g2#. If QS starts with his move he can play RxG, and it would currently be considered harmless when the G is protected and the R (after the capture) is hanging, as R>G. While in reality I will not only be losing a full G, but it is in fact very quationable whether I will be able to avert the mate at all. If there is something else to trade, like BxB, the RxG can be postponed to deeper levels of the QS, but remains just as deadly.

So I would like the QS to realize that the G is effectively unprotected, no matter how many of your own pieces can recapture it. If any recapture of the Rook would return a mated-in-1 score rather than the gain of a Rook, then it would be forced to stand pat after the loss of the Gold. Which is more correct.

[hgm]

Kind of shocking that SPEAR doesn't seem to have perfect mate detection either. It was in the process of totally grinding Shokidoki to pieces (SPEAR at +28, Shokidoki at -16), and then allows itself to be checkmated in 5!

Code: Select all

[Event "Edited game"]
[Site "MAKRO-PC"]
[Date "2015.04.28"]
[Round "-"]
[White "-"]
[Black "-"]
[Result "0-1"]
[Variant "shogi"]
[Annotator "3. +1.79   1... -0.08"]

1. c4= i6 {-0.08/14 11} 2. h4= Sd8 {-0.16/13 9} 3. Sd2= {+1.79/12 12} Kf8
{-0.12/15 13} 4. Sf2= {+2.15/12 6} Sg8 {+1.00/14 8} 5. f4= {+1.88/12 2.7}
b6 {+0.88/15 12} 6. h5 {+1.91/12 2.7} c6 {+0.60/13 12} 7. Sf3=
{+1.94/12 15} b5 {+0.40/15 15} 8. h6 {+3.05/12 13} hxh6 {+0.72/13 2.5} 9.
Rxh6= {+1.82/12 7} P@h7 {+1.52/14 10} 10. Rh2= {+0.93/12 15} b4
{+1.80/15 10} 11. bxb4= {+0.91/12 15} Rxb4 {+1.48/15 39} 12. Gc2=
{+1.12/12 24} Rxc4 {+1.36/14 22} 13. Sc3= {+3.84/12 5} Rc5 {+0.40/14 21}
14. P@b8 {+3.75/12 10} Nc7 {+0.76/14 13} 15. b9+ {+2.64/12 28} Nd5
{-0.16/13 1:03} 16. Sd4= {+3.30/11 28} Rxc2+ {-2.12/13 32} 17. Rxc2=
{+3.78/12 7} P@b4 {-2.16/12 10} 18. R@b8 {+7.04/11 28} G@b3 {-2.36/12 13}
19. Re2= {+4.19/11 26} Gxb2= {-3.16/13 21} 20. Rxb2= {+6.09/11 27} g6
{-3.64/11 13} 21. G@e4 {+4.76/10 27} B@c1 {-3.08/11 18} 22. Re2=
{+4.09/11 26} Bxd4 {-2.60/12 20} 23. dxd4= {+4.05/10 26} S@d3 {-3.80/11 19}
24. dxd5 {+4.05/9 25} Sxe2+ {-3.48/10 15} 25. Sxe2= {+3.62/10 24} R@b3
{-3.12/10 21} 26. S@a2 {+4.30/8 24} Rb2+ {-4.32/9 2.8} 27. B@d4
{+3.83/10 24} b3+ {-2.72/11 20} 28. Bxb2= {+3.72/9 24} +Pxb2= {-2.04/11 29}
29. +Pxa9 {+3.12/8 23} +Pxa1= {-2.28/10 36} 30. R@c2 {+3.28/9 24} L@c5
{-3.96/10 59} 31. P@c3 {+3.11/10 23} +Pxb1= {-3.92/10 16} 32. Rxb1+
{+4.62/10 22} Lxc3= {-4.96/12 17} 33. Rxc3= {+5.60/12 23} B@d2
{-5.40/12 15} 34. Kf2= {+5.05/12 21} Bxc3+ {-5.00/12 16} 35. +Rxc1=
{+5.05/10 21} +Bg7= {-5.12/11 57} 36. N@f5 {+5.74/8 22} +Bh8 {-2.80/9 23}
37. d6 {+5.95/7 21} dxd6 {-2.56/9 16} 38. L@e5 {+4.25/8 21} Gfe8
{-1.16/8 11} 39. B@b7 {+7.68/8 20} Gde9 {-1.32/9 11} 40. Bxc6+ {+7.49/8 21}
N@h3 {-1.12/9 13} 41. P@d7 {+7.81/9 20} Sxd7 {-1.52/10 10} 42. Nxe7+
{+7.18/9 19} Gxe7 {+1.72/9 2.5} 43. Lxe7+ {+7.18/9 19} Kxe7 {+1.44/9 13}
44. +Bb6 {+7.82/9 19} Ge8 {+1.16/8 10} 45. G@i2 {+7.05/9 20} Nxi1+
{+1.24/9 9} 46. Gxi1= {+6.63/9 19} R@b2 {+1.36/9 15} 47. N@f5 {+8.07/9 18}
Kf8 {+1.44/10 6} 48. +Rxb2= {+9.41/10 19} +Bxb2= {+1.12/9 21} 49. L@e7
{+9.68/9 18} N@f6 {+0.16/8 39} 50. Lxe8+ {+9.97/9 18} Sxe8 {-0.64/8 6} 51.
R@b9 {+8.44/9 18} Nxe4 {-1.04/8 21} 52. exe4= {+9.42/9 17} G@f9
{-0.88/8 12} 53. +Bc6 {+10.57/8 18} +Bf6= {-1.72/7 9} 54. +Bxd6
{+10.41/7 16} P@e7 {-0.60/8 8} 55. N@d5 {+10.16/7 17} L@d8 {-0.16/7 20} 56.
P@d7 {+11.49/8 17} Lxd7 {-3.68/8 17} 57. Ndxe7+ {+13.06/8 15} +Bxe7
{-7.68/9 39} 58. Nxe7+ {+16.82/8 15} Sxe7 {-400.00/9 1:03} 59. +Bxd7
{+16.82/7 15} R@d2 {-10.64/8 55} 60. Rb8+ {+16.53/7 13} P@e8 {-9.96/8 33}
61. +Bxe7 {+14.85/7 14} Kxe7 {-400.00/8 44} 62. B@b4 {+16.47/7 13} L@d6
{-11.92/8 38} 63. Bxd2= {+12.71/8 15} Lxd2+ {-6.00/6 2.9} 64. P@h8
{+13.59/7 14} +Lxe2= {-5.72/6 6} 65. Gxe2= {+11.52/8 16} B@d4 {-5.80/7 14}
66. S@e3 {+11.52/8 16} Bxh8 {-5.44/6 3} 67. L@e5 {+11.37/7 15} Kf8
{-4.48/7 7} 68. L@e6 {+11.18/7 15} L@e9 {-5.92/7 17} 69. Le7+ {+13.76/9 14}
Kg7 {-6.36/9 8} 70. +Lxe8 {+13.99/9 14} Lxe8 {-5.88/9 8} 71. Lxe8+
{+13.84/8 13} Gxe8 {-5.96/8 7} 72. +Rxe8 {+13.91/8 15} S@f9 {-5.96/7 5} 73.
+Rd8 {+12.56/8 12} Bg9 {-6.12/6 4} 74. G@e9 {+13.88/7 14} h6 {-6.60/7 9}
75. Gxf9 {+15.97/7 13} Sxf9 {-6.32/6 2.5} 76. R@d9 {+15.71/7 12} G@f8
{-5.92/7 7} 77. S@e7 {+14.75/7 14} B@a6 {-7.16/6 5} 78. Re9+ {+16.20/7 12}
P@e8 {-8.76/7 16} 79. Sxe8+ {+18.49/8 13} Bb5 {-10.84/8 19} 80. P@d7
{+18.95/8 13} P@d9 {-14.04/7 7} 81. +Rdxd9 {+23.38/8 12} P@d4 {-16.12/7 5}
82. +Sxf8 {+26.05/9 13} d3+ {-16.72/7 4} 83. Gxd3= {+28.33/8 11} Bxd3+
{-15.16/8 8} 84. +Sxg9 {+29.39/9 13} L@f3 {+399.80/9 1.4}
{White resigns} 0-1

Strange it can overlook such a simple mate. Shokidoki already sees it at 5 ply, as expected with a tsume mate-in-5. (84... L@f3 85. Kxf3 N@g5 86. Kg4 +Be2 87. Lf3 +Bxf3 88. Kf5 G@f6#) I guess it must be because one of the checks (86... +Be2) is not through a drop,