Search code examples
algorithmartificial-intelligencegraph-theoryminimaxalpha-beta-pruning

Is it necessary to have an optimal action at node R to prune a branch in alpha beta pruning?

Minimax tree

The image shows a tree where there is no optimal action at R. If the utility at the * branch is 8 or lower the best action at R would be to go left. If the utility of the star branch is 9 or greater, R would choose right and the min player would chose the left branch and not the * branch [min(9,*)]. Can we prune * in this case?

I think we can prune it even though there may be no optimal action. Our AI(max player) would never let things go in that branch.

Solution

  • You cannot prune that branch:

    At the top level node, the maximizing player R has two potential moves. If the first one (left) is played, the minimizing opponent can achieve a value of 8, and so the first player should assume 8 as value for the first move.

    The second possible move for the first player has two possible counter moves from the minimizing player. For the first of those the maximizing player can ensure a value of 9.

    But here is the issue: the maximizing player cannot assume that this is the move that the opponent will play. Maybe if the opponent plays the alternative (*) move, it will turn out that the value for the opponent is more interesting, and less than 8, like maybe 7. In that case the maximizing player should choose the left move, going for the 8 score, as they don't want to risk that the opponent goes for *, where the maximizing player would maybe have to be satisfied with a 7, while they were sure to get an 8 when going "left".

    If the utility of the star branch is 9 or greater, R would choose right...

    Either you follow a branch and get the end-node's utility, or you prune the branch. You cannot have it both ways. If you prune the branch, then you don't know the node's utility.

    Our AI(max player) would never let things go in that branch.

    With pruning *, your decision for R would only depend on the scores you know, and thus you would go right in that case (going for the 9), which is not always the right decision, as now the opponent has control and can move into the * node. There is no way the AI can prevent going in that branch if it considers the second move as an option. It can only prevent it by not considering its second move at all.