Author: Uri Blass
Date: 10:33: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 > >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. The rules of chess say that the if a game takes more than 9999 half moves both sides can ask for a draw by the 50 move rule. If you do not assume that both opponents are stupid in your calculation then it is clear that one of them will ask for the draw so you can assume for practical purpose that it is a draw. > > > >> >>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? In this case the loser can ask for a draw during the game because of the 50 move rule so the mate is not relevant for deciding that the position is drawn. >Can you prove there isn't? I can prove for a bigger constant that there is not. The shortest mate is of less than 10^100 plies because every game of 10^100 plies include repetitions and if there is a mate there is a shorter mate with no repetitions. Uri
This page took 0.03 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.