Author: Robert Hyatt
Date: 14:21:30 09/15/04
Go up one level in this thread
On September 15, 2004 at 15:54:40, Gerd Isenberg wrote: >On September 15, 2004 at 15:11:35, Robert Hyatt wrote: > >>On September 15, 2004 at 14:48:51, Gerd Isenberg wrote: >> >>>On September 15, 2004 at 12:17:14, Robert Hyatt wrote: >>> >>>>On September 15, 2004 at 09:53:53, Stuart Cracraft wrote: >>>> >>>>>Hi, >>>>> >>>>>Anyone know of some code somewhere that implements >>>>>at least part (or all) of the originally described >>>>>singular extension and/or any modifications to it that >>>>>have proven worthwhile (if any)? >>>>> >>>>>I am curious what mediocre (or better) results people >>>>>have gotten with singular extension. Originally Anantharaman >>>>>hypothesized that it wouldn't be good at the slower >>>>>speeds of most programs at the time and would require >>>>>fast speeds to show effect. Has this proven true or >>>>>false in the intervening 15 years? >>>>> >>>>>Is singular extension now generally discredited as a >>>>>non-reproducible singularity in and of itself? >>>>> >>>>>Thanks, >>>>> >>>>>Stuart >>>> >>>> >>>>It worked in Cray Blitz for the last two years it competed. How much it >>>>improves overall chess skill is debatable. Early on the DB guys claimed very >>>>significant improvements. Later more thorough testing showed that there was >>>>definitely an improvement, but not as large as originally thought. >>>> >>>>I have not really spent a lot of time doing this in Crafty although there is a >>>>SE version roaming around that I released, but it didn't do SE like the DB guys >>>>did. Their implementation is not a 2 week deal. Expect to spend a year getting >>>>it working as they did, if not more. >>>> >>>>Some commercial programs use variants. IE Wchess used the PV-singular part of >>>>singular extensions, but not the fail-high part the DB guys defined. >>> >>>There are so many applications of a reduced/modified pre-search to gain more >>>informations for better move sorting, pruning, extensions and reductions. >>> >>>1. Internal iterative deepening >>>2. Nullmove oberservation or pre-verification >>>3. Looking for singularity >>>4. Looking for multiple beta cuts >>> >>>I wonder whether there is an approach to combine a few of them on cut-nodes. >> >>Hsu's paper defined singular extensiosn for PV nodes and CUT nodes. His paper >>said "we have found no useful definition for a singular move at an ALL node >>however.." > >Hmm isn't the definition simply that there is one move which is by a certain >amount better than all others, independent on pv-, cut- and all-node? No. There is a precise definition of a singular move, but the test is only defined for PV and CUT nodes. At an ALL node there is absolutely no way to determine if one move is better than all others. > >Probably the forced situation, that there is only _one_ move (e.g. becomes >alpha while all others are less alpha-margin), makes it worth to look deeper to >look whether the all-node becomes a singular cut node or improves alpha, with >possible influence at the root. That test won't work. Tests where the value is <= alpha or <= alpha-margin are really meaningless in the context of alpha/beta/minmax search. That is why they could not define a workable test for singularity at ALL nodes. > >> >> >>> >>>Btw. considering minimal tree node types, pv-, cut- and all nodes >>>(pv most left, cut successor from pv or all, all successor from cut) >>>What information may we gain, for a cut node, where only one successor has to be >>>searched in a minimal tree, if it behaves like an all node? >> >>All I can immediately think of is that your move ordering is bad at that CUT >>node, because by definition you only need to search 1 move at a CUT node, and >>not even the best move, just one "good enough to produce a cutoff." > >Yes, but even considering rather perfect move ordering it should happen in >practice - otherwise you will never found a better move at the root. > >I'm interested in some statistics, how often cut-nodes behave all-like (eval >fails, first fails, all fail), same for all nodes with cuts and this correlates >with branching factor - and the influence of several move ordering heuristics. > That is what my "fail-high-on-first-move" metric in Crafty measures. How often when you fail high is it on the first move??? There is a slightly different metric that can be defined which is how often is an ALL node really a CUT node, generally caused by poor move ordering issues that we all suffer from... >Hmm, is it worth to update node types incrementally during search? >I guess with a counter of played pv-moves (0..N) in the top of the current path >and ply index one may determine the minimal tree node type as well... >So we have distance D of the current node to the last pv node in the current >path. > >If D == zero we have a pv-node. >If D is odd we have a cut node. >If D is even and greater zero we have an all node. > > >> >>>E.g. if static eval <= alpha or even first move doesn't improve alpha? >>> >>>Thanks, >>>Gerd
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.