Author: Tony Werten
Date: 03:00:25 11/30/00
Go up one level in this thread
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. > >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, I'm not really sure, but I'll give it a try. It seems that before you stopped quiescence search when MVV/LVA gave a negative score. If this is true, you will not get a smaller tree with SEE. What you did was tossing out almost all captures. You can not get a smaller tree than that. ( Well, if you search 8 ply, toss out anything deeper than 6 ply is about the same) Unfortunately it's not correct. Using see will gave you a better quality, but you have to search more nodes. Before you only searched upwards captures like BxR wich are always wins. With see you search the same plus RxB, RxR, RxR. That's always more nodes. cheers, Tony >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. > >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). > >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. > >A few days back I posted these numbers at d2d4 d7d5 e2e4 e7e5... here is what I >am seeing with SEE move ordering: > >>Monsoon With SEE >>1 45 109 >>2 621 1064 >>3 3725 4348 >>4 14146 15678 >>5 38694 45627 >>6 183449 169397 >>7 598020 725485 >>8 1286875 2114973 <= this is the one I am most worried about... 2x the size > >The breakdown is 666433 internal (search nodes with children in search), >757424 horizon (nodes at depth zero -- also counted as qnodes), >1447872 qnodes (depth zero and their descendents in qsearch), >668 leaf (win/loss/draw positions). > >Thanks again for all the help, >Scott
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.