This course has already ended.

Quiz: Adversarial search and games

../_images/minimax_q6.png

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>

../_images/minimax_q6.png

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 <

../_images/minimax_q6.png

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 >

../_images/minimax_q6.png

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 <

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.

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.

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.

../_images/tictactoe.png

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?

../_images/tictactoe.png

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?

../_images/tictactoe.png

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.

Why is depth-limited minimax sometimes preferable to minimax without a depth limit?
The minimax algorithm implements an adaptation of the
../_images/minimax_q5.png

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