Monte Carlo Search

MonteCarloSearch.py

MAX_DEPTH = 5 # the fixed maximum depth for game tree expansion
MAX_PROBES = 10 # the fixed maximum number of MCS probes for a non-terminal state
import random

def value(game, state, role, depth):
  """
  returns the estimated value of the given state for the given role by
  expanding the search tree until MAX_DEPTH has been reached and then
  using MCS for non-terminal states' value estimation.
  This method can be used to select the best action for the given role by
  doing a 1-move look-ahead and applying this method to each resulting state.
  """
  if game.isTerminal(state): return game.getGoalValues(state)[role]
  if depth >= MAX_DEPTH: return monteCarloValue(game, state, role)
  return max(value(game, game.getNextState(state, jointMove), role, depth+1) for jointMove in game.getLegalJointMoves(state))
  
def monteCarloValue(game, state, role):
  return sum(randomProbeValue(game, state, role) for _ in xrange(MAX_PROBES)) / MAX_PROBES
  
def randomProbeValue(game, state, role):
  if game.isTerminal(state): return game.getGoalValues(state)[role]
  jointMove = {}
  for role in game.getRoles():
    jointMove[role] = random.choice(game.getLegalMoves(state, role))
  return randomProbeValue(game, game.getNextState(state, jointMove), role)