Author: Dan Andersson
Date: 14:28:07 05/08/01
Go up one level in this thread
A bit of nitpicking, nothing serious. >All inputs into any computer program must be finite. Otherwise, the program >cannot ever terminate or even stop reading the input. Thats not strictly true your program might operate on a stream that might or might not terminate. And the algorithm should only need a finite subset to compute an output. > >O(f(N)) means that the time spent by the algorithm will always lie below some >constant times the function f() if N is large enough. The problem here is that the number of chess positions are finite. > >Chess is exponential (with all current algorithms). To argue otherwise is just >plain silly. Similarly for other NP-hard problems or problems of any nature. > >Consider sorting. We are not going to insert an infinite set into our sorting >algorithm. Even if we could magically sort in O(N) it will never terminate. So An interesting example. We might have a perfectly sorted list for every N by inserting the new number when it appears. And that has the following connection to solving chess: By using the Science-Fiction device that generates all legal (maybe not a necessary condition) chess positions we have to ask ourselves what is the lowest complexity function that proves the graph. Really interesting question, need to think hard on this. I'm only speculating now, too tired to think really, but Proof Set (Not number)search seems a good candidate for a solution attempt and if so the solution could be =< O(N^2) I think. >we are *ALWAYS* talking about finite inputs. The type of function determines >how large a value of N is feasible. Will you solve a chess tree of depth 5000? >No. Not now. Probably not ever. As in never-ever. > >Your arguments are absurd. Thanks for making me use my noggin' Regards Dan Andersson
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.