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