Author: Andrew Williams
Date: 16:24:56 06/25/04
Go up one level in this thread
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. Andrew
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.