0

I am trying to write a minimax algorithm for a pacman game. I am having a problem with the recursion - sometimes my algorithm 'works' (it does not crash, but returns the wrong value still), and then sometimes it crashes and gives me a recursion error, saying max recursion depth exceeded. Can someone shed some light on what I am doing wrong here? Thank you!

 def minimax(self, gamestate, depth, agent):
        if depth == self.depth or gamestate.isWin() or gamestate.isLose():
            return self.evaluationFunction(gamestate), Directions.STOP
        best_move = None

        if agent == 0: ## Pacman is max
            best_val = float('-inf')
        else: ## ghosties are min
            best_val = float('inf')

        actions = gamestate.getLegalActions(agent)
        for action in actions:
            next_agent = agent + 1  ## quit moving me! ## this goes here to set next_agent to be same as agent each iteration, because it also gets changed below
            successor = gamestate.generateSuccessor(agent, action) ## generate successors gamestate (ie new board)
            if next_agent == gamestate.getNumAgents():
                next_agent = 0  ## Once we reach the last agent, set back to 0
                depth += 1  ## increment depth

            v = self.minimax(successor, depth, next_agent)

            ## here is where we set the max and min values based on the agent
            if agent == 0: ## pacman - max
                if v > best_val:
                    best_val = v
                    best_move = action
            else: ## ghost - min
                if v < best_val:
                    best_val = v
                    best_move = action
        return best_move, best_val
Elizabeth
  • 13
  • 1
  • 7
  • Did you try to add some `print` statements in there to see what it was doing? How do you know that the algorithm returns the wrong value? – Stef Oct 04 '20 at 02:55
  • You may consider increasing the recursion limit in Python. https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it and you should use alpha-beta pruning to decrease the number of nodes (and branches) since the search space is exponential. – Paco Wong Oct 04 '20 at 02:58
  • I know it is not returning the most optimal value because this assignment is from Berkeley and comes with an autograder that runs your code against test cases. It shows you the most optimal move, and the move you are returning. If these do not equal, you aren't returning the most optimal node. – Elizabeth Oct 05 '20 at 03:35
  • Also - alpha beta pruning is the next question. We do not implement it for this question, just minimax! – Elizabeth Oct 05 '20 at 03:35

0 Answers0