Author: Tord Romstad
Date: 09:19:43 03/15/04
Go up one level in this thread
On March 15, 2004 at 09:17:31, Vasik Rajlich wrote: >Of course, selective search if done right will work, the commercial programs >prove this. At the moment, I am completely re-doing my evaluation. I think >selective search must be tied to the evaluation, and in particular the part of >the evaluation which measures the high-value aspects of a position. In the >middlegame, this is king safety. In the endgame, this is passed pawns. I am not sure I agree that a good selective search *must* be tied to the evaluation, but (as you already know) I believe that this is at leat one of the approaches which it is possible to make work. The following is a copy of an e-mail I sent to Vasik an hour or two ago. I post it here as well, in case somebody else is interested. Please take everything I write with boatloads of salt. My engine is not very strong, and more experienced programmers will probably laugh when they read about my primitive techniques. But because it might have some interest for newbies, and because the experts might enjoy a good laugh, here is a simplified description of how my selective search works: Hello, Vasik! As promised, I send you a brief description of how my selective search works. Because my search looks rather unconventional (for instance, as you might remember from CCC, I use the concept of the "cost" of a move instead of extensions and reductions), I've tried to translate what I do to a more normal language. First of all, I should mention that I use MTD(f), which means that all my searches are done with a zero width window. Therefore, the search fails high or low at all nodes. I call the static eval at all interior nodes, and use the evaluation to make many different search decisions, like explained below. Basically, I have two different selective search mechanisms. The first one is very simple, and is used in many programs (I think). In the last n plies of the search (n is currently 2, but I haven't yet decided whether 2 or 3 works best), I do what I call "static null move pruning". When the static eval returns a score >= beta, there are no hanging pieces, no mate threat, the king safety for the side to move is good, and there were no extensions in the last two moves of the path leading to the position, I just return the score without doing a search. I do something similar further from the leaves as well, but only when the score is *very* far above beta. The other mechanism is based partly on how a move changes the various components of the evaluation function, and partly on the history of the move. In addition to all the common extensions, I extend moves which dramatically changes the value of some evaluation component (usually king safety or passed pawns). If a move dramatically increases the pressure on the opponent's king, I extend the move. The magnitude of the extension depends on how much the evaluation component in question increases. At all nodes, the first three moves are always searched to full depth (or more, in case they are extended). When the first three moves fail low, I expect the node to be a fail-low node, and reduce the search depth for the remaining moves unless they seem particulary promising. All the remaining moves are searched with reduced depth unless one of the following conditions are satisfied: 1. The move is extended. In this case, it obviously doesn't make sense to reduce the search depth. 2. One of the last two moves in the path leading to the position were extended. 3. The move played contains a threat (of mate or of capturing a piece), or moves a hanging piece to a safe square. 4. The static eval or one of its components make a jump in positive direction when the move is made. 5. The move has often caused a beta cutoff in the past (I compare the history table entry for the move to the total number of nodes searched). When a reduced move fails high, it is re-searched with normal search depth. Like in the case of extensions, the amount of the reduction depends on just how bad the move looks. At the node directly following a reduction, I immediately return a fail low score if the null move search fails low by a big margin. In cases like this it is clear that the reduced move contains a dangerous threat, and it is too risky to search it with reduced depth. The idea of these reductions is that a move which does not appear promising and which very rarely has worked in the past is usually very unlikely to fail high. I also have some other search tricks which you perhaps would not classify as "selective search", but which might still be interesting to you: I use a dynamic null move reduction factor. The null move search is usually skipped unless there is a good reason to think that the node is a fail-high node (this is decided by comparing the value of the nstatic eval to beta, of course). When I am *very* sure of a fail high (huge static eval, no hanging pieces, safe king, and no other kind of danger reported after calling the eval), I use R=4 or (in extreme cases) R=5. In most "normal" positions, I use values close to 3. When there is some obvious kind of danger in the position (like an unsafe king for the side to move, or a high passed pawn eval for the opponent), I use values in the range 1 to 2, in an attempt to avoid horizon effect problems. Like many other places in my search, I also consider the path leading to the position when deciding which value of R to use. When there has been an extension in the last few plies, I avoid using values bigger than R=3. In the qsearch, I use the eval to decide which moves to search. The decision of whether or not to search checks is based mainly on the king safety of the opponent. If the static eval is slightly below beta, but there is a hanging piece which when captured will yield a score high above beta, I return a fail-high score immediately unless the position is too tactically complicated. If the position is only moderately complicated, I use a simple attack-table-based SEE to cull losing captures. In more complicated positions, I use a slower, but more accurate SEE. If the position is really wild, the engine decides not to trust the SEE at all, and searches all captures. I hope you will be able to find something of interest in the above description. Feel free to ask questions if something was not clear. Cheers, 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.