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