Alpha beta pruning Python code: keep cutoff returns labeled as bounds

A pruning trace returns 3 for a branch whose full minimum is -20. The root still chooses correctly, but calling that return exact misrepresents what the traversal established.

Keep the bound label beside every skipped leaf.

The example computes the same root choice with two different visit traces. A MAX root has MIN children A=[4,7], B=[3,-20], and C=[6,5]. Full minimax visits six leaves and chooses C/5. Pruning in A,B,C order visits five; C,B,A visits four. The browser calculation is an original JavaScript trace aid, with the Python-shaped algorithm described separately rather than presented as a Python run.

A cutoff return is not an exact minimum.
A cutoff return is not an exact minimum.
Open the full example ↗

Establish the full baseline

Use stable leaf IDs A1,A2,B1,B2,C1,C2. The exact branch minima are A=4, B=-20, C=5, so max(4,-20,5)=5. All utilities are supplied terminal values, not heuristic estimates for a real game. Keep the baseline exact values separate from what pruning discovers. A view that knows every fixture value must not silently place an unvisited value into the pruning observation column just because another calculation exposed it.

In A,B,C order, visit A1=4 then A2=7, establishing exact A=4 and root alpha=4. B1=3 makes B's eventual minimum at most three. B therefore cannot improve the root incumbent, so skip B2. The returned three is an upper bound, not exact B=-20. Continue through C1=6 and C2=5 to establish exact C=5. The visited sequence is 4,7,3,6,5; the skipped ID is B2. Leaf count describes this traversal, not an elapsed-time benchmark.

Reorder without changing the utility tree

With C,B,A order, C establishes root incumbent five. B1=3 cuts B2, and A1=4 cuts A2. The visited sequence becomes 6,5,3,4. C still wins with five. A's return happens to equal its full minimum, but the pruned traversal did not visit A2, so its status is still upper bound. A coincidental equality with baseline knowledge cannot replace the evidence needed to mark that subtree exact.

For a bounded Python implementation, iterate explicit ordered branch lists. At each MIN branch initialize beta to positive infinity, append each leaf ID/value to visited, and update beta with min. Cut when beta is at most alpha and unvisited leaves remain. Record those IDs as skipped. If the list was fully examined, record exact. At the root update choice only when the returned value is strictly greater than alpha, giving the first-in-order policy for ties. This shallow fixture is not an arbitrary-depth game evaluator.

Validate before accepting a trace

The editable tree requires a nonempty list of named branches, nonempty finite-number leaf lists, and unique branch names. Invalid input is held instead of converted to zero. The page calculates both baseline and pruning from current values, so editing the tree clears the old result. In native Python tests, retain source revision, interpreter, input order, root result, visited/skipped IDs, and return statuses. A root-only test would miss the misleading exact-value label that motivated this task.

Finish by checking root agreement and trace honesty together. This tree has a unique optimal branch, so both orders select C. An arbitrary tied tree can choose another equally optimal action under the declared first-in-order rule; do not generalize this fixture into order-invariant actions or universal speedups. Keep the actual Python source and tests authoritative when you port the same bounded algorithm, and preserve each trace under the exact utilities and order that produced it.

Make your own working example

Build an original finite-tree pruning trace aid. MAX root has ordered MIN branches A:[4,7], B:[3,-20], C:[6,5], with stable leaf IDs formed from branch name and one-based leaf number. Provide editable JSON branches, Trace A/B/C, Reverse branch order, and Reset. This is JavaScript calculation, not Python execution or a real game.

Calculate full minimax over every leaf, then a pruning traversal using root alpha and each MIN branch beta. Cut only when beta<=alpha and leaves remain. Label complete branches exact; label cutoff returns upper_bound and list skipped IDs. Root updates strictly on improvement for a first-in-order tie policy.

Default order visits 4,7,3,6,5, skips B2, root C/5; B return 3 is an upper bound, not exact -20. Reverse C,B,A visits 6,5,3,4 and skips B2,A2, still C/5. Show baseline branch minima separately. Reject empty branches, duplicate branch names and nonfinite/nonnumeric utilities. Edits invalidate feedback. Include concise Python-port instructions, without claiming arbitrary-depth support, benchmark speed, or native tests.

Use one self-contained HTML file with no remote dependency. Keep the initial sample, output, and labeled controls near the top. Use at least 16px text, strong contrast, visible focus, and a stacked layout at 360px without horizontal overflow. Use explicit type=button click handlers and explicit DOM selectors; do not depend on native form submission. Clear stale feedback when task inputs change. Render entered text safely. Keep practice data local to the current page; do not imply saving, sending, or production integration. Return only the finished HTML.

Explain the cutoff in the review copy

Keep the native Python source and actual trace tests together. In NOS, eligible static explanatory text can be revised visually without asking AI to regenerate the HTML. Use that to clarify why B's displayed return is a bound; the computed trace remains tied to the current tree.

Keep reading