Q 1. Two players, the MAX and the MIN are playing a game where there are only two possible actions, “left” and “right”. The search tree for the game is shown in Figure 1. The leaf/terminals nodes, which are all at depth 4, contain the evaluation function at the corresponding state of the game. The MAX player is trying to maximize this evaluation function, while the MIN player is trying to minimize this evaluation function. a. Consider the operation of the Minimax algorithm over the above search tree and indicate the value of each intermediate node. b. Consider the operation of the Minimax algorithm with alpha-beta pruning over the above search tree. Indicate which nodes will not be considering by this algorithm. Furthermore, indicate the alpha and beta values on each intermediate node that is visited. c. What action will the MAX player choose at the root state according to the exhaustive Minimax algorithm? What action will the MAX player choose at the root state according to the Minimax algorithm employing alpha-beta pruning? In general, is the best move computed by the two versions of the algorithm guaranteed to be the same or not?
Q 1. Two players, the MAX and the MIN are playing a game where there are only two possible
actions, “left” and “right”. The search tree for the game is shown in Figure 1. The leaf/terminals
nodes, which are all at depth 4, contain the evaluation function at the corresponding state of
the game. The MAX player is trying to maximize this evaluation function, while the MIN player
is trying to minimize this evaluation function.
a. Consider the operation of the Minimax
indicate the value of each intermediate node.
b. Consider the operation of the Minimax algorithm with alpha-beta pruning over the
above search tree. Indicate which nodes will not be considering by this algorithm.
Furthermore, indicate the alpha and beta values on each intermediate node that is
visited.
c. What action will the MAX player choose at the root state according to the exhaustive
Minimax algorithm? What action will the MAX player choose at the root state according
to the Minimax algorithm employing alpha-beta pruning? In general, is the best move
computed by the two versions of the algorithm guaranteed to be the same or not?
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
