Author: Michael Yee
Date: 15:45:07 02/16/04
Go up one level in this thread
On February 16, 2004 at 17:14:16, George Tsavdaris wrote: > >Stefan Zipproth wrote in http://www.zipproth.com/chess/tbs.htm : > >""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" >Is there an alternative to table bases? >Today's chess engines work by searching through all possible lines in a given >position. One could think that it may be possible to find a rule that simply >tells which move is the correct one, without having to search in the dark. >Unfortunately, this cannot be true for two reasons: > >A)Apparently there is no such (perfect) rule for most 3- or 4-men-positions >(else Nalimov would not have work), so it is very unlikely that there is such a >rule for 32-men. > >B)As far as I know it is possible to prove that there is no such rule, using the >mathematical theory of complexity. >""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" > >I don't think we can prove A) as the number of rules we can think is infinite. > >As for the more important B), although i don't know the proof of the above >theory he refers, i deeply believe that a rule that tells which move(s) is the >correct one, exists 100%. Also i don't believe we can prove that it is not >possible to prove that a rule for solving chess exists. > >So does anyone know if there is a proof or some information about the B) he >refers above? Regarding (b), I don't think complexity theory applies here. Normally when you say some problem (like the traveling salesman problem) is NP-hard or NP-complete, you are making a statement about the running time of algorithms as a function of problem instance size (e.g., number of cities in the TSP). In the case of chess, we just have one instance size (an 8x8 board). Similarly, when someone proved a while ago that minesweeper was NP-complete, it didn't mean that the game was unsolvable in any way. It just meant that there is "likely" no algorithm with a running time that grows polynomially with the size of the board. Michael Michael
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.