Author: Robert Hyatt
Date: 18:50:50 05/09/01
Go up one level in this thread
On May 09, 2001 at 20:35:54, Ricardo Gibert wrote: >On May 09, 2001 at 18:36:49, Robert Hyatt wrote: > >>On May 09, 2001 at 18:00:24, Ricardo Gibert wrote: >> >>>On May 09, 2001 at 16:24:02, Robert Hyatt wrote: >>> >>>>On May 09, 2001 at 14:08:10, Ricardo Gibert wrote: >>>> >>>>>On May 09, 2001 at 14:04:55, Eugene Nalimov wrote: >>>>> >>>>>>Uri, there is branch of the mathematics (not even computer science, just >>>>>>ordinary mathematics) that studies the complexity of algorithms. Algorithms were >>>>>>used in mathematics long before computers appeared, for example GCD algorithm >>>>>>was known to the classic greeks. >>>>>> >>>>>>*Very* rude explanation of big-O notation is: you have the algorithm that >>>>>>require M operations (or steps, or machine instructions, or clock cycles, etc.) >>>>>>when input in N elements long. You are increasing length of the input; how much >>>>>>operations will be necessary now? That has *nothing* to do with the fact that >>>>>>majority of practically used algorithms will terminate in finite number of steps >>>>>>when input is finite. >>>>>> >>>>>>Eugene >>>>> >>>>> >>>>>But the the length of the input does not increase and that's the whole point. >>>>> >>>> >>>> >>>> >>>>But it does. From 38^1, to 38^2, to 38^3, ... to 38^N where N is huge. >>>>There is no linear relationship to express that cost per additional >>>>ply. There is no polynomial either. And it can not be done with an NP >>>>algorithm either. >>> >>>http://www.icdchess.com/forums/1/message.shtml?168847 >>> >>>> >>>> >>>>You say chess is finite. I say it isn't. Until the FIDE rules are changed, >>>>it _clearly_ is not finite. >>> >>>The fact the both players are not required to invoke the 50 move rule changes >>>nothing as far as solving chess is concerned. It can be proven that it is in the >>>best interest for at least one side to invoke the 50 move rule. >> >>No it can't. Suppose the game turns out to be a forced draw? I and my opponent >>are long-lived (we can live as long as the universe surivives) and the prize >>for winning the game is all the wealth in the universe. For such a prize, I >>am willing to play for a few zillion years to try to win, since no one has >>proven (yet) that I can't. My opponent wants to do the same as it is winner >>takes all. So we play on and on and on, trying to find a way to win. Yes, >>you might say "but once you win, it only proves I would have taken the draw >>when I had one of the many chances." But hindsight and all that... So what >>_forces_ the game to be finite until it is proven to be a forced win? And if >>it isn't, it is obviously infinite in size. >> >> >> >>> To solve chess >>>this can be assumed that at least one side will invoke the 50 move rule without >>>changing the outcome. As far solving chess, it can be treated as finite even if >>>is not actually finite. >> >>How? If you can't prove one side has a forced win, then it is totally unbounded >>as the game can go on and on with both sides _trying_ for a win. > > >If side X has a win and 50 moves elapse without a pawn move or capture, then >side X has played suboptimally against side Y and the algortihm must backtrack >to find where it went wrong. If side X has a loss and and 50 moves elapse >without a pawn move or capture, then the algorithm must backtrack to find where >side Y went wrong. If sides X & Y have only a draw, there is no point is >continuing. In every case, there is no need to go beyond 50 moves. Why do you think this is true. We already _know_ that in the 5-piece endings, and even more commonly in the 6 piece endings, we have positions that are forced mates in > 50 moves. In a game where it is "winner take all" I would continue playing even if I knew I was in a mated-in-N position because if I claim the draw, I get nothing, if my opponent wins, I get nothing, and if he plays sub-optimally I might get the grand prize... If we can't prove a forced mate, then we have to resort to something else. As it is possible that wins exist beyond the 50 move rule at any time. And since the rules allow both players to play on if they wish, I don't see how we can force them to stop... nor can we arbitrarily say "no wins in X moves, we therefore call this a draw". The three-fold repetition problem is much less of a hindrance than the 50-move rule. But fortunately neither is forced. You might search the tree and say a repeated position is absolutely a draw, and have that as a legitimate bound, but not the 50-move rule. Because I can construct lots of positions with just 6 pieces on the board where one side wins in more than 50 moves with no captures. I can do the same for 5 pieces. I haven't checked on the 4=piece files... So, in leaving this argument, I want to make two points: 1. My books on complexity don't require N to be unbounded. One of five says "for all N" but I don't read that to require it be unbounded. I can say "for all chess addicts" knowing (a) that is a large number; (b) that I have no idea how many there are other than it is a large number. I could also read that as "for all interesting N" how hard is it to sort something, compute something, search something, etc... and each time I increase N, how much more work do I have to do to do it. 2. In one book, quicksort is covered in detail, with a finite number of values, used to illustrate the NlogN complexity of it. I think that the only requirement is that the O() function must function for any N value you can reasonably give, so that the function doesn't suddenly become discontinuous or change to exponential from polynomial or whatever... I don't find any text that says specifically "for something to be of complexity of anything but O(1) it must have an unbounded number of possible values". To do so destroys too many examples. Weather forecasting was one I gave. Do you do atmospheric samples once per square mile of surface area on the planet? once every 100 square yards? once every square foot? Every square inch? every square mm? Every square angstrom? There is a definite bound on that data set, because atmospheric sampling doesn't apply at subatomic distances. So is that _really_ O(1)? Not in any book I have _ever_ read. Not in any journal paper either. They all give that problem as a polynomial complexity even they _know_ that there is a upper bound on the number of atmospheric samples that can be taken on planet Earth. I have a hard time thinking of any truly non-O(1) real-world problem, based on that. I'm sure the Navier-Stokes guys are most interested in the O(1) solution to their CFD problems just the same. :) I don't want to keep the argument going... It borders on the religous wars from math discussions about what is the value of infinity/infinity? I simply use complexity theory in the way it has been used forever in computability discussions... as I add input how much does it cost computationally. Any other point of view is esoteric and impractical... > >In the real world, you can continue playing, because humans make mistakes, but >this of no consequence to an algorithm that has the aim of solving chess. > > >> >> >> >>> >>>You do something similar in your program in treating repetition of positions. >>>You assume it is equal when the position repeats within the PV even if it is not >>>really equal. You do this, since it is a harmless assumption if you handle it >>>right. Repeating a position already played is not the same as repeating a >>>position that only occurs in the PV. If that distinction is not made, there will >>>be problems. >> >> >>Actually I do it pretty much right, near the root. out in the tree I take >>liberties to avoid draws that I couldn't see otherwise. But that is prone to >>error.
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.