Tic Tac Toe is a simple game. It takes a small amount of trial and error to master its strategy. Trying to code those strategies efficiently produces a number of challenges. I have chosen perl as the language to program a Tic-Tac-Toe bot, since it is the language I use most at work. This was an exercise to keep my programming juices flowing since I am currently between projects and bogged down with administrative work.

To start, let's identify some basic strategies and considerations our bot will use.

Basic strategies:

1. Make a winning move.
   
2. Prevent opponent from making a winning move
   
3. Obtain a "fork"
   
4. Prevent opponent from being able to fork
   
5. Take the center square

The strategies in the above table are in basic order of importance. Item 1 is obvious: Make a winning move and the game is over. When that opportunity arises, it takes priority over any other strategy. Item 2 is also obvious: If you do not have a winning move, but your opponent will on his next move, you need to block it.

Items 3 and 4 involve the "fork". For those of you unfamiliar with strategy games, a fork is a move that requires two responses, but your opponent can only respond to one of them. In chess, it is when one piece can attack either of two of the opponent's pieces on its next move. In Tic Tac Toe, a fork looks like this:

Game 1
X| |    X| |    X| |    X| |    X| |X
-----   -----   -----   -----   -----
 | |     |O|     |O|     |O|     |O| 
-----   -----   -----   -----   -----
 | |     | |     | |X   O| |X   O| |X
Move 1  Move 2  Move 3  Move 4  Move 5

It will be O's turn on move 6. X can win on his next turn by playing either the middle of the top row, or the middle of the right column. O will only be able to block one or the other on Move 6. X, unless he is generous or drunk, has won the game.

A simple table of weights using the above basic strategies will work against us in the case of the above game. After move 3, O will see that there is no immediate winning move, nor is there an immediate opponent winning move that must be blocked. O will see that the upper-right square is a potential fork for X, and so is the lower-left. Both of those squares will have equal weight, and will be a higher weight than any other square. However, playing either of those squares results in losing the game.

How then, can we teach our bot not to fall for the bait? For starters, the bot must consider not only his next move, but also the opponent's move after that. Before we get too involved in how to account for this, let's think of a standard way to refer to the board and possible wins that will be easy to code for.

First, the board has nine squares:

1|2|3
-----
4|5|6
-----
7|8|9

Because of the simplicity of the board, we don't really need the computer to think of it as a 3x3 table. The board, instead, can be thought of as a 9 digit string, substituting X and O where they are played. The board after move 5 above can be thought of as the string "X2X4O6O8X". Searching for digits in the string shows us that possible moves left are 2, 4, 6, and 8.

Second, there are 8 possible wins. A simple array of 8 values could be referenced after each move to play a new piece, and to check for a win. The possible wins are "123", "456", "789", "147", "258", "369", "159", and "357".

A simple board setup and move processor might look like this:

#!/usr/bin/perl
 
use strict;
use warnings;
 
my $board = "123456789";
my @wins = qw/ 123 456 789 147 258 369 159 357 /;
 
sub move { # Returns 0 for invalid, 1 for valid, 2 for winning move
 my $piece = shift; # X or O
 my $move  = shift; # 1 through 9
 return 0 if $piece !~ /^[XO]$/ or $move !~ /^[1-9]$/;
 return 0 unless $board =~ s/$move/$piece/;
 for (0..7) {
  return 2 if $wins[$_] =~ s/$move/$piece/ && $wins[$_] eq $piece x 3;
 }
 return 1;
}

This gives us a good starting point to build on. Later more logic can be added to make this a complete game, but what we'll focus on now is bot strategy.

Let's assume for now that the bot will always play 'O' and will not play the first move. First, our least important strategem (take the center square) will be the first thing considered. When the game starts, there will be no wins, blocks, or forks to consider for at least two moves, so the bot can go ahead and attempt to grab the center square:

sub bot {
 return if move('O', 5);
}

The second and third items to consider will be making a winning move if there is one, and making a block if it is necessary. These outweigh considerations of forks. A more fleshed out routine that considers these strategies might look like this:

sub bot {
 return if move('O', 5);
 my $move;
 my @open = ($board =~ /(\d)/g);
 for $move (@open) { return move('O',$move) if grep {/$move/ && /O\d?O/} @wins; }
 for $move (@open) { return move('O',$move) if grep {/$move/ && /X\d?X/} @wins; }
 move ('O', $open[0]);
}

The routine above first tries to play the center square, and if that fails cycles through the open moves and checks for any possible win that has the current open move and two Os. Failing, that, the same thing is done again, but this time checking for two Xs where a block would be needed. Failing that, the first open move is played.

In order to check for possible forks, we first need a way to check for possible wins. Let's define a possible win as a line that has a player's piece, and two open squares. If a square has two or more lines that are possible wins, playing that square will result in a fork.

Consider the following game:

Game 2
1|2|3   O|2|3   O|2|3
-----   -----   -----
4|X|6   4|X|6   4|X|6
-----   -----   -----
7|8|9   7|8|9   7|8|X
Move 1  Move 2  Move 3

After move 1, square 3 has one possible win for X, the diagonal line 3-5-7, and none for O. After move 2, square 3 has one possible win for both X and O. For X it is the same, 3-5-7, and for O it is the horizontal line 1-2-3.

After move 3, X has a potential fork by playing square 3. He can win on the diagonal 3-5-7, and also on the vertical 3-6-9. Each of these lines has a player's piece, and two open squares.

It will help the bot to be able to consider the benefits and threats associated with each open square, so let's add a routine called "check" that will return an array of all possible wins for a given piece type (X or O) and square number:

sub check {
 my $piece = shift; # X or O
 my $move  = shift; # 1 through 9
 return 0 if $piece !~ /^[XO]$/ or $move !~ /^[1-9]$/;
 return grep { /$piece/ && /$move/ && /\d${piece}?\d/ } @wins;
}

The list that is returned can be treated as an array, which will come in handy later, as we will see, or as a scalar to find out if it is a possible fork.

Adding a handler for the bot's goal of playing a fork, our bot AI subroutine looks like this:

sub bot {
 return if move('O', 5);
 my $move;
 my @open = ($board =~ /(\d)/g);
 for $move (@open) { return move('O',$move) if grep {/$move/ && /O\d?O/} @wins; }
 for $move (@open) { return move('O',$move) if grep {/$move/ && /X\d?X/} @wins; }
 for (@open) { return move('O',$_) if ( check('O', $_) > 1 ); }
 move ('O', $open[0]);
}

But what can we do to prevent the opponent from obtaining a fork? For starters, we need to be able to see what an opponent is forced to play after our move. If we play one of the two open squares on a possible win line, the opponent must play the other, or lose on the following turn. In Game 2 above, if O plays 2, X must play 3, which gives him a fork. Conversely if O plays 3, X must play 2, which does not result in a fork.

So to satisfy strategy 4, prevent opponent from forking, we need to find a square that forces our opponent to play a non-forking move. If we run "check" on a square for O and get 1, and check for the other square on the same line results in less than 2 for X, then we have a safe move. Code to check for that might look like this:

for $move (@open) {
 if ( my @seq = check('O', $move) ) {
  my ($opposite) = $seq[0] =~ /([^O$move])/;
  return move('O', $move) if ( check('X', $opposite) < 2 );
 }
}

Combined with the bot AI from above, we should have a bot that can not be beaten. It's possible that it does not employ the ideal winning strategy, but all the situations that would result in a loss should be accounted for.

After making some small adjustments to the "move" subroutine, and adding code to draw the board, exit gracefully, and accept user input, our completed program looks like this:

#!/usr/bin/perl
 
use strict;
use warnings;
 
my $board = "123456789";
my @wins = qw/ 123 456 789 147 258 369 159 357 /;
 
sub board {
 print "\n$_" for ($board =~ /(...)/g);
 if ($_ = shift) { print; exit; }
}
 
sub move { # Returns 0 for invalid move or piece, 1 for valid
 my $piece = shift; # X or O
 my $move  = shift; # 1 through 9
 return 0 if $piece !~ /^[XO]$/ or $move !~ /^[1-9]$/;
 return 0 unless $board =~ s/$move/$piece/;
 for (0..7) {
  board ("\n$piece wins!\n") if $wins[$_] =~ s/$move/$piece/ && $wins[$_] eq $piece x 3;
 }
 board ("\nTie!\n") if $board !~ /\d/;
 return 1;
}
 
sub check {
 my $piece = shift; # X or O
 my $move  = shift; # 1 through 9
 return 0 if $piece !~ /^[XO]$/ or $move !~ /^[1-9]$/;
 return grep { /$piece/ && /$move/ && /\d${piece}?\d/ } @wins;
}
 
sub player {
 my $retval = 0;
 my $move;
 until ( $retval ) {
  print "\nMove : ";
  chomp ($move = <>);
  $retval = move('X', $move);
 }
}
 
sub bot {
 return if move('O', 5);
 my $move;
 my @open = ($board =~ /(\d)/g);
 for $move (@open) { return move('O',$move) if grep {/$move/ && /O\d?O/} @wins; }
 for $move (@open) { return move('O',$move) if grep {/$move/ && /X\d?X/} @wins; }
 for (@open) { return move('O',$_) if ( check('O', $_) > 1 ); }
 for $move (@open) {
  if ( my @seq = check('O', $move) ) {
   my ($opposite) = $seq[0] =~ /([^O$move])/;
   return move('O', $move) if ( check('X', $opposite) < 2 );
  }
 }
 move ('O', $open[0]);
}
 
while (1) {
 board;
 player;
 bot;
}