Due Date: 21 July 2023 Total Marks: 145
Unique Assignment Number: 633536 FOR SUPER SEMESTER – Semesters 1 & 2
(1.1) Clearly explain what a utility function is, and why it is used during adversarial searches. (3)
(1.2) Is the ideal strategy only available if we have perfect information? Explain your answer.
(1.3) Explain how forward pruning works. Provide at least one approach to forward pruning in your
explanation, as well as a problem that may be encountered with forward
pruning.
(1.4) Does the order in which nodes are examined in minimax matter? Explain your answer. (3)
(1.1) A utility function is a mathematical function used to assign values to different game states or
outcomes in a game. It represents a player's preference or satisfaction with each possible game state.
The utility function is used during adversarial searches, such as minimax, to evaluate the desirability
of different moves or strategies. By assigning values to game states, the utility function helps
determine the best move for a player in order to maximize their chances of winning.
(1.2) No, the ideal strategy is not only available if we have perfect information. The ideal strategy
refers to the best possible move or sequence of moves that can be made in a game. While perfect
information can certainly help in determining the ideal strategy, it is not always necessary. Players
can make reasonable assumptions or predictions about the unknown aspects of the game and still
come up with effective strategies. Imperfect information can add uncertainty and complexity to the
decision-making process, but it does not necessarily mean that the ideal strategy cannot be
achieved.
(1.3) Forward pruning is a technique used in game tree search algorithms to reduce the number of
nodes evaluated during the search. It involves eliminating or ignoring certain branches of the game
tree that are unlikely to lead to a desirable outcome. One approach to forward pruning is called
alpha-beta pruning.
Alpha-beta pruning works by maintaining two values, alpha and beta, during the search. Alpha
represents the maximum lower bound on the utility value that a player can achieve, and beta
represents the minimum upper bound. As the search progresses, if a node's alpha value becomes
greater than or equal to its beta value, it means that the node can never be reached in the actual
gameplay, and thus the rest of its subtree can be pruned.
, One problem encountered with forward pruning is that it can potentially lead to incorrect decisions.
Pruning certain branches of the game tree may cause the algorithm to miss important moves or
strategies that could have resulted in a better outcome. Therefore, careful consideration and analysis
are required to ensure that forward pruning is applied correctly and does not result in suboptimal
decisions.
(1.4) Yes, the order in which nodes are examined in minimax does matter. Minimax is a recursive
algorithm that explores the entire game tree to determine the best move for a player. The algorithm
alternates between maximizing and minimizing the utility values at each level of the tree. The order
in which nodes are examined determines the sequence of moves and, consequently, the final
decision made by the algorithm.
If nodes are examined in a different order, it can lead to different decisions being made by the
algorithm. The order in which nodes are examined can affect the pruning process in alpha-beta
pruning and can influence the outcome of the search. Therefore, the order of node examination is an
important factor in the effectiveness and efficiency of the minimax algorithm.
Question 2
(2.1) The minimax values for all nodes in Figure 1 are as follows:
Node A: Minimax value = 5
Node B: Minimax value = 0
Node C: Minimax value = -4
Node D: Minimax value = 5
Node E: Minimax value = -8
Node F: Minimax value = -4
Node G: Minimax value = 3
Node H: Minimax value = -3
Node I: Minimax value = -12
Node J: Minimax value = 5
Node K: Minimax value = -8
Node L: Minimax value = -3
Node M: Minimax value = 3
Node N: Minimax value = -4
Node O: Minimax value = -12
Node P: Minimax value = 5
Node Q: Minimax value = -8
Node R: Minimax value = -3
Unique Assignment Number: 633536 FOR SUPER SEMESTER – Semesters 1 & 2
(1.1) Clearly explain what a utility function is, and why it is used during adversarial searches. (3)
(1.2) Is the ideal strategy only available if we have perfect information? Explain your answer.
(1.3) Explain how forward pruning works. Provide at least one approach to forward pruning in your
explanation, as well as a problem that may be encountered with forward
pruning.
(1.4) Does the order in which nodes are examined in minimax matter? Explain your answer. (3)
(1.1) A utility function is a mathematical function used to assign values to different game states or
outcomes in a game. It represents a player's preference or satisfaction with each possible game state.
The utility function is used during adversarial searches, such as minimax, to evaluate the desirability
of different moves or strategies. By assigning values to game states, the utility function helps
determine the best move for a player in order to maximize their chances of winning.
(1.2) No, the ideal strategy is not only available if we have perfect information. The ideal strategy
refers to the best possible move or sequence of moves that can be made in a game. While perfect
information can certainly help in determining the ideal strategy, it is not always necessary. Players
can make reasonable assumptions or predictions about the unknown aspects of the game and still
come up with effective strategies. Imperfect information can add uncertainty and complexity to the
decision-making process, but it does not necessarily mean that the ideal strategy cannot be
achieved.
(1.3) Forward pruning is a technique used in game tree search algorithms to reduce the number of
nodes evaluated during the search. It involves eliminating or ignoring certain branches of the game
tree that are unlikely to lead to a desirable outcome. One approach to forward pruning is called
alpha-beta pruning.
Alpha-beta pruning works by maintaining two values, alpha and beta, during the search. Alpha
represents the maximum lower bound on the utility value that a player can achieve, and beta
represents the minimum upper bound. As the search progresses, if a node's alpha value becomes
greater than or equal to its beta value, it means that the node can never be reached in the actual
gameplay, and thus the rest of its subtree can be pruned.
, One problem encountered with forward pruning is that it can potentially lead to incorrect decisions.
Pruning certain branches of the game tree may cause the algorithm to miss important moves or
strategies that could have resulted in a better outcome. Therefore, careful consideration and analysis
are required to ensure that forward pruning is applied correctly and does not result in suboptimal
decisions.
(1.4) Yes, the order in which nodes are examined in minimax does matter. Minimax is a recursive
algorithm that explores the entire game tree to determine the best move for a player. The algorithm
alternates between maximizing and minimizing the utility values at each level of the tree. The order
in which nodes are examined determines the sequence of moves and, consequently, the final
decision made by the algorithm.
If nodes are examined in a different order, it can lead to different decisions being made by the
algorithm. The order in which nodes are examined can affect the pruning process in alpha-beta
pruning and can influence the outcome of the search. Therefore, the order of node examination is an
important factor in the effectiveness and efficiency of the minimax algorithm.
Question 2
(2.1) The minimax values for all nodes in Figure 1 are as follows:
Node A: Minimax value = 5
Node B: Minimax value = 0
Node C: Minimax value = -4
Node D: Minimax value = 5
Node E: Minimax value = -8
Node F: Minimax value = -4
Node G: Minimax value = 3
Node H: Minimax value = -3
Node I: Minimax value = -12
Node J: Minimax value = 5
Node K: Minimax value = -8
Node L: Minimax value = -3
Node M: Minimax value = 3
Node N: Minimax value = -4
Node O: Minimax value = -12
Node P: Minimax value = 5
Node Q: Minimax value = -8
Node R: Minimax value = -3
