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 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[]]]
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 19963 days, 23 hours, 16 minutes ago.