Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Evaluation-based Reductions and/or Extensions

Author: Vasik Rajlich

Date: 05:56:13 12/31/03

Go up one level in this thread


On December 31, 2003 at 06:45:47, Mridul Muralidharan wrote:

>On December 31, 2003 at 03:45:02, Vasik Rajlich wrote:
>
>>On December 30, 2003 at 10:37:57, Mridul Muralidharan wrote:
>>
>>>On December 28, 2003 at 13:32:05, Tom Likens wrote:
>>>
>>>>Hello Everyone,
>>>>
>>>>I've been experimenting recently with using the evaluation function to shape
>>>>the search tree.  Specifically, I've been using the static evaluation of
>>>>the current position and the previous position to determine if a move should
>>>>be extended or reduced.  I also have been making allowances for moves that
>>>>increase or decrease the pressure against the king, attack hung pieces,
>>>>save hung pieces etc.
>>>>
>>>>So far the results have been exciting, but also potentially frustrating.
>>>>The main problem I've encountered is that any pruning or extensions based on
>>>>the previous node's score cause hashing problems because this becomes path
>>>>dependent. In a way, I suppose this isn't much different then making these
>>>>type of decisions based on the value of alpha or beta as well, but these new
>>>>effects have (at least for my program) seemed more detrimental.
>>>>
>>>>My (obvious) question, how do other programmers deal with this phenomenon?
>>>>I suppose ignoring it is one option, but I'm hoping there is a better
>>>>solution.
>>>>
>>>>regards,
>>>>--tom
>>>
>>>
>>>
>>>Hi Tom,
>>>
>>>  In mess , I always do the latter - though none of the former.
>>>All my extensions are guided by some components of the evaluation (not whole of
>>>it).
>>>But my idea is not to extend more - it is to extend less.
>>>Just by printing out the positions that your program extends at - you will find
>>>that most of the ridiculous moves also get extended - and multiple ply
>>>extensions are like shooting yourself in the head while hanging yourself ;)
>>>
>>>I have tried to make it as path independent as possible - I had posted the idea
>>>here at CCC , but since the search is not available , I will do so again.
>>>
>>>Basic idea is simple : I have refined it over past so many months to a level
>>>where very rarely do I see a position from which an always extend program would
>>>perform better w.r.t search tree as compared to current mess (well which also
>>>does similar things in the QSearch).
>>>
>>>Before extending a move , I see the following :
>>>
>>>1) Is the move good ?
>>>
>>>This can become subjective very fast - a move that look like a stupid move could
>>>end up being a brilliant sac which leads to mate in 5 after a short 3 ply
>>>search. I ignore these kind of rare cases.
>>>
>>>For most cases , the definition could be something like this - a move that does
>>>not leave a piece hung or makes an opponent piece hung such that the opponent
>>>cannot gain from this move. (Well, this changes for checks).
>>>
>>>This involves making sure that positions like this dont happen !
>>>[D]8/8/3k4/2r5/8/3PK3/2B5/8 w - - 0 1
>>>
>>>Here even though the pawn push does make the rook hung , the rook can easily
>>>capture the hung opponent piece and get away with this threat.
>>>
>>>This is a simplified position - there are lots of other cases like this.
>>>
>>>Also , please do note that all moves which give a >= 0 SEE scores need not be
>>>good -
>>>1) Opponent could initiate another capture sequence on another hung piece which
>>>would be more profitable than recapturing.
>>>2) This move could leave other pieces hung so that opponent need not recapture ,
>>>but capture the other hung piece and you wont be able to recap that piece to
>>>save your previously attacked with piece. (hmm is this clear ?!)
>>>
>>>So determining whether a move is "good" can get tricky very very fast.
>>>I use attacktables very extensively for this purpose.
>>>
>>>Checks are like NMI's , and so I handle them seperately ... basic idea is , are
>>>hey good checks - as in unavoidable checks. Can king capture the checking piece
>>>, or some other piece capture this. If it can capture , then will another xray
>>>piece give a check when recapturing , etc.
>>>
>>>2) What are the options.
>>>
>>>After move has been made , next ply before toggling the "needs_extend" flag , I
>>>try to see what my options are before deciding on whether I should extend....
>>>(Since this involves all legal moves , it is applied to checks only).
>>>Obviously ,we are talking of only moves that need extensions.
>>>Right now , I have a check extensions , and a very scaled down recapture
>>>extension - the only path dependent extension in mess : and which I keep
>>>throwing out and brining back in.
>>>I do keep fooling around with other stuff , but none have stayed long enough
>>>....
>>>
>>>Now , after making the "threatening check" move previous ply , we have to decide
>>>whether to extend this subtree or not.
>>>For this I check the following :
>>>a) Was the previous move good ?
>>>b) What are my options here ?
>>>
>>>If (a) is false , no extensions - very simple. (No 1rep for me now ... but
>>>because of the nature of deciding whether a move is good , I have not seen a
>>>position where a bad move leads to immediate mate or a 1rep subtree that should
>>>have been extended).
>>>If true , then : we see out options. If we can make a good capture to escape
>>>check - then no extension (this would mean capturing the checking piece without
>>>loss and without hanging our pieces (or the gain from capturing is higher and
>>>there are no xray recapture pieces)).
>>>If we can make sufficient number of "good move" check evasions , then no
>>>extension. I keep fooling around with 3 - 5 here.
>>>
>>>The above stuff is used along with various scaling factors and a few other
>>>parameters for also move ordering.
>>>Mess decides to do or avoid a non-cap checking or threatening move in QSearch
>>>based on logic very similar to above - but since there an entire sub-tree is
>>>getting cutoff , the criterions are different - including how king is positioned
>>>, pawn cover , king safety , queen attack , mobility , analysis of surrounding
>>>squares , etc.
>>>
>>>Regards
>>>Mridul
>>
>>It's true that most extensions extend non-sensical variations, however most
>>moves searched in the main part of the tree are non-sensical. I am not sure if
>>the approach of trying to extend/search only "good" moves is the right way. I've
>>heard several times on this board the idea come up of somehow not extending
>>checks, or not extending all checks, or some general rule that wouldn't extend
>>some class of stupid checks - and the experienced computer chess guys are always
>>in unison: "extend all checks". It's quite ok for search to look at all sorts of
>>non-sense as long as there is some minimal chance that a few moves down the road
>>the variation becomes good. This is also the problem with futility pruning,
>>static evaluation doesn't see it but sometimes, even though very rarely, a few
>>more moves change the picture.
>>
>>I think the main extend/non-extend or search/no-search criterion has to be how
>>static the position is, or how static the move in question is. I have in my mind
>>some scenarios like: you arrive after six ply at a rook endgame, three vs three
>>on the kingside, no weaknesses, no particular king issues. You should be able to
>>decide to stop searching here, and it has nothing to do with any of the previous
>>moves being bad or the position being bad.
>>
>>Checks are pretty much always non-static, even the really stupid checks. I think
>>the main thing to look at re. extensions/reductions is not the specific
>>positions where a reduction/extension goes into effect, because you know that
>>99% of search is for a human totally bogus, but some sort of overall statistics
>>re. the extending/reducing rule. Something like: 99.5% of time not reaching the
>>search bounds is ok (0.5 % success is enough), but 99.8% of time is not enough.
>>
>>Hope that was at least slightly clear :-)
>>
>>Vas
>
>
>Hi,
>
>  If you do look at the search tree of a typical chess program you would change
>your opinion very fast :)
>Extensions are typically used to look more deeply into threatening moves so that
>the search horizon does not cover up some very bad threat/loss.
>Extensions are bad for the branching factor - the more you extend , the more
>your b.f is worsened and the more unpredictable your search becomes (it could
>end up extending to very long some very stupid variations).
>  Consider a typical case here :
>[D] r1b1kbnr/ppppqppp/2n5/4p3/4P3/3P1Q2/PPP2PPP/RNB1KBNR w KQkq - 0 4
>
>Should the move Qxf7?? be extended ?
>Is there any threat that extending this move will uncover ?
>
>Most programs which blindly extend , for example crafty , will extend the
>subtree after Qxf7.
>Now this is a simple case and arguements would be , this qould hit a fail
>high/fail low very fast and get rejected very fast.
>But in your search tree , you will have not 1 or 2 , but many many moves like
>this.
>And considering that > 20% of your moves could be checks (well this is highly
>position and program dependent) , how many of them are good checks ?
>I started following this _after_ I saw the effects of extensions on the search
>tree. I already know others who limit extensions , and I am sure most of the
>commercials also do the same - though they may not accept that here :)
>Extensions are way too expensive for the search tree !
>
>Regards
>Mridul

I don't know how much luck you had with the initial debugging of your program.
In my case I had to do some really tedious debugging involving stepping through
the tree node-by-node. One quite funny bug I had was occurring in the search
after 1. e4 e5. My program was analyzing the nonsense variation 2. Nf3 Nc6 3. d4
Bb4+ 4. Bd2 Nf6 5. Nxe5 Nxe4 6. Nxc6 Nxd2 7. Nxd8 Nxf1+ - and crashing.
Actually, from a computer chess point of view, this is a perfectly normal
variation I think, I doubt that there is any sense in trying to prune it.

Basically, if you're going to search several million nodes, you will look at a
lot of junk. The point of a smart search, as I see it, is to try to somehow
increase the relevance of the variations very very slightly, maybe into the 0.1%
range, rather than 0.05%. This means that you can invest some of your available
nodes into some various "lottery tickets" variations, ie. probably won't work,
but you never know.

Re. Qxf7, as you pointed out, the investment won't be so high because you will
be failing low throughout the entire resulting search. It will be even cheaper
than that because:

1) It will fail low right after an immediate null move.
2) It removes material from the board, further reducing the branching factor for
that variation.
3) It creates a big material imbalance so you may be able to A) use lazy eval in
the subtree B) make some reductions later in the tree once things quiet down.
(For example, a quiet move with a big material deficit can be a reduction
criterion.)
4) There are only two replies, again reducing the cost.

It seems that a reduction/extension mechanism shouldn't be trying to figure out
which moves are actually good. It should be trying to figure out which moves are
worth searching, based on:

1) The very small chance that those moves will eventually be in the 0.001% of
moves which are either part of the PV or force a change in the PV, rather than
one of the 99.999% which could have been skipped.
2) The expected cost of the search.

Cheers,
Vas



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.