Author: Bruce Moreland
Date: 09:40:24 12/01/00
Go up one level in this thread
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
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.