# Othello.frink

``` 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.        TODO: Make Frink specify that a interface method implements a constraint.    */    applyMove[move] :=    {       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          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 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 : 6, 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[]]] ```