Author: Robert Hyatt
Date: 14:25:01 09/15/04
Go up one level in this thread
On September 15, 2004 at 17:21:30, Robert Hyatt wrote: >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. That is crude. The problem is that suppose you are wrong at ply=2. That causes you to mis-categorize every node below that because when you are wrong at ply=2, for non-PV ply=1 moves, it suggests that either the current ply-1 move is better than the best so far and you are changing your mind, or that the current ply=2 move is not the best and another move will cause a cutoff. But below that ply=2 move that is normally a CUT node, ply=3 would normally be an ALL node, but that changes since the ply=2 node is wrong. This was one of the many categorizing things I did in the Cray Blitz DTS "where to split" code to try to be sure I hit on an ALL node, not a CUT 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.