Game.frink

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.  This decision tree does
      // not currently search that tree properly.  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:  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.  The nextMoves[] function should probably just do
    this itself.

    THINK ABOUT:  Should this require a hash code and/or equals function?  That
    would enable previously-evaluated positions to be hashed and 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:  Have a winFor[] function which returns the player number that
    a position is a win for?  Or 0 if for neither.  This made the tic-tac-toe
    solver more elegant.

    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 alwasy 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.

       TODO: Make Frink specify that a interface method implements a constraint.
   */

   applyMove[move]

   /** 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 19576 days, 19 hours, 51 minutes ago.