Bonus for "null move SEE"

[matthewlai]

I have been experimenting with this idea that's so simple that I can't imagine people aren't doing it already, but I also can't find mentioning of it on the wiki, so here we go.

The idea is that if a move moves a piece that could have been safely captured by the opponent, it's more likely to be good (that means it should probably be ordered before other neutral moves, and have lower reduction if you are doing LMR). Especially if the move itself also has a non-negative SEE.

The way to determine that is very simple -
Just do a null move, and compute the SEE value for the FROM square of the move. If it's positive, that means if we don't move it, the opponent can probably capture it.

[hgm]

I am using something like that in Joker. For one, the SEE score used to order captures is not just the SEE of the to-square, but the sum of the SEEs of from- and to-square. (I think many people do that.) Secondly, if there is a threat against a piece, it tries to order at least one safe non-capture of that piece with the captures, with a sort score equal to its from-square SEE.

[matthewlai]

I am using something like that in Joker. For one, the SEE score used to order captures is not just the SEE of the to-square, but the sum of the SEEs of from- and to-square. (I think many people do that.) Secondly, if there is a threat against a piece, it tries to order at least one safe non-capture of that piece with the captures, with a sort score equal to its from-square SEE.

Ah yes, adding them up makes sense. I didn't know people are doing it.

I tried a naive implementation (sorting all safe escapes after killers), and it actually made almost no difference at all. My guess is there are just too many safe escapes most of the time, and a lot of times the best move is not to move the piece (but to defend it with another piece).

[hgm]

For Joker there was also no spectacular gain. I guess the reason is that most of the time the threat evasion actually would already be one of the killer moves. This would not be true for a new threat created by the preceding move, but because of null moving engines typically save up threats created by silly opponent moves in all-nodes, rather than cashing them, most threats will be pre-existing threats. At some point null-moving then starts to be refuted by the threat 'evaporating', and no other hostage being available for execution. The evasion that made the threat evaporate (likely a withdrawal, protection or interposition) then becomes killer, and will be used succesfully against all other pointless alternatives for the null move (e.g. of captures of a piece less valuable than the threatened one).

Another problem is that it is hard to judge statically whether withdrawal, protection or interposition is the applicable threat evasion, so that always going for a withdrawal might backfire.

In my new engine Simple I will try an interesting novelty: I will pass an 'abort threshold' to Search(), which is a bit similar to beta, but can produce a cutoff already in the move-generation phase, when this encounters a capture with a SEE (on the to-square) above that threshold. The caller would know from an otherwise invalid return score that the move was aborted, and could then postpone its search by re-scheduling it (or cancel it altogether). The idea is that when you capture a Knight (say), you would search it with the value of a Knight as abort threshold, so that if the opponent could counter-strike (on another square, obviously) to gain more than that Knight, (say a Queen for a Rook), the capture of that Knight just got you deeper into trouble. Actually the situation is very similar to the one where you did capture that Knight with a Queen, and it was protected by a Rook (even though in reality yuou might have captured it with a Pawn, or it was not protected at all). The counter-strike against an existing target substitutes for protection of the actually captured piece, and sort of grafts onto the SEE sequence of captures. If this gets negative, the original capture deserves to be traeted just like any bad capture (pruned in QS, postponed in full-width search).

[matthewlai]

For Joker there was also no spectacular gain. I guess the reason is that most of the time the threat evasion actually would already be one of the killer moves. This would not be true for a new threat created by the preceding move, but because of null moving engines typically save up threats created by silly opponent moves in all-nodes, rather than cashing them, most threats will be pre-existing threats. At some point null-moving then starts to be refuted by the threat 'evaporating', and no other hostage being available for execution. The evasion that made the threat evaporate (likely a withdrawal, protection or interposition) then becomes killer, and will be used succesfully against all other pointless alternatives for the null move.

Another problem is that it is hard to judge statically whether withdrawal, protection or interposition is the applicable threat evasion, so that always going for a withdrawal might backfire.

That is a very good theory. I agree that's probably what's happening (they become killers anyways).

I guess I'll be abandoning this idea then! I just tried a few different variants, and none of them made much of a difference.

[hgm]

Please note I still added a remark to my previous post (and was interrupted by a phone call) when you were already answering it!

[matthewlai]

Please note I still added a remark to my previous post (and was interrupted by a phone call) when you were already answering it!

Cool! I was experimenting with something similar actually, except I was doing essentially a q-search, using SEE as eval. That is likely going to be way too slow for any engine with a reasonable NPS!

Compared to my normal eval function, SEE takes negligible time.

[hgm]

Yes, SEE is pretty slow for me. In fact I hope that this abort-threshold mechanism allows me to avoid it alltogether. Only use the protected / unprotected info on every piece.

I got this idea when I tried to stabilize the QS in my Chu-Shogi engine HaChu. QS tends to explode there, because Chu Shogi has hit-and-run captures. In an attempt to contain the explosion I initially pruned lines where you did lower your score in the two preceding ply. But that prunes too much: in the presence of a QxQ trade capture of any piece < Q would lead to a 'counter-strike' against Q, and therefore 'auto-fail'. Even if it was just gobbling up an unprotected Rook through PxR. While the Q against which the counter-strike would be directed could very well be protected, so that it was just collecting a Rook followed by a Queen trade. It was pretty essential to not let yourself be discouraged by the initiation of the trade of a valuable piece.

So I realized the importance of the concept of 'obvious gain', which is the value of the victim if the victim is unprotected, but subtracts the value of its capturer when it is protected. Only if the 'obvious gain' of a counter-strike gets above the specified threshold would the search be aborted. (In HaChu with an automatic fail high, even though the score might still be below alpha, effectively pruning the opponent's capture leading to it, and in Simple with an invalid score that triggers re-scheduling in the parent.)

The problem is that it is always a pain to know if something is protected or not. You could figure this out case by case, or just globally, by running the (pseudo-)capture generator for it. To know if the pieces of the side to move are protected can be a cheap side effect of the move generation that you have to do for that side anyway. For judging the obvious gain of a counter-strike in the daughter node this is usable, but already causes the inaccuracy of the recorded protector being the moved piece, or a new protector unblocked by the moved piece. The latter is even possible for the recapture, in case of an X-ray attack. (The former is always the case on a recapture, so that it can be trivially corrected for.) For a general counter-strike you are much more in the dark. Of course you could add code to figure all this out. (E.g. during move generation a slider move blocked by a similarly moving piece could be 'virtually extended' to update the attackers counts downstream of it to include X-ray attacks.)

[Gerd Isenberg]

Yi-Fan Ke, Tai-Ming Parng (1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2

They assign higher prio to those moves whose origin squares are guarded by the opponents pieces.

[matthewlai]

Yi-Fan Ke, Tai-Ming Parng (1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2

They assign higher prio to those moves whose origin squares are guarded by the opponents pieces.

Cool! I can't find much about the paper, but it does sound like it.