________ is used in game trees to reduce the number of branches of the search…

Answer: Alpha-beta pruning procedure

What it does: Alpha-beta pruning reduces the number of branches searched in a minimax game tree by skipping entire subtrees that cannot affect the final minimax decision, while preserving the exact minimax value.

• It maintains two bounds: alpha (the best value found so far for the maximizer) and beta (the best for the minimizer).

• Traverse the tree depth-first and update alpha and beta as child values are discovered.

• When at any point alpha is greater than or equal to beta, the current branch can be pruned because it cannot influence the final decision.

Key properties:

• Correctness-preserving: pruning never changes the minimax result; it only avoids exploring irrelevant subtrees.

• Performance improvement: with good move ordering, alpha-beta can reduce the effective branching factor substantially (best-case complexity roughly decreases from O(b^d) to about O(b^(d/2))).

Why the other approaches are not correct:

• Best-first search is a heuristic search strategy for exploring graphs and trees, not a correctness-preserving pruning method for minimax game trees.

• Goal stack planning is a planning technique used in classical AI planning and is unrelated to pruning game-tree searches.

• Minimax search is the underlying algorithm that computes optimal play; alpha-beta is an enhancement to minimax that reduces the number of nodes evaluated.

Takeaway: Alpha-beta pruning is the standard technique used to reduce search effort in game trees without affecting the computed optimal move.