Author: Dann Corbit
Date: 18:10:15 01/20/06
Go up one level in this thread
On January 20, 2006 at 20:29:04, Joseph Ciarrochi wrote: > > >engines try to exclude a number of bad lines quickly to improve depth of >search.. Let's say one of those bad lines turns out to be good at a depth of 12. >Once the line is excluded, how does the engine go back to it? > >for example, let's say a queen sack looks terrible at depth of 3, and its value >is only discoverable at depth of 10. Once the queen sack is excluded at depth of >3, how does the engine later discover that the queen sack was a good idea? One of two ways: 1. Fail low on the pv node 2. Fail high on the non-pv node. #1 means that we think things are great with our current choice of move, which is why we picked it in the first place. But deeper search may turn up something bad (called a fail low -- BAD for a pv node, GOOD for non-pv nodes). When that happens, we widen out our window and desperately search for something better. #2 means that we were happy with our pv node -- indeed, it probably failed high. Maybe our score is +100 centipawns (we imagine ourselves to be 1 full pawn ahead). But when we did our next iteration (e.g. going from ply 13 to ply 14) we suddenly saw a big bonus on one of the non-pv moves. Now, we widen out our search, and research the new fail high node. This time, we're happy. Because we had something good and found something even better. All chess engines use some kind of alpha-beta variant for searching. To understand this algorithm, read this: http://www.seanet.com/~brucemo/topics/alphabeta.htm It's definitely the best alpha-beta description that I ever saw. Not wild about his font, choice though, so I copy and paste it to notepad.
This page took 0.42 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.