Author: Dan Newman
Date: 19:04:40 08/17/00
Go up one level in this thread
On August 16, 2000 at 19:05:36, Tom Kerrigan wrote: >On August 16, 2000 at 16:56:21, Andrew Dados wrote: > >>On August 15, 2000 at 19:24:25, Tom Kerrigan wrote: >> >>>On August 15, 2000 at 18:33:26, Larry Griffiths wrote: >>> >>>>On August 15, 2000 at 17:03:24, Tom Kerrigan wrote: >>>> >>>>>On August 15, 2000 at 13:43:55, Larry Griffiths wrote: >>>>> >>>>> >>>>>No matter how you generate your moves, you should always be searching captures >>>>>before killers. >>>>> >>>>>Also, at this early stage in your program's development, you should just >>>>>generate all your moves at once and move on. Doing this "quick killer" stuff >>>>>doesn't give you a very big performance gain and it makes your code much more >>>>>complicated. >>>>> >>>>>-Tom >>>> >>>>I am using a lot of code concepts from my previous chess program. >>>>This program is more object-oriented and uses bitboards heavily. >>>>My "quick killer" code reduces the search time up to 50% and I consider >>>>that a very good performance gain. >>> >>>That sounds odd to me. >>> >>>About 80-90% of your nodes should be in q-search, where you don't have to >>>generate killers. So the most you can possibly hope for from "quick killer" >>>stuff is 10-20% (and that obviously won't be achieved...). >>> >>>-Tom >> >>A well written qsearch shouldn't use more then 60% total nodes imo. >> >>Note a 'paradox' : if you can cut qsearch nodes by less then half from 90% down >>to 50% your program overall speedup is up to 5 times (non qsearch nodes go up >>from 10% to 50% of all). > >I think you're counting qsearch nodes differently than me. The way I count them, >I believe it's impossible to be < 60%. > >-Tom Yes. It makes a big difference whether you count qnodes as nodes reached by the qsearch or as nodes from which a qsearch is conducted. I've never been sure which makes more sense, but I've always chosen the latter, and that gives a much larger number. There is some logic (and practicality) to this choice on my part: 1) I count the root node as part of the full- width search, so I count the qsearch's "root" node as a qnode, and 2) I put a qnodes++ at the top of qsearch(), which is simple. Trying to count the other way would require more code. I did some crude calculations (which ignore iterative deepening) and got Q = (b-1)/b for the fraction of the minimum number of qnodes to the total number of nodes where b is the branching factor. So for the usual branching factor of 3 (null move, etc.) we get 66% or greater. In the endgame the branching factor can go below 2 and the qnode fraction can go below 50%, but elsewhere it's likely to be well above that 66%. (The (b-1)/b is for the case when there are no captures available when we step into qsearch(), so it is a minimum.) -Dan.
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.