Tic-tac-toe in Erlang — board abstraction

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 into these sections:

Board abstraction

The board object is implemented as a 9-tuple, with each of the 9 elements representing a spot on a 3×3 tic-tac-toe board. The tuple elements can have these values:

x_mark spot is marked X
o_mark spot is marked O
empty spot is not marked

An empty spot can also be marked with a predicted outcome instead of with the atom empty. A predicted outcome tells us if the game is expected to end in a win/loss/tie assume the next move is made at that spot. The predicted outcome also tells us how many moves it’ll take before the game is won or lost. The prediction assumes that all future moves are intelligent, that turns are not skipped, and that marks are not erased.

A predicted outcome is represented by an integer from -5 through 4. None of the code outside the predicted outcome section assumes this however, and none of the following code from the board tuple section would need to change if predicted outcomes were re-written to be atoms or tuples instead of integers.

If the board is already won (three of the same marks in a row) then the empty spots are marked empty and never hold predicted outcomes because the outcome is already known.

If you change the game’s next move from X to O (by skipping X‘s turn), you have to re-calculate all the predicted outcomes even though none of the X/O marks on the board have changed. The predicted outcomes depend not just on the board but also on whose turn it is.

I chose to use a tuple rather than a record because the values in all the elements are the same, and because the elements are accessed by integer index and not by name. If, however, the board representation was changed to, say, a list or record, the functions outside this section should not be affected.

Interface

The functions in the board tuple section wrap an abstract interface around the board object. No place in the code outside this section assumes the board is a tuple. If you changed the board into a list or record you’d just have to change the functions here.

The functional interface to access and manipulate the board is described here.

init_board( )
Creates a new board, ready for a first move. This function is used in init_game(..).
fix_board_predicted_outcomes( Board, Xo_next_move )
Calculates predicted outcomes for all empty positions on a board. Xo_next_move tells us if it’s X‘s or O‘s turn next.
clear_board_predicted_outcomes( Board )
Throws away all predicted outcomes on a board and sets empty positions to the atom empty. Use this after you make a move or skip a turn or do anything that invalidates predicted outcomes.
get_board_best_predicted_position( Board )
Returns the position (integer 1-9) of the best next move. It tries to avoid the center of the board (position 5) and it breaks ties with random_list_element(..). It uses get_best_position_from_pair_list(..). Uses the predicted outcomes on the board, and returns a random position if they are not calculated.
get_board_mark( Board, Position )
Returns the mark at a board position (Position is an integer 1-9). The mark can be x_mark, o_mark, empty, or a predicted outcome (integer).
mark_board( Board, Position, Mark )
Adds a mark (x_mark or o_mark) to a board. It is also used to erase a mark (set a board position to empty). It is not used to set predicted outcomes.
count_board_xo( Board )
Returns how many spots are marked X or O (x_mark or o_mark). Return is an integer 1-9.
is_board_empty( Board )
Returns true or false. Equivalent to (0 == count_board_xo( Board)).
is_board_full( Board )
Returns true or false. Equivalent to (9 == count_board_xo( Board)).
is_board_won( Board, Xo )
Xo is either x_mark or o_mark. Tells you if a board has 3 X‘s or O‘s in a row. Will not check for O‘s if Xo is x_mark, and vice versa. If you want to check if either X or O has won call (is_board_won( Board, x_mark) orelse is_board_won( Board, o_mark)).

Source code

Here’s the Erlang source code for the board tuple section of the tic.erl file.

% --------------------------------------------------------------
% Board tuple and functions
% --------------------------------------------------------------
%
%   A Board is a 9-tuple, representing a 3x3 tic-tac-toe board.
%   (9 elements is 3 rows times 3 columns.)
%
%   To examine all positions match against:
%     {_1, _2, _3, _4, _5, _6, _7, _8, _9}
%   Which correspondings to this tic-tac-toe layout:
%             |    |
%          _1 | _2 | _3
%        ----------------
%          _4 | _5 | _6
%        ----------------
%          _7 | _8 | _9
%             |    |
%
%   Each element has one of these values:
%     x_mark      - spot marked X
%     o_mark      - spot marked O
%     empty       - spot not marked
%
%   When an element is empty it can be marked with
%   a predicted outcome instead of 'empty'. A predicted
%   outcome is an integer.
%
%   The predictions are relative to state. If state
%   is x_next and the prediction is_outcome_a_loss( P)
%   and outcome_turn_count( P) == 2, it means X is
%   expected to lose (and O is expected to win) after
%   2 more moves by O.
%
%   There are never any predicted outcomes if
%   state is x_winner or o_winner since we already
%   know the winner. And there are no empty elements
%   to hold a prediction if state==cat_game.

% --------------------------------------------------------------
% init_board( )
%
%   Creates a board full of 'empty'.
%   Could also create a board full of undecided_outcome( ).
%   Calling predict_outcomes( Board, Xo) with an empty board
%   will get you a list of undecided_outcome( ) values.

init_board( ) ->
  { empty, empty, empty,
    empty, empty, empty,
    empty, empty, empty
  }.

% --------------------------------------------------------------
% fix_board_predicted_outcomes( Board, Xo_next )
%
%   Sets all the elements not marked x_mark or o_mark to a
%   predicted outcome (integer). The outcomes are calculated
%   assuming Xo_next (x_mark or o_mark) will be next marked on
%   the board.

fix_board_predicted_outcomes( Board, Xo ) ->
  ?m_assert( (Xo == x_mark) or (Xo == o_mark)),
  ?m_assert( not is_board_full( Board)),
  ?m_assert( not is_board_won( Board, x_mark)),
  ?m_assert( not is_board_won( Board, o_mark)),

  case is_board_empty( Board) of
    true  -> Board;
    false ->
      % Break up the board.
      {M1, M2, M3, M4, M5, M6, M7, M8, M9} =
        Board,

      % Find all the predicted outcomes.
      [P1, P2, P3, P4, P5, P6, P7, P8, P9] =
        predict_outcomes( Board, Xo),

      % Function to find the element value for the new board.
      Combo_fn =
        fun
          ( x_mark, collide ) -> x_mark;
          ( o_mark, collide ) -> o_mark;
          ( Mark  , Outcome ) ->
            ?m_assert( Mark /= x_mark),
            ?m_assert( Mark /= o_mark),
            ?m_assert( is_outcome_valid( Outcome)),
            Mark,
            Outcome
        end,

      % Create the new board.
      { Combo_fn( M1, P1), Combo_fn( M2, P2), Combo_fn( M3, P3),
        Combo_fn( M4, P4), Combo_fn( M5, P5), Combo_fn( M6, P6),
        Combo_fn( M7, P7), Combo_fn( M8, P8), Combo_fn( M9, P9)
      }
  end.

% --------------------------------------------------------------
% clear_board_predicted_outcomes( Board )
%
%   Returns a board where all spots that are not marked either
%   x_mark or o_mark will be marked 'empty' instead.
%   This clears all predicted outcomes from the board.

clear_board_predicted_outcomes(
    {M1, M2, M3, M4, M5, M6, M7, M8, M9} )
  ->
  Clear_fn =
    fun
      ( x_mark ) -> x_mark;
      ( o_mark ) -> o_mark;
      ( _      ) -> empty
    end,

  % Create the new board.
  { Clear_fn( M1), Clear_fn( M2), Clear_fn( M3),
    Clear_fn( M4), Clear_fn( M5), Clear_fn( M6),
    Clear_fn( M7), Clear_fn( M8), Clear_fn( M9)
  }.

% --------------------------------------------------------------
% get_board_best_predicted_position( Board )
%
%   Returns the position (1-9) of the best next move.
%
%   This relies on predicted outcomes stored in the board
%   elements. If no predicted outcomes are stored this returns
%   a random open position.

get_board_best_predicted_position( Board ) ->
  ?m_assert( not is_board_full( Board)),

  % Get the position of the best predicted outcome on the Board.
  % First we get a list of {Pos, Outcome} pairs from Board.
  %   zip: Changes board into list [ {1,M1}, {2,M2}, .. ].
  %   filter: Strips out all x_mark and o_mark marks.
  %   map: Changes 'empty' into undecided_outcome( ).
  %
  % We could use a list comprehension instead of lists:map(..):
  %   get_best_position_from_pair_list(
  %     [ { Pos, case Mark of
  %                empty -> undecided_outcome( ); _ -> Mark
  %              end
  %       }
  %       || {Pos, Mark} <- lists:zip(
  %                           lists:seq( 1, 9),
  %                           tuple_to_list( Board)),
  %          (Mark /= x_mark),
  %          (Mark /= o_mark) ]
  %
  get_best_position_from_pair_list(
    lists:map(
      fun
        ( {Pos, empty}     ) -> {Pos, undecided_outcome( )};
        ( Pos_outcome_pair ) -> Pos_outcome_pair
      end,
      lists:filter(
        fun
          ( {_, Mark} ) ->
            (Mark /= x_mark) andalso
            (Mark /= o_mark)
        end,
        lists:zip(
          lists:seq( 1, 9),
          tuple_to_list( Board))))).

% --------------------------------------------------------------
% get_best_position_from_pair_list( List_of_pairs )
%
%   Looks at all the pairs in a list and selects the one with
%   the best outcome. Returns the position from the best pair.
%
%   The pairs look like {Position, Outcome}.

get_best_position_from_pair_list( Pairs_all ) ->

  % Find the best outcome in the list of all outcomes.
  Outcome_best =
    lists:foldl(
      fun
        ( {_, Out_a}, Out_b ) ->
          case is_first_outcome_better( Out_a, Out_b) of
            true  -> Out_a;
            false -> Out_b
          end
      end,
      element( 2, hd( Pairs_all)),
      tl( Pairs_all)),

  % Find all the pairs with the best outcome.
  Pairs_best =
    lists:filter(
      fun ( {_, Out} ) -> Out == Outcome_best end,
      Pairs_all),

  % Return a position, the first element in the pair.
  element( 1,
    % Choose a pair from the list.
    % If there is only one choice left, return it.
    % There should always be at least one choice available.
    if
      tl( Pairs_best) == [] ->
        % A list has only one element if the tail is [].
        hd( Pairs_best);
      true ->
        % Return a random element from the list after removing
        % position 5 (if it is there).
        % Position 5 is the middle of the board, and the game
        % gets boring after the middle is marked.
        random_list_element( lists:keydelete( 5, 1, Pairs_best))
    end).

% --------------------------------------------------------------
% get_board_mark( Board, Position )
%
%   Returns the mark on the Board at Position.
%   A mark is either: x_mark, o_mark, empty, or a
%   predicted-outcome integer.

get_board_mark( Board, Pos ) -> element( Pos, Board).

% --------------------------------------------------------------
% mark_board( Board, Position, Mark )
%
%   Returns a new board with Mark at Position.
%   Use this to put new x_mark and o_marks on the board, and to
%   clear spots by marking them 'empty'.

mark_board(
  { _,_2,_3,_4,_5,_6,_7,_8,_9}, 1, M ) ->
  { M,_2,_3,_4,_5,_6,_7,_8,_9};
mark_board(
  {_1, _,_3,_4,_5,_6,_7,_8,_9}, 2, M ) ->
  {_1, M,_3,_4,_5,_6,_7,_8,_9};
mark_board(
  {_1,_2, _,_4,_5,_6,_7,_8,_9}, 3, M ) ->
  {_1,_2, M,_4,_5,_6,_7,_8,_9};
mark_board(
  {_1,_2,_3, _,_5,_6,_7,_8,_9}, 4, M ) ->
  {_1,_2,_3, M,_5,_6,_7,_8,_9};
mark_board(
  {_1,_2,_3,_4, _,_6,_7,_8,_9}, 5, M ) ->
  {_1,_2,_3,_4, M,_6,_7,_8,_9};
mark_board(
  {_1,_2,_3,_4,_5, _,_7,_8,_9}, 6, M ) ->
  {_1,_2,_3,_4,_5, M,_7,_8,_9};
mark_board(
  {_1,_2,_3,_4,_5,_6, _,_8,_9}, 7, M ) ->
  {_1,_2,_3,_4,_5,_6, M,_8,_9};
mark_board(
  {_1,_2,_3,_4,_5,_6,_7, _,_9}, 8, M ) ->
  {_1,_2,_3,_4,_5,_6,_7, M,_9};
mark_board(
  {_1,_2,_3,_4,_5,_6,_7,_8, _}, 9, M ) ->
  {_1,_2,_3,_4,_5,_6,_7,_8, M}.

% ------------------------------------------------------
% count_board_xo( Board )
%
%   Returns the number of X's and O's on the board.

count_board_xo( {_1,_2,_3,_4,_5,_6,_7,_8,_9} ) ->
  Num =
    fun
      ( x_mark ) -> 1;
      ( o_mark ) -> 1;
      ( _      ) -> 0
    end,
  Num( _1) + Num( _2) + Num( _3) +
  Num( _4) + Num( _5) + Num( _6) +
  Num( _7) + Num( _8) + Num( _9).

% ------------------------------------------------------
% is_board_empty( Board )
%
%   True if Board has no X or O marks.

is_board_empty( {_1,_2,_3,_4,_5,_6,_7,_8,_9} ) ->
  (_1 /= x_mark) andalso (_1 /= o_mark) andalso
  (_2 /= x_mark) andalso (_2 /= o_mark) andalso
  (_3 /= x_mark) andalso (_3 /= o_mark) andalso
  (_4 /= x_mark) andalso (_4 /= o_mark) andalso
  (_5 /= x_mark) andalso (_5 /= o_mark) andalso
  (_6 /= x_mark) andalso (_6 /= o_mark) andalso
  (_7 /= x_mark) andalso (_7 /= o_mark) andalso
  (_8 /= x_mark) andalso (_8 /= o_mark) andalso
  (_9 /= x_mark) andalso (_9 /= o_mark).

% ------------------------------------------------------
% is_board_full( Board )
%
%   True if every spot on Board is marked with X or O.

is_board_full( {_1,_2,_3,_4,_5,_6,_7,_8,_9} ) ->
  ((_1 == x_mark) orelse (_1 == o_mark)) andalso
  ((_2 == x_mark) orelse (_2 == o_mark)) andalso
  ((_3 == x_mark) orelse (_3 == o_mark)) andalso
  ((_4 == x_mark) orelse (_4 == o_mark)) andalso
  ((_5 == x_mark) orelse (_5 == o_mark)) andalso
  ((_6 == x_mark) orelse (_6 == o_mark)) andalso
  ((_7 == x_mark) orelse (_7 == o_mark)) andalso
  ((_8 == x_mark) orelse (_8 == o_mark)) andalso
  ((_9 == x_mark) orelse (_9 == o_mark)).

% --------------------------------------------------------------
% is_board_won( Board, Xo )
%
%   Predicate to test if Board is a winning board for Xo.
%   Returns 'true' or 'false'.
%
%   Board is a 9-tuple.
%
%   Xo is either x_mark or o_mark.

is_board_won( Board, Xo ) ->
  ?m_assert( (Xo == x_mark) or (Xo == o_mark)),
  is_board_won_detail( Board, Xo).

% Check all winning combinations.
% Check for 3-in-a-row:
is_board_won_detail( {X,X,X,_,_,_,_,_,_}, X ) -> true;
is_board_won_detail( {_,_,_,X,X,X,_,_,_}, X ) -> true;
is_board_won_detail( {_,_,_,_,_,_,X,X,X}, X ) -> true;

% Check for 3-in-a-column:
is_board_won_detail( {X,_,_,X,_,_,X,_,_}, X ) -> true;
is_board_won_detail( {_,X,_,_,X,_,_,X,_}, X ) -> true;
is_board_won_detail( {_,_,X,_,_,X,_,_,X}, X ) -> true;

% Check diagonals:
is_board_won_detail( {X,_,_,_,X,_,_,_,X}, X ) -> true;
is_board_won_detail( {_,_,X,_,X,_,X,_,_}, X ) -> true;

% No winner (yet):
is_board_won_detail( {_,_,_,_,_,_,_,_,_}, _ ) -> false.

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

Leave a Comment 

Comments

Leave a Reply