% --------------------------------------------------------------
% tic_count.erl
% --------------------------------------------------------------
%
%   Erlang module to explore the tic-tac-toe game space.
%   Reports how big the tic-tac-toe game tree gets after 1 move,
%   2 moves, etc.

-module( tic_count ).

-export([
  report/0,
  report_winning_boards/1,
  report_continuing_boards/1 ]).

-compile( nowarn_unused_function ).

-author( "Neal Binnendyk" ).
-copyright( "Copyright (c) 2009 Neal Binnendyk, Ixacta Inc" ).

% --------------------------------------------------------------
% Exported reporting functions
% --------------------------------------------------------------

% --------------------------------------------------------------
% report( )
%
%   This code stops calculating next_pair(..) at ply 9, although
%   we could calculate ply 10. Since there are no boards with
%   ply 10 we'd end up with a pair of empty sets. We could even
%   keep going to ply 11 etc, but for all plys after 9 we end
%   up with the same thing: no game states, no boards, and a
%   pair of empty sets.

report( ) ->
  lists:foldl(
    fun( Ply_index, Pair ) ->
      report_pair_counts( Ply_index, Pair),
      if Ply_index =:= 9 -> ok;
      true ->
        next_pair( Ply_index band 1, Pair)
      end
    end,
    init_pair( ),
    lists:seq( 0, 9)),
  ok.

% --------------------------------------------------------------
% report_winning_boards( Ply_report )
% report_continuing_boards( Ply_report )

report_winning_boards( Ply_report ) ->
  report_boards( Ply_report, 1),
  ok.

report_continuing_boards( Ply_report ) ->
  report_boards( Ply_report, 2),
  ok.

% --------------------------------------------------------------
% report_boards( Ply_report, Index )
%
%   This uses foldl(..) to loop through the game tree,
%   generating all the boards for a ply using the boards from
%   from the last ply.
%
%   This stops calculating the next ply once it has reported.
%   The loop continues to the end, but it does no calculation
%   and just passes 'ok' along the chain.

report_boards( Ply_report, Index ) ->
  lists:foldl(
    fun
      ( _, ok ) -> ok;
      ( Ply_index, Pair ) ->
        case Ply_index =:= Ply_report of
          true  -> report_set( element( Index, Pair)), ok;
          false -> next_pair( Ply_index band 1, Pair)
        end
    end,
    init_pair( ),
    lists:seq( 0, 9)),
  ok.

% --------------------------------------------------------------
% Search game space
% --------------------------------------------------------------
%
%   The game space is a directed graph of game boards.
%   Boards that are identical after rotation and reflection are
%   considered the same.
%   At each ply of the game there are a set of possible game
%   boards that can be achieved. These are divided into two
%   groups: winning boards (3 in a row), and other boards
%   which are continuing games, except after ply 9 when the
%   board is full and the game ends in a tie.

% --------------------------------------------------------------
% init_pair( )
% next_pair( Mark, Prev_pair )
%
%   init_pair( ) -- The game space at ply 0.
%   next_pair( ) -- Given all the boards at ply N, returns all
%     the boards at ply N+1.

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

next_pair( Mark, {_, Set_of_other_boards} ) ->
  calc_set_of_next_boards( Mark, Set_of_other_boards ).

% --------------------------------------------------------------
% calc_set_of_next_boards( Mark, Set_of_previous_boards )

calc_set_of_next_boards( Mark, Set_of_previous_boards ) ->
  fold_set(
    fun( Board_previous, Pair_current_boards ) ->
      add_next_move_boards_to_pair_as_necessary(
        Mark, Board_previous, Pair_current_boards)
    end,
    { init_set( ), init_set( ) },
    Set_of_previous_boards).

% --------------------------------------------------------------
% add_next_move_boards_to_pair_as_necessary(
%   Mark, Board, Pair_of_sets_of_boards )

add_next_move_boards_to_pair_as_necessary(
    Mark, Board, Pair_of_sets_of_boards )
->
  lists:foldl(
    fun( Position, Pair_accumulate ) ->
      after_move_add_board_to_pair_if_necessary(
        Position, Mark, Board, Pair_accumulate)
    end,
    Pair_of_sets_of_boards,
    lists:seq( 1, 9)).

% --------------------------------------------------------------
% after_move_add_board_to_pair_if_necessary(
%   Position, Mark, Board, Pair_of_sets_of_boards )

after_move_add_board_to_pair_if_necessary(
    Position, Mark, Board, Pair_of_sets_of_boards )
->
  case get_board_mark_at( Position, Board ) of
    empty ->
      add_board_to_pair_if_necessary(
        Mark,
        mark_board_at( Position, Mark, Board),
        Pair_of_sets_of_boards);
    _ ->
      Pair_of_sets_of_boards
  end.

% --------------------------------------------------------------
% add_board_to_pair_if_necessary(
%   Mark, Board, Pair_of_sets_of_boards )

add_board_to_pair_if_necessary(
    Mark, Board, {Set_won_boards, Set_other_boards} )
->
  case is_board_won_by( Mark, Board ) of
    true ->
      { add_board_to_set_if_necessary( Board, Set_won_boards),
        Set_other_boards
      };
    false ->
      { Set_won_boards,
        add_board_to_set_if_necessary( Board, Set_other_boards)
      }
  end.

% --------------------------------------------------------------
% add_board_to_set_if_necessary( Board, Set_of_boards )
%
%   Returns a set with Board added to if Board (or one of its
%   simple reflection/rotation transformations) is not already
%   in the set. Otherwise just returns Set_of_boards unchanged.

add_board_to_set_if_necessary( Board, Set_of_boards ) ->
  case is_board_in_set( Board, Set_of_boards ) of
    true  -> Set_of_boards;
    false -> add_to_set( Board, Set_of_boards)
  end.

% --------------------------------------------------------------
% is_board_in_set( Board, Set_of_boards )
%
%   Checks the 8 simple rotations and reflections of Board.
%   Returns true if any of the 8 are in the Set_of_boards.
%
%   Improvement: look at the 8 board transformations and return
%   the least one (using the '<' operator). And only save the
%   least board in the set. This would make board print-outs a
%   little easier to read.

is_board_in_set( Board, Set_of_boards ) ->
  is_rotated_board_in_set( Board, Set_of_boards) orelse
  is_rotated_board_in_set(
    reflect_board( Board), Set_of_boards).

% --------------------------------------------------------------
% is_rotated_board_in_set( Board, Set_of_boards )

is_rotated_board_in_set( Board, Set_of_boards ) ->
  case is_in_set( Board, Set_of_boards) of true -> true;
  false ->
    B1 = rotate_board( Board),
    case is_in_set( B1, Set_of_boards) of true -> true;
    false ->
      B2 = rotate_board( B1),
      case is_in_set( B2, Set_of_boards) of true -> true;
      false ->
        B3 = rotate_board( B2),
        is_in_set( B3, Set_of_boards)
      end
    end
  end.


% --------------------------------------------------------------
% report_pair_counts( Ply_index, Pair_of_sets_of_boards )

report_pair_counts(
    Ply_index, {Set_of_won_boards, Set_of_other_boards} )
->
  Count_winners = count_set( Set_of_won_boards  ),
  Count_others  = count_set( Set_of_other_boards),
  write_line( "After ply ~w:", Ply_index),
  write_line( "  ~w winning boards"   , Count_winners),
  write_line( "  ~w continuing boards", Count_others ),
  ok.

% --------------------------------------------------------------
% Isolate set interface
% --------------------------------------------------------------
%
%   This uses the set object from the sets module.
%   Implement the following interface to change this to use
%   another module like:
%     ordsets
%     orddict
%     dict
%     lists

% --------------------------------------------------------------
% init_set( )
% init_set( Board )

init_set( ) ->
  sets:new( ).

init_set( Board ) ->
  sets:from_list( [Board]).

% --------------------------------------------------------------
% count_set( Set_of_boards )

count_set( Set_of_boards ) ->
  sets:size( Set_of_boards).

% --------------------------------------------------------------
% is_in_set( Board, Set_of_boards )

is_in_set( Board, Set_of_boards ) ->
  sets:is_element( Board, Set_of_boards).

% --------------------------------------------------------------
% add_to_set( Board, Set_of_boards )

add_to_set( Board, Set_of_boards ) ->
  sets:add_element( Board, Set_of_boards).

% --------------------------------------------------------------
% fold_set( Fn_board_accum, Accumulate_init, Set_of_boards )
%
%   Fn_board_accum must be a function like this:
%     Fn( Board, Accumulate_prev ) -> Accumulate_next

fold_set( Fn, Acc0, Set_of_boards ) ->
  sets:fold( Fn, Acc0, Set_of_boards).

% --------------------------------------------------------------
% report_set( Set_of_boards )

report_set( Set_of_boards ) ->
  lists:foreach(
    fun( Board ) ->
      write_line( ),
      report_board( Board)
    end,
    lists:sort( sets:to_list( Set_of_boards))),
  ok.

% --------------------------------------------------------------
% Isolate board interface
% --------------------------------------------------------------
%
%   A Board is a 9-tuple, representing a 3x3 tic-tac-toe board.
%   (9 elements is 3 rows times 3 columns.)

% --------------------------------------------------------------
% init_board( Mark )

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

% --------------------------------------------------------------
% get_board_mark_at( Position, Board )

get_board_mark_at( Position, Board ) ->
  element( Position, Board).

% --------------------------------------------------------------
% mark_board_at( Position, Mark, Board )
%
%   Returns a new board with Mark at Position.

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

% --------------------------------------------------------------
% rotate_board(  Board ) - rotates Board quarter turn clockwise
% reflect_board( Board ) - reflects Board around horizontal axis
%
%   Transforms a tic-tac-toe board by rotating it 90 degrees
%   clockwise, and by reflecting it around the horizontal axis.
%   Reflecting it is like picking the paper up and putting it
%   face down.
%
%   From these 2 primitive transforms we can construct the 8
%   simple rotation/reflection transforms.

rotate_board(
  {_1,_2,_3,
   _4,_5,_6,
   _7,_8,_9} )
->
  {_7,_4,_1,
   _8,_5,_2,
   _9,_6,_3}.

reflect_board(
  {_1,_2,_3,
   _4,_5,_6,
   _7,_8,_9} )
->
  {_7,_8,_9,
   _4,_5,_6,
   _1,_2,_3}.

% --------------------------------------------------------------
% is_board_won_by( Mark, Board )
%
%   Predicate to test if Board is a winning board for Mark.
%   Returns 'true' or 'false'.

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

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

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

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

% --------------------------------------------------------------

report_board( {_1,_2,_3,_4,_5,_6,_7,_8,_9} ) ->
  Move_string = fun
    ( 0 ) -> "X"; ( 1 ) -> "O"; ( _ ) -> "."
  end,
  Write_strip = fun( A, B, C ) ->
    write_space( 2),
    write_string( Move_string( A)),
    write_string( Move_string( B)),
    write_string( Move_string( C)),
    write_line( )
  end,
  Write_strip( _1, _2, _3),
  Write_strip( _4, _5, _6),
  Write_strip( _7, _8, _9).

% --------------------------------------------------------------
% Simple String Output
% --------------------------------------------------------------

% --------------------------------------------------------------
% write_line( )
% write_line( Str, Arg)
% write_string( Str)
% write_string( Str, Arg)
% write_space( )
% write_space( N)

write_line( ) ->
  io:nl( ).

write_line( Str, Arg ) ->
  write_string( Str, Arg),
  write_line( ).

write_string( Str ) ->
  io:fwrite( Str).

write_string( Str, Arg ) ->
  io:fwrite( Str, [Arg]).

write_space( ) ->
  write_string( " ").

write_space( 0 ) ->
  ok;
write_space( N ) when N > 0 ->
  write_space( ),
  write_space( N - 1).