Author: Andrew Dados
Date: 09:57:21 12/02/00
Go up one level in this thread
On December 01, 2000 at 12:40:24, Bruce Moreland wrote: >On December 01, 2000 at 03:25:14, Tony Werten wrote: > >>On November 30, 2000 at 03:54:37, Bruce Moreland wrote: >> >>>On November 30, 2000 at 03:34:10, Scott Gasch wrote: >>> >>>>Hi again, >>>> >>>>The other day I posted about move ordering, tree size and SEE vs MVV/LVA. The >>>>response from experienced programmers was that a SEE was better than the naive >>>>MVV/LVA ordering, especially in the qsearch. So for the past couple of days >>>>I've been writing a SEE. It's based on crafty's swap code and understands >>>>pieces pinned to the king and xray attacks (pieces added to the attack/defend >>>>because of discovered attack). I have been through this code in a debugger and >>>>am about 99% sure it works fine. >>> >>>Detecting pins is no big deal, I think. >>> >>>Think about it from this point of view. Set up a position from a random game, >>>and make a random move. What did that move very likely do? Leave a piece >>>en-prise. I be that most of the cases handled by the SEE don't involve anything >>>tricky. >>> >>>>When I finally got around to testing the new SEE's effect on the search tree I >>>>was surprised to discover that it actually increased the tree size in all of my >>>>test position. Both Bob and Bruce mentioned that there could be significant >>>>qsearch node savings with a SEE... perhaps I misunderstood how to implement >>>>this. I'm simply doing the same thing I was with MVV/LVA: stop considering >>>>nodes when the value of a capture becomes negative. Since the list is sorted, >>>>all the rest will be negative too. I am also doing "delta" or "futility" >>>>pruning -- if the stand pat score + the SEE value of a move + 1 pawn is less >>>>than alpha I again stop considering at this node. >>> >>>Maybe two years ago I turned by SEE off, turned MVV/LVA on, and my tree grew by >>>some factor like perhaps double. >>> >>>>My tree is not vastly larger than before but it is definately larger... >>>>especially as depth increases. The move order I am using currently is hash >>>>move, winning captures (as decided by the SEE), even captures, non-captures by >>>>history value, and finally losing captures (as decided by the SEE). >>> >>>Good order, although you should experiment once you think you have it running. >>> >>>>I am selecting the best move (by value) for all moves from a certain node also. >>>>Some have said that it's better to not waste the CPU on this selection process >>>>because in an "all" node you have to search them all anyway, who cares about the >>>>order. But when I experiment with only selecting the best N moves and then >>>>taking the rest as they come the tree size always increases. >>> >>>Fair enough, but the selection process has speed consequences. A 5% smaller >>>tree isn't worth attaining if you spend 10% more time per node getting it. >> >>I have to disagree with you on this one. Sometimes it's worth much more than 10% >> >>Suppose you have a branchingfactor of 5. You get a chance to reduce this with 5% >>at a cost of 10% in time. (normal node costs 1) >> >>ply normal cost reduced 5% extra cost 10% >>1 20 20 22 >>2 100 95 104 >>3 500 451 456 >>4 2500 2143 2357 >>5 12500 10179 11199 >> >>So depending on your average search depth you can decide how much extra time >>you're allowed to spend on reducing the number of nodes. > >I meant that it isn't worth reducing tree size by 5%, if your node rate drops by >10%. > >If your tree size is 60000 and your time is 60 seconds, you are doing 1000 nps. >If your tree size is 60000 * 95% = 57000, and your node rate is 1000 / 1.1 = 909 >nps, it takes you 63 seconds to search this tree. > >Regardless of the actual math, I think my point can be seen. Speed is a >function of both nps and tree size, and people who throw out one in favor of the >other are making a mistake. > >bruce If you reducing BF by x% at the y% cost of speed (y>x) it only depends on depth reached whether you actually go faster. Reducing BF gives you exponential savings... so if you move to faster processors and slower time control you can get faster while at blitz on 233Mhz you may get slower. Speed is a function of tree size, but tree size is combined function of BF and depth reached... -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.