gistfile1.txt

import multiAgents                                                                                                                                                                                                                                                                                                          

class TrivialProblem(object):
  """ make a tree that looks like this:

                root (4)
                /      \
          min left (4)  min right (2)
           / \            /    \
         4   3          2       deeper (1000) 
         A   B          C         |
                                 1000 (D)
  """
  def __init__(self):
    s = StubbedGameState
    # first leaves
    A = s({}, 4, 'A', win=True)
    B = s({}, 3, 'B', lose=True)
    C = s({}, 2, 'C', win=True)
    D = s({}, 1000, 'D', lose=True)

    # note the alphabetical ordering of action names is important here, L before R
    deeper = s({'pacLeft': D}, 1000, 'deeper')
    minLeft = s({'gLeft': A, 'gRight': B}, 4, 'minLeft')
    minRight = s({'gLeft': C, 'gRight': deeper}, 2, 'minRight')

    self.startState = s({'pacLeft': minLeft, 'pacRight': minRight}, 4, 'root')

explored = set()
class StubbedGameState(object):
  def __init__(self, actionsToStates, score, name, win=False, lose=False):
    self.actions = actionsToStates.keys()
    self.actions.sort()
    self.actionsToStates = actionsToStates
    self.win = win
    self.name = name
    self.lose = lose
    self.score = score

  def generateSuccessor(self, agentIndex, action):
    explored.add(self.name)
    return self.actionsToStates[action]

  def getScore(self):
    return self.score

  def getLegalActions(self, agentIndex):
    return self.actions

  def isWin(self):
    return self.win

  def isLose(self):
    return self.lose

  def getNumAgents(self):
    return 2

prob = TrivialProblem()
studentAgent = multiAgents.AlphaBetaAgent(depth=3)
correctSet = set(['minLeft', 'minRight', 'root'])
incorrectSet = set(['minLeft', 'minRight', 'root', 'deeper'])
action = studentAgent.getAction(prob.startState)

if action != 'pacLeft':
  print 'Your alphabeta agent returned a suboptimal action'
  # fail
if explored == correctSet:
  print 'good job!'
else:
  print 'Your alphabeta agent did not prune successfully for a small game tree'
  #fail
~