Computer Chess Club Archives


Search

Terms

Messages

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

Author: Mridul Muralidharan

Date: 03:45:47 12/31/03

Go up one level in this thread


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



This page took 0.01 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.