Author: Antonio Dieguez
Date: 09:08:21 05/10/01
Go up one level in this thread
On May 09, 2001 at 18:09:38, Dann Corbit wrote: >On May 09, 2001 at 18:06:36, Uri Blass 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 >> >>The dimension of the board here is a variable and the problem of solving chess >>means to 8*8. >> >>Here n is not bounded so you can say that it is not O(1) and even exponential. >> >>You can say that from computer's point of view n is bounded because the computer >>has not enough memory for very big numbers but the bound is so big that for >>practical purpose we can assume that n is not bounded. > >Consult ANY text on NP problems. Chess will be listed as a classic example. That is not counting the 50 move rule neither the 3 rep rule. For practical purposes we could ignore them anyway, but I see only one easy bound that is the maximum possible movility^fixed depth.
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.