- DATA.ML.310
- 4. Adversarial Search and Constraint Satisfaction Problems
- 4.2 Quiz: Adversarial search and games

# Quiz: Adversarial search and games¶

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>

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 <

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 >

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 <

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).

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.

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.

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.

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.

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.

Is the following statement True or False?

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

Is the following statement True or False?

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

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.

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.

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.

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.

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 _{3} = 1 and −1 to any position with O _{3} = 1.
All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as
Eval(s)=3X _{2} (s)+X _{1} (s)−(3O _{2} (s)+O _{1} (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?

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 _{3} = 1 and −1 to any position with O _{3} = 1.
All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as
Eval(s)=3X _{2} (s)+X _{1} (s)−(3O _{2} (s)+O _{1} (s)).

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

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 _{3} = 1 and −1 to any position with O _{3} = 1.
All other terminal positions have utility 0. For nonterminal positions, we use a linear evaluation function defined as
Eval(s)=3X _{2} (s)+X _{1} (s)−(3O _{2} (s)+O _{1} (s)).

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

For the following situation, should one use adversarial search?

A zero-sum game with one or more opponents.

For the following situation, should one use adversarial search?

Finding the right classification for a group of images.

For the following situation, should one use adversarial search?

A single-player puzzle game, such as Sudoku.

For the following situation, should one use adversarial search?

Playing chess against oneself.

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?