Author: Stuart Cracraft
Date: 16:32:31 06/25/04
Go up one level in this thread
On June 25, 2004 at 19:20:08, Dann Corbit 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... > >Internal iterative deepening. >http://www.chessbrain.net/beowulf/theory.html > >>>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) > >SEE will probably help a lot. Yes -- I must. > >>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. > >What is your fail high percentage? If it is below 90, then you can have a large >improvement in fewer nodes searched by better move ordering. I need to collect this statistic. > >>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. > >I assume that you use an aspriation window? Yes -- alpha=eval-1p to beta=eval+1p of previous iteration's search value. If 1st iteration then eval is set to static board eval without search. > >It looks like most of what is left for improvment could be through razoring or >other frontier pruning types of ideas. But they have danger, of course. > >What is your NULL MOVE set to for reductions? It is R=3. Have tried 2, 4, 5, ply/2 and ply-2 where ply is the current iteration depth being searched. Every higher search results in a massive additional decrease in total nodes searched. I haven't played out any games though so I don't know the quality of the moves with the much higher reduction settings for the null move search. I question the R=2 and R=3 recommended settings for high-depth searches (see other thread.) Thanks. Stuart
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.