Problem 621971 · medium · Level 06 Heuristics & Optimization

How Much Does the Scout Skip?

minimax · alpha-beta pruning · move ordering · recursion

A game tree is given as nested lists: an integer is a finished position (a leaf) with that score, and a list is a position whose items are the positions after each possible move. The player to move at the root wants the score as high as possible, the other player as low as possible, and they alternate level by level. The value of a position is the score reached when both play perfectly.

A scout explores the tree with two numbers, low (start: minus infinity) and high (start: plus infinity), and counts every position it visits, leaves included:

  • At a leaf it returns the leaf's score.
  • At a position of the maximising player it visits the children in turn, passing them the current low and high. After each child it sets best to the largest value returned so far and raises low to best if best is larger. As soon as low >= high it skips the remaining children. It returns best.
  • At a position of the minimising player it does the same with the smallest value, lowering high instead, and also stops as soon as low >= high.

Return a tuple of four integers:

  1. the value of the root,
  2. the number of positions in the whole tree,
  3. how many positions the scout visits when it takes the children left to right,
  4. how many it visits when it takes the children best first: at a maximising position in decreasing order of their value, at a minimising position in increasing order; children with equal values keep their left-to-right order.

The helper random_tree(branching, depth, seed) is available: it builds a tree in which every position above the leaves has exactly branching children, with depth levels of moves and leaf scores from -99 to 99.

Examples

Input:  tree = [[3, 5], [2, 9]]
Output: (3, 7, 6, 6)
Explanation: the right child's first leaf is 2 < 3, so its leaf 9 is never visited.

Input:  tree = [[2, 9], [3, 5]]
Output: (3, 7, 7, 6)
Explanation: left to right nothing can be skipped; best first starts with [3, 5].

Input:  tree = [[5, 1, 8], [4], [6, 7, 2]]
Output: (4, 11, 11, 7)

Constraints

  • The tree has at most 25,000 positions and at most 10 levels; every list has at least one item.
  • Leaves are integers.

Goals

  • Compute the minimax value of a game tree given as nested lists
  • Implement cut-offs with a lower and an upper bound and count the nodes they visit
  • Measure how much visiting the best children first shrinks the search
Starting Python…