Author: Tord Romstad
Date: 06:19:22 12/29/03
Go up one level in this thread
On December 29, 2003 at 00:17:34, Russell Reagan 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 > >I've been thinking about this and reading the other posts, and I have a few >thoughts and questions. > >My guess is that this idea of using evaluation to guide the search does have >significant upside, and that it will probably require less efficient use of the >transposition table to avoid significant search instability. I think it is >probably worth sacrificing some efficiency of the transposition table (not as >many cutoffs, for instance) for the upside of the cutoffs and reductions that >can be achieved with this idea. > >I think your evaluation function must be suited for this kind of use. For >instance, most evaluation functions would probably give a very poor static >evaluation of the current position, and are only more accurate when combined >with other approaches, like quiescence search. I think that in general you get >the best results when you combine ideas that fit well together and compliment >each other (like an evaluation function that evaluates quiet positions >accurately, combined with quiescence search that ensures that only quiet >positions are evaluated). I bet a lot of evaluation functions are not suited for >this kind of method for guiding the search, so when a lot of people try it, they >won't get very good results. You are right about this. It is best to be very conservative about applying pruning and reductions in positions which are not sufficiently quiescent. Hanging, pinned, trapped or overloaded pieces, advanced passed pawns, or poor king safety for one of the sides should raise warning signs. >I'm not sure I really understand the subtleties involved with this problem since >I have not toyed with it myself, but I have two ideas about how to solve this >problem. > >First idea. When you store all of your data for a position (current hash key, >best move, score, etc.) in the transposition table, store the hash key for the >previous position. You may be able to use this by itself, but it is probably >better combined with the second idea. > >Second idea. When you store data in the transposition table, in addition to >storing information about what the score represents (lower bound, upper bound, >exact score), store information such as 'this score is based on an altered >search', or 'this score is based on a reduced search', or whatever. > >With those two ideas, I think you could probably use the data from a >transposition table probe more accurately. For instance, if it is a normal >score, use it normally (for cutoffs or whatever). If it is an altered score, >then maybe you will only use the best move for move ordering. > >What do you think? Do these ideas do anything to solve the problem? Do they >introduce new problems? At least for my engine, I'm afraid these ideas wouldn't help me much. The first idea could work, but it has the obvious disadvantages of increasing the size of the hash table entries, and of reducing the number of hash table hits. The problem with the second idea is that 'this score is based on an altered search' would be true for almost every node of the tree in Gothmog (even in the rare case that no move has been pruned, reduced, or extended for evaluation-dependent reasons, there will usually be some node in the subtree where this happens). Using this idea would be almost equivalent to completely avoiding the use of hash table cutoffs. Tord
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.