Author: Russell Reagan
Date: 00:50:37 01/21/05
Go up one level in this thread
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.
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.