Delaying Extensions Idea (does anyone do this)?

[mjlef]

OK, here is my next screwy idea: Try to order the moves you search based not just on the likelihood of them being found best, but also based on how big a sub tree they will generate.

In cutoff nodes, many moves can often lead to a cutoff. So, instead of say searching a capture move which might cause an extension (like a recapture or check), delay searching those moves. I think for this to work you still need to use good move ordering. For example, searching winning captures first. But why search a capture that is also a check (or extended for other reasons) if a not-extended move might still fail high.

Has anyone played with this idea? I will start some tests and see if it works.

I thin an efficient search need not search the best moves. An efficient search will search "good enough" moves with small subtrees. What do you think?

Mark

Howdy Mark

Well, i don't played with your idea and i think your idea is already outdated with "modern" PVS searches. Let me explain my point of view.
"Modern" searches, like based on LMR/PHR, doing a lot of researches while the searchis running, or at at least they should do it.

However, if we entering a node again, we have a hashmove already from the previous search, which should lead to a cutoff.

If i'm looking back, good old times, your idea might giving a nice improvment in special cases of threads and pins.

Best,
Daniel

Naturally, if there is a hash move for a position, it would be searched first. I meant this to be used for move ordering of other moves.

Here is what I tried last night:

Whenever a move causes a beta cutoff, make a score for a move (much like a history table) based on the number of subtree nodes divided by 2^depth (an estimate of the average subtree size assuming a branching factor of 2). I multiply this by a contstant for scaling, and subtract it from a bigger constant, to make a positive score (smaller subtree size) better. I added two history arrays, one for capture and one for non-captures. I take the existing value in the array, mutliply by 3, add the new value then divide by 4 (weighted average, to smooth out the values).

I left in place other move ordering which goes hash, winning captures by SEE (sub ordered by the history array for captures), equal captures (sub ordered by the the new history values), non captures (ordered by the new non-capture history values), then losing cpatures (ordered by how bad the loss is). I did not try and guess if the node would be a fail high one or not (if it is an all node them all this extra work would not be very helpful)

Results? Slightly better in testing against the otherwise identical program using standard ordering. Slightly better against the average results against 5 opponents (Fruit, etc). I only got in about 100 fast games, but to me this suggests the idea is not as totally worthless as most of my ideas.

A simpler scheme instead of all this node counting might be to just use it as a kind of tie criteria. If two moves both appear to win say a pawn, search the non-extending one first. The nono-extending one would typically have a smaller subtree (checks might be the expection, since there would be fewer replies).

A related idea I experimented a bit a month or so ago was for any move which would cause an extension, first search without the extension. If the extension was good enough to cause a beta cutoff, accept it (non-pv nodes, of course). If not, research with the extension added. I never did enough tests to see if this helped or not. My hope was say a winning capture check might be able tpo prove it was good enough without the need to extend... more testing soon.

Mark

[hgm]

A few remarks:

That a hash move goes first does not affect the usefulness of move ordering: the latter determines which move will become hash move in the first place!

The side having the move in cut nodes should try to simplify (i.e. indeed aim for a small search tree).

Even with recapture extension, a capture can be a simplifying move. The opponent wouldn't be able to play that piece anymore (reducing the branching factor B). And he will certainly try to play it if he still has it, as he plays in the all nodes! If I play a non-capture, an (N-1)-ply tree with large B remains. If I play a capture, and he recaptures, due to the extension there will also be an (N-1)-ply tree left, but now with smaller B. And in all the moves where he doesn't recapture (which will also all be tried) he will not get the extension, he will have the smaller B, and he will have a sizable material loss. The latter will cause more null-move refutations (we can afford to ignore more threats before he gets even), more futility pruning, etc. The total is likely to be smaller (unless we merely captured a Pawn).

Of course we always try to refute by the null move first, and only if this fails low we have to worry about ordering the other moves. But then we have information from the null-move search, which we can employ for obtaining a more sensible ordering. If there is an obvious threat against one of our high pieces, a good or neutral capture against the aggressor might be the obvious answer to defuse the situation. If the threatened piece was not soft-pinned, withdrawing it might be another option to avoid complication. Defending, on the other hand would build up tension, and you might expect larger trees from it. The same with interposing, as the interposed piece will take the place of the threatened one as potential victim of a capture that will be certainly tried if the move is a cut-move.

To refute the nonsense branches where the opponent fails to recapture in an all-node, a null move is most of the time no good, as it offers him the opportunity to recapture anyway, and compared to the immediate recapture you have offered him a free move (many of which might be useful for him). The preferred refutation here is to move the piece he failed to recapture back to where it came from. (There is no harm in move ordering being path dependent.) Unless his move made a new, worse threat against you, of course.

[hMx]

OK, here is my next screwy idea: Try to order the moves you search based not just on the likelihood of them being found best, but also based on how big a sub tree they will generate.

In cutoff nodes, many moves can often lead to a cutoff. So, instead of say searching a capture move which might cause an extension (like a recapture or check), delay searching those moves. I think for this to work you still need to use good move ordering. For example, searching winning captures first. But why search a capture that is also a check (or extended for other reasons) if a not-extended move might still fail high.

Has anyone played with this idea? I will start some tests and see if it works.

I thin an efficient search need not search the best moves. An efficient search will search "good enough" moves with small subtrees. What do you think?

Mark

Hi,

While not directly applicable to playing programs... yes, Chest (solving mate problems) does this rather explicitly. It orders the moves of the to-be-mated side by smallest-tree-first. It is not the only ordering criterium, but an important one.

For Chest this works really great!

Cheers,
Heiner