Author: Roberto Waldteufel
Date: 17:03:15 05/05/98
Go up one level in this thread
On May 05, 1998 at 14:47:43, Don Dailey wrote: >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 > >Robeto, > >I don't understand. Is part of this algorithm never to stop on an >even ply number? > >- Don Yes, that is right - well almost, anyway. The idea is to search for a win for the side to move, ie the machine. The algorithm only stops on an even ply if either a) the position has occurred already in the current variation, in which case it is scored as a draw b) The side to move is in checkmate or stalemate c) the depth at the parent node was already less than zero, in which case the search is in "quiescence mode", implying that the previous ply was a capture or a move to get out of check. Orriginally I kept two depth scores, one for even plies and one for odd. Each depth was consulted or decremented only at its appropriate levels in the tree. The stop condition was then for the sum of the depth scores to fall below zero, but this did not work well, since usually ony one side is severely restricted in choice of moves. Hence I did away with one of the scores, so the algorithm decides whether or not to keep searching based solely on the restriction of moves of one side, (the defending side),without regard to the number of choices available to the attacker. The use of a logarithmic scale for depth reduction is used to simulate the effect of multiplying the number of moves available to the defender at each ply to form a sort of one-sided combined branching count. It's just more efficient to use addition instead of multiplication to calculate this branching count. Roberto
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.