Author: Bruce Moreland
Date: 00:54:37 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. 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. >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 Here we go, right away. Why twice as many nodes in the first ply? You can dump this tree and find out. Is it doing a stupid move first? If so, why? bruce >>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.