Consider game trees Tree-1 and Tree-2 as shown. The first level is a MAX agent and the second level is a MIN agent. The value in the square node is the output of the utility function.
For what ranges of $x$ and $y$, the right child of node $B$ and the right child of node $E$ will be pruned by alpha-beta pruning algorithm?
The problem involves alpha-beta pruning in a minimax game tree. Let's analyze the pruning for Tree-1 and Tree-2 based on the provided utility values.
Alpha-Beta Pruning Basics:
- Alpha represents the minimum score that the maximizing player is assured of.
- Beta represents the maximum score that the minimizing player is assured of.
- Nodes are pruned when alpha is greater than or equal to beta.
Tree 1 Analysis:
- At node A, the MAX agent chooses between 2 and B.
- Node B is a MIN node with children x and 1.
- Node B will choose the minimum of x and 1.
- A will choose the maximum of 2 and min(x,1).
- To prune the right child of B, the first child must be 1 (since it's a MIN node).
- Thus, prune if x ≤ 2 because A won't choose B over 2 if B ≥ 2.
Tree 2 Analysis:
- At node C, the MAX agent chooses between 5 and E.
- Node E is a MIN node with children y and the right child.
- Node E will choose the minimum of y and its right child.
- C will choose the maximum of 5 and min(y,right child).
- To prune the right child of E, first child y should be ≤ 5.
- Therefore, prune if y ≥ 2, because any value less than 5 will not influence beyond 5.
Conclusion:
- The right child of node B is pruned if x \leq 2.
- The right child of node E is pruned if y \geq 2.
Thus, the correct range that leads to pruning is x ∈ (-∞, 2] and y ∈ [2, ∞).
Important Questions from Adversarial Search
Consider the following statement: In adversarial search, $\alpha-\beta$ pruning can be applied to game trees of any depth where $\alpha$ is the (m) value choice we have formed so far at any choice point along the path for the MAX player and $\beta$ is the (n) value choice we have formed so far at any choice point along the path for the MIN player. Which ONE of the following choices of (m) and (n) makes the above statement valid?
Consider the game tree for a two-player turn-taking minimax game as shown in the figure. The value of a terminal node represents the utility of the game state if the game ends there. The numbers written next to the edges denote the strategies.
There are two players MAX and MIN. At any particular state of the game, MAX prefers to move to a state of maximum value. On the other hand, MIN prefers to move to a state of minimum value.
Suppose MAX starts the game at the root and has three strategies: 1, 2 and 3.
Next, MIN plays and also has three strategies: 1, 2 and 3. The game ends there.
Both players always take optimal strategies throughout the game.
At the root, the best strategy for MAX is ___________ . (Answer in integer)
