Programming and Data Types

Program 4 -- Tic-Tac-Toe

This program plays a game of tic-tac-toe. It plays the number of rounds indicated by the tries input argument and returns a vector with the results. The first element of the return vector shows the number of wins for player X, the second element shows the wins for player O, and the third element is the number of games that resulted in a tied score.

Operating System	MATLAB 6.1	MATLAB 6.5	Performance Gain
Windows	7.7 sec.	0.9 sec.	x 8.6
Linux	17.9 sec.	1.8 sec.	x 9.9
Solaris	43.9 sec.	7.4 sec.	x 5.9

• % FILE:    tictactoe.m
  % PURPOSE: if random legal moves are tried, how often do each of
  %    X and O win?
  
  function tictactoe(tries)
  X   = 1;
  O   = 2;
  NOWIN = 3;
  
  result = [0 0 0];                 % [X_wins, O_wins, No_Winner]
  
  for k = 1:tries
     board = zeros(3);
     player = X;
     winner = NOWIN;
     for moves = 1:9
        illegal = 1;
        while illegal               % Find a random, empty space.
           m = ceil(rand*3);
           n = ceil(rand*3);
           illegal = board(m,n);    % Is this space already taken?
        end
        board(m,n) = player;        % No, place the X or O here.
  
        % Starting with the 5th alternating move [X O X O X],
        % if the current player occupies 3 squares across, or
        % 3 down, or 3 on \ diagonal, or 3 on / diagonal, ...
        if moves > 4 && ...
           (board(m,1) == player && board(m,2) == player && ...
              board(m,3) == player) || ...
           (board(1,n) == player && board(2,n) == player && ...
              board(3,n) == player) || ...
           (board(1,1) == player && board(2,2) == player && ...
              board(3,3) == player) || ...
           (board(1,3) == player && board(2,2) == player && ...
              board(3,1) == player)
  
           % ... then that player wins this round.
           winner = player;
           break;
        end
  
        % Give the other player a turn.
        if player == O, player = X;  else player = O;  end
     end
  
     % Keep score for each round.
     result(winner) = result(winner) + 1;
  end
  
  result
  

Try running the program for 10,000 iterations, recording the elapsed time with tic and toc.

• tic;  tictactoe(10000);  toc
  

What Makes It Faster

Like the previous sample programs, the tictactoe program spends nearly all of its time in the nested for and while loop. It uses only scalar and matrix data types that support MATLAB performance acceleration. It also makes no function calls and does not use function overloading.

In addition, the following factors also speed up program execution.

Logical Operators.   One of the more interesting things about this program is the extended if statement in the middle of the for loop.

• if moves > 4 && ...
     (board(m,1) == player && board(m,2) == player && ...
        board(m,3) == player) || ...
  

This statement has the following characteristics, each of which is a factor in qualifying for performance acceleration:

• Each expression of the extended if statement evaluates to a logical scalar value. The expression board(m,1) == player is an example of this.
• The if statement performs logical AND and OR using the && and || operators rather than the slower & and |. You should use the & and | operators only for element-wise logical operations on arrays.

Short-Circuiting.   One more thing to note about this extended if statement, although not associated with performance acceleration, is that it saves time on some iterations by short-circuiting. Short-circuiting means that the conditional statement may at times be resolved without having to evaluate every part of the expression. For example, if moves is not greater than 4, then the conditions comparing board spaces to player positions do not need to be evaluated, thus saving processing time.

• if moves > 4 && ...
     (board(m,1) == player && board(m,2) == player && ...
        board(m,3) == player) || ...
  

Program 3b -- Vector Comparison, Vectorized

Measuring Performance