Author: Scott Gasch
Date: 00:34:10 11/30/00
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, 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.