1. A game can be formally defined as a kind of search problem with the following components.
a) Initial State
b) Successor Function
c) Terminal Test
d) All of the mentioned
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, lose, or draw, with values +1, -1, or 0..
2. The initial state and the legal moves for each side define the __________ for the game.
a) Search Tree
b) Game Tree
c) State Space Search
d) Forest
Explanation: An example of game tree for Tic-Tac-Toe game.
3. General algorithm applied on game tree for making decision of win/lose is ____________
a) DFS/BFS Search Algorithms
b) Heuristic Search Algorithms
c) Greedy Search Algorithms
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.
4. The minimax algorithm computes the minimax decision from the current state. It uses a simple recursive computation of the minimax values of each successor state, directly implementing the defining equations. The recursion proceeds all the way down to the leaves of the tree, and then the minimax values are backed up through the tree as the recursion unwinds.
a) true
b) false
Explanation: true
5. What is the complexity of minimax algorithm?
a) Same as of DFS
b) Space – bm and time – bm
c) Time – bm and space – bm
d) Same as BFS
Explanation: Same as DFS.
6. 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
Explanation: The alpha-beta search computes the same optimal moves as minimax, but eliminates the branches that can’t influence the final decision.
7. Which values are independant in minimax search algorithm?
a) Pruned leaves x and y
b) Every states are dependant
c) Root is independant
d) None of the mentioned
Explanation: The minimax decision are independant of the values of the pruned values x and y because of the root values.
8. To which depth does the alpha-beta pruning can be applied?
a) 10 states
b) 8 States
c) 6 States
d) Any depth
Explanation: Alpha–beta pruning can be applied to trees of any depth and it is possible to prune entire subtree rather than leaves.
9. Which search is similar to minimax search?
a) Hill-climbing search
b) Depth-first search
c) Breadth-first search
d) All of the mentioned
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.
10. Which value is assigned to alpha and beta in the alpha-beta pruning?
a) Alpha = max
b) Beta = min
c) Beta = max
d) Both Alpha = max & Beta = min
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.