Author: Robert Hyatt
Date: 21:34:00 05/17/01
Go up one level in this thread
On May 17, 2001 at 17:50:11, Jesper Antonsson wrote: > >Well, too bad for you. I have stated all along that I was talking about chess >algorithms with the inherent constraints the rules of chess implies. > Here is a question: Go back a hundred years or so to before the 50-move rule and 3-fold repetition rules were added. Now is the game O(1) or O(W^D) since there is no real limit on the game at all... If you say O(1) how? Because nothing says a game tree can't have cycles, including an infinite number of cycles, just like the TSP can have cycles for the right data input. If you say now it is not O(1) then how can a simple rule-change cause this since from now to the end of the universe, each additional ply is going to take W times as long as the previous ply? If you limit the game to 50 moves max, period, or 100 plies, It is _still_ an exponential algorithm since searching 100 plies (or 38^100 positions) is _still_ not going to be done, ever... Warping theory to say O(1) simply turns O() notation into something that is totally meaningless / useless. Except for the theorists that might use that. The practical folks will live with the exponential nature of that O(1) search forever.
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.