More examples
作业Algorithm – 该题目是一个常规的Algorithm的练习题目代写, 涵盖了Algorithm等程序代做方面
- Pacman is going to play against a careless ghost, which makes a move that is optimal for Pacman 1/3 of the time, and makes a move that that minimizes Pacman’s utility the other 2/3 of the time. Fill in the correct utility values in the game tree below where Pacman is the maximizer.
Solution:
2.Describe how the minimax and alphabeta algorithms change for two- player, nonzero-sum games in which each player has a distinct utility function and both utility functions are known to both players. If there are no constraints on the two terminal utilities, is it possible for any node to be pruned by alphabeta?
Solution.
The minimax Algorithm for non-zero-sum games works exactly as for multiplayer games, that is, the evaluation function is a vector of values, one for each player, and the backup step selects whichever vector has the highest value for the player whose turn it is to move. The alpha-beta pruning is not possible in general non-zero sum games, because an unexamined leaf node might be optimal for both players.
- a) Let’s look at a non-zero sum version of a game. In this formulation, player A’s utility will be represented as the first of the two leaf numbers, and player B’s utility will be represented as the second of the two leaf numbers. Fill in this non-zero sum game tree assuming each player is acting optimally.
b)Which nodes can be pruned from the game tree above through alpha- beta pruning? If no nodes can be pruned, explain why not.
Solution.
a)
b)No nodes can be pruned. Because this game is non-zero sum, there can exist a leaf node anywhere in the tree that is good for both player A and player B.
4.True/False: Alpha-beta pruning can alter the computed minimax value of the root of a game search tree.
Solution.
False. Alpha-beta pruning only speeds up computation; it does not change the answer.
- a) Evaluate and fill the heuristic values for all the empty states in the game tree below. Assume that the minimax algorithm is being used, according to the labels on the right.
b)On the same diagram above, indicate which states will not be explored if alpha-beta pruning is used. Assume that the branches are explored from left to right.
Solution.