Author: Dann Corbit
Date: 20:18:01 01/20/05
Go up one level in this thread
On January 20, 2005 at 22:44:13, Russell Reagan wrote: >On January 20, 2005 at 10:40:11, Robert Hyatt wrote: > >>There are those that will argue that the complexity >>of chess is O(1) simply because chess is finite. And once you search to the end >>of the game, further searches will take no longer (going deeper produces no new >>information and takes no more additional time since every branch stops when the >>game ends along that branch). But I'll leave that nonsense to those that want >>to take things too literally. :) I'll use the good old stand-by O(W^D) for the >>complexity of chess for today, tomorrow, and for as long as I personally will >>live... >> >>This is one of those discussions that do nothing more than waste time and >>bandwidth, with neither side able to convince the other of whether it is O(1) or >>exponential. :) > > >Using the same logic which concludes that chess is O(1), isn't a linear search >also O(1)? To use a tool such as O-notation in such a way seems to render it >useless (to the person who uses it incorrectly). > >Reminds me of the person who goes to the doctor and says, "Doc, it hurts every >time I bend my arm like this..." And the doctor says, "Then stop bending your >arm like that." > >You are right. What a waste of time. On the other hand, is Tic-Tac-Toe exponential? Strictly speaking -- yes it is. But even the lamest computer can solve it minimax in a fraction of a second. So there can come to be some point where it no longer matters that it is exponential because the compute speed has caught up to the size of the problem and it has really become O(1). So it is not something that we can just dismiss as irrelevant. I think this is especially the case when the input is fixed (as in the case of an adversarial game) rather than sorting or something where we might want to sort the cards in a deck, but we might also want to sort all the CTAG sequences in Chrysanthemum DNA.
This page took 0.01 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.