|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.
|| 7.7 sec.
|| 0.9 sec.
|| x 8.6
|| 17.9 sec.
|| 1.8 sec.
|| x 9.9
|| 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
What Makes It Faster
Like the previous sample programs, the
tictactoe program spends nearly all of its time in the nested
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
This statement has the following characteristics, each of which is a factor in qualifying for performance acceleration:
ifstatement evaluates to a logical scalar value. The expression
board(m,1) == playeris an example of this.
ifstatement performs logical
||operators rather than the slower
|. You should use the
|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.
|Program 3b -- Vector Comparison, Vectorized||Measuring Performance|