Author: Mark Rawlings
Date: 08:34:21 01/21/05
Go up one level in this thread
On January 21, 2005 at 04:27:23, Dann Corbit wrote: >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. Just a clarification: Regular 8x8 Othello is not solved; only the 6x6 version was solved. Based on what's going on with the 10-piece databases for checkers, I'd say checkers will be solved long before 8x8 Othello. Mark
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.