Threat Move

[BubbaTough]

A threat move is (I think) the best move following a null move. I am curious about other engine writer's experience with it. Do they find it useful for move ordering? Or for reduction (or non-reduction)? Have folks tried it for a variety of things and decided not to use it?

I have played around with it a little and not had any success, but it seems like a useful concept and would love to hear the experience of others.

-Sam

[hgm]

If the null move fails low with a score bound that is more than 50 cP below current eval, I record it as a threat, and remember the refutation to-square. When I get to move sorting, I then run through all non-captures to see if moves are leaving from this threatened square. Each move I find is then subjected to SEE, to test if it goes to a safe square. As soon as I have one, I add the value of the threat to the sort key (which for captures contains victim value or SEE), and call it quits. (Captures got the threat value added to their sort key already before, when they capture the piece on the from-square of the null-move refutation, or are done with the piece at the to-square.)

Thus a single non-capture that saves a piece that is under threat is sorted amongst the good captures, in a natural place. This sseems to have some beneficial effect.

[bob]

A threat move is (I think) the best move following a null move. I am curious about other engine writer's experience with it. Do they find it useful for move ordering? Or for reduction (or non-reduction)? Have folks tried it for a variety of things and decided not to use it?

I have played around with it a little and not had any success, but it seems like a useful concept and would love to hear the experience of others.

-Sam

Killer should handle this. You do a null-move search, if a move fails high for the opponent (to kill the null move) then it should become a killer and get tried soon on the real search after each move at this ply.

[BubbaTough]

A threat move is (I think) the best move following a null move. I am curious about other engine writer's experience with it. Do they find it useful for move ordering? Or for reduction (or non-reduction)? Have folks tried it for a variety of things and decided not to use it?

I have played around with it a little and not had any success, but it seems like a useful concept and would love to hear the experience of others.

-Sam

Killer should handle this. You do a null-move search, if a move fails high for the opponent (to kill the null move) then it should become a killer and get tried soon on the real search after each move at this ply.

This was exactly my thought too Hyatt...and the few times its not true (when Killer is excluded because it is capture, or it is overwritten by other killers during the ply) did not seem important enough. Unless people cite positive experiences with it, I will likely ignore it.

-Sam

[Tord Romstad]

A threat move is (I think) the best move following a null move. I am curious about other engine writer's experience with it. Do they find it useful for move ordering? Or for reduction (or non-reduction)? Have folks tried it for a variety of things and decided not to use it?

I have played around with it a little and not had any success, but it seems like a useful concept and would love to hear the experience of others.-Sam

I don't use it for move ordering, but I do use threat moves in many of my criterions for reductions and forward pruning. It helps to make the selective search much more tactically accurate. I have described the details a few times before here and/or on the Winboard forum. If you are interested, but can't find my old posts in the archives, please let me know, and I'll describe how it works.

Tord

[hgm]

Killer should handle this. You do a null-move search, if a move fails high for the opponent (to kill the null move) then it should become a killer and get tried soon on the real search after each move at this ply.

The problem is that the killer is like 'mustard after the meal'. It helps you to quickly refute the stupid moves the search tries when it is hunting for peanuts with its good captures, before it accidentally stumbles on the move that saves its Queen by withdrawing it. This withdrawal is unlikely to be a killer at this level, as it is a specific refutation of the previous move, not likely to be any good had this move not attacked our Queen.

So you still have to refute all the moves you you searched before it, albeit efficiently, something that would not have been needed at all if you had immediately tried to save your Queen through non-capture withdrawal.

[Tord Romstad]

A threat move is (I think) the best move following a null move. I am curious about other engine writer's experience with it. Do they find it useful for move ordering? Or for reduction (or non-reduction)? Have folks tried it for a variety of things and decided not to use it?

I have played around with it a little and not had any success, but it seems like a useful concept and would love to hear the experience of others.

-Sam

Killer should handle this. You do a null-move search, if a move fails high for the opponent (to kill the null move) then it should become a killer and get tried soon on the real search after each move at this ply.

No, killers are a very poor substitute for threat moves. The most important threat moves are usually captures and promotions, which (at least in most programs) are excluded from the killers.

Tord

[BubbaTough]

I don't use it for move ordering, but I do use threat moves in many of my criterions for reductions and forward pruning. It helps to make the selective search much more tactically accurate. I have described the details a few times before here and/or on the Winboard forum. If you are interested, but can't find my old posts in the archives, please let me know, and I'll describe how it works.

Tord

Thanks Tord, I looked at your program after your description...no need to repeat details (for me anyway). It was what inspired me to look into threat moves in the first place. I have not tried implementating your concepts, but they look very interesting and original.

No, killers are a very poor substitute for threat moves. The most important threat moves are usually captures and promotions, which (at least in most programs) are excluded from the killers.

Yes I was thinking about that. For the most part killers ?may? be a good substitute for threat moves for move ordering (which I understand you don't use Tord). But maybe not. Captures that look bad in SEE but look good in threat move should be searched early for example. And I still don't have a good feel for how often a useful killer from the null search is overwritten by a less useful killer. I don't think logic is enough to determine whether the overhead for keeping them separately is worth it. My single small test was inconclusive.


Has anyone else tried them for anything?

-Sam

[bob]

A threat move is (I think) the best move following a null move. I am curious about other engine writer's experience with it. Do they find it useful for move ordering? Or for reduction (or non-reduction)? Have folks tried it for a variety of things and decided not to use it?

I have played around with it a little and not had any success, but it seems like a useful concept and would love to hear the experience of others.

-Sam

Killer should handle this. You do a null-move search, if a move fails high for the opponent (to kill the null move) then it should become a killer and get tried soon on the real search after each move at this ply.

No, killers are a very poor substitute for threat moves. The most important threat moves are usually captures and promotions, which (at least in most programs) are excluded from the killers.

Tord

And which are searched first, because of the good-captures-first ordering strategy... I've never gotten any sort of gain from this idea, although I can try it again with the current testing to get a pretty accurate measure of its effect...

[Tord Romstad]

No, killers are a very poor substitute for threat moves. The most important threat moves are usually captures and promotions, which (at least in most programs) are excluded from the killers.

And which are searched first, because of the good-captures-first ordering strategy... I've never gotten any sort of gain from this idea, although I can try it again with the current testing to get a pretty accurate measure of its effect...

I think you miss the point. The main purpose of keeping track of threat moves is not to use the information for move ordering, but to use it for decisions about move selection, reductions and extensions. When deciding what moves to prune or reduce, it is very useful to know what the opponent is threatening. The move that refuted the null move at the same node (which is what we call the "threat move" in this discussion) is a very natural thing to take into consideration. The most obvious example is if the threat move is a capture: In this case, it makes sense to not prune any move which defends the captured piece, or moves it to a safe square. I use this and many similar tricks in my "super-qsearch", the transitional phase of tapered selective search between the main search and the qsearch.

Tord