Author: Dann Corbit
Date: 10:59:33 01/16/01
Go up one level in this thread
On January 16, 2001 at 10:35:52, José Carlos wrote: >On January 16, 2001 at 10:18:00, Roy Eassa wrote: > >>On January 16, 2001 at 04:17:22, José Carlos wrote: >> >>>On January 15, 2001 at 22:19:03, Dann Corbit wrote: >>> >> >>>>If a program has a better O(f(n)) algorithm, at some point it will dominate. >>> >>> Just in case someone does not know what this means: >>> >>> Suppose a car race with two cars. Car A acceletares very fast, but has a top >>>speed of 100 mph. Car B needs much more time to accelerate, but it can get 150 >>>mph. With little time, car A will get more distance than car B but, given enough >>>time, B will pass A and win the race. >>> >> >> >>So there really ARE programs that do proportionally better given longer time >>controls and/or faster CPUs than other programs (which do proportionally better >>with shorter time controls and/or slower CPUs)? >> >>Despite Christophe's many protestations to the contrary? > > I don't think I have experience enough to say Christophe is wrong, because >he's in this business since a long tima ago, and started my program less than 2 >years ago, but, IMHO, the answer to your question is yes. Just in my opinion. I >posted my arguments in this forum, so you can search in the archives, if you >want, and decice whether I'm right or wrong. The theory says that about algorithms (and the math backs it up). On the other hand, what is the superior algorithm that someone has invented? Chess search is an exponential process. Narrow the search too much and you miss important tactics. Widen the search too much and you don't see deeply enough. If there is a breakthrough algorithm (like Alpha-Beta was, like NULL-MOVE was to a far lesser degree) that might improve the algorithm enough to let some particular program dominate at long time controls. But I have not seen one demonstrated. So (in essense) the theory says that it is possible for some given algorithm to dominate. Practically speaking, I don't know what the algorithm might be. All the chess algorithms I know of are: O(exp(n)) Which is (and humorously so in this case) an algorithm which is generally considered 'unsolvable'! Of course, we realize that computers can play chess. But they can't play perfect chess. If someone found a chess algorithm that was O(n^2) it would clobberize every other chess program on the planet, given long enough time control. [Of course, long enough might be 'G/Century']
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.