Author: Dann Corbit
Date: 17:18:09 05/09/01
Go up one level in this thread
On May 09, 2001 at 20:07:29, Ricardo Gibert wrote: >On May 09, 2001 at 18:28:21, Dann Corbit wrote: > >>On May 09, 2001 at 18:20:59, Ricardo Gibert wrote: >> >>>On May 09, 2001 at 17:40:16, Dann Corbit wrote: >>> >>>>On May 09, 2001 at 17:32:27, Ricardo Gibert wrote: >>>>[snip] >>>>References: A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for >>>>n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, >>>>Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A >>>>31 (1981) 199-214. >>>> >>>>FCOL >>> >>>n is clearly finite, but unbounded in the above, so the time required is >>>exponential. All quite correct. This is a perfect example that makes *my* case. >>>The authors clearly understand about big-O perfectly. They took the pains to >>>generalize the problem to n*n chess. They didn't just say chess, because they >>>understood perfectly that that would not be correct, which is all that I've been >>>saying. >>> >>>It's clear people cannot tell when a variable is bounded or unbounded and what >>>is meant by finite and infinite and when a variable has been instantiated and >>>when it has not and what the difference between an instantiated variable and a >>>constant, etc. >> >>Here are some references that classify chess as NP. One goes so far as to offer >>a formal proof: >> > >The references to chess in this one are incoherent: >>http://www.cs.duke.edu/~dr/1.00s/L37.html "Intractable Algorithms Chess Note: here N is number of moves looking ahead. We Have an Algorithm! Layers of look ahead: If I do this, then he does this, .... Problem Solved (?!) Can Represent Possibilities by Tree Assume 10 Possibilities Each Move t = A * 10^N !!!! Exponential Sample Numbers " Seems plain enough to me. >This one references "linear chess" but does not define what they mean by it: >>http://www.cs.bu.edu/fac/lnd/toc/z/node18.html > >Here they discuss alphabeta and minimax as applied to chess. Just because >alphabets and minimax are O(exp(n)) does not mean that task of solving chess in >O(exp(n)): >>http://www.glyph.pe.kr/phoenix/AI/AIChess4.htm > >This next one has the following to say about chess: > >"Exhaustive searching and naive game-playing programs (e.g., chess) have >exponential time complexity: O(2^N)." > >They qualify what they say with the word "naive", so I can't say they're wrong: >>http://www.cis.ksu.edu/~schmidt/300f00/Lectures/Week3.html > >The following is a less readable version of 2nd one you give above, which leads >me conclusion that you did not really examine this nor any of the others with >any care: >>http://www.cs.bu.edu/fac/lnd/toc/n-npcom >> >>Are they all confused? >>Or are they simply using the standard definition of P/NP? > >Note: >(1) that a "game playing program" is not the same as "solving chess" a program >that plays random moves is clearly not O(exp(n)). No arguments there. I do submit (however) that the task of solving additional plies is exponential in difficulty, even from a random board position. At least using my definitions. >(2) saying that "a certain algorithm that solves chess is O(f(n))" is not the >same as saying "solving chess is O(f(n))". You yourself gave an algorithm that >sorts in O(n!), even though the problem of sorting is O(n*log(n)) or even less. No arguments there either. I think I understand your definition well enough. It's different than the one I use, but well -- there we are. I use my definition to calculate whether tasks are feasible or not. Probably because my degree is in applied mathematics (numerical analysis) and I suspect your degree is in pure maths of some sort. The definition I use is valuable to me because it helps me to get work done effectively. I cannot use the definition that you offer because it does not create pragmatic or heuristic results. So I think it's time to simply give up the ghost as far as trying to reach some conclusion. I am certainly aware that there are others who use a definition very different from the one I use. As long as they don't use it to perform feasibility studies, I don't see any real harm in that.
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.