use Game.frink

/** This is a class to play the game of Othello/Reversi.  It uses Game.frink
    which specifies the GameState interface that this implements to play the
    game.

    Official rules:
    https://www.worldothello.org/about/about-othello/othello-rules/official-rules/english

    The current implementation uses a naive static evaluation function which
    simply counts the number of pieces.  There is more strategy available at:
    https://www.samsoft.org.uk/reversi/strategy.htm

    Also see:
    https://stackoverflow.com/questions/12334216/othello-evaluation-function

    where a suggestion is that a static evaluation function can just be a
    random number and that works effectively because "The logic is that the
    player with the most choices will be able to steer the game to get the
    highest random number, and so this approach again means that the AI will
    favour moves which give it lots of choices, and his opponent few." and the
    suggestion was found to be effective.
*/

/** 
*/
class Othello implements GameState
{
   /** A 2x2 array with integer values. */
   var board

   /** A count of the number of filled spaces. */
   var filled

   /** A function that sorts the goodness of moves. */
   class var moveOrderer = {|a,b| distFromCorner[a] <=> distFromCorner[b] }

   /** Create a new starting board */
   new[] :=
   {
      board = new array[[8,8],0]
      board@3@3 = 1
      board@3@4 = -1
      board@4@3 = -1
      board@4@4 = 1
      filled = 4
   }

   /** Copy constructor. */
   new[orig is Othello] :=
   {
      board = deepCopy[orig.board]
      filled = orig.filled
   }
   
   /** Distance from corner.  The object is an OthelloMove. */
   distFromCorner[move] :=
   {
      val = 0
      if move.row >= 4
         val = 7 - move.row
      else
         val = move.row

      if move.col >= 4
         val = val + (7 - move.col)
      else
         val = val + move.col
      
      return val
   }

   /** Returns true if this is a terminal state (e.g. a winning or losing
       position that cannot be followed any further.)

       TODO:  Fix this.  If a player cannot make a move, they forfeit their
       turn and the other player plays.

       The official rules state:
       "When it is no longer possible for either player to move, the game is
        over. Disks are counted and the player with the majority of their
        colour showing is the winner."

       "Note: It is possible for a game to end before all 64 squares are
       filled."
   */
   isTerminal[player] :=
   {
      return ! canMove[player]
   }
   
   /** Perform a static evaluation of the game state.  This should always give a
       ranking for the win probability for player +1.

       TODO:  This evaluation function is really naive and only counts the
       number of pieces on the board.  This can be improved.

       THINK ABOUT:  Should this take a player argument?  That might allow it
       to use a different evaluation function for each player which would be
       interesting and allow different training functions.
   */
   staticEvaluate[] :=
   {
      sum = 0
      for row = 0 to 7
         sum = sum + sum[board@row]

      return sum
   }

   /** Generates the next moves for the specified player (+1 or -1.)  The
       resultant types should be an instance of OthelloMove which implements
       GameMove.
   */
   nextMoves[player] :=
   {
      moves = new array
      ROW:
      for row = 0 to 7
      {
         COL:
         for col = 0 to 7
            if (board@row@col == 0)
            {
               ROWDIR:
               for rowdir = -1 to 1
               {
                  if (row <= 1 and rowdir == -1) or (row >= 6 and rowdir == 1)
                     next ROWDIR // No capture possible this direction

                  COLDIR:
                  for coldir = -1 to 1
                  {
                     if coldir==0 and rowdir==0
                        next COLDIR
                     
                     if (col <= 1 and coldir == -1) or (col>=6 and coldir == 1)
                        next COLDIR // No capture possible this direction

                     if testCapture[row, col, rowdir, coldir, player] == true
                     {
                        moves.push[new OthelloMove[row, col, player]]
                        next COL  // A move found in this space, try next space
                     }
                  }
               }
            }
         }

      moves.sort[moveOrderer]
      return moves
   }

   /** Checks to see if the specified player has any move at all.  Returns
       true if they can. */
   canMove[player] :=
   {
      if filled == 64
         return false
      
      for row = 0 to 7
         for col = 0 to 7
            if (board@row@col == 0)
            {
               ROWDIR:
               for rowdir = -1 to 1
               {
                  if (row <= 1 and rowdir == -1) or (row >= 6 and rowdir == 1)
                     next ROWDIR // No capture possible this direction

                  COLDIR:
                  for coldir = -1 to 1
                  {
                     if coldir==0 and rowdir==0
                        next COLDIR
                     
                     if (col <= 1 and coldir == -1) or (col>=6 and coldir == 1)
                        next COLDIR // No capture possible this direction

                     if testCapture[row, col, rowdir, coldir, player] == true
                        return true
                  }
               }
            }

      return false
   }
   
   /** Applies a move to this GameState and returns the next GameState.  The
       move should implement GameMove.
   */
   applyMove[move is OthelloMove] :=
   {
      newBoard = new Othello[this]  // Copy board
      if move != undef
         newBoard.doApplyMove[move.row, move.col, move.player]
      return newBoard
   }

   /** Applies a move to this GameState and returns the next GameState. */
   doApplyMove[row, col, player] :=
   {
      if (board@row@col == 0)
      {
         ROWDIR:
         for rowdir = -1 to 1
         {
            if (row <= 1 and rowdir == -1) or (row >= 6 and rowdir == 1)
               next ROWDIR // No capure possible this direction

            COLDIR:
            for coldir = -1 to 1
            {
               if coldir==0 and rowdir==0
                  next COLDIR
               
               if (col <= 1 and coldir == -1) or (col>=6 and coldir == 1)
                  next COLDIR // No capture possible this direction

               if testCapture[row, col, rowdir, coldir, player] == true
               {
                  r1 = row + rowdir
                  c1 = col + coldir
                  // println["playing $row $col $rowdir $coldir $player"]
                  while board@r1@c1 == -player
                  {
                     board@r1@c1 = player  // Flip piece
                     r1 = r1 + rowdir
                     c1 = c1 + coldir
                  } 
               }
            }
         }
      }
      board@row@col = player
      filled = filled + 1           
   }

   /** Returns true if a capture can be made by the player playing at
       row, col and going in direction rowdir, coldir */
   testCapture[row, col, rowdir, coldir, player] :=
   {
      r1 = row + rowdir
      c1 = col + coldir
      if board@r1@c1 == -player  // Opposite player's color adjacent, keep going
      {
         do
         {
            r1 = r1 + rowdir
            c1 = c1 + coldir
            if r1<0 or r1>7 or c1<0 or c1>7  // Off the board, not captured
               return false
            
            val = board@r1@c1
            if val == 0     // Empty place before player's color
               return false
            
            if val == player // Found player's color again
               return true
         } while true
      }

      return false
   }

   /** If this position is a win for a player (-1 or +1), it returns that
       player's number, otherwise returns 0. */
   winFor[] :=
   {
      if ! canMove[-1] and ! canMove[1]
         return signum[staticEvaluate[]]
      else
         return 0
   }
   
   /** Renders the game state in a human-friendly format (e.g. drawing the
       game board.) */
   toString[] :=
   {
      str = "   0 1 2 3 4 5 6 7\n"
      for r = 0 to 7
      {
         str = str + "$r "
         for c = 0 to 7
         {
            v = board@r@c 
            if v == 0
               str = str + " ."
            else
               if v == -1
                  str = str + " O"
               else
                  str = str + " X"
         }
         if r < 7
            str = str + "\n"     
      }

      return str
   }

   /** Turns a player number (-1 or +1) into the associated character. */
   class playerToString[player] :=
   {
      if player == 1
         return "X"
      if player == -1
         return "O"
      else
         return "nobody"
   }
}

/** This implements the GameMove interface to represent a move in an Othello
    game. */
class OthelloMove implements GameMove
{
   /** The move is represented as a row, column, and player. */
   var row
   var col
   var player

   new[r, c, p] :=
   {
      row = r
      col = c
      player = p
   }
   
   /** Returns a human-readble string for logging and display. */
   toString[] :=
   {
      "Row: $row  Col: $col  Player: $player"
   }
}

// The rest of this program actually plays the game by taking user input
// and letting the computer calculate its move by calling Game.negamax[]

// LOL thanks to the eval you can do WarGames-style "ZERO" for number of players
players = eval[input["Number of players: ", 0]]
board = new Othello[]

println[board.toString[]]

var row
var col

// Represents which player number moves next.  In official Othello rules
// black always moves first.
movesNext = random[[-1,1]]

while board.canMove[1] or board.canMove[-1]
{
   p = Othello.playerToString[movesNext]
   if players==2 or (players==1 and movesNext == 1)    // Human moves
   {
      if board.canMove[movesNext]
      {
         do
         {
            println[]
            [row, col] = eval[input["Enter move for $p", ["row: ", "col: "]]]
            if board.board@row@col != 0
               println["Try again."]
         } while board.board@row@col != 0

         move = new OthelloMove[row, col, movesNext]
      } else
      {
         println["Player $p has no moves!"]
         move = undef
      }
   } else    // Computer moves
   {
      [move, value] = Game.negamax[board, movesNext==1 ? 8 : 7, movesNext]
      if move != undef
         println["\nComputer ($p, $movesNext) chose " + move.toString[] + ", perceived value = " + (value * movesNext)]
      else
         println["\nComputer player ($p) apparently has no move!"]
   }

   if move != undef
      board = board.applyMove[move]
   
   println[board.toString[]]
   movesNext = -movesNext
}

println["Win for " + Othello.playerToString[board.winFor[]] + " by " + abs[board.staticEvaluate[]]]