Extract
[...] Iterates over all possible actions the current ghost can take. Generates the successor state and determines whether to use maxValue or minValue based on the current agent index. Updates the minimum value and the corresponding action if the current action is better for the ghost. Returns the best (minimum) score and the corresponding action for the ghost. Calls the maxValue 3.2 Alpha-beta Pruning Similarly, the Alpha-beta pruning was implemented in the AlphaBetaAgent class. Algorithm 3 Alpha-Beta Search Algorithm function ALPHA-BETA-SEARCH(game, state) player ? game.To-MOVE(state) value, move ? [...]
[...] 5 Conclusion The test results for Questions q2 and q3 present a stark contrast in performance. For Question q2, the tests were conclusively successful, indicating that the implemented algorithms or functionalities performed accurately and reliably. Every individual test case passed, and when applied in a game scenario, the 'MinimaxAgent ' secured a score of 84, although it was unable to achieve a win. On the other hand, Question q3 reveals challenges with the current implementation. While many of the test cases for this question also passed successfully, critical failures were observed. [...]
[...] Minimax and Alpha-Beta Pruning 1 Introduction This report covers the implementation of the Minimax algorithm and Alpha-beta pruning in the context of the Pac-Man Projects developed at UC Berkeley. Both the algorithms were implemented and tested using the provided framework and autograder tool. 2 Set up instructions The implementation is based on the Project 2 : Multi-Agent Search, whose details and instructions are provided on the project link. After downloading and extracting the codebase, it was ensured that the framework works as expected by running the Pac-Man game. [...]
[...] The results from the autograder for questions q2 and q3 are attached below. Python Output for Question q2 Starting on 9-19 at 23:15:52 Question q2 PASS: test_cases\q2\0-eval-function-lose-states-1.test (repeat for each test case) PASS: test_cases\q2\8-pacman-game.test Question q2: 5/5 Finished at 23:16:19 Provisional grades Question q2: 5/5 Total: 5/5 Your grades are NOT yet registered. To register your grades, make sure to follow your instructor's guidelines to receive credit on your project. Python Output for Question q3 Starting on 9-19 at 23:15:25 Question q3 PASS: test_cases\q3\0-eval-function-lose-states-1.test (repeat for each test case) FAIL: test_cases\q3\6-tied-root.test Incorrect generated nodes for depth=3 Student generated nodes: A B max min1 min2 Correct generated nodes: A B C max min1 min2 Tree: max min1 min2 A B C 10 10 (repeat for each test case) FAIL: test_cases\q3\8-pacman-game.test Bug: Wrong number of states expanded. [...]
[...] MAX-VALUE(game, state, return move function MAX-VALUE(game, state, if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null for all a in game.ACTIONS(state) do v2, a2 ? MIN-VALUE(game, game.RESULT(state, if v2 > v then move ? v2, a ? ? if ? ? ? then return move return move function MIN-VALUE(game, state, if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null for all a in game.ACTIONS(state) do v2, a2 ? MAX-VALUE(game, game.RESULT(state, if v2 [...]
