Author: José Carlos
Date: 04:37:46 01/21/05
Go up one level in this thread
On January 21, 2005 at 03:50:37, Russell Reagan wrote: >On January 20, 2005 at 23:18:01, Dann Corbit wrote: > >>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. > > >Isn't O-notation used for analyzing situations where N can grow to infinity? >Describing 3x3 tic-tac-toe in terms of O-notation doesn't really make sense to >me. For 3x3 tic-tac-toe, what is N? At least for chess, N is practically >infinity, for now. Isn't N meant as the input elements number, like in a sorting algorithm or int he Salesman problem? Something we may vary and see how that variation affects the solution time? Chess and tic-tac-toe are constant problems in that sense, so O-notation doesn't apply, IMHO. You could use, for example, variable size board for tic-tac-toe, being 3 the minimum, and then ask yourself "how does solution time increase when I use 4x4 board instead of 3x3? Then you give a sense to O(N). José C.
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.