You have too options:

1. Attempt to come up with some game-specific intelligence.  For
example, in tic-tac-toe, you might program these rules:

   - If the computer player has two symbols in a row, it MUST play
     the remaining square to win the game.

   - If the human player has two symbols in a row, the computer
     MUST play the remaining square to prevent the win.

   - Given a choice, it's better to play in the center than elsewhere.
     It's also better to play in a corner than on a side.

2. Or, you can program general forethought.  Do a google search for
"minimax".  There are also optimizations such as alpha-beta, scout,
etc... but you really don't need them for a game as trivial as your
basic tic-tac-toe project.

Tic-tac-toe is a turn based game including a board, "pieces" and
two players. Just like chess.  Just like chess, there are three
possible outcomes if both players play optimally:

1. player A wins
2. player B wins
3. neither A nor B wins

In the case of Tic-tac-toe, which has been "solved", we know that it'
choice three: neither A nor B wins and, it this case, it is called a
draw.

In the case of chess, "we don't know".  We know that it's one of those
three possible outcomes, but we can't tell which one (and depending
on the rules, "neither A nor B wins" is not necessarely a draw [it can
be an "infinite" game], but I disgress).

Whatever, if you really want your computer opponent to play Tic-tac
optimally, he'll never make a mistake and hence he'll never lose.  The
human player will probably sometimes make a mistake and hence
sometimes loose (but never win).

Is that what you want?

If that's what you want, it's very simple: you write a method that
plays optimally (for each player, not just for "your" computer).
This can be done very simply using recursivity (at least if you're
comfortable with recursivity).

However, to make it less "boring", you could add some ramdoness:
make the computer play optimally only 80% of the time, so the
human player at least has some chance to sometimes win the game.

If you can't manage to write the recursive method that plays
optimally every time, I'll gladly do it for you.

See you soon on c.l.j.p.,

Jean

P.S : another game that has been solved is "6x7" ("Puissance 4" in
French,  where you have to align 4 pieces in a grid made of 42 spots).

There is a demo program for TicTacToe on any of the JDK distributions.

For me ..\jdk1.5.0_05\demo\applets\TicTacToe

As others have said, the general approach to this type of problem
involves the Minimax algorithm or one of its variants -- although
it can be argued that Tic-Tac-Toe is so small that Minimax is
overkill.  Still, it's useful to understand how Minimax works even
if it is overkill here.

I wrote a TTT program some time ago that allowed the user to switch
between "easy," "medium" and "hard" engines.  The "hard" engine
used minimax (and since it exhaustively searches the game tree,
it could not be beaten).  Below is the code for the "hard" engine.
I didn't bother including the supporting classes -- you should be
able to understand the algorithm by reading what's here, without
having detailed knowledge of classes like TTTPosition.

Note that this solution is effective, but the code was quickly
written and is rather inelegant.  The first improvement would be to
use negamax rather than minimax, which eliminates the "if X do this
but if O do that" stuff.

package ttt;

import java.util.*;

public class TTTEngineHard extends TTTEngine {
 public int eval(TTTPosition position) {
   int bestPos = 0;
   char turn = position.getTurn();
   int bestVal = (turn == X ? -1 : 1);

   for (int i = 0; i < 9; i++) {
     if (position.isEmpty(i)) {
       TTTPosition newPos = new TTTPosition(position);
       newPos.putSquare(i);
       int value = miniMax(newPos);
       if ((turn == X && value > bestVal) || (turn == O && value <
bestVal)) {
         bestVal = value;
         bestPos = i;
       }
     }
   }

   return bestPos;
 }

 private int miniMax(TTTPosition position) {
   int staticEval = evaluate(position);

   if (staticEval != 0) return staticEval;

   ArrayList successors = getSuccessors(position);

   if (successors.isEmpty()) return 0;

   int turn = position.getTurn();
   int best = (turn == X ? -1 : 1);
   ListIterator i = successors.listIterator();
   while (i.hasNext()) {
     TTTPosition newPos = (TTTPosition) i.next();

     int value = miniMax(newPos);       

     if ((turn == X && value > best) ||
     (turn == O && value < best))
       best = value;
   }

   return best;
 }

 private ArrayList getSuccessors(TTTPosition position) {
   ArrayList arrayList = new ArrayList();

   for (int i = 0; i < 9; i++) {
     if (position.isEmpty(i)) {
       TTTPosition newPosition = new TTTPosition(position);
       newPosition.putSquare(i);
       arrayList.add(newPosition);
     }
   }

   return arrayList;
 }
   
 private int evaluate(TTTPosition position) {
   TTTWinResult winResult = position.checkForWinner();

   if (winResult == null) return 0;

   return (position.getSquare(winResult.getStartSquare()) == X ? 1 :
-1);
 }
}

Larry Coon
University of California