Quiz: Adversarial search and games

Question 1

Consider the following game tree, where one of the leaves has an unknown payoff, x. Player 1 moves first, and attempts to maximize the value of the game.

The next question asks you to select constraints on x specifying the set of values it can have. If x has no lower limit, select ‘None’ for that limit. If x has no possible values, select ‘None’. As an example, if you think x can take on all values larger than 16, you should enter x > 16.

Assume Player 2 is a minimizing agent (and Player 1 know this), calculate the range of values of x where is Player 1 guaranteed to choose Action 1. What is the lower limit, x>

1110None6751215981314

Question 2

Consider the following game tree, where one of the leaves has an unknown payoff, x. Player 1 moves first, and attempts to maximize the value of the game.

The next question asks you to select constraints on x specifying the set of values it can have. If x has no upper limit, select ‘None’ for that limit. If x has no possible values, select ‘None’. As an example, if you think x can take on all values larger than 16, you should enter x < None.

Assume Player 2 is a minimizing agent (and Player 1 know this), calculate the range of values of x where is Player 1 guaranteed to choose Action 1. What is the upper limit, x <

1110None6751215981314

Question 3

Consider the following game tree, where one of the leaves has an unknown payoff, x. Player 1 moves first, and attempts to maximize the value of the game.

The next question asks you to select constraints on x specifying the set of values it can have. If x has no lower limit, select ‘None’ for that limit. If x has no possible values, select ‘None’. As an example, if you think x can take on all values larger than 16, you should enter x > 16.

Assume Player 2 chooses actions at random with each action having equal probability (and Player 1 knows this). Calculate the range of values of x where is Player 1 guaranteed to choose Action 1. What is the lower limit, x >

1110None6751215981314

Question 4

Consider the following game tree, where one of the leaves has an unknown payoff, x. Player 1 moves first, and attempts to maximize the value of the game.

The next question asks you to select constraints on x specifying the set of values it can have. If x has no upper limit, select ‘None’ for that limit. If x has no possible values, select ‘None’. As an example, if you think x can take on all values larger than 16, you should enter x < None.

Assume Player 2 chooses actions at random with each action having equal probability (and Player 1 knows this). Calculate the range of values of x where is Player 1 guaranteed to choose Action 1. What is the upper limit, x <

1110None6751215981314

Question 5

Player MAX and player MIN are playing a zero-sum game with a finite number of possible moves. MAX calculates the minimax value of the root to be M. You may assume that at every turn, each player has at least 2 possible actions. You may also assume that a different sequence of moves will always lead to a different score (i.e., no two terminal nodes have the same score). Is the following statement True or False?

Assume MIN is playing sub-optimally at every turn, but MAX does not know this. The outcome of the game could be larger than M (i.e. better for MAX).

True

False

Question 6

Player MAX and player MIN are playing a zero-sum game with a finite number of possible moves. MAX calculates the minimax value of the root to be M. You may assume that at every turn, each player has at least 2 possible actions. You may also assume that a different sequence of moves will always lead to a different score (i.e., no two terminal nodes have the same score). Is the following statement True or False?

Assume MIN is playing sub-optimally at every turn. If MAX plays according to the minimax strategy, the outcome of the game could be less than M.

True

False

Question 7

Player MAX and player MIN are playing a zero-sum game with a finite number of possible moves. MAX calculates the minimax value of the root to be M. You may assume that at every turn, each player has at least 2 possible actions. You may also assume that a different sequence of moves will always lead to a different score (i.e., no two terminal nodes have the same score). Is the following statement True or False?

Assume MIN is playing sub-optimally at every turn. MAX following the minimax policy will guarantee a better outcome than M.

True

False

Question 8

Player MAX and player MIN are playing a zero-sum game with a finite number of possible moves. MAX calculates the minimax value of the root to be M. You may assume that at every turn, each player has at least 2 possible actions. You may also assume that a different sequence of moves will always lead to a different score (i.e., no two terminal nodes have the same score). Is the following statement True or False?

Assume MIN is playing sub-optimally at every turn, and MAX knows exactly how MIN will play. There exists a policy for MAX to guarantee a better outcome than M.

True

False

Question 9

Is the following statement True or False?

In a fully observable, turn-taking, zero-sum game between two perfectly rational players, it does not help the first player to know what strategy the second player is using - that is, what move the second player will make, given the first player’s move.

True

False

Question 10

Is the following statement True or False?

In a partially observable, turn-taking, zero-sum game between two perfectly rational players, it does not help the first player to know what move the second player will make, given the first player’s move.

True

False

Question 11

Is the following statement True or False?

When we use alpha-beta pruning, the trade-off is that we may obtain a suboptimal solution.

True

False

Question 12

Is the following statement True or False?

Using alpha-beta pruning does not affect the optimality of the solution.

True

False

Question 13

Is the following statement True or False?

The ordering of nodes on the same level of the tree does not affect the runtime of the algorithm.

True

False

Question 14

Is the following statement True or False?

Alpha-beta pruning uses recursion to send back up min, max, alpha, and beta values from leaf nodes.

True

False

Question 15

Is the following statement True or False?

For every game tree, the utility obtained by MAX using minimax decisions against a suboptimal MIN will be never be lower than the utility obtained playing against an optimal MIN.

True

False

Question 16

Is the following statement True or False?

There could exist a game tree in which MAX can do even by better using a suboptimal strategy against a suboptimal MIN.

True

False

Question 17

This problem exercises the basic concepts of game playing, using tic-tac-toe as an example. We define X _n as the number of rows, columns, or diagonals with exactly n X’s and no O’s. Similarly, O _n is the number of rows, columns, or diagonals with just n O’s. The utility function assigns +1 to any position with X ₃ = 1 and −1 to any position with O ₃ = 1. All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as Eval(s)=3X ₂ (s)+X ₁ (s)−(3O ₂ (s)+O ₁ (s)).

Shown above is the whole game tree starting from an empty board down to depth 2 (i.e. one X and one O on the board), taking symmetry into account. Evaluations of some of the positions at depth 2 are marked. What are the values of evaluations at W, Y, and Z?

2-1, 1, -101, 0, -2-10, 1, 111, 2, 01, 1, -1-1, 1, -2-1, 0, 12, 1, 0

Question 18

This problem exercises the basic concepts of game playing, using tic-tac-toe as an example. We define X _n as the number of rows, columns, or diagonals with exactly n X’s and no O’s. Similarly, O _n is the number of rows, columns, or diagonals with just n O’s. The utility function assigns +1 to any position with X ₃ = 1 and −1 to any position with O ₃ = 1. All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as Eval(s)=3X ₂ (s)+X ₁ (s)−(3O ₂ (s)+O ₁ (s)).

Using the minimax algorithm, what are the backed-up values for the positions at depths 1, indicated by variables A, B, and C?

2-1, 1, -101, 0, -2-10, 1, 111, 2, 01, 1, -1-1, 1, -2-1, 0, 12, 1, 0

Question 19

This problem exercises the basic concepts of game playing, using tic-tac-toe as an example. We define X _n as the number of rows, columns, or diagonals with exactly n X’s and no O’s. Similarly, O _n is the number of rows, columns, or diagonals with just n O’s. The utility function assigns +1 to any position with X ₃ = 1 and −1 to any position with O ₃ = 1. All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as Eval(s)=3X ₂ (s)+X ₁ (s)−(3O ₂ (s)+O ₁ (s)).

What is the value of the root node, indicated by R?

2-1, 1, -101, 0, -2-10, 1, 111, 2, 01, 1, -1-1, 1, -2-1, 0, 12, 1, 0

Question 20

For the following situation, should one use adversarial search?

A zero-sum game with one or more opponents.

Yes

No

Question 21

For the following situation, should one use adversarial search?

Finding the right classification for a group of images.

Yes

No

Question 22

For the following situation, should one use adversarial search?

A single-player puzzle game, such as Sudoku.

Yes

No

Question 23

For the following situation, should one use adversarial search?

Playing chess against oneself.

Yes

No

Question 24

Why is depth-limited minimax sometimes preferable to minimax without a depth limit?

Depth-limited minimax will achieve the same output as minimax without a depth limit, but can sometimes use less memory.

Depth-limited minimax is never preferable to minimax without a depth limit.

Depth-limited minimax can make a more optimal decision by not exploring states known to be suboptimal.

Depth-limited minimax can arrive at a decision more quickly because it explores fewer states.

Question 25

The minimax algorithm implements an adaptation of the

Uniform cost search

BFS

DFS

Question 26

Consider the Minimax tree above, where the green up arrows indicate the MAX player and red down arrows indicate the MIN player. The leaf nodes are each labeled with their value. What is the value of the root node?

Posting submission...