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.

Q: Does alpha beta pruning change the value returned by minimax?

Alpha beta prunes only branches proved irrelevant, so the value and the chosen move are identical to those a full minimax search would return. It changes only the effort. That distinguishes it sharply from forward pruning techniques, which discard branches on suspicion and do change the result. A technique that is free in the sense of costing nothing in quality deserves to be used always, which is exactly the status alpha beta has.

Q: Alpha beta with perfect ordering reduces the effective branching factor to \( \sqrt{b} \). What is it for b = 36?

Taking the square root of the branching factor gives:\[ \sqrt{36} = 6 \]so the effective branching factor falls to 6, which means the same effort searches twice the depth. For chess, with about thirty five legal moves, that is the difference between a weak program and a strong one. Halving the exponent is a far larger gain than any constant factor, which is why move ordering receives so much attention.

Q: What determines how much alpha beta actually prunes?

Examining the best move first establishes a strong bound immediately and allows everything else to be cut, while examining the worst first prunes nothing at all. Perfect ordering gives the square root improvement and random ordering gives roughly the three quarters power. Depth, evaluation quality and move count matter but do not control the pruning. That an algorithm's benefit depends entirely on a heuristic choice made outside it is unusual and it makes move ordering a first class concern.

Q: What is a killer move heuristic?

A move that produced a cutoff in a sibling position is likely to do so again, so trying it early improves the ordering cheaply. Capture ordering and the history heuristic serve the same purpose by different means. Abandoning lines and shortest wins are different ideas. Reusing information gathered elsewhere in the tree, at almost no cost, is characteristic of the practical machinery that turns a textbook algorithm into a competitive program.

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

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

Does alpha beta pruning change the value returned by minimax?

A.Yes, it returns an approximation to the true value
B.Only when the move ordering is poor
C.No, it returns exactly the same value
D.Yes, it may return a slightly worse move

Answer: C

Alpha beta prunes only branches proved irrelevant, so the value and the chosen move are identical to those a full minimax search would return. It changes only the effort. That distinguishes it sharply from forward pruning techniques, which discard branches on suspicion and do change the result. A technique that is free in the sense of costing nothing in quality deserves to be used always, which is exactly the status alpha beta has.

Discuss in Forum

Alpha beta with perfect ordering reduces the effective branching factor to \( \sqrt{b} \). What is it for b = 36?

A.18
B.36
C.1296
D.6

Answer: D

Taking the square root of the branching factor gives:

\[ \sqrt{36} = 6 \]

so the effective branching factor falls to 6, which means the same effort searches twice the depth. For chess, with about thirty five legal moves, that is the difference between a weak program and a strong one. Halving the exponent is a far larger gain than any constant factor, which is why move ordering receives so much attention.

Discuss in Forum

What determines how much alpha beta actually prunes?

A.The order in which moves are examined at each node
B.The depth to which the search is permitted to run
C.The accuracy of the evaluation function at the leaves
D.The total number of legal moves in the position

Answer: A

Examining the best move first establishes a strong bound immediately and allows everything else to be cut, while examining the worst first prunes nothing at all. Perfect ordering gives the square root improvement and random ordering gives roughly the three quarters power. Depth, evaluation quality and move count matter but do not control the pruning. That an algorithm's benefit depends entirely on a heuristic choice made outside it is unusual and it makes move ordering a first class concern.

Discuss in Forum

10.

What is a killer move heuristic?

A.Selecting the move that ends the game most quickly
B.Trying moves that caused cutoffs elsewhere at the same depth first
C.Searching moves that capture material before quiet moves
D.Abandoning a line as soon as one player is clearly winning

Answer: B

A move that produced a cutoff in a sibling position is likely to do so again, so trying it early improves the ordering cheaply. Capture ordering and the history heuristic serve the same purpose by different means. Abandoning lines and shortest wins are different ideas. Reusing information gathered elsewhere in the tree, at almost no cost, is characteristic of the practical machinery that turns a textbook algorithm into a competitive program.

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