% Need to distinguish:
%    move_is_legal ( i, j, B, player ) returns 
%     -1: there are NO legal moves left for this player.
%      0: this move is not legal, but there are others.
%      positive: this move is legal, and causes this many flips.
%
function reversi_game ( )

%*****************************************************************************80
%
%% reversi_game() runs a game of reversi between the user and the computer.
%
%  Discussion:
%
%    An 8x8 board of squares is displayed.
%
%    The 2x2 central block of squares is marked with 
%      X O
%      O X
%    where X is the player's marker, and O the computer's.
%
%    The opponents alternate turns, placing their marker on a legal square.
%    A square is legal if putting a marker there will flip at least one
%    of the opponent's markers.  Explaining FLIPPING IS FLIPPING TRICKY.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    24 June 2025
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    Al Sweigart,
%    Invent your own computer games with Python,
%    4th Edition, 2017,
%    No Starch Press,
%    ISBN13: 978-1-59327-795-4
%    LC: QA76.76.C672
%
  height = 8;
  width = 8;
  computer = 1;
  human = 2;
  player = computer;

  timestamp ( );
%
%  Say hello.
%
  fprintf ( 1, '\n' );
  fprintf ( 1, 'reversi_game():' );
  fprintf ( 1, '  MATLAB/Octave version %s\n', version ( ) );
  fprintf ( 1, '  Play reversi/Othello against the computer.' );
%
%  Initialize the game board.
%
  B = board_start ( );
%
%  The opponents alternate in choosing a move.
%
  while ( true )
%
%  If at least one legal move...
%
    player = 3 - player;

    board_display ( B );
%
%  Get a move from computer,
%
%   if ( player == computer )

%     [ i, j ] = move_optimal ( );
%
%  Or a move from human, after being sure it is legal.
%
%   else

      while ( true )
        [ i, j ] = move_click ( height );
        flips = move_is_legal ( i, j, B, player );
        if ( 0 < flips )
           break;
        end
      end

%   end 
%
%  [i,j] might be [0,0] because no legal move.
%
    B(i,j) = player;
    B = board_update ( i, j, B, player );

%   end

  end
%
%  Terminate.
%
  fprintf ( 1, '\n' );
  fprintf ( 1, 'reversi_game():\n' );
  fprintf ( 1, '  Normal end of execution.\n' );

  return
end
function board_background ( m, n, r, color_back, color_fore )

%*****************************************************************************80
%
%% board_background() initializes the board background.
%
%  Discussion:
%
%    An MxN array of squares is drawn, each filled with the same color,
%    and each of "radius" r.  As long as r <- 0.5, the board will fit
%    within a square of dimensions [0,M]x[1,N].
%
%    Note that the unit cell (i,j), with radius 1/2, is assumed to be centered 
%    at (i-0.5,j-0.5), with vertices (i-1,j-1), (i,j-1), (i,j), (i-1,j).
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    07 November 2017
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer M, N, the height and width of the board, measured
%    in unit cells.
%
%    real R, the radius of each cell.  A cell of radius 0.5 will
%    fill its unit square.  A cell of radius 0.45 will leave a margin
%    in which the board background color is visible.  R should not
%    exceed 0.5!
%
%    colors COLOR_BACK, COLOR_FORE.  These can be
%    any of the 8 abbreviated color terms 'r', 'g', 'b', 'c',
%    'm', 'y', 'w', 'k', or an RGB triple such as [1.0,0.4,0.0].
%    The board background is drawn with COLOR_BACK, and the board
%    cells are then drawn with COLOR_FORE.
%
  d = max ( 0.5 - r,  0.0 );

  fill ( [ -d, n+d, n+d, -d ], [ -d, -d, m+d, m+d ], color_back );

  hold ( 'on' );

  for i = 1 : m

    for j = 1 : n

      square_ij_fill ( m, i, j, r, color_fore );

    end
    
  end

  hold ( 'off' );

  axis ( 'equal' );
  axis ( 'off' );

  return
end
function board_display ( B )

%*****************************************************************************80
%
%% board_display() displays the current reversi board.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    24 June 2025
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer B(8,8): the current reversi board.
%
  m = 8;
  n = 8;
%
%  Initialize the board of MxN gray squares, each of "radius" 0.45,
%  on a white background.
%
  radius = 0.45;
  white = 'w';
  gray = [ 0.9, 0.9, 0.9 ];
  board_background ( m, n, radius, white, gray );
%
%  Draw a red circle in 1 squares, and blue in 2 squares.
%
  red = [ 1.0, 0.0, 0.0 ];
  blue = [ 0.0, 0.0, 1.0 ];

  hold ( 'on' );

  for i = 1 : m
    for j = 1 : n
      if ( B(i,j) == 1 )
        circle_ij_fill ( m, i, j, radius, red );
      elseif ( B(i,j) == 2 )
        circle_ij_fill ( m, i, j, radius, blue );
      end
    end
  end

  hold ( 'off' );

  return
end
function B = board_start ( )

%*****************************************************************************80
%
%% board_start() initializes the reversi board.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    24 June 2025
%
%  Author:
%
%    John Burkardt
%
%  Output:
%
%    integer B(8,8): the initial board configuration.
%
  B = zeros ( 8, 8 );

  B(4,4) = 2;
  B(4,5) = 1;
  B(5,4) = 1;
  B(5,5) = 2;

  return
end
function B = board_update ( i, j, B, player )

%*****************************************************************************80
%
%% board_update() updates the reversi board after player's move at (i,j).
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    24 June 2025
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer i, j: the indices of the square that was just marked.
%
%    integer B(8,8): the previous board configuration.
%
%    integer player: the index of the player.
%
%  Output:
%
%    integer B(8,8): the updated board.
%
  opponent = 3 - player;

  for ns = -1 : 1
    for ew = -1 : 1

      if ( ns == 0 && ew == 0 ) 
        continue;
      end
      
      i1 = i + ns;
      j1 = j + ew;

      while ( cell_onboard ( i1, j1 ) && B(i1,j1) == opponent )
        i1 = i1 + ns;
        j1 = j1 + ew;
        if ( cell_onboard ( i1, j1 ) && B(i1,j1) == player )
          while ( true )    
            i1 = i1 - ns;
            j1 = j1 - ew;
            if ( i1 == i && j1 == j )
              break;
            end
            B(i1,j1) = player;
          end
        end
      end

    end
  end

  return
end
function onboard = cell_onboard ( i, j )

%*****************************************************************************80
%
%% cell_onboard() reports whether (i,j) is a legal cell index.
%
  onboard = ( 1 <= i && i <= 8 && 1 <= j && j <= 8 );

  return
end
function [ i, j ] = move_click ( height );

%*****************************************************************************80
%
%% move_click() selects a square by mouse click. 
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    08 November 2017
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer height: the number of rows.
%
%  Output:
%
%    integer I, J, the row and column selected by the user.
%
  [ x, y ] = ginput ( 1 );

  j = ceil ( x );
  i = height + 1 - ceil ( y );
  
  return
end
function flips = move_is_legal ( i, j, B, player )

%*****************************************************************************80
%
%% move_is_legal() counts the flips associated with a proposed move.
%
%  Discussion:
%
%    A legal move must cause at least one flip.
%
%    The proposed move might be illegal because:
%    * i or j is out of bounds;
%    * B(i,j) is already nonzero;
%    * Choosing B(i,j) does not cause any flips.
%
%    If the proposed move is illegal, flips is returned as 0.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    25 June 2025
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer i, j: the proposed move.
%
%    integer B(8,8): the current board.
%
%    integer player: the player whose optimal move is to be chosen.
%
%  Output:
%
%    integer flips: the number of flips for this move.
%
  flips = 0;

  if ( ~ cell_onboard ( i, j ) )
    return;
  end

  if ( B(i,j) ~= 0 )
    return;
  end

  opponent = 3 - player;

  for ns = -1 : 1
    for ew = -1 : 1

      if ( ns == 0 && ew == 0 ) 
        continue;
      end
      
      i1 = i + ns;
      j1 = j + ew;

      while ( cell_onboard ( i1, j1 ) && B(i1,j1) == opponent )
        i1 = i1 + ns;
        j1 = j1 + ew;
        if ( cell_onboard ( i1, j1 ) && B(i1,j1) == player )
          while ( true )    
            i1 = i1 - ns;
            j1 = j1 - ew;
            if ( i1 == i && j1 == j )
              break;
            end
            flips = flips + 1;
          end
        end
      end

    end
  end

  return
end
function [ i, j ] = move_optimal ( B, player )

%*****************************************************************************80
%
%% move_optimal() selects the optimal square for the player. 
%
%  Discussion:
%
%    A greedy algorithm is used, which looks at all legal moves.  
%
%    A legal move to a corner is always preferred.  
%
%    Otherwise, a move with maximal flips is suggested.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    25 June 2025
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer B(8,8): the current board.
%
%    integer player: the player whose optimal move is to be chosen.
%
%  Output:
%
%    integer I, J, the row and column of the optimal move.
%
  iopt = 0;
  jopt = 0;
  flips_opt = 0;

  for i = 1 : 8
    for j = 1 : 8

      if ( B(i,j) == 0 )
%
%  Positive value of flips means the move is legal.
%
        flips = move_is_legal ( i, j, B, player );

        if ( 0 < flips )

          if ( i == 1 && j == 1 || ...
               i == 1 && j == 8 || ...
               i == 8 && j == 1 || ...
               i == 8 && j == 8 )
            iopt = i;
            jopt = j;
            flips_opt = flips;
            return
          end
     
          if ( flips_opt < flips )
            iopt = i;
            jopt = j;
            flips_opt = flips;
          end

        end

      end
    end
  end
  
  return
end
function circle_ij_fill ( m, i, j, r, color )

%*****************************************************************************80
%
%% circle_ij_fill() plots a filled circle in cell (I,J).
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    25 October 2017
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer M, the number of rows in the matrix.
%
%    real I, J, the indices of the cell.
%
%    real R, the radius of the circle.
%
%    MATLAB color COLOR, can be any of the 8 abbreviated color terms
%    'r', 'g', 'b', 'c', 'm', 'y', 'w', 'k', or an RGB triple such as 
%    [1.0,0.4,0.0].  The circle is filled with this color.
%
  a = linspace ( 0.0, 2.0 * pi, 25 );
  x =     j - 0.5 + r * cos ( a );
  y = m - i + 0.5 + r * sin ( a );

  fill ( x, y, color );

  return
end
function square_ij_fill ( m, i, j, r, color )

%*****************************************************************************80
%
%% square_ij_fill() plots a filled square centered at Cell(I,J)
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    07 November 2017
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer M, the number of rows in the matrix.
%
%    integer I, J, the indices of the cell.
%
%    real R, the radius of the square.
%
%    color COLOR, can be any of the 8 abbreviated color terms
%    'r', 'g', 'b', 'c', 'm', 'y', 'w', 'k', or an RGB triple such as 
%    [1.0,0.4,0.0].  The circle is filled with this color.
%
  xc = j - 0.5;
  yc = m - i + 0.5;

  a = xc - r;
  b = xc + r;
  c = yc - r;
  d = yc + r;

  fill ( [ a, b, b, a ], [ c, c, d, d ], color );

  return
end
function timestamp ( )

%*****************************************************************************80
%
%% timestamp() prints the YMDHMS date as a timestamp.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    14 November 2022
%
%  Author:
%
%    John Burkardt
%
  t = now ( );
  c = datevec ( t );
  s = datestr ( c, 0 );
  fprintf ( 1, '%s\n', s );

  return
end
