Author: Robert Hyatt
Date: 21:07:49 10/04/00
Go up one level in this thread
On October 04, 2000 at 12:57:25, Ricardo Gibert wrote: >On October 04, 2000 at 12:04:01, Mike Adams wrote: > >>>I'm sure there is some truth to what you are saying, but if Crafty needs to >>>search to a greater depth to find the same tactics, isn't that a sign of some >>>type of inefficiency? >> >> I've noticed that some things speed up search a lot while compromising the >>integrity of the idea of a pure search. Move ordering doesnt do this normally. >>If you search every node with simple Min Max or NegaMax it will be really slow >>but you will see everything up to the depth you search. Now if you include alpha >>beta and some move ordering like order like capture it will be much quicker and >>just as reliable. You'll get the same depth but faster. Now say you were >>getting depht 5, Now you add Null Move and Futility Pruning. Both these >>algorithms are to put it simply ways of finding out if certain parts of the tree >>get lower scores and therefor are not worth searching. Now your no longer >>searching everything. You're making estimates. Lets say this brings you from >>depth 5 to depth 7. Well its no longer a pure depth 7 search as you would have >>had if you searched every postion. Sometimes the result of this 'estimated >>search' will vary from a pure search. Well here is how I look at it. In many >>situations your 'estimated search' is good enought and your getting 2 extra >>depth. In some situations you miss things that you would have seen with a pure >>search at an earlier depth tell later. But that can be ok. lets say a depth 5 >>tactic doesnt appear untill depth 7 with 'estimated search'. Well if you did a >>pure search you would have got depth 5 and seen it. With the 'estimated search' >>you got depth 7 and finnaly saw it. As long as the extra depth required is not >>more than the gains from the 'estimates search' you really havent lost much. And >>often in the cases were things take longer to find it is the case that you'll >>still find whatever you would have found with the full search. Now lets say a >>tactic should show up at depth 5 you're getting depth 7 with this 'estimated >>search' and you miss the tactic because you need depht 8 or 9. Then you lose but >>from what i have seen with Pulsar it is much better to cut off the bad lines and >>get the deeper search than it is to be cautious and do a pure search every time. > >Alphabeta and futility pruning are theoretically sound so you can search deeper >without sacrificing soundness, while nullmove (a form of selective search) >involves making a tradeoff albeit an effective one. No forward pruning is completely "sound". Futility pruning is no exception. It can work well. And it can produce wrong answers. Which is why I no longer use it.
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.