Tic-tac-toe in Erlang — next move calculations and predictions

This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called tic.erl and available here. The source file and this tutorial are organized as follows:

Next move calculations and predictions

This section provides a function that predicts the outcome of every possible next move. Given a board with 7 open spaces, this returns 7 predictions, one for each open space. If it is X‘s turn to play, the 7 predictions describe whether X will win, lose or tie for each of X‘s possible next moves.

This section contains the most interesting code in the tutorial. It explores the entire game decision tree, assuming that each player will do his best to win and make the other player lose. This was a favorite subject of early A.I. research (combinatorial game theory). The Wikipedia article about game trees even talks specifically about tic-tac-toe. Because tic-tac-toe is so simple we don’t prune the game tree. Instead we just let the computer generate and evaluate thousands of paths through the tree. Each path is min/max (fuzzy-and/or) evaluated and the best is selected.

This section is also interesting because it contains the function calc_all_outcomes(..) which branches down to the next half-move (ply) of the game. Several alternative implementations for calc_all_outcomes(..) are given in the comments, including some that spawn tens of thousands of Erlang processes (which are more like threads).

Interface

This section implements a single function.

predict_outcomes( Board, Xo )
Returns a list of 9 results, one for each position on the tic-tac-toe Board.
If the position is already marked X or O, the return for that position is the atom collide. Otherwise it is a predicted outcome. Xo is either x_mark or o_mark, depending on whether it’s X‘s or O‘s turn to move.

Source code

Here’s the Erlang source code for the calculate predicted outcomes section of the tic.erl file.

% --------------------------------------------------------------
% Calculate Predicted Outcomes - predict_outcomes(..)
% --------------------------------------------------------------
%
%   Functions that, given a board and the next mover (X or O),
%   calculate the expected outcome of playing the next move at
%   each of the open spots on the board.
%
%   predict_outcomes( Board, Xo_next_move ) is the only
%   function "exported" from this section. The other functions
%   just implement the algorithm.
%
%   A predicted outcome states whether playing that spot on the
%   board will result in a win/loss/tie, and how many moves it
%   will take to win/lose. Presumably the player will want to
%   choose the move the wins the quickest or loses the slowest.
%   But lots of times there are several moves that lead to the
%   same predicted outcome. We could consider adding more info
%   to the outcomes to help us choose between them.
%
%     We could keep a score of how many winning/losing
%     opportunities are presented in the next board.
%     Right now we just look for the smartest next move, but
%     we could also add up all the winning next moves and
%     subtract all the losing next moves and keep that as
%     a tie-breaking value.
%
%     We could count all the paths leading wins and losses
%     and use these values as tie-breakers. We could weight
%     the paths so that longer winning paths were less
%     valuable than shorter ones. Remember that each move
%     is a node in a tree that leads to other moves, and the
%     leaves of the game-tree are all wins, losses, and ties.

% --------------------------------------------------------------
% predict_outcomes( Board, Xo_init )
%
%   Returns a list of 9 results, one for each position on the
%   tic-tac-toe Board. A result is either 'collide' or a
%   predicted outcome, assuming we play Xo_init at that
%   position.
%
%   Board (9-tuple) - A tic-tac-toe board that is still being
%     played. It cannot be marked as a cat game or with a
%     winning three-in-a-row.
%
%   Xo_init - either x_mark or o_mark, depending on whether
%     it is X's or O's turn to move.

predict_outcomes( Board, Xo_init ) ->
  ?m_assert( (Xo_init == x_mark) or (Xo_init == o_mark)),

  % Calc Countdown so we search until we use up all the open
  % spots on the board. That is unless we find a winning or
  % losing board first.
  Countdown = 9 - count_board_xo( Board),
  ?m_assert( Countdown  > 0),
  ?m_assert( Countdown =< 9),

  % We start with undecided_outcome, but we never return it
  % without incrementing it at least once (with next_outcome).
  % We do, however, return undecided_outcome( ) if we run out
  % of open spots on the board, and thus predict a cat game.
  % But that "cat game" undecided_outcome( ) is not derived
  % from Init_outcome.
  Init_outcome = undecided_outcome( ),
  calc_all_outcomes( Board, Xo_init, Countdown, Init_outcome).

% --------------------------------------------------------------
% calc_all_outcomes( Board, Xo_next, Countdown, Outcome_start )
%
%   Given a Board and a next move (Xo_next), returns a list
%   of 9 predicted outcomes. The first outcome assumes Xo_next
%   is played at the first board position, the second outcome
%   in the return list assumes Xo_next is played at spot 2, etc.
%
%   Any spots that are already marked X or O on the board
%   will be marked with the 'collide' atom in the return list.
%
%   Xo_next - either x_mark or o_mark. Says which mark to put
%     down next on the board, an X or an O. This flips back
%     and forth between X and O as we look ahead and recurse
%     deeper.
%
%   Countdown - how many moves deep to explore. Stop when
%     this gets to zero.
%
%   Outcome_start - The outcome we'd have returned if the
%     board was already won. But since it's not won, we
%     increment Outcome_start at least once [using
%     next_outcome( Outcome_start)] before returning it.
%
%   Outcome_start tells us if Xo_next is the same as the Xo_init
%   we started with when predict_outcomes(..) was called. If
%   next_outcome( Outcome_start) is a winning outcome, then
%   Xo_next == Xo_init. Otherwise they are different.

calc_all_outcomes( Board, Xo, Countdown, Outcome_start ) ->
  % Check the parameters.
  ?m_assert( (Xo == x_mark) or (Xo == o_mark)),
  ?m_assert( Countdown > 0),
  ?m_assert( is_outcome_valid( Outcome_start)),

  % There are a couple ways to do this. The most straightforward
  % is to just use map (lists:map(..)) to build the list of 9
  % outcomes.
  %
  %   lists:map(
  %     fun( Pos ) ->
  %       given_move_predict_outcome(
  %         Board, Xo, Pos, Countdown, Outcome_start)
  %     end,
  %     lists:seq( 1, 9))
  %
  % Or you can use a list comprehension, which is a little more
  % elegant. Here are two equivalent ways to code it.
  %
  %   [ Out ||
  %     Pos <- lists:seq( 1, 9),
  %     Out <- [ given_move_predict_outcome(
  %                Board, Xo, Pos, Countdown, Outcome_start)
  %            ]
  %   ]
  %
  %   [ given_move_predict_outcome(
  %        Board, Xo, Pos, Countdown, Outcome_start)
  %     || Pos <- lists:seq( 1, 9) ]
  %
  % Since given_move_predict_outcome(..) is free of side-
  % effects, order of execution doesn't matter. So you can also
  % calculate all 9 elements of the list at the same time. Or
  % at least in separate processes. Order does matter, however,
  % in the result-list, so we have to restore order in the end.
  %
  % Note that these make a lot of processes - several hundred
  % thousand, all running at the same time. So you cannot run
  % the following bits of code on many systems.
  %
  %   % Multi-process solution using nested list comprehensions.
  %   % Uses child pids to order the results.
  %   Pid_parent = self( ),
  %   [ receive {Pid_child, Outcome_predicted} ->
  %       Outcome_predicted
  %     end
  %     || Pid_child <-
  %          [ spawn(
  %              % Send the results back to the parent process.
  %              % Also send self( ) (the child'd process ID) so
  %              % the parent can reassemble the list in order.
  %              fun( ) ->
  %                Pid_parent !
  %                  { self( ),
  %                    given_move_predict_outcome(
  %                      Board, Xo, Pos,
  %                      Countdown, Outcome_start)
  %                  }
  %              end)
  %            || Pos <- lists:seq( 1, 9)
  %          ]
  %   ]
  %
  %   % Multi-process solution using nested list comprehensions.
  %   % Uses Pos (board position, 1-9) to order the results.
  %   Pid_parent = self( ),
  %   [ receive {Pos, Outcome_predicted} ->
  %       Outcome_predicted
  %     end
  %     || Pos <-
  %        [ Pos
  %          || Pos <- lists:seq( 1, 9),
  %             is_pid(
  %               spawn(
  %                 fun( ) ->
  %                   Pid_parent !
  %                     { Pos,
  %                       given_move_predict_outcome(
  %                         Board, Xo, Pos,
  %                         Countdown, Outcome_start)
  %                     }
  %                 end)) ]]
  %
  %   % Same as above except using foreach(..) to scatter and
  %   % map(..) to gather.
  %   Pid_parent = self( ),
  %   Scatter_fn =
  %     fun( Pos ) ->
  %       spawn(
  %         fun( ) ->
  %           Pid_parent !
  %             { Pos,
  %               given_move_predict_outcome(
  %                 Board, Xo, Pos, Countdown, Outcome_start)
  %             }
  %         end)
  %     end,
  %   Gather_fn =
  %     fun( Pos ) ->
  %       receive { Pos, Outcome_predicted } ->
  %         Outcome_predicted
  %       end
  %     end,
  %   lists:foreach( Scatter_fn, lists:seq( 1, 9)),
  %   lists:map( Gather_fn, lists:seq( 1, 9))
  %
  % We'll stick to a simple solution to calc the 9 outcomes.
  [ given_move_predict_outcome(
        Board, Xo, Pos, Countdown, Outcome_start)
    || Pos <- lists:seq( 1, 9) ].

% --------------------------------------------------------------
% given_move_predict_outcome(
%     Board, Xo, Pos, Countdown, Outcome )
%
%   Predicts an outcome (win/loss/cat) given a move.
%
%   Returns a predicted outcome or 'collide'. The returned
%   outcome is relative to the Xo_init initially passed to
%   predict_outcome(..). So if the predicted outcome is
%   "win in 2" and Xo is not the same as Xo_init, then
%   we are predicting that Xo will actually lose in 2.
%
%   Xo is the X or O to mark on the Board.
%
%   Pos is which position (1-9) on the Board to mark.
%
%   Countdown tells us when to stop searching the play space.
%
%   Outcome is what we'd have returned if we'd won in the
%   last move. If we win in this move we're about to try,
%   we'll return next_outcome( Outcome).

given_move_predict_outcome( Board, Xo, Pos, Countdown, Outcome )
  ->
  % Check the parameters.
  ?m_assert( (Xo == x_mark) or (Xo == o_mark)),
  ?m_assert( (1 =< Pos) and (Pos =< 9)),
  ?m_assert( Countdown > 0),
  ?m_assert( is_outcome_valid( Outcome)),

  % Check to see if Pos on Board is available to be marked.
  case get_board_mark( Board, Pos) of
    x_mark -> collide;
    o_mark -> collide;
    _ ->
      Next_board     = mark_board( Board, Pos, Xo),
      Next_countdown = Countdown - 1,
      Next_outcome   = next_outcome( Outcome),
      after_move_predict_outcome(
        Next_board, Xo, Next_countdown, Next_outcome)
  end.

% --------------------------------------------------------------
% after_move_predict_outcome( Board, Xo, Countdown, Outcome )
%
%   Called immediately after Xo has been marked on the Board.
%
%   Countdown tells us when to stop searching for wins/loses.
%   It will be zero if Board has no more unmarked spots.
%
%   Outcome is returned if the last Xo move was a winning move.
%
%   Returns a predicted outcome.
%   If the last move was a winner, return the Outcome passed in.

after_move_predict_outcome( Board, Xo, Countdown, Outcome ) ->
  % Check the parameters.
  ?m_assert( (Xo == x_mark) or (Xo == o_mark)),
  ?m_assert( Countdown >= 0),
  ?m_assert( is_outcome_valid( Outcome)),
  ?m_assert( not is_outcome_undecided( Outcome)),

  case is_board_won( Board, Xo) of
    true  -> Outcome;
    false ->
      case Countdown == 0 of
        true  -> undecided_outcome( );
        false ->
          try_all_moves_best_outcome( Board,
            if Xo == x_mark -> o_mark;
               Xo == o_mark -> x_mark
            end,
            Countdown, Outcome)
      end
  end.

% --------------------------------------------------------------
% try_all_moves_best_outcome( Board, Xo, Countdown, Outcome )
%
%   Applies all possible next moves to Board, looking for
%   the best one. Board must have at least one open position.
%   Predicts the best outcome (for Xo) after trying Xo in all
%   the open positions on the Board.
%
%   Board is a non-winning board with at least one unplayed
%   spot available for the next Xo mark.
%
%   Xo is the next X or O to mark on the Board.
%
%   Countdown tells us when to stop searching for wins/loses.
%
%   Outcome is predicted outcome we would have returned if the
%   last move had been a winner. Since Board is not a winner,
%   we will apply at least one more mark and transform
%   Outcome into next_outcome( Outcome) at least one more time
%   before returning.

try_all_moves_best_outcome( Board, Xo, Countdown, Outcome ) ->
  % Check the parameters.
  ?m_assert( (Xo == x_mark) or (Xo == o_mark)),
  ?m_assert( Countdown > 0),
  ?m_assert( is_outcome_valid( Outcome)),
  ?m_assert( not is_outcome_undecided( Outcome)),

  % Filter out all occurances of 'collide'. There should always
  % be at least one outcome that is not 'collide'.
  [ First_outcome | Remaining_outcomes ] =
    lists:filter(
      fun( X ) -> X /= collide end,
      calc_all_outcomes( Board, Xo, Countdown, Outcome)),

  % Given this move, ask what all the outcomes of all the next
  % moves are. Assume the other player will pick the outcome
  % that is best for him, which will be the move that is worst
  % for us.
  %
  % The returned outcomes are all relative to the Xo_init that
  % we passed in to predict_outcomes(..) to start this search.
  % So if Xo (the mark we just put down on the board) is the
  % same as Xo_init, we want to return the best move for us.
  % But since we get a list of outcomes for all the possible
  % next moves by the other player, we have to assume that he
  % will choose the move that is worst for us.
  %
  % On the other hand, if Xo is not Xo_init, we assume the next
  % other player is Xo_init and will select the move that is
  % best for Xo_init and worst for us.
  %
  % We can tell if Xo is the same as Xo_init because
  % is_outcome_a_win( Outcome) will be true.
  %
  lists:foldl(
    case is_outcome_a_win( Outcome) of
      true  ->
        % Xo is the same as Xo_init.
        % Collect the worst outcome from all the next moves
        % because that is the next move the other player
        % will choose (we assume).
        fun
          ( A, B ) ->
            case is_first_outcome_better( B, A ) of
              true  -> A;
              false -> B
            end
        end;
      false ->
        % Xo is not the same as Xo_init.
        % Collect the best outcome, because it is best for
        % Xo_init and Xo_init moves next.
        fun
          ( A, B ) ->
            case is_first_outcome_better( A, B ) of
              true  -> A;
              false -> B
            end
        end
    end,
    First_outcome,
    Remaining_outcomes).

February 13, 2009 | Filed Under download, erlang, sample code, tic tac toe, tutorial

Leave a Comment 

Comments

Leave a Reply