Author: Tony Werten
Date: 00:25:14 12/01/00
Go up one level in this thread
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. cheers, Tony > >>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.