Author: Dann Corbit
Date: 01:27:23 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. Tic-Tac-Toe is exactly analogous to chess. I have 9 choices for my first move. My opponent has 8 choices for his move, so we have 72 possibilities so far. Obviously, the game is exponential also. The plies are less and the choices are less. But it is still exponential. If you had to work out all the possibilites with pen and paper, then it wouldn't seem so trivial. The total games are less than 9! since some games finish early. But the same sort of thing is true in chess. Obviously, an computer can make tic-tac-toe to be trivial. Similarly (but slightly harder) for Connect 4. Othello is solved, but it was a lot harder than Connect 4. Checkers will be solved soon, but it was a lot harder than Othello. In 10 years, Checkers will be what Tic-Tac-Toe is today. Trivial.
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.