a) Initial State

b) Successor Function

c) Terminal Test

d) Utility Function

Explanation: The initial state includes the board position and identifies the player to move. A successor function returns a list of (move, state) pairs, each indicating a legal move and the resulting state. A terminal test determines when the game is over. States where the game has ended are called terminal states. A utility function (also called an objective function or payoff function), which gives a numeric value for the terminal states. In chess, the outcome is a win, loss, or draw, with values +1, -1, or 0.

d) MIN/MAX Algorithms

Explanation: Given a game tree, the optimal strategy can be determined by examining the min/max value of each node, which we write as MINIMAX- VALUE(n). The min/max value of a node is the utility (for MAX) of being in the corresponding state, assuming that both players play optimally from there to the end of the game. Obviously, the min/max value of a terminal state is just its utility. Furthermore, given a choice, MAX will prefer to move to a state of maximum value, whereas MIN prefers a state of minimum value.

c) Alpha-beta pruning

Explanation: The alpha-beta search computes the same optimal moves as minimax, but eliminates the branches that can't influence the final decision.

a) Pruned leaves x and y

Explanation: The minimax decision are independent of the values of the pruned values x and y because of the root values.

d) Both a & b

Explanation: Alpha and beta are the values of the best choice we have found so far at any choice point along the path for MAX and MIN.

d) Any depth

Explanation: Alpha-beta pruning can be applied to trees of any depth and it is possible to prune entire sub-tree rather than leaves.

b) Depth-first search

Explanation: The minimax search is depth-first search, So at one time we just have to consider the nodes along a single path in the tree.

a) Along the path of search

Explanation: Alpha-beta search updates the value of alpha and beta as it gets along and prunes the remaining branches at node.

b) Hash table of previously seen positions

Explanation: Transposition is the occurrence of repeated states frequently in the search.

a) Evaluation function

Explanation: Because we need to cut the search off at some point and apply an evaluation function that gives an estimate of the utility of the state.