## 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.

**D.**For a MAX node, it backs up the maximum of the values of the children.

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.

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:**

Fundamentals of Artificial Intelligence Quiz 1