Date: Fri, 20 Feb 1998 00:02:11 -0600 (CST)
From: Dave Rusin <rusin>
To: virus@cs.ucsb.edu
Subject: Re:  tictactoe

>I heard that there exists a mathematical formula for
>the standard tictactoe which given the current position finds the next
>best move.  I was wondering if you are aware of it and if you could
>provide me with some pointers to this "formula?" 

You, in
>  | Computer Science, Santa Barbara    |
don't want a "formula", you want an algorithm! For standard tic-tac-toe, you
can construct the entire game tree easily enough (using symmetry helps):
simply list all the possible sequences of moves which might be selected.
Follow each path to its end and determine who wins. Your algorithm would
consist of prescribing a choice of path in the tree to select, for
each vertex representing one of your moves. At each such vertex you need only
save the part of the game tree which follows from the option you select;
obviously you would select an option which is sure to result in a win,
if such an option exists.

I suppose you know that tictactoe is so simple that it has been completely
analyzed: the player who goes first can be assured nothing worse than a draw.
Thus it requires keeping more of the game tree if you're writing an
algorithm to describe the optimal moves for the player who goes second.

If you were hoping for a pithy strategy, well, I suppose I could formulate 
it, but that would give a false impression of the general situation: if
someone says they have a strategy guaranteed to produce a win for a certain
game, what that probably means is _not_ a set of rules of the form
"always counter an attack of type  X  with a response of type  Y";
instead, it usually means a cumbersome checklist of rules of the form "If on
move 37 the other player takes option #3, choose option #4; if s/he
chooses option #5, respond with option #11; if ...". Hardly enlightening,
and certainly not a "formula", but possibly optimal!

dave
==============================================================================

Date: Thu, 19 Feb 1998 23:21:14 -0800 (PST)
From: [deleted] <virus@cs.ucsb.edu>
To: Dave Rusin <rusin@math.niu.edu>
Subject: Re:  tictactoe

:>  | Computer Science, Santa Barbara    |
:don't want a "formula", you want an algorithm! For standard tic-tac-toe, you
Well, I know all of that about the search tree etc.  Just the professor in
one of my classes last year mentioned that there was a mathematical
formula.  The other day I was reminded of it and I thought it would be
interesting to look at it so I started looking for it on the web.  

I am not trying to find a winning strategy/algorithm for tic tac toe :).  

Thanks for the info
[deleted]