Author: Dann Corbit
Date: 16:56:04 05/08/01
Go up one level in this thread
On May 08, 2001 at 19:35:28, Dan Andersson wrote: >>If you are right, your program will absolutely blow others out of the water. I >>hope you are right also. Of course, the discovery of such an algorithm will >>*still* mean that chess is O(exp(n)), for those that know what the term means. >>-- wink, wink. >There is no way in hell I can think of to get such behaviour from my programs >search, but there are some theoretically correct pruning methods hidden in >there. No, I won't tell. Well, having said that, will you say if there are theoretically sound forward pruning techniques beside proof number search? >>Be that as it may, I think it may stay exponential -- just thinking about the >>problem set. As long as we have any sort of probability of two possible good >>choices at multiple points in the path, I am sure you can visualize the >>exponential nature. >The beauty of the proof set and proof number search is that there is always one >most proving node. The problem is generating the tree, generating a possibly new >most proving node, if all positions are already available there might be some >way to avoid a combinatorial explosion. Define "all positions already available." Surely it can't mean what it sounds like, so I assume you are talking about small subtrees -- probabaly already pruned (soundly!) at that. ;-) Speaking of sound/unsound pruning techniques... As everyone knows, NULL move is theoretically unsound. Suppose that I use NULL move with R=2 and (starting with ply 1) my R=2 algorithm always completes two more plies than the non-NULL move version. In a case like that, the algorithm is theoretically unsound as a function of plies, but not as a function of time. So can we come up with more than one definition of theoretically unsound? [snip]
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.