/** 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. THINK ABOUT: Should there be a winFor[] method which returns a player number if the game state represents a win for a player? It should return the player's number for whom it is a win, or 0 otherwise. This was found to be useful in a few implementations. */ 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[] }