Download or view Othello.frink in plain text format
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.
*/
applyMove[move is OthelloMove] :=
{
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[1]
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[1] 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 ? 10 : 9, 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[]]]
Download or view Othello.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, 20 hours, 18 minutes ago.