Suppose every terminal pair satisfies . At a B-node with immediate A-parent, let be the A-coordinate of a completed alternative already retained by the parent. If a completed B-child supplies B-coordinate , then every eventual B-selected pair has and hence . Therefore permits discarding this B-option and skipping its remaining children. Equality is also safe if the parent keeps its existing option on a tie.
The inequality remains valid at completed subtrees because max-n search copies one terminal pair. If the observed pair is , then , so and is a weaker sufficient test. At this reduces to the usual MIN-node alpha-beta pruning cutoff. A discarded option is not assigned a fabricated exact pair; the proof uses a certified alternative at the immediate parent.
Articles by others on the same topic
There are currently no matching articles.