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