CS6601 Challenge Question 3 - Game Playing Raymond Jia Fall 2024 Note*: Please review…
- User
CS6601 Challenge Question 3 - Game Playing Raymond Jia Fall 2024 Note*: Please review the course textbook AIMA 4th Edition Chapter 5, Canvas Game Playing Modules, and Assignment 2 before attempting this Challenge Question. Introduction Figure 1: Game Tree A Consider a two-player game where players take turns to make moves and the utility of each state is a whole number. We are playing as player one, and it is currently our turn to make a move (represented by a max node at depth 0). The utility for our game states have a minimum value of −100 (game lost) and a maximum value of 100 (game won). The game tree of depth 3 at this current turn can be see in Figure 1 above, with the leaf nodes showing the utility values of the game states at depth 3. Q1 [1pt] Using Minimax, what is the value of the utility value that will be propagated to the top in Game Tree A seen in Figure 1? (AIMA 4th Ed. Section 5.2 ) Answer as a whole number between 0 and 100 inclusive. Q2 [2pt] If we perform Minimax with iterative deepening on Game Tree A seen in Figure 1 starting at a depth of 0 and incrementing the depth limit by 1 until a depth limit of 3 is reached, how many nodes will be explored in total during the process? Answer as a whole number. 1 Q3 [2pt] If we use Alpha-Beta Pruning on Game Tree A seen in Figure 1, how many leaf nodes will be pruned? (AIMA 4th Ed. Section 5.2.3 ) Answer as a whole number. Q4 [2pt] If we re-order the nodes in the game tree, we can make Alpha-Beta Pruning more effective by pruning more nodes. How many leaf nodes will be pruned if we use Game Tree B seen in Figure 2 instead of Game Tree A? Figure 2: Game Tree B Answer as a whole number. Q5 [3pts] Re-order the game tree such that the number of nodes pruned using Alpha-Beta Pruning is maximized. How many nodes will be pruned when using the re-ordered tree? Answer as a whole number. 2
- Assistant
To maximize the number of nodes pruned using Alpha-Beta pruning, you would reorder the game tree so that the best moves (from the maximizing player's perspective) are evaluated first at each node. In the best-case scenario, Alpha-Beta pruning can reduce the number of nodes that need to be evaluated from (O(b^d)) to (O(b^{d/2})), where (b) is the branching factor and (d) is the depth of the tree.
For a tree of depth 3 with a branching factor of 3, the total number of leaf nodes is (3^3 = 27). In the best-case ordering, you only need to evaluate approximately (3^{1.5} \approx 5) leaf nodes. Therefore, the maximum number of leaf nodes that can be pruned is (27 - 5 = 22).
So, the maximum number of leaf nodes that can be pruned by optimally reordering the tree is 22.
Answer: 22