Author: Robert Hyatt
Date: 15:36:49 05/09/01
Go up one level in this thread
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. > >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.