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 is TicTacToeMove] := { 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[]]]