Mate at a glance

[hgm]

Has anyone here used a static method to recognize if mate-in-1 is possible? For drop games it seems pretty important to consider mate-in-1 moves at any level in QS, to prevent the engine thinking it can happily recapture after the opponent just captured the piece he can drop with mate in 1.

I was thinking about setting a bit for every square in the opponent King neighborhood that is attacked by a piece of your own, or occupied by a piece of his (or off board). And then using this 8-bit code as an index in a table that indicates if a mate is in principle possible by checking and covering the remaining squares with a single piece, and if so by which piece type. It could then generate drops of that piece type (if in hand) on the indicated squares (if empty).

This would overlook mates through board moves, though. But perhaps detecting those should not be the goal, deep in QS. (As you could have played them before). You might occasionally waste time by dropping something that would not leave a way for the King to step out of check, but where the checker is immediately captured by a non-royal defender. Figuring out which squares are protected is much more expensive that to figure out which squares are attacked, though. (As the latter can be done as a side effect of generating your own captures, which you would do in QS anyway.)

[Gerd Isenberg]

Yep, most mates in one in IsiChess statically, including distant mates in N with pure delaying interposing defences. Xinix has Mate at a glance as well. To dense the 8 surrounding bits as index is a good idea and should speed things up for your dropping piece logic.

https://chessprogramming.wikispaces.com ... t+a+Glance
https://chessprogramming.wikispaces.com ... t%20Checks
http://www.stmintz.com/ccc/index.php?id=209201

[Ferdy]

Has anyone here used a static method to recognize if mate-in-1 is possible? For drop games it seems pretty important to consider mate-in-1 moves at any level in QS, to prevent the engine thinking it can happily recapture after the opponent just captured the piece he can drop with mate in 1.

I was thinking about setting a bit for every square in the opponent King neighborhood that is attacked by a piece of your own, or occupied by a piece of his (or off board). And then using this 8-bit code as an index in a table that indicates if a mate is in principle possible by checking and covering the remaining squares with a single piece, and if so by which piece type. It could then generate drops of that piece type (if in hand) on the indicated squares (if empty).

This would overlook mates through board moves, though. But perhaps detecting those should not be the goal, deep in QS. (As you could have played them before). You might occasionally waste time by dropping something that would not leave a way for the King to step out of check, but where the checker is immediately captured by a non-royal defender. Figuring out which squares are protected is much more expensive that to figure out which squares are attacked, though. (As the latter can be done as a side effect of generating your own captures, which you would do in QS anyway.)

I had it in the eval (mini-shogi) to detect mate in 1 drop move, when the side to move has an on-hand piece that when dropped can check opp king and that king cannot escape because its escape squares are attacked. But this does not give an extra points. Perhaps because I already have some bonus for attacking squares around the opp king. Also my qsearch only detects checking moves at depth -1 and 0. It is possible that I am in check, and need to evade so that my bonus for mate in 1 is wrong. I have not given much time improving the thing.

[hgm]

What do you mean by 'in eval'? That you have eval return +MATE when the stm can make such a drop? Do you also check whether the drop is safe (i.e. the checker cannot be captured)?

I am very surprised that such drop-mate detection would not help, Elo-wise. (Although it would probably do more in regular Shogi than in mini-Shogi.) I would have expected to be helpful, if it can be implemented without significant cost, as being checkmated by drops in a totally won position material-wise (like +25 or so) occurs quite frequently.

It might be like you say, though, that counting a mate when you are in check yourself spoils it. In Shokidoki I would not have that problem; it detects checks in every node, to extend for the evasion.

@Gerd: thanks for the links!

[Ferdy]

What do you mean by 'in eval'? That you have eval return +MATE when the stm can make such a drop? Do you also check whether the drop is safe (i.e. the checker cannot be captured)?

That is static evaluation. I simply give a bonus of rook value (due to my qsearch limitation) if the side to move is the color that will deliver the mate in one, otherwise only half of rook value. Yes the drop is safe, my mini is bitboard and all attack info needed were already available.

I already have existing eval that says if I have an on-hand piece type, and the board has an empty safe squares where my piece type can check the opp king from that square then give bonus (this includes sliders from a distant), the only difference is that I have not checked the opp king escape squares.

[hgm]

I have played a little bit with this now, and the results are very encouraging:

*) Adding 5 points (on the internal scale R=100, P=10) to the eval for the side to move for every attacked empty square next to the King, leads to a self-play score of 54.7% (1000 games). Note the side not to move gets nothing. (So this can be seen as a King-Safety-dependent side-to-move bonus.)

*) Recognizing mates through a contact check-drop (also counting a Knight jump as contact check) where the opponent has no pseudo-legal moves (other than with King) that can capture the checker, causes a self-play score of 54.45% (1000 games). Note that this does not detect mates where a piece that could capture the checker is pinned.

*) Doing both of this causes a self-play score of 61-62% (260 games).

*) This was for regular Shogi, but the latter also seems to work for mini-Shogi.

Against SPEAR it doesn't seem to help much, though. But SPEAR searches entirely different from Shokidoki. It is very good at detecting tsume mates. (It uses a proof-number search for that.) So it sees them much before Shokidoki does anyway, even when Shokidoki ses them 1 ply earlier that it did before. In addition, it builds very strong fortresses for its King, so that Shokidoki usually doesn't get a chance to attack squares near the King anyway. Because the PN search is rather expensive, SPEAR's tactical ability for non-mates is lacking, however, so that Shokidoki usually gobbles up material continually. So Shokidoki usually wins the games where it can avoid to be mated, by depleting SPEAR of most of its material that is not in the King fortress before it launches a final attack.

[hgm]

When I make the side-to-move bonus not only dependent on King Safety, but also on pieces in hand, it seems to work even better. In stead of awarding 5 points per attacked empty square near the King, I now award 3 + 2*handValue, where the handValue is the number of non-Pawns in hand, where Rook, Bishop and Generals count double. This was just a first try, but in self-play against the version that awards 5 points it scores 54% in 460 games. As the error there is still 2.3% this still needs some more games to be absolutely sure. 4% still is a pretty big improvement for such a simple change, even in self-play.

If the result holds, it could of course also mean that 5 points was not enough, and the improvement comes from the fact that the bonus is now on average much higher, because on average many more than 1 piece are in hand. (Especially if some count double...) But it could also be that the advantage of having the move indeed increases as there are more pieces in hand. There are a lot of parameters here that could be tuned: each combination of a square next to the King and a piece in hand could have its own weight. (Presumably the piece represents a higher danger if it would check on the square next to the King that is attacked.)

[Ferdy]

I have played a little bit with this now, and the results are very encouraging:

*) Adding 5 points (on the internal scale R=100, P=10) to the eval for the side to move for every attacked empty square next to the King, leads to a self-play score of 54.7% (1000 games). Note the side not to move gets nothing. (So this can be seen as a King-Safety-dependent side-to-move bonus.)

Right we also do this in chess and with some bonus added (up to some point) as number of attackers increases.

*) Recognizing mates through a contact check-drop (also counting a Knight jump as contact check) where the opponent has no pseudo-legal moves (other than with King) that can capture the checker, causes a self-play score of 54.45% (1000 games). Note that this does not detect mates where a piece that could capture the checker is pinned.

On-hand pieces are troublesome, especially those generals. A sort of advance eval is to evaluate carefully which pieces of yours are under threat by the opponent, more valuable attacker or not, as this would lead to a capture and later dropped close to your king. A safe king would reduce this threat bonus. Tuning certainly helps here.

*) Doing both of this causes a self-play score of 61-62% (260 games).

*) This was for regular Shogi, but the latter also seems to work for mini-Shogi.

Against SPEAR it doesn't seem to help much, though. But SPEAR searches entirely different from Shokidoki. It is very good at detecting tsume mates. (It uses a proof-number search for that.) So it sees them much before Shokidoki does anyway, even when Shokidoki ses them 1 ply earlier that it did before. In addition, it builds very strong fortresses for its King, so that Shokidoki usually doesn't get a chance to attack squares near the King anyway. Because the PN search is rather expensive, SPEAR's tactical ability for non-mates is lacking, however, so that Shokidoki usually gobbles up material continually. So Shokidoki usually wins the games where it can avoid to be mated, by depleting SPEAR of most of its material that is not in the King fortress before it launches a final attack.

In crazyhouse sunsetter is good at finding mates early, it also spends more time on every move and often gives away material. I have not looked Siyam lately, but I have a version that plays a little better than the released version. I will check if I have those evaluation features implemented. I will check also about this PN search. Thanks for the info.

[hgm]

Right we also do this in chess and with some bonus added (up to some point) as number of attackers increases.

I thought in Chess the King Safety term is usually calculated for both sides, with equal weight. The reported results were for evaluating only the safety of the King of the side not to move. (Based on the idea that the stand-pat could be replaced by a defensive move that would fix the King Safety of the side to move.)

I should add the Shokidoki already had a King Safety eval term based on proximity of enemy pieces, where enemy pieces two squares away already cause a hefty penalty, without actually checking if they attacked squares next to the King. Another difference with King Safety terms in Fruit (say) is that it only counts attacks on empty squares, and thus ignores attacks on occupied squares next to the King (which usually would be captures).

On-hand pieces are troublesome, especially those generals. A sort of advance eval is to evaluate carefully which pieces of yours are under threat by the opponent, more valuable attacker or not, as this would lead to a capture and later dropped close to your king. A safe king would reduce this threat bonus. Tuning certainly helps here.

In principle QS should already be able to figure that out by playing out the captures. I think pruning 'bad captures', like we do in Chess, is a bad idea in Shogi. The strong programs are 'sacrificing' Rook or Bishop for Gold or Silver all the time, just to get a general in hand to keep the King attack going. The opponent than has the choice to recapture (but will then gets its King Safety evaluated when the opponent stands pat with the extra general in hand), or must stand pat himself (representing a quiet defence against the impending general drop), accepting the loss of the general.

In crazyhouse sunsetter is good at finding mates early, it also spends more time on every move and often gives away material. I have not looked Siyam lately, but I have a version that plays a little better than the released version. I will check if I have those evaluation features implemented. I will check also about this PN search. Thanks for the info.

This definitely is an important trade-off for drop-game engines. You can very easily overdo it, and spend too much search time on looking for mates that during most of the game are just not there.

[Ferdy]

Right we also do this in chess and with some bonus added (up to some point) as number of attackers increases.

I thought in Chess the King Safety term is usually calculated for both sides, with equal weight.

In Deuterium I have tempo bonus for certain eval features one of those is related to king attack.

I should add the Shokidoki already had a King Safety eval term based on proximity of enemy pieces, where enemy pieces two squares away already cause a hefty penalty, without actually checking if they attacked squares next to the King.

I have the same for Lima, Siyam and crazyhouse Imortal.

Another difference with King Safety terms in Fruit (say) is that it only counts attacks on empty squares, and thus ignores attacks on occupied squares next to the King (which usually would be captures).

I make simplification this way, there are two threats, threat to empty squares and threat to squares occupied by opp pieces. In the latter, there are 3 threats, threat to valuable pieces, threat to equal pieces and threat to inferior pieces. Threat to inferior pieces has more value in games with drops than in chess.

On-hand pieces are troublesome, especially those generals. A sort of advance eval is to evaluate carefully which pieces of yours are under threat by the opponent, more valuable attacker or not, as this would lead to a capture and later dropped close to your king. A safe king would reduce this threat bonus. Tuning certainly helps here.

In principle QS should already be able to figure that out by playing out the captures. I think pruning 'bad captures', like we do in Chess, is a bad idea in Shogi. The strong programs are 'sacrificing' Rook or Bishop for Gold or Silver all the time, just to get a general in hand to keep the King attack going. The opponent than has the choice to recapture (but will then gets its King Safety evaluated when the opponent stands pat with the extra general in hand), or must stand pat himself (representing a quiet defence against the impending general drop), accepting the loss of the general.

In crazyhouse sunsetter is good at finding mates early, it also spends more time on every move and often gives away material. I have not looked Siyam lately, but I have a version that plays a little better than the released version. I will check if I have those evaluation features implemented. I will check also about this PN search. Thanks for the info.

This definitely is an important trade-off for drop-game engines. You can very easily overdo it, and spend too much search time on looking for mates that during most of the game are just not there.

In Imortal I still have futility pruning and bad capture by SEE pruning that I cannot drop due to loss of strength.