Author: Dann Corbit
Date: 15:10:23 05/08/01
Go up one level in this thread
On May 08, 2001 at 18:05:08, Jesper Antonsson wrote: >On May 08, 2001 at 15:58:05, Dann Corbit wrote: >>On May 07, 2001 at 17:03:05, Jesper Antonsson wrote: > >>>I can use you as a reference. I remember you in RGCC discussing upper limits on >>>the number of distinct positions in chess and as far as I can remember you >>>agreed there was such a limit. Thus the search space is finite and you can store >>>partial results as you search, and when you have searched all nodes once, you >>>are done. "Another ply deeper" will be almost instantaneous, just as when you >>>find a mate in an easy position and then pull results from hash. NOTE: The >>>practicality of the above approach, or the number of atoms in the universe, is >>>totally irrelevant. > >>All inputs into any computer program must be finite. Otherwise, the program >>cannot ever terminate or even stop reading the input. > >Yes, and that is irrelevant. I haven't mentioned anything about infinite inputs, >by the way. > >>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. > >Yes, and for chess we can choose a constant that suffices for all N if f(N)=1. >In other words, when the depth is large enough, the search stops exhibiting >exponential properties and another ply won't take any more time than the current >ply, just as when you find mate. Is this so damned hard to understand? > >>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. > >It's you who don't know your theory. > >>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 >>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. > >Correct, and irrelevant. > >>Your arguments are absurd. > >*sigh* I will never solve chess. Humanity will probably never solve chess >either. A practical, live, chess search from the initial position will exhibit >exponential behaviour. Any real input to an algorithm will be finite. And all >that is all totally irrelevant. The point is that the chess search space is >theoretically finite, and therefore, at a large depth, the search will stop it's >exponential behaviour. That this depth cannot be attained in *practise* has >nothing to do with chess' NP-ness, because that is a theoretical property for >which such practical considerations is irrelevant. > >If you want to misuse well defined theory, I can't stop you, but this is getting >ridiculous. See my other message. By the way, by the VERY DEFINITION OF THE TERMS YOU ARE LAUGHABLY WRONG. ;-) The function f(x) = 1 is O(n!) also O(exp(n)) also O(n^3) also O(n) also O(log(n)) also O(1). Be that as it may, you have no idea what you are talking about. Go back to class and listen this time. ;-)
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.