Author: Robert Hyatt
Date: 05:45:11 05/05/98
Go up one level in this thread
On May 04, 1998 at 16:38:43, Roberto Waldteufel wrote: >I have read about the singular move extension heuristic as used by >Deeper Blue, and indeed about extension heuristics in general. I have >also experimented with some variable depth schemes in my search trees. >One quite promising idea is to set the depth to some arbitrary value at >the start of each iteration (this value being increased a little prior >to each successive iteration), and then decrease the depth at each odd >level by an amount proportional to the logarithm of the number of legal >moves for the opponent at that level, and calling a quiescence search >when this depth drops below zero. The depth remains unchanged at even >levels. This has the effect of pusuing forcing lines for the machine >much deeper, even if some quiet moves are interspersed between the >checks. It works very well for some tactical positions where the machine >can mate or win material through a long sequence of moves, most, but not >all of which are checks. > >I understand that in the singular move extension scheme, the node is >extended if its evaluation is significantly higher than that of its >next-best sibling, but I do not understand exactly how this condition >can be tested when a beta-cutoff occurs, since the evaluation scores for >some of the sibling nodes is then not known to the algorithm. Can >anybody enlighten me? > >Robeto Waldteufel If you read the Deep Thought team paper on singular extensions, what you find is that on a "fail high" node, when you get a fail high condition you can *not* return(beta) at that point. Rather, you *still* have to search the remainder of the nodes. But if you search them to normal depth, this turns into a minimax tree that is unaccaptable, so what has to be done is to search the remainder of the moves to a reduced depth (ie depth-2 is a good starting point). This controls overhead, at the cost of some accuracy. The remainder of the moves are searched with an offset alpha/beta window, alpha-X, beta-X, where X is found by testing. If *all* moves fail low with that window, then the move that failed high is "singular". It is researched with depth+1...
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.