Author: Ricardo Gibert
Date: 17:35:54 05/09/01
Go up one level in this thread
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. 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.