I am currently implementing an alpha-beta pruning algorithm for a minimax function. This exercise corresponds to the multiagent section of the PacMan Project at Berkeley University.
My implementation:
class AlphaBetaAgent(MultiAgentSearchAgent):
"""
Your minimax agent with alpha-beta pruning (question 3)
"""
def getAction(self, gameState):
"""
Returns the minimax action using self.depth and self.evaluationFunction
"""
"*** YOUR CODE HERE ***"
def maxValue(state, depth: int, alpha: int, beta: int):
depth += 1
if state.isWin() or state.isLose() or depth == self.depth:
return self.evaluationFunction(state)
else:
value: int = -sys.maxsize - 1
legalActions: list = state.getLegalActions(0)
for action in legalActions:
value = max(value, minValue(
state.generateSuccessor(0, action), 1, depth, alpha, beta))
if beta <= value:
return value
alpha = max(alpha,value)
return value
def minValue(state, ghostIndex: int, depth: int, alpha: int, beta: int):
if state.isWin() or state.isLose():
return self.evaluationFunction(state)
else:
value: int = sys.maxsize * 2 + 1
legalActions: list = state.getLegalActions(ghostIndex)
if ghostIndex == state.getNumAgents() - 1:
for action in legalActions:
value = min(value, maxValue(
state.generateSuccessor(ghostIndex, action), depth, alpha, beta))
else:
for action in legalActions:
value = min(value, minValue(state.generateSuccessor(
ghostIndex, action), ghostIndex + 1, depth, alpha, beta))
if alpha >= value:
return value
beta = min (beta, value)
return value
pacManMoves: list = gameState.getLegalActions(0)
value: int = -sys.maxsize - 1
alpha: int = -sys.maxsize - 1
beta: int = sys.maxsize*2+1
move: str = Directions.STOP
for currentMove in pacManMoves:
currentValue = minValue(
gameState.generateSuccessor(0, currentMove), 1, 0, alpha, beta)
if (currentValue > value):
value = currentValue
move = currentMove
return move
Output:
Question q3
===========
*** PASS: test_cases\q3\0-eval-function-lose-states-1.test
*** PASS: test_cases\q3\0-eval-function-lose-states-2.test
*** PASS: test_cases\q3\0-eval-function-win-states-1.test
*** PASS: test_cases\q3\0-eval-function-win-states-2.test
*** FAIL: test_cases\q3\0-lecture-6-tree.test
*** Incorrect generated nodes for depth=2
*** Student generated nodes: A B C D E F G H I max min1 min2 min3
*** Correct generated nodes: A B C D E F G H max min1 min2 min3
*** Tree:
*** max
*** /-/ | \--\
*** / | \
*** / | \
*** min1 min2 min3
*** /|\ /|\ /|\
*** / | \ / | \ / | \
*** A B C D E F G H I
*** 3 12 8 5 4 6 14 1 11
*** FAIL: test_cases\q3\0-small-tree.test
*** Incorrect generated nodes for depth=3
*** Student generated nodes: A B C D deeper minLeft minRight root
*** Correct generated nodes: A B C minLeft minRight root
*** Tree:
*** root
*** / \
*** minLeft minRight
*** / \ / \
*** A B C deeper
*** 4 3 2 |
*** D
*** 1000
*** FAIL: test_cases\q3\1-1-minmax.test
*** Incorrect generated nodes for depth=3
*** Student generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Correct generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ |
*** c1 c2 cx
*** / \ / \ |
*** d1 d2 d3 d4 dx
*** -3 -9 10 6 -3.01
***
*** a - max
*** b - min
*** c - max
***
*** Note that the minimax value of b1 is -3.
*** FAIL: test_cases\q3\1-2-minmax.test
*** Incorrect generated nodes for depth=3
*** Student generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Correct generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ |
*** c1 c2 cx
*** / \ / \ |
*** d1 d2 d3 d4 dx
*** -3 -9 10 6 -2.99
***
*** a - max
*** b - min
*** c - max
***
*** Note that the minimax value of b1 is -3.
*** FAIL: test_cases\q3\1-3-minmax.test
*** Incorrect generated nodes for depth=3
*** Student generated nodes: a b1 b2 c3 c4 cx d5 d6 d7 d8 dx
*** Correct generated nodes: a b1 b2 c3 cx d5 d6 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** | / \
*** cx c3 c4
*** | / \ / \
*** dx d5 d6 d7 d8
*** 4.01 4 -7 0 5
***
*** a - max
*** b - min
*** c - max
***
*** Note that the minimax value of b2 is 4.
*** PASS: test_cases\q3\1-4-minmax.test
*** FAIL: test_cases\q3\1-5-minmax.test
*** Incorrect generated nodes for depth=4
*** Student generated nodes: A B C D E F G H Z a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Correct generated nodes: A B C D E F G Z a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ |
*** c1 c2 cx
*** / \ / \ |
*** d1 d2 d3 d4 dx
*** / \ / \ / \ / \ |
*** A B C D E F G H Z
*** -3 13 5 9 10 3 -6 8 3.01
***
*** a - max
*** b - min
*** c - max
*** d - min
***
*** Note the minimax value of b1 is 3.
*** FAIL: test_cases\q3\1-6-minmax.test
*** Incorrect generated nodes for depth=4
*** Student generated nodes: A B C D E F G H Z a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Correct generated nodes: A B C D E F G Z a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ |
*** c1 c2 cx
*** / \ / \ |
*** d1 d2 d3 d4 dx
*** / \ / \ / \ / \ |
*** A B C D E F G H Z
*** -3 13 5 9 10 3 -6 8 2.99
***
*** a - max
*** b - min
*** c - max
*** d - min
***
*** Note the minimax value of b1 is 3.
*** FAIL: test_cases\q3\1-7-minmax.test
*** Incorrect generated nodes for depth=4
*** Student generated nodes: I J K L M O P Z a b1 b2 c3 c4 cx d5 d6 d7 d8 dx
*** Correct generated nodes: I J K M O P Z a b1 b2 c3 c4 cx d5 d6 d7 d8 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** | / \
*** cx c3 c4
*** | / \ / \
*** dx d5 d6 d7 d8
*** | / \ / \ / \ / \
*** Z I J K L M N O P
*** -1.99 -1 -9 4 7 2 5 -3 -2
***
*** a - max
*** b - min
*** c - min
*** d - max
***
*** Note that the minimax value of b2 is -2
*** FAIL: test_cases\q3\1-8-minmax.test
*** Incorrect generated nodes for depth=4
*** Student generated nodes: I J K L M O P Z a b1 b2 c3 c4 cx d5 d6 d7 d8 dx
*** Correct generated nodes: I J K M O P Z a b1 b2 c3 c4 cx d5 d6 d7 d8 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** | / \
*** cx c3 c4
*** | / \ / \
*** dx d5 d6 d7 d8
*** | / \ / \ / \ / \
*** Z I J K L M N O P
*** -2.01 -1 -9 4 7 2 5 -3 -2
***
*** a - max
*** b - min
*** c - min
*** d - max
***
*** Note that the minimax value of b2 is -2.01
*** PASS: test_cases\q3\2-1a-vary-depth.test
*** FAIL: test_cases\q3\2-1b-vary-depth.test
*** Incorrect generated nodes for depth=2
*** Student generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Correct generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ |
*** -4 c1 c2 9 cx -4.01
*** / \ / \ |
*** d1 d2 d3 d4 dx
*** -3 -9 10 6 -4.01
***
*** a - max
*** b - min
*** c - max
***
*** Note that the minimax value of b1 is -3, but the depth=1 limited value is -4.
*** The values next to c1, c2, and cx are the values of the evaluation function, not
*** necessarily the correct minimax backup.
*** PASS: test_cases\q3\2-2a-vary-depth.test
*** FAIL: test_cases\q3\2-2b-vary-depth.test
*** Incorrect generated nodes for depth=2
*** Student generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 d4 dx
*** Correct generated nodes: a b1 b2 c1 c2 cx d1 d2 d3 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ |
*** -4 c1 c2 9 cx -3.99
*** / \ / \ |
*** d1 d2 d3 d4 dx
*** -3 -9 10 6 -3.99
***
*** a - max
*** b - min
*** c - max
***
*** Note that the minimax value of b1 is -3, but the depth=1 limited value is -4.
*** The values next to c1, c2, and cx are the values of the evaluation function, not
*** necessarily the correct minimax backup.
*** PASS: test_cases\q3\2-3a-vary-depth.test
*** FAIL: test_cases\q3\2-3b-vary-depth.test
*** Incorrect generated nodes for depth=2
*** Student generated nodes: a b1 b2 c3 c4 cx d5 d6 d7 d8 dx
*** Correct generated nodes: a b1 b2 c3 cx d5 d6 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** | / \
*** 5.01 cx 8 c3 c4 5
*** | / \ / \
*** dx d5 d6 d7 d8
*** 5.01 4 -7 0 5
***
*** a - max
*** b - min
*** c - max
***
*** Note that the minimax value of b1 is 4, but the depth=1 limited value is 5.
*** The values next to c3, c4, and cx are the values of the evaluation function, not
*** necessarily the correct minimax backup.
*** PASS: test_cases\q3\2-4a-vary-depth.test
*** FAIL: test_cases\q3\2-4b-vary-depth.test
*** Incorrect generated nodes for depth=2
*** Student generated nodes: a b1 b2 c3 c4 cx d5 d6 d7 d8 dx
*** Correct generated nodes: a b1 b2 c3 cx d5 d6 dx
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** | / \
*** 4.99 cx 8 c3 c4 5
*** | / \ / \
*** dx d5 d6 d7 d8
*** 4.99 4 -7 0 5
***
*** a - max
*** b - min
*** c - max
***
*** Note that the minimax value of b1 is 4, but the depth=1 limited value is 5.
*** The values next to c3, c4, and cx are the values of the evaluation function, not
*** necessarily the correct minimax backup.
*** FAIL: test_cases\q3\2-one-ghost-3level.test
*** Incorrect generated nodes for depth=3
*** Student generated nodes: a b1 b2 c1 c2 c3 c4 d1 d2 d3 d4 d5 d6 d7 d8
*** Correct generated nodes: a b1 b2 c1 c2 c3 d1 d2 d3 d5 d6
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ / \
*** c1 c2 c3 c4
*** / \ / \ / \ / \
*** d1 d2 d3 d4 d5 d6 d7 d8
*** 3 9 10 6 4 7 0 5
***
*** a - max
*** b - min
*** c - max
*** FAIL: test_cases\q3\3-one-ghost-4level.test
*** Incorrect generated nodes for depth=4
*** Student generated nodes: A B C D E F G H I J K L M N O P a b1 b2 c1 c2 c3 c4 d1 d2 d3 d4 d5 d6 d7 d8
*** Correct generated nodes: A B C D E F I K a b1 b2 c1 c2 c3 d1 d2 d3 d5 d6
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ / \
*** c1 c2 c3 c4
*** / \ / \ / \ / \
*** d1 d2 d3 d4 d5 d6 d7 d8
*** / \ / \ / \ / \ / \ / \ / \ / \
*** A B C D E F G H I J K L M N O P
*** 3 13 5 9 10 11 6 8 1 0 4 7 12 15 2 14
***
*** a - max
*** b - min
*** c - max
*** d - min
*** FAIL: test_cases\q3\4-two-ghosts-3level.test
*** Incorrect generated nodes for depth=3
*** Student generated nodes: a b1 b2 c1 c2 c3 c4 d1 d2 d3 d4 d5 d6 d7 d8
*** Correct generated nodes: a b1 b2 c1 c2 c3 c4 d1 d2 d3 d4 d5 d6 d7
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ / \
*** c1 c2 c3 c4
*** / \ / \ / \ / \
*** d1 d2 d3 d4 d5 d6 d7 d8
*** 3 9 10 6 4 7 0 5
***
*** a - max
*** b - min
*** c - min
*** FAIL: test_cases\q3\5-two-ghosts-4level.test
*** Incorrect generated nodes for depth=4
*** Student generated nodes: A B C D E G H I J K L M O a b1 b2 c1 c2 c3 c4 d1 d2 d3 d4 d5 d6 d7 d8
*** Correct generated nodes: A B C D E G H I J a b1 b2 c1 c2 c3 d1 d2 d3 d4 d5
*** Tree:
*** /-----a------\
*** / \
*** / \
*** b1 b2
*** / \ / \
*** c1 c2 c3 c4
*** / \ / \ / \ / \
*** d1 d2 d3 d4 d5 d6 d7 d8
*** / \ / \ / \ / \ / \ / \ / \ / \
*** A B C D E F G H I J K L M N O P
*** 3 13 5 9 10 11 6 8 1 0 4 7 12 15 2 14
***
*** a - max
*** b - min
*** c - min
*** d - max
*** PASS: test_cases\q3\6-tied-root.test
*** PASS: test_cases\q3\7-1a-check-depth-one-ghost.test
*** PASS: test_cases\q3\7-1b-check-depth-one-ghost.test
*** PASS: test_cases\q3\7-1c-check-depth-one-ghost.test
*** PASS: test_cases\q3\7-2a-check-depth-two-ghosts.test
*** PASS: test_cases\q3\7-2b-check-depth-two-ghosts.test
*** PASS: test_cases\q3\7-2c-check-depth-two-ghosts.test
*** Running AlphaBetaAgent on smallClassic 1 time(s).
Pacman died! Score: 84
Average Score: 84.0
Scores: 84.0
Win Rate: 0/1 (0.00)
Record: Loss
*** Finished running AlphaBetaAgent on smallClassic after 15 seconds.
*** Won 0 out of 1 games. Average score: 84.000000 ***
*** FAIL: test_cases\q3\8-pacman-game.test
*** Bug: Wrong number of states expanded.
*** Tests failed.
There are a lot of functions inherent to the exercise that are already given and that I have not modified. The only function that has been modified for the purpose of the exercise is the one mentioned above.
Source code: https://github.com/MaAlonsoA/AI-Class/tree/feature/AlphaBetaAgent
Running the autograder with python autograder.py -q q3
Running on python 3.9.4
Solution:
There were two bugs in my previous implementation:
Previously in the minValue function calculated the value for all 'legal actions' if there was only one ghost left. This is incorrect, you only have to calculate it once.
legalActions: list = state.getLegalActions(ghostIndex)
if ghostIndex == state.getNumAgents() - 1:
for action in legalActions:
value = min(value, maxValue(
state.generateSuccessor(ghostIndex, action), depth, alpha, beta))
else:
fixed:
legalActions: list = state.getLegalActions(ghostIndex)
for action in legalActions:
if ghostIndex == state.getNumAgents() - 1:
value = min(value, maxValue(
state.generateSuccessor(ghostIndex, action), depth, alpha, beta))
if alpha > value:
return value
beta = min (beta, value)
else:
The currentValue needs to be checked to see if it is greater than beta.
for currentMove in pacManMoves:
currentValue = minValue(
gameState.generateSuccessor(0, currentMove), 1, 0, alpha, beta)
if (currentValue > value):
value = currentValue
move = currentMove
return move
fixed:
for currentMove in pacManMoves:
currentValue = minValue(
gameState.generateSuccessor(0, currentMove), 1, 0, alpha, beta)
if currentValue > value:
value = currentValue
move = currentMove
if currentValue > beta:
return move
alpha = max(alpha, value)
return move