Extension - Reductions and threats

[mjlef]

OK,

This is a germ of an idea which I am testing now. Looking at huge trees my program often generates after extensions, and how it hurts search depth, this idea popped into my head:

After any extension involving a threat, reduce the depth the same amount once the threat is over. Example, if you extend on soem passed pawn push, once that pawn promotes or is captured, reduce the depth the same amount you extended it. Doing this seems to let me do more passed pawn move extensions without a huge blowup. The idea could be extended to mate threats, extensions for tactical threats, etc. Does anyone do this and what have been your results?

I will post my results once I get a lot more games in (specific limits seem critical).

Mark

[Klaus Friedel]

OK,

After any extension involving a threat, reduce the depth the same amount once the threat is over. Example, if you extend on soem passed pawn push, once that pawn promotes or is captured, reduce the depth the same amount you extended it. Doing this seems to let me do more passed pawn move extensions without a huge blowup. The idea could be extended to mate threats, extensions for tactical threats, etc. Does anyone do this and what have been your results?

I will post my results once I get a lot more games in (specific limits seem critical).

Mark

I played around with this idea for a while in Snitch, but it never worked for me.
I have no glue, why it doesn't work, but in all my tests the "normal extention" always performed better than the one with the reduction after threat removed.

Regards,

Klaus

[mridul]

OK,

This is a germ of an idea which I am testing now. Looking at huge trees my program often generates after extensions, and how it hurts search depth, this idea popped into my head:

After any extension involving a threat, reduce the depth the same amount once the threat is over. Example, if you extend on soem passed pawn push, once that pawn promotes or is captured, reduce the depth the same amount you extended it. Doing this seems to let me do more passed pawn move extensions without a huge blowup. The idea could be extended to mate threats, extensions for tactical threats, etc. Does anyone do this and what have been your results?

I will post my results once I get a lot more games in (specific limits seem critical).

Mark

Hi Mark,

I have found that extensions hurt : both branching factor and gameplay in most cases.
Whenever I look at the moves being extended , more than 99% of them are quite worthless and should not even be looked : but alas.
So essentially , I instead of getting into uncertain and potentially dubious grounds of reductions I try to not extend in most cases.
Most checks are stupid , same for passed pawn pushes.
I do not extend mate threats as of now , but even when I used to , there were a set of criterions that needed to be satisfied.

If a move that would need to get extended , I try to do a static analysis of the position and if I find that there is some potential for the move : attack or defending potential - I allow extention for the move , else if the move is 'stupid' , I dont extend , else I extend.

For example , a simple case where this is useful would be for a huge set of checks where the 'checking piece' is hung.
You can ofcourse come up with more cases

When I enable and disable this , the change in time to depth is > 40% while the number of missed tactics (found using a special search where a subtree is searched with and without extension to check for flip) is of the order of a few tens of moves for a depth 13 search from a typical middle game position.

Regards,
Mridul

[mjlef]

Well, today I play games against otherwise identical programs. I added logic to extend on a passed pawn to the 7th (must have the square in front empty) or to the 6th (2 squares in front empty, plus opponent has to have very little material such as a bishop and pawns).

I reduce when a passed pawn on the 7th is captured, or it promotes.

After 50 games, the extend and reduce version is leading about 60 rating points. Your mileage may vary, but it might be worth a try. I also do not see huge search slowdowns or blowups as much when passed pawns are around. Maybe someone has some sample blowup positions I could try.

Once I get a few hundred more auto-play games in I should better know if this is real or not. 50 games is never enough.

I agree most extensions are not very helpful and often cause explosions reducing search depth too much. I am thinking of trying this: extend check, but reduce the capture of the checking piece (as along as it is not a one reply to check, and maybe I should not reduce captures next to the king). Should prune down extenindg and tossing away pieces, but still keep those pesky check that push threats over the horizon.

[H.G.Muller]

How is extending for a certain tactic, and after it is done reducing it again, different from merely including that tactic in quiescence search?

I agree that extending useless moves (checks with a hung piece, bad recaptures) tends to eat a lot of nodes in most extension schemes. The idea to only extend good moves, and revoke the extension oif the move proves bad, thus makes great sense.

Actually, the best moves to extend would be uncertain moves, that might be good. By scoring a passer on the 6th or 7 row optimistically as the piece that the opponent might have to sacrifice, and pessimistically as the loss of a Pawn, would force a contingency search to deepen the branch that pushes the Pawn until it is lost or promotes. After that the score interval collapse to a single value, and continued deepening will then concentrate on promising branches that do have uncertainty left in them, or, lacking those, deepening the undeepest branches with a single score.

[Uri Blass]

How is extending for a certain tactic, and after it is done reducing it again, different from merely including that tactic in quiescence search?

It is different because the reducing is not done always but only in part of the cases.

There are cases when pawn in the 7th rank is not captured.

Uri

[mjlef]

How is extending for a certain tactic, and after it is done reducing it again, different from merely including that tactic in quiescence search?

It is different because the reducing is not done always but only in part of the cases.

There are cases when pawn in the 7th rank is not captured.

Uri

Exactly. The main reasons to extend are if you think the other side is trying to delay something (e.g. toss in a meaninless check to hide me frome losing my rook) or if you are uncertain how something will turn out (dangerous passed pawn being pushed). Extending for the whole remaining depth makes no sense if the reason for extending is now gone. If it has not been resolved one way or another, then extra depth is warrented to try and figure it out. Once the pawn promotes, I think the search might profit more from looking down other lines deeply than searching all those queen moves one ply deeper anyway.

Anyway, I added the following silly rule. Extend all checks, but if the response to the checking move is to capture the piece that last moved, then reduce it again. Same idea...the uncertainly of the check extends the search, when the threat is resolved, reduce it back. Probably better would be to look at mate threats and other threats when giving check. if the response gets rid of the mate threat, ect., then you can reduce it back to some normal depth. I wish I had a few more machines to test these dumb ideas.

Mark

[bob]

Hey Mark...

Been a long time since the crafty vs Now marathons on ICC years ago, glad to see you back into the thick of things.

I've become a bit more pessimistic on extensions, since they are essentially doing the same thing as reductions, just in reverse. So the key, for me, is to try to limit extensions to moves that potentially influence the root score (checks are examples). I've removed recapture extensions since my search depth is already deep enough that I don't worry so much about a single capture/recapture eating a paltry 2 plies. When searching to depth=8 in the early 90's, that was critical. But today, searching to depth 16 or beyond, it is less critical.

Today I only extend moves that give check, or moves in positions where there is only one legal move to escape check. No passed pawn push extensions, no recaptures, nothing else except for the classic "mate threat" which is triggered when a null-move search does not fail high, and returns a mate score, saying "if you do nothing, you get mated" which indicates some sort of significant threat is present. Otherwise, I let the inverse idea of reductions take over, where I reduce non-passed pawn pushes, etc, which is a form of extending them. I.E. if you extend all passer pushes, or you reduce all non-passer-pushes, you get exactly the same result... But you get deeper overall depth for other moves.

You might have been around when Bruce and I were discussing the "late move reduction" idea (didn't call it that) back in 1997? Only thing we didn't think of was using a history-based approach to exclude some moves from the reduction. Of course, back then our depths were way mkore limited, which might make reductions more risky than they are at today's common depths... We noted how fast we could get to deeper depths, but we also noticed some tactical oversights. The deeper depths of today, plus the history-based reduction decision seems to be working.

[H.G.Muller]

Exactly. The main reasons to extend are if you think the other side is trying to delay something (e.g. toss in a meaninless check to hide me frome losing my rook) or if you are uncertain how something will turn out (dangerous passed pawn being pushed). Extending for the whole remaining depth makes no sense if the reason for extending is now gone. If it has not been resolved one way or another, then extra depth is warrented to try and figure it out. Once the pawn promotes, I think the search might profit more from looking down other lines deeply than searching all those queen moves one ply deeper anyway.

You say 'exactly', but your last statement suggests that you will always take the extension back, no matter if it ends good (promotion) or bad (Pawn loss). I agree that this is a sensible thing to do.

But it still seems to me that this is kind of an extended QS. Your tree only looks different if the arrival of the Pawn on 6th or 7th and its final conversion span the normal search horizon. It is basically a one-time extension made only in QS: if you evaluate in QS and find an advanced Pawn, and you have not done it before, you give an extension.

Basically the question always is: "is a situation (e.g. with an advanced Pawn) quiet enough to trust the static evaluation?" If the answer is "no", you search. Because without the search the evaluatio of the whole line leading to the current leave will be crap, and compromise the stability of the search, which all kind of false and unnecessary PV switches in earlier nodes, all causing lots of wasted search effort.

In conventional QS the answer is only "no" if there are (good) captures possible. But in makes sense to extend that to other notoriously unclear situations, such as nearly-promoting Pawns, presence of pinned pieces (for which it is not only a question if they can be captured now, but, equally important, if they can be attacked now).

[Uri Blass]

Exactly. The main reasons to extend are if you think the other side is trying to delay something (e.g. toss in a meaninless check to hide me frome losing my rook) or if you are uncertain how something will turn out (dangerous passed pawn being pushed). Extending for the whole remaining depth makes no sense if the reason for extending is now gone. If it has not been resolved one way or another, then extra depth is warrented to try and figure it out. Once the pawn promotes, I think the search might profit more from looking down other lines deeply than searching all those queen moves one ply deeper anyway.

You say 'exactly', but your last statement suggests that you will always take the extension back, no matter if it ends good (promotion) or bad (Pawn loss).

No

It is possible that there is no promotion and no pawn loss and in this case he does not take back the extension.

Uri

[H.G.Muller]

How should I understand the following sentence, then?

Once the pawn promotes, I think the search might profit more from looking down other lines deeply than searching all those queen moves one ply deeper anyway.

To me this suggests it argues for revoking the extension on promotion as well.

[Uri Blass]

How should I understand the following sentence, then?

Once the pawn promotes, I think the search might profit more from looking down other lines deeply than searching all those queen moves one ply deeper anyway.

To me this suggests it argues for revoking the extension on promotion as well.

Of course but there are cases when there is no promotion and no capture of the pawn.

For example see line like
a7 Ra8 Be4 Bb7 Bxb7 Nxb7 Ra1

Uri

[Tord Romstad]

OK,

This is a germ of an idea which I am testing now. Looking at huge trees my program often generates after extensions, and how it hurts search depth, this idea popped into my head:

After any extension involving a threat, reduce the depth the same amount once the threat is over. Example, if you extend on soem passed pawn push, once that pawn promotes or is captured, reduce the depth the same amount you extended it. Doing this seems to let me do more passed pawn move extensions without a huge blowup. The idea could be extended to mate threats, extensions for tactical threats, etc. Does anyone do this and what have been your results?

I tried something similar a long time ago, but I wasn't able to prove that it was an improvement, and ended up removing it in order to keep things simple. It's an interesting idea, but it introduces some rather annoying search inconsistencies.

Tord

[bob]

If you are talking about late move reductions, you already have enough search inconsistencies to choke a mule.

[mjlef]

Thanks Bob,

It is nice to be remembered.

OK, my probably worthless tests:

The extend a pawn to the 6th and 7th with the conditions I mentioned before, and reducing it when capture or promoted: 51 wins 38 losses and 13 draws. Seems to help, but I have seen other things in the past I was more sur eof which later proved false.

Adding to that the extend checks, but reduce a reply capturing the checking piece gave 30 wins 25 losses and 46 draws, so that seems to hurt over just the passed pawn rule. I think I will try again, but never reduce captures of the checking piece if the checking piece move also happened to be a capture. I think doing that is risky since it could expose the king.

I have been trying adaptive null move pruning, but do not get a clear advantage of using R=2/3 versus always R=3. Perhaps my conditions on deciding when to use R=2 are not so great.

I am fortunate enough to live here in Sofia for a few years, so I have been going to the Mtel masters tournament (Anand, Topalov, etc). A friend even invisted me to dinner with Asome of the players! Seems my life is about chess now!

[mjlef]

[/quote]
You say 'exactly', but your last statement suggests that you will always take the extension back, no matter if it ends good (promotion) or bad (Pawn loss).

[/quote]

That is right. The idea is just to extend things which are unknown (the passed pawn might be lost or might be a big win). Once it is gone from the board, the uncertainty is less ands so this branch of the search tre need not be so long anymore.

Looking at my code I realize I just recue one ply's worth when capturing or promoting. if it was a pawn which when from the 5th to 6th and then 6th to 7th, it got two extsions. Probaly I should carry the extensions with the piece, and reduce by 2 ply when it is captured or promotes. Well, let me test some more ideas and see if they are worth the bother.

Mark

[mjlef]

[/quote]
You say 'exactly', but your last statement suggests that you will always take the extension back, no matter if it ends good (promotion) or bad (Pawn loss). I agree that this is a sensible thing to do.
[/quote]

I am actually only doing this in the main seach, not qsearch. I try to keep my qsearches very small now.

[bob]

I have been running tests like this:

crafty vs program X, various time controls. I use 40 different starting positions so that opening book randomness plays no role in the games. I am playing 6 games with each position, 3 with crafty as white, 3 with Crafty as black. So 480 games. I run the same test twice, and do _not_ get exactly the same win/draw/loss result. The results vary by at least 10 games + or - in one or more of the three columns. This is a set of games played on our 128 node dual-processor 64 bit xeon cluster, so each program gets one full CPU, and I typically play 40 games at a time against 1 opponent usng xboard, or 120 games at a time against three different opponents also using xboard. Pondering is enabled since each node has two cpus and the programs are limited to 1 each for this particular testing. But the variations in pondering time, or even just clock variances cause a different move here and there by either ending the search slightly quicker or delaying the end slightly and finding a different move, or the history values getting changed which greatly changes the late move reduction behavior. In any case, it is hard to draw conclusions from 480 games in my testing, using 40 would almost tell me nothing...

[mjlef]

If only we all have 128 node clusters! I will just have to make due with the three computers I have.

I use 50 bland starting positions can let each program play white then black. If a run of 100 such games looks promising, I repeat at other time controls to get around 300 games. Some things I just test at fixed depth (say move ordering changes) but mostly just fixed time per move.

Any users of Free Pascal around? I really need to compile NOW for newer processors and I am having some problems with it.

[Steve Maughan]

Any users of Free Pascal around?

I have Borland Delphi 2006. If you'd like me to compile just send me a note.

Regards,

Steve