Fundamentals of Artificial Intelligence Quiz 2
For more complex games, such as chess or checker the AND/OR search to termination is out of question. Which of the following statements are true?
I. Our goal in searching such a game tree might be, instead, merely to find a good first move.
II. Extract from the search graph an estimate of the ‘best’ first move.
I. Our goal in searching such a game tree might be, instead, merely to find a good first move.
II. Extract from the search graph an estimate of the ‘best’ first move.
Both statement I and II are true.
The AO* algorithm can best be seen as the following TWO major operations:
1. Top-down: graph-growing; 2. Bottom-up: cost-revising, SOLVE-labelling.
For a game tree: Each node has b children and a d-ply look ahead is performed. What is the number of leaf nodes to be examined?
For a game tree where each node has 𝑏 b children and a 𝑑 d-ply lookahead is performed, the number of leaf nodes that need to be examined is given by:
b^d
b^d
For complex games such as chess or checkers, a good first move can be extracted by a procedure called the Minimax. The minimax value is the backed-up value of the root from all the leaves. Identify the correct statements w.r.t the minimax for such a game tree.
A. The minimax rule backs up values from the children of a node; given a static evaluation function for the tip nodes.
B. Represents the outcome when both the players play perfectly.
C. Backed-up values identify the best move for each player.
B. Represents the outcome when both the players play perfectly.
C. Backed-up values identify the best move for each player.
Alpha-beta pruning is a layering on top of minimax. Identify the correct statements w.r.t alpha-beta pruning.
A. Alpha-beta pruning is an optimization technique for minimax algorithm.
B. Alpha-beta pruning cuts off branches in the game tree which need not be searched because there already exists a better move available.
C. Alpha-beta pruning is guaranteed to compute the same value for the root node as computed by minimax.
D. For alpha-beta pruning one traverses the search tree in depth-first order.
B. Alpha-beta pruning cuts off branches in the game tree which need not be searched because there already exists a better move available.
C. Alpha-beta pruning is guaranteed to compute the same value for the root node as computed by minimax.
D. For alpha-beta pruning one traverses the search tree in depth-first order.
For solutions in an AND-OR graph, which of the following statements are true.
A. Need an algorithm similar to best-first search; but with the ability to handle the AND arc appropriately.
B. AO* algorithm use a single structure – a graph – representing part of the search graph.
C. At least one arm of an AND arc must lead to a solution node.
D. A solution graph of an AND-OR graph is analogous to a path in an ordinary graph.
A. Need an algorithm similar to best-first search; but with the ability to handle the AND arc appropriately.
B. AO* algorithm use a single structure – a graph – representing part of the search graph.
C. At least one arm of an AND arc must lead to a solution node.
D. A solution graph of an AND-OR graph is analogous to a path in an ordinary graph.
A. Need an algorithm similar to best-first search; but with the ability to handle the AND arc appropriately.
B. AO* algorithm use a single structure – a graph – representing part of the search graph.
D. A solution graph of an AND-OR graph is analogous to a path in an ordinary graph.
B. AO* algorithm use a single structure – a graph – representing part of the search graph.
D. A solution graph of an AND-OR graph is analogous to a path in an ordinary graph.
Alpha-beta pruning had been reinvented a number of times! The earliest version was by _______________ for a checkers simulation.
Arthur Samuel
Give one word or a phrase for: A mathematical representation of a situation in which each participant’s gain or loss of utility is exactly balanced by the losses or gains of utility of the other participants.
Zero-sum Game
Solving a constraint satisfaction problem on a finite domain is an/a ___________ problem with respect to the domain size.
NP complete
____________ is a backtracking algorithm for CSP that is aware of the underlying constraint graph; determines where to jump back to, based on the actual conflict that it has recorded.
Conflict-directed Backjumping
Also Available:
