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.