Reputation: 68
Hey guys does anyone know how to solve this problem, it confuses me on how to get the answer, is there videos or anything that teaches you how to expand a tree.
Suppose you are playing a turn-taking, zero-sum game, where the opponent is a rational agent and you would like to use two-step look ahead to decide your move. You know that the complete min-max tree of the two-step look ahead strategy for this game will be a complete binary tree as shown in Figure 1 Suppose you are given access to a heuristic function that will give you a good estimate on the value of the leaf nodes of the complete tree (these estimated values are also written in Figure 1).
Relying on the given heuristic, how should the tree be expanded if we want to maximize the benefit of αβ-pruning? Please write the answer as a sequence of edges to be visited.
Answer given to me was: e1-e4-e10-e9-e3-e8-e2-e6-e13-e14
Upvotes: 2
Views: 347
Reputation: 28829
Alpha-beta pruning will eliminate the most branches from evaluation if the best child node (from the perspective of the first-person player at that level) is evaluated first, so e1 before e2 at depth 1 because e1 has the higher score, e4 before e3 because we are minimizing at that level, e10 before e9 (higher score), and so on.
Upvotes: 1