Author: José Antônio Fabiano Mendes
Date: 10:30:21 05/09/01
Go up one level in this thread
On May 09, 2001 at 13:07:03, Robert Hyatt wrote: >On May 09, 2001 at 12:49:46, Uri Blass wrote: > >>On May 09, 2001 at 10:02:05, Robert Hyatt wrote: >> >>>On May 09, 2001 at 00:41:38, Uri Blass wrote: >>> >>>>On May 08, 2001 at 23:44:33, Robert Hyatt wrote: >>>> >>>>>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. >>>>> >>>>> >>>>>I want to point out that the above is apples and oranges. apples = number of >>>>>unique positions on a chess board; oranges = number of unique positions that >>>>>occur in games. Why are they different? It has to do with 3-fold repetition >>>>>and the 50-move rule. IE each unique "position" as you are calling them can >>>>>be counted as a huge number of chess positions, because there are _lots_ of >>>>>ways to reach the same position by different sequences of moves. And each >>>>>of those positions, even though they match piece for piece on the board, they >>>>>are totally unique. >>>>> >>>>> >>>>>> >>>>>>>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. >>>>> >>>>>Why not just pick up any theory book and see where a tree search is >>>>>placed in complexity classes? I'll be happy to cite a couple of dozen such >>>>>books on my office bookshelves... >>>>> >>>>>You are contradicting your self multiple times. Simple sorts are O(N^2). >>>>>Yet for infinite input they _never_ terminate. Yet they can be sorted with >>>>>an algorithm in polynomial time. I can give you a sample of a non-deterministic >>>>>P algorithm as well if you want. NP or not NP doesn't have anything to do with >>>>>a specific problem instance. It has everything to do with how the problem >>>>>behaves as the number of input values increases. In the case of chess it is >>>>>clearly exponential, which is _not_ any form of a polynomial. >>>> >>>>No >>>>Chess is clearly polynomial and even O(1) like every solvable problem that is a >>>>practical problem. >>> >>> >>>Then give me a polynomial with a term for depth that will produce the number >>>of nodes the tree will contain for any depth D. >> >>No problem for chess. >> >>my polynom is only the constant 999999999999^99999999999999 "Who Can Name the Bigger Number?" [an interesting article] http://www.cs.berkeley.edu/~aaronson/bignumbers.html > >OK.. now prove to me how that serves as a complexity estimate for a tree >defined as N = W ^ D. > >or you can pick +infinity (a constant defined by 1/0) as your "polynomial" >if you want. And again, this has _nothing_ to do with complexity... > >I want a polynomial that estimates the size of the tree based on the depth >being searched, and the branchinf factor. I don't want a constant that you >"suppose" represents the upper bound on the tree size. First, your upper >bound is contrary to the rules of chess since the 50 move rule is not >an absolute game-ending condition. > >You are greatly confusing complexity with bounded or unbounded. > >From a well-known book: > >"The time complexity of the algorithm, or the running time, is O(f(n)), if >f(n) is a bound on the number of operations needed to complete the computation. > >N = W ^ D is _clearly_ a bound on the size of the tree search space for >branching factor W searched to depth D. Clearly the complexity of minimax is >O(W^D) which is _not_ a polynomial in any shape, form, or fashion. > >It is a problem with exponential complexity, not polynomial and not even a >non-deterministic polynomial solution, by simple induction as well as citations >in various books. > > > >>This polynom gives an upper bound for the number of nodes for any depth D. >> > > > >So you are saying that 99999999 ^ 9999999999 is bigger than W^D for all D? > >Or in effect, you are saying that A ^ A is bigger than W^D where you pick >A? OK... I'll bite. I make W = A+1 and D=A+1 and your "polynomial" fails. >For any value of A you choose, in fact. > > > > >>Note that programs do not have to search depth D>9999 because after searching to >>this depth you found the best move and deeper search is going to change nothing. > >Please cite a reference to prove that. I know of no theory that says that >9999 half-moves is the deepest allowable tree. I know of the rules of chess >that clearly allow games to go longer than that. > > > >> >>if you did not find forced mate then it is clearly a draw because of the 50 move > > >no it isn't, since the 50 move rule is not an absolute limit. > > >>rule and if you found a forced mate there is no point in searching deeper. >> >>Uri > >Suppose we find there is a forced mate in 150000 plies? And none sooner? >Can you prove there isn't? I can't prove there is. So we just wait. And >deal with an exponential complexity algorithm as it slowly gets closer and >closer to answering the question.
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.