Author: Dan Honeycutt
Date: 21:57:22 06/25/04
Go up one level in this thread
On June 26, 2004 at 00:22:45, Stuart Cracraft wrote: >On June 25, 2004 at 19:24:56, Andrew Williams wrote: > >>On June 25, 2004 at 19:11:34, Stuart Cracraft wrote: >> >>>On June 25, 2004 at 17:46:37, Dann Corbit wrote: >>> >>>>On June 25, 2004 at 16:55:47, Stuart Cracraft wrote: >>>> >>>>>On June 25, 2004 at 16:46:31, Dann Corbit wrote: >>>>> >>>>>>What is your branching factor? >>>>>> >>>>>>The best programs have a branching factor between 2 and 3. >>>>>> >>>>>>If you already have a branching factor in that range, do not expect any more >>>>>>really dramatic speedups. >>>>> >>>>>This seems like a very useful measure to implement but I am not >>>>>sure how it might be done. >>>>> >>>>>Take the # of total legal moves searched at each node (prior >>>>>to cut) and divide by the total number of nodes searched across >>>>>all nodes? >>>>> >>>>>Time between iterations in mine goes up about 2x >>>>>to 6x per iteration but this is obviously a different measure >>>>>than what you are suggesting. >>>> >>>>That is close enough. Look at the deeper plies to see what sort of time ratio >>>>you are seeing. >>>> >>>>If those average around 2-3, there is not a huge amount of fat to trim. If they >>>>average around 5-6, then you will still see some huge speedups. >>>> >>>>Are you using a pvs search? That cuts a lot of nodes. >>>> >>>>IID gives better move ordering and sometimes cuts nodes because of that. >>>> >>> >>>What is IID? I have iterative deepening... >>> >>>>Without knowing what techniques you are using, it is hard to speculate about >>>>what sort of speedups you might see. >>> >>>Yes I use PVS though currently the pv is not searched first and I wonder >>>how much that will help. However, the best move found by the previous >>>iteration is searched first on the next iteration as a very >>>cheap approximation. Eventually I will walk the transposition table for >>>the PV. >>> >>>Briefly, it has: >>>o iterative deepening (hash table not cleared through iterations) >>>o history heuristic (thank you Jonathan) >>>o 1-tier 1M entry transposition table (algorithm: replace-always) >>>o null move with reduction factor R=3 >>>o quiescence search all caps MVV/LVA (no SEE though) >>>o extensions: move in capture search to get out of check >>>o evaluation - just pc/sq at the present. >>> >>>There are no other search extensions, no fractional, extensions, no >>>futility, no razoring. >>> >>>So that's it. Bare bones. Just looking for big things I've missed >>>that won't take an arm and a leg to implement before the real >>>research can begin. Looking for double-digit improvement possibilities >>>that remain, if any. >>> >>>I wonder if searching the PV first instead of just the PV's first move >>>first would make a big difference. Probably so. Can't think of much >>>else on my own presently. >> >>Killers don't make a huge difference, but they're very easy to implement. Move >>ordering improvements will give a nice improvement - but only if your current >>move-ordering is poor. Do you measure first-move beta-cutoff percentage? This is >>a nice measure, if only because most people generate it. It is the percentage of >> nodes where a beta-cutoff is available and that beta-cutoff is discovered on >>the first move tried in the node. Over 90% for this measure is what you're >>looking for. >> > >Hi -- I implemented the measure (I think) and it is showing only about 70%. > >:-( That's good (not the 70 percent). You now know what needs work. SEE, history, killers - better move ordering. Dan H.
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.