Author: Uri Blass
Date: 02:51:32 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. No it is trivial draw also with pen and paper because of symmetry reasons. I can draw it easily against every opponent. Here is the strategy when I begin to draw. 1)put X in the middle ___ _X_ ___ 2)if the opponent put O not in the corner then I see easily forced mate in 3 by 2 moves to the corners when the second move to the corner create double threat or win immediatly so the opponent has to put O in the corner(because of symmetry which corner is not important) ___ _X_ __O 3)I put X in the corner of the same diagnol X__ _X_ __O 4)The opponent has to put O in another corner to prevent the threat of mate in 2 by putting X in another corner. X__ _X_ O_O 5)I have only one place to put X to prevent mate in 1 and I threat mate in 1. X X OX0 6)the opponent has only one possibility to prevent mate in 1 XO X OXO 7)It is easy to see that the result is at least a draw for the X side because the O side will be able to use only one O and with one more O the opponent cannot win. Now you only need a strategy to be sure of at least a draw for the O side It may be harder to explain everything there but it is still easy and expereinced humans will draw every game easily. Uri
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.