Repository navigation
Bug: Minimax crashes with RecursionError on non-power-of-2 input sizes #14886
Description
Description
backtracking/minimax.py uses math.log(len(scores), 2) to compute tree height, then checks depth == height as the base case. Since math.log returns a float, the comparison int == float never succeeds for non-power-of-2 input sizes, causing infinite recursion.
height = math.log(len(scores), 2) # e.g. math.log(6, 2) = 2.584...
# ...
if depth == height: # depth is int, height is float 2.584 -- NEVER TRUE
return scores[node_index]Reproduction
from minimax import minimax
import math
# Works (power of 2):
scores = [3, 5, 2, 9, 12, 5, 23, 23] # len=8
print(minimax(0, 0, True, scores, math.log(8, 2))) # OK: 12
# Crashes (non-power of 2):
scores = [3, 5, 2, 9, 12] # len=5
print(minimax(0, 0, True, scores, math.log(5, 2))) # RecursionError!Crashes for sizes: 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17...
The doctests only pass because they use size 8 (2^3).
Suggested Fix
Either validate input or use integer height:
import math
def minimax(depth, node_index, is_max, scores, height):
if depth < 0:
raise ValueError("Depth cannot be less than 0")
if not scores:
raise ValueError("Scores cannot be empty")
if not (len(scores) & (len(scores) - 1) == 0):
raise ValueError("Number of scores must be a power of 2")
# ...Or rewrite to use array slicing instead of index arithmetic, which works for any size.
Impact
Any user who passes a non-power-of-2 list gets an unhandled RecursionError. There is no documentation about this constraint.
Found during systematic algorithm audit: https://github.com/devladpopov/algorithm-autopsy
Activity