Adversarial Search and Games Questions and Answers

Q: What is a ply in game tree terminology?

A ply is a single player's move, so what a chess player calls a move is two plies, and search depths are always quoted in plies to avoid the ambiguity. Full moves, cutoff depth and complete lines are different notions. Precision here matters because a program searching ten plies is looking five moves ahead in the everyday sense, and confusing the two doubles or halves every estimate of a program's strength.

Q: What is the minimax value of a position?

The minimax value is computed by backing up terminal utilities, with each player choosing the successor best for themselves, so it presumes optimal play by both sides. Against a weak opponent a different move might score better, but minimax guarantees the value against any opponent. Averaging belongs to expectimax, direct evaluation is the leaf estimate, and luck belongs to games of chance. A value defined by an assumption is only as useful as the assumption, which is why the assumption is stated explicitly.

Q: Why does minimax assume optimal opponent play?

Assuming the strongest reply gives a lower bound on what the player can achieve, so the move chosen is safe whatever the opponent does. Modelling a weaker opponent could score more against that opponent and worse against a better one. Ease of computation is not the argument, real opponents err constantly, and pruning is a separate technique. Choosing a criterion that is robust to the opponent's behaviour, rather than optimal against a guess about it, is a defensible conservative choice.

Q: What is a zero sum game?

In a zero sum game the utilities of the two players always add to a constant, so a single number describes the position from both points of view and minimax applies directly. Chess, draughts and go are of this kind. Zero payoffs, forced draws and move counts are different properties. Games that are not zero sum admit cooperation and require a payoff for each player, which changes the algorithms substantially and is why the restriction is stated.

Q: What does alpha represent in alpha beta pruning?

Alpha is a lower bound on the value the maximiser has already secured elsewhere in the tree, and beta is the corresponding upper bound for the minimiser. When a node's value is shown to fall outside the window between them, further exploration of it cannot affect the result and is abandoned. Depth and current evaluation are different quantities. Two bounds carried down the tree, and used to prove that a subtree cannot matter, is the whole of the technique.

Q: When does alpha beta pruning cut off a branch?

A branch is abandoned as soon as it is proved that the value at the root is already determined regardless of what the branch contains, which happens when a minimiser finds a value at or below alpha, or a maximiser one at or above beta. Low evaluations, depth limits and equal values are unrelated conditions. Pruning that is provably safe, changing the search's cost but not its result, is a different and stronger thing than pruning by heuristic judgement.

The strategy used to reduce the number of tree branches and the number of static evaluations applied in case of a game tree is

A.Minmax strategy
B.Alpha-beta pruning strategy
C.Constraint satisfaction strategy
D.Static max strategy

Exam Year(s)

UGC NET - 2012,

Answer: B

Alpha-beta pruning is the strategy that cuts off branches of a game tree that cannot affect the final decision, so it reduces the number of branches searched and the number of static evaluations made, while giving the same result as minimax. Minimax by itself examines the whole tree to the chosen depth, constraint satisfaction is a different problem-solving technique, and 'static max' is not a standard strategy. The answer is Alpha-beta pruning strategy, option (B).

Discuss in Forum

In alpha-beta pruning, _________ is used to cut off the search at maximizing level only and _________ is used to cut off the search at minimizing level only.

A.alpha, beta
B.beta, alpha
C.alpha, alpha
D.beta, beta

Exam Year(s)

UGC NET - 2013,

Answer: B

In alpha-beta pruning, beta is used to cut off the search at the maximizing level only, and alpha is used to cut off the search at the minimizing level only. A maximizing node can be pruned when its value reaches or exceeds beta, the best the minimizer can already get higher up. A minimizing node can be pruned when its value falls to or below alpha.

Therefore the order beta, alpha is right, and the other three combinations are incorrect.

Discuss in Forum

α - β cutoffs are applied to ______

A.Depth first search
B.Best first search
C.Minimax search
D.Breadth first search

Exam Year(s)

UGC NET - 2013,

Answer: C

Alpha-beta cutoffs are applied to Minimax search. Alpha-beta pruning keeps the best values found so far for the maximising and minimising players and stops exploring a branch that cannot change the minimax value, so it gives the same result with fewer nodes.

Depth first, best first and breadth first search are uninformed or heuristic search methods over a graph and have no max and min players, so there is nothing to prune with an alpha and a beta value. Alpha-beta cutoffs belong to two-player game trees, which is minimax search.

Discuss in Forum

________ is used in game trees to reduce the number of branches of the search tree to be traversed without affecting the solution.

A.Best first search
B.Goal stack planning
C.Alpha-beta pruning procedure
D.Min-max search

Exam Year(s)

UGC NET - 2014,

Answer: C

Alpha-beta pruning reduces the branches of a game tree without affecting the solution.

It cuts off branches that cannot influence the minimax decision, and so it returns the same value as plain min-max with fewer nodes examined.

Min-max search examines the whole tree, best first search and goal stack planning are not pruning methods for game trees. Alpha-beta pruning keeps two values, alpha as the best already found for the maximiser and beta for the minimiser, and cuts off a branch when alpha is at least beta. The value at the root is not changed, which is why the solution is not affected.

Discuss in Forum

What is a ply in game tree terminology?

A.One move by one player
B.A complete move by both players in turn
C.The depth at which the evaluation function is applied
D.A branch of the game tree from root to leaf

Answer: A

A ply is a single player's move, so what a chess player calls a move is two plies, and search depths are always quoted in plies to avoid the ambiguity. Full moves, cutoff depth and complete lines are different notions. Precision here matters because a program searching ten plies is looking five moves ahead in the everyday sense, and confusing the two doubles or halves every estimate of a program's strength.

Discuss in Forum

What is the minimax value of a position?

A.The best value the player to move could possibly obtain by luck
B.Its value assuming both players play optimally thereafter
C.The average value of all positions reachable from it
D.The value assigned by the evaluation function directly

Answer: B

The minimax value is computed by backing up terminal utilities, with each player choosing the successor best for themselves, so it presumes optimal play by both sides. Against a weak opponent a different move might score better, but minimax guarantees the value against any opponent. Averaging belongs to expectimax, direct evaluation is the leaf estimate, and luck belongs to games of chance. A value defined by an assumption is only as useful as the assumption, which is why the assumption is stated explicitly.

Discuss in Forum

Why does minimax assume optimal opponent play?

A.Opponents in practice always play optimally
B.The assumption is required for alpha beta pruning to work
C.It guarantees the value achieved against any opponent
D.Optimal play is easier to compute than realistic play

Answer: C

Assuming the strongest reply gives a lower bound on what the player can achieve, so the move chosen is safe whatever the opponent does. Modelling a weaker opponent could score more against that opponent and worse against a better one. Ease of computation is not the argument, real opponents err constantly, and pruning is a separate technique. Choosing a criterion that is robust to the opponent's behaviour, rather than optimal against a guess about it, is a defensible conservative choice.

Discuss in Forum

What is a zero sum game?

A.Both players receive a payoff of zero at the end
B.The game always ends in a draw with optimal play
C.The sum of the moves available to both players is fixed
D.One player's gain is exactly the other's loss

Answer: D

In a zero sum game the utilities of the two players always add to a constant, so a single number describes the position from both points of view and minimax applies directly. Chess, draughts and go are of this kind. Zero payoffs, forced draws and move counts are different properties. Games that are not zero sum admit cooperation and require a payoff for each player, which changes the algorithms substantially and is why the restriction is stated.

Discuss in Forum

What does alpha represent in alpha beta pruning?

A.The best value the maximising player can guarantee so far
B.The best value the minimising player can guarantee so far
C.The depth at which the search will be cut off
D.The evaluation of the position currently being examined

Answer: A

Alpha is a lower bound on the value the maximiser has already secured elsewhere in the tree, and beta is the corresponding upper bound for the minimiser. When a node's value is shown to fall outside the window between them, further exploration of it cannot affect the result and is abandoned. Depth and current evaluation are different quantities. Two bounds carried down the tree, and used to prove that a subtree cannot matter, is the whole of the technique.

Discuss in Forum

10.

When does alpha beta pruning cut off a branch?

A.When both players have the same value at a node
B.When a node's value cannot affect the value at the root
C.When the evaluation function returns a very low value
D.When the search has reached its maximum permitted depth

Answer: B

A branch is abandoned as soon as it is proved that the value at the root is already determined regardless of what the branch contains, which happens when a minimiser finds a value at or below alpha, or a maximiser one at or above beta. Low evaluations, depth limits and equal values are unrelated conditions. Pruning that is provably safe, changing the search's cost but not its result, is a different and stronger thing than pruning by heuristic judgement.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Adversarial Search and Games Questions and Answers || Adversarial Search and Games MCQ Questions and Answers || Adversarial Search and Games GK Questions and Answers || Adversarial Search and Games GK MCQ Questions || Adversarial Search and Games Multiple Choice Questions and Answers || Adversarial Search and Games GK || GK on Adversarial Search and Games || Artificial Intelligence Questions and Answers || Artificial Intelligence MCQ Questions and Answers || Artificial Intelligence GK Questions and Answers || GK on Artificial Intelligence

Adversarial Search and Games Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications