Author: Mridul Muralidharan
Date: 07:37:57 12/30/03
Go up one level in this thread
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
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.