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.
3. Which search is equal to minimax search but eliminates the branches that can't influence the final decision?
a) Depth-first search
b) Breadth-first search
c) Alpha-beta pruning
d) None of the mentioned
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.