Software-Engineering
April 14, 2024Artificial-Intelligence
April 14, 2024Artificial-Intelligence
| Question 35 |
Which of the following statements are true?
A) Minimax search is breadth-first; it processes all the nodes at a level before moving to a node in the next level.
B) The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined.
C) The alpha-beta search algorithm computes the same optimal moves as the minimax algorithm.
D) Optimal play in games of imperfect information does not require reasoning about the current and future belief states of each player.
Choose the correct answer from the options given below:
A) Minimax search is breadth-first; it processes all the nodes at a level before moving to a node in the next level.
B) The effectiveness of the alpha-beta pruning is highly dependent on the order in which the states are examined.
C) The alpha-beta search algorithm computes the same optimal moves as the minimax algorithm.
D) Optimal play in games of imperfect information does not require reasoning about the current and future belief states of each player.
Choose the correct answer from the options given below:
| (A) and (C) only | |
| (A) and (D) only | |
| (B) and (C) only | |
| (C) and (D) only |
Question 35 Explanation:
Minimax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario.
Optimal decision in deterministic, perfect information games
Idea : choose the move resulting in the highest minimax value
Completeness: Yes if the tree is finite
Optimality: Yes, against an optimal opponent.
Time Complexity: O(bm)
Space Complexity: O(bm) – depth first exploration.
Hence Statement (A) is true.
Statement (B):
Alpha Bound of J:
→ The max current The max current val of all MAX ancestors of J of all MAX ancestors of J
→ Exploration of a min node, J, Exploration of a min node, J, is stopped when its value is stopped when its value equals or falls below alpha. equals or falls below alpha.
→ In a min node, we n node, we update beta update beta
Beta Bound of J:
→ The min current The min current val of all MIN ancestors of J of all MIN ancestors of J
→ Exploration of a Exploration of a max node, J ax node, J, is stopped when its stopped when its value equals or exceeds beta equals or exceeds beta
→ In a max node, we update a ax node, we update alpha
Pruning does not affect the final result
Does ordering affect the pruning process?
Best case O(bm/2)
Random (instead of best first search) – O(b3m/4)
Hence statement (B) is false.
Statement C: This statement is true.
Statement D: This statement is false because past exploration information is used from transposition tables.
Optimal decision in deterministic, perfect information games
Idea : choose the move resulting in the highest minimax value
Completeness: Yes if the tree is finite
Optimality: Yes, against an optimal opponent.
Time Complexity: O(bm)
Space Complexity: O(bm) – depth first exploration.
Hence Statement (A) is true.
Statement (B):
Alpha Bound of J:
→ The max current The max current val of all MAX ancestors of J of all MAX ancestors of J
→ Exploration of a min node, J, Exploration of a min node, J, is stopped when its value is stopped when its value equals or falls below alpha. equals or falls below alpha.
→ In a min node, we n node, we update beta update beta
Beta Bound of J:
→ The min current The min current val of all MIN ancestors of J of all MIN ancestors of J
→ Exploration of a Exploration of a max node, J ax node, J, is stopped when its stopped when its value equals or exceeds beta equals or exceeds beta
→ In a max node, we update a ax node, we update alpha
Pruning does not affect the final result
Does ordering affect the pruning process?
Best case O(bm/2)
Random (instead of best first search) – O(b3m/4)
Hence statement (B) is false.
Statement C: This statement is true.
Statement D: This statement is false because past exploration information is used from transposition tables.
Correct Answer: C
Question 35 Explanation:
Minimax is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario.
Optimal decision in deterministic, perfect information games
Idea : choose the move resulting in the highest minimax value
Completeness: Yes if the tree is finite
Optimality: Yes, against an optimal opponent.
Time Complexity: O(bm)
Space Complexity: O(bm) – depth first exploration.
Hence Statement (A) is true.
Statement (B):
Alpha Bound of J:
→ The max current The max current val of all MAX ancestors of J of all MAX ancestors of J
→ Exploration of a min node, J, Exploration of a min node, J, is stopped when its value is stopped when its value equals or falls below alpha. equals or falls below alpha.
→ In a min node, we n node, we update beta update beta
Beta Bound of J:
→ The min current The min current val of all MIN ancestors of J of all MIN ancestors of J
→ Exploration of a Exploration of a max node, J ax node, J, is stopped when its stopped when its value equals or exceeds beta equals or exceeds beta
→ In a max node, we update a ax node, we update alpha
Pruning does not affect the final result
Does ordering affect the pruning process?
Best case O(bm/2)
Random (instead of best first search) – O(b3m/4)
Hence statement (B) is false.
Statement C: This statement is true.
Statement D: This statement is false because past exploration information is used from transposition tables.
Optimal decision in deterministic, perfect information games
Idea : choose the move resulting in the highest minimax value
Completeness: Yes if the tree is finite
Optimality: Yes, against an optimal opponent.
Time Complexity: O(bm)
Space Complexity: O(bm) – depth first exploration.
Hence Statement (A) is true.
Statement (B):
Alpha Bound of J:
→ The max current The max current val of all MAX ancestors of J of all MAX ancestors of J
→ Exploration of a min node, J, Exploration of a min node, J, is stopped when its value is stopped when its value equals or falls below alpha. equals or falls below alpha.
→ In a min node, we n node, we update beta update beta
Beta Bound of J:
→ The min current The min current val of all MIN ancestors of J of all MIN ancestors of J
→ Exploration of a Exploration of a max node, J ax node, J, is stopped when its stopped when its value equals or exceeds beta equals or exceeds beta
→ In a max node, we update a ax node, we update alpha
Pruning does not affect the final result
Does ordering affect the pruning process?
Best case O(bm/2)
Random (instead of best first search) – O(b3m/4)
Hence statement (B) is false.
Statement C: This statement is true.
Statement D: This statement is false because past exploration information is used from transposition tables.
Subscribe
Login
0 Comments