Download or view Game.frink in plain text format
/** This file contains classes, interface definitions, and algorithms for
implementing a game tree search.
There are 2 players designated +1 and -1.
Depth is the number of plies to search. 0 means only statically evaluate
this position as a terminal position.
To implement a game, you will need to write a class that implements the
GameState interface and one that implements the GameMove interface, defined
below.
The Game class has class-level methods that perform searches over the
game state. You will probably want to call the negamax function to
find the best move.
A sample implementation of all the requisite interfaces and programs to
play the games can be found in
TicTacToe.frink or Othello.frink
*/
class Game
{
/** Performs a negamax evaluation of the current position. This sets up for
the recursive call.
args:
[state, depth, player]
where:
state: An instance of a class that implements the GameState interface
which represents the position of the game.
depth: An integer representing how many moves deep the game tree will
be searched. This should almost always be an *even* number
(especially for small search depths)
because that analyzes this player's move and the opposing
player's immediate countermove. If you don't immediately
consider the opposing player's countermove, that leads to a
possibly-disastrous evaluation of the position.
player: An integer -1 or +1 indicating the player to move next.
Returns:
[move, value]
move: the best top-level GameMove found during search
value: the expected value of that move for the specified player.
(positive is better for that player.) If you want a consistent
estimate of which player is going to win, multiply value by
player. This will give a prediction of which player is expected
to win. (e.g. if value * player = -26, this predicts that
player -1 will win.)
*/
class negamax[state is GameState, depth, player] :=
{
return negamax[state, depth, -1e100, 1e100, player]
}
/** This is the actual recursive call for a negamax search.
see https://en.wikipedia.org/wiki/negamax#negamax_with_alpha_beta_pruning
Returns:
[move, value]
move: the best top-level GameMove found during search
value: the value for the specified player (positive is better.)
*/
class negamax[state is GameState, depth, alpha, beta, player] :=
{
if depth == 0 or state.isTerminal[player]
return [undef, player * state.staticEvaluate[]]
value = -1e100
bestMove = undef
// TODO: Order moves? Alpha-Beta pruning really only works well when
// the better possible moves are evaluated first.
// THINK ABOUT: If nextMoves is empty or isTerminal[player] is true,
// what do we do? In games like
// Othello, if a player cannot make a valid move, they forfeit their turn
// and the opposite player is allowed to move. About the only thing we
// can do in that case is return undef for bestMove. Should a GameState
// have a method which is queried as to what occurs when a player has no
// valid moves? In chess, if a player has no legal moves, then it is
// apparently an automatic draw.
// It would be possible to make a nextMoves[] implementation that,
// if it cannot move and it should forfeit its turn and the other player
// should move, it should return some sort of a null move.
MOVES:
for move = state.nextMoves[player]
{
nextState = state.applyMove[move]
[nextMove, moveValue] = negamax[nextState, depth-1, -beta, -alpha, -player]
moveValue = -moveValue
if moveValue > value
{
value = moveValue
bestMove = move
// println["Best move is now " + move.toString[]]
}
alpha = max[alpha, value]
if alpha >= beta
break MOVES
}
// THINK ABOUT: If bestMove is undef, no moves were found.
return [bestMove, value]
}
}
/** This interface specifies methods that must be implemented by a class that
represents the instantaneous state of a game. (e.g. the board positions
and any other state relevant to the game (e.g. for chess, has each player
already castled or the more subtle 50-moves rule (i.e. it's a draw if no
capture has been made and no pawn moved in the last 50 turns.)
THINK ABOUT: Should there be an optional orderMoves[] function? This would
try to make the better moves first. This is necessary to make alpha-beta
pruning work faster.
THINK ABOUT: Should this require a hash code and/or equals function? That
would enable previously-evaluated positions to be require no re-evaluation.
THINK ABOUT: Some game engines do a applyMove / undoMove combination which
allows less memory allocation than just doing an applyMove. Change this?
Note that doing so makes it much more error-prone to put a GameState into
a dictionary or set, among many other problems.
THINK ABOUT: Should there be a playerNumberToName function which turns the
player number (e.g. -1 and +1) to a name (e.g. "Black" and "White" or
"X" and "O")?
THINK ABOUT: Should there be a newGame[] function which returns a
GameState object with a starting board position? This would allow a
controller class (maybe Game) to automatically initialize and start playing
any game. It might need to return some information about what player plays
first, too? In chess, white always plays first but in other games the
starting player may be chosen randomly.
THINK ABOUT: Should there be an isValid[GameMove] to allow the computer to
validate that a player's move (or its own move) is valid? That would allow
easier writing of a program to take player input. Some game engines also
allow their move generators to be simpler and generate "possibly correct"
moves that are verified more stringently later (e.g. the "50-move rule"
in chess.) But that could be a separate interface to make a GameState
as easy as possible to implement.
THINK ABOUT: It might be cool if there was a method to render a graphics
object for graphical representation. But that could be a separate
interface to make a GameState as easy as possible to implement.
*/
interface GameState
{
/** Returns true if this is a terminal state (e.g. a winning or losing
position that cannot be followed any further.) Player is the player to
move next (-1 or +1), but is not always relevant.
*/
isTerminal[player]
/** Perform a static evaluation of the game state. This should always give a
ranking for the win probability for player +1. */
staticEvaluate[]
/** Generates the next moves for the specified player (+1 or -1.) The
return type should be an array of objects that implement the GameMove
interface. Preferably, the potentially best moves should be sorted to
the front of the array, as that makes the alpha-beta pruning work the
most efficiently.
*/
nextMoves[player]
/** Applies a move to this GameState and returns the next GameState. The
move should implement GameMove, and specifically, an implementation of
GameMove that is specific to this game.
*/
applyMove[move is GameMove]
/** If this position is a win for a player (-1 or +1), it returns that
player's number, otherwise returns 0. */
winFor[]
/** Renders the game state in a human-friendly format (e.g. drawing the
game board.) */
toString[]
}
/** This is an interface that indicates a move in a game. This should be
related to a specific GameState type. */
interface GameMove
{
/** Returns a human-readble string for logging and display. */
toString[]
}
Download or view Game.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 19966 days, 1 hours, 51 minutes ago.