Author: David Dory
Date: 15:30:25 02/20/02
Go up one level in this thread
Uri, Forward pruning has been a proposed answer to effeciently limit the size of the search tree since the early days of Dr. Shannon. Unfortunately, no one has found a way to throw out the dirty bath water, without dumping the baby out also, so to speak. For a good discussion on this from an expert, take a read of Chess Skill in Man and Machine. This was one of the big differences between CHESS 3.6 and CHESS 4.5 You may recall that the Northwestern University Chess Program CHESS was world champion, several years. Quote from page 92 of the above: (Slate and Atkins) "The implementation of full-width searching had immediate beneficial results." The authors go on to say the correct search would indeed include a smaller tree using various techniques, some of which were not perfected. They give this diagram as an example of the problem of forward pruning: [d]2k5/3p4/b2p3p/1p1Pp1pP/pP2P1P1/P2N1K2/8/8 w -- the move Nf2 would, he felt, surely be pruned out. However, a full width search easily finds a nice knight's tour: Nd1, Ne3, Nf5, Nxh6. I think you'd be amazed at the number of "special cases" you would have to program into a forward pruner. In particular, I think you'd be adding such "special cases" until you realized you had slowed the program down so much, it was actually _weaker_ than a full-width program. There must be a better way to make a stronger program than forward pruning. Dave
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.