TicTacToe.frink

Download or view TicTacToe.frink in plain text format


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[]]]


Download or view TicTacToe.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 19576 days, 19 hours, 45 minutes ago.