# TicTacToe.frink

``` use Game.frink /** This uses the Game interface to play tic-tac-toe.     To be able to play a game, we have to implement the GameState and GameMove     interfaces specified in Game.frink. */ /** This class implements the GameState class to play tic-tac-toe. */ class TicTacToe implements GameState {    /** The board is represented by a 3x3 array where an empty spot is        represented by a zero.  Player +1 is represented by +1        and player -1 represented by a -1.  This allows easy detection of a        run by summation.  It also provides an easy way of sorting a line for        potential "goodness" because a win will have a sum of +3 or -2, an        almost-completed row will have a sum of +2 or -2, a blocked line (where        no win is possible) will have a sum of 0.  Alpha-beta pruning works        best and fastest when the best potential moves are evaluated first, so        the best moves could be found by sorting by absolute value of the rows        that intersect that move.    */    var board    /** Create a new blank starting board */    new[] :=    {       board = new array[[3,3],0]    }    /** Copy constructor. */    new[orig is TicTacToe] :=    {       board = deepCopy[orig.board]    }        /** Returns true if this is a terminal state (e.g. a winning or losing        position that cannot be followed any further.) */    isTerminal[player] :=    {       return winFor[] != 0 or allFilled[]    }    /** If this is a win for either player, returns the player number for whom        it is a win, otherwise returns 0 */    winFor[] :=    {       /** Check rows */       for r = 0 to 2       {          sum = sum[board@r]          if abs[sum] == 3             return signum[sum]       }       /** Check columns */       for c = 0 to 2       {          sum = sum[board.getColumn[c]]          if abs[sum] == 3             return signum[sum]       }       /** Check diagonals */       sum = 0       for n = 0 to 2          sum = sum + board@n@n       if abs[sum] == 3          return signum[sum]       /** Check other diagonal */       sum = 0       for n = 0 to 2          sum = sum + board@n@(2-n)       if abs[sum] == 3          return signum[sum]       return 0    }    /** Returns true if all spaces are filled. */    allFilled[] :=    {       for r = 0 to 2          for c = 0 to 2             if board@r@c == 0                return false       return true               }        /** Perform a static evaluation of the game state.  This should always give a        ranking for the win probability for player +1. */    staticEvaluate[] :=    {       val = winFor[]       if val != 0          return val       else          return 0   // TODO:  Improve this (although it works fine for any                     //        exhaustive search)    }    /** Generates the next moves for the specified player (+1 or -1.)  The        resultant types should each be an object that implements the GameMove        interface.        THINK ABOUT:  Should this make a list or iterate?    */    nextMoves[player] :=    {       moves = new array              for r = 0 to 2          for c = 0 to 2             if board@r@c == 0   // Space is empty                moves.push[new TicTacToeMove[r, c, player]]       return moves              }    /** Applies a move to this GameState and returns the next GameState.        The move should be an instance of TicTacToeMove which implements        GameMove. */    applyMove[move] :=    {       newBoard = new TicTacToe[this]   // Copy board       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] :=    {       board@row@col = player    }    /** Renders the game state in a human-friendly format (e.g. drawing the        game board.) */    toString[] :=    {       str = ""       for r = 0 to 2       {          for c = 0 to 2          {             v = board@r@c              if v == 0                str = str + " ."             else                if v == -1                   str = str + " O"                else                   str = str + " X"          }          if r < 2             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 a Tic-Tac-Toe     game. */ class TicTacToeMove 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"    } } // LOL thanks to the eval you can do WarGames-style "ZERO" for number of players players = eval[input["Number of players: ", 0]] // The rest of this program actually plays the game by taking user input // and letting the computer calculate its move by calling Game.negamax[] board = new TicTacToe[] var row var col movesNext = random[[-1,1]]  // Represents which player number moves next. while ! board.isTerminal[movesNext] {    p = TicTacToe.playerToString[movesNext]    if players==2 or (players==1 and movesNext == 1)    // Human moves    {       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 TicTacToeMove[row, col, movesNext]    } else    // Computer moves    {       [move, value] = Game.negamax[board, 9, movesNext]       if move != undef          println["\nComputer (\$p) chose " + move.toString[] + ", value=\$value"]    }    board = board.applyMove[move]    println[board.toString[]]    movesNext = -movesNext } println["Win for " + TicTacToe.playerToString[board.winFor[]]] ```