N-ary recursion #

Definition. A recursive method that is not linear recursive uses n-ary recursion.

Specific cases include:

• binary recursion if a method performs up to two recursive calls each time it is executed,
• ternary recursion if it performs up to three recursive calls each time it is executed,
• etc.

Examples.

The algorithm seen earlier to print all files in a folder uses n-ary recursion.

All the binary tree algorithms seen earlier use binary recursion.

Divide and conquer #

The divide-and-conquer paradigm is a variation of the methodology seen earlier to solve a problem recursively. In the divide-and-conquer approach, the smaller inputs $I_1$, .., $I_k$ usually have (nearly) the same size.

Divide-and-conquer has been instrumental in discovering efficient solutions to pervasive computational problems. Well-known examples include:

• the Karatsuba algorithm for multiplying two numbers,
• the Strassen algorithm for matrix product,
• Mergesort for (stable) sorting.

Example: Mergesort #

Mergesort is one of (many) algorithms commonly used to sort an array, i.e. to solve the following problem:

Input: an array $A$

Output: a sorted array with the same elements as $A$

Observation. As we saw already, the array can be of any type (int, String, City, Unit, etc.), and the sorting criterion can be any total preorder over this type.

The Mergesort algorithm may be summarized as follows:

• (Base case). If $A$ has size $1$, then return it ($A$ is already sorted).
• (Inductive case). Otherwise:
  • (divide): partition $A$ into its left half $A_1$ and its right half $A_2$,
  • (solve): sort $A_1$ and sort $A_2$ (recursively),
  • (combine): merge (the sorted versions of) $A_1$ and $A_2$.

Here is a naive implementation, in pseudocode:

// Returns a sorted array that contains the same elements as A.
Type[] mergesort(Type[] A) {

    // Base case: the input array has size 1, it is already sorted.
    if(A.length == 1){
        return A
    }

    // Inductive case (the input array has size > 1)

    // Compute the middle index (rounded down)
    int middleIndex = (A.length - 1) / 2

    // Copy the left half of A into a new array
    Type[] leftHalf = copy(A[0 .. middleIndex])
    // Sort it
    leftHalf = mergesort(leftHalf)

    // Copy the right half of A into a new array
    Type[] rightHalf =  copy(A[middleIndex + 1 .. A.length - 1])
    // Sort it
    rightHalf = mergesort(rightHalf)

    // merge the two sorted halves
    return merge(leftHalf, rightHalf)
}

Warning. This implementation is suboptimal (some arrays can be reused). We only used it to keep the explanation simple.

Type[] merge(Type[] A, Type[] B)

Type[] merge(Type[] A, Type[] B){

    // Output array
    Type[] C = new Type[A.length + B.length]

    // Index to iterate over A
    int a = 0
    // Index to iterate over B
    int b = 0
    // Index to iteratate over C
    int c = 0

    // while we have not reached the end of A or B
    while (a < A.length && b < B.length) {
        if(A[a] <= B[b]) {
            C[c] = A[a]
            a++
        } else {
            C[c] = B[b]
            b++
    }

    // If we reached the end of A,
    if(a == A.length){
        // append all remaining elements of B to the output array.
        append(B, b, C, c)
    } else
        // Otherwise we reached the end of B.
        // So append all remaining elements of A to the output array.
        append(A, a, C, c)
    }
}

append (Type[] D, int d, Type[] C, int c) {
    while (d < D.length){
        C[c] = D[d]
        d++
    }
}

Merge sort in action. You can find visual illustrations of the execution of merge sort online. For instance this animation, or this (more accurate) one.

Observation. Merge sort is a stable sorting algorithm.

Tree and graph traversal #

Earlier in this chapter, we used different algorithms to traverse a binary tree, where nodes were instances of the following class:

One of these algorithms was the so-called “pre-order traversal”:

traverse(Node root){
    // inductive case only (do nothing in the base case)
    if (root != null){
        print(root.label)
        traverse(root.leftChild)
        traverse(root.rightChild)
    }
}

This algorithm naturally generalizes to trees where nodes may have more than two children. Nodes in such a tree can be represented as instances of the following class:

And the algorithm becomes:

traverse(Node root){
    if (root != null){
        print(root.label)
        foreach child in root.children {
            traverse(child)
        }
    }
}

This algorithm can in turn be adapted to traverse a graph. More precisely, to explore all nodes reachable (directly or transitively) from a given source node in the graph.

Warning. When applied to a graph, the algorithm above:

• may not terminate (if the graph contains a loop),
• may process some nodes multiple times (even if the graph is acyclic).

In order to avoid this, a common technique consists in labelling nodes in a graph with an additional boolean attribute visited, which indicates whether a node has already been visited during a traversal:

And the algorithm becomes:

traverse(Node root){
    if (root != null && !root.visited){
        root.visited = true
        print(root.label)
        foreach child in root.children {
            traverse(child)
        }
    }
}

Terminology. This approach is often called depth-first exploration of a graph.

Minimax/Maximin #

Minimax is a recursive algorithm with applications in games, robotics, decision making, etc.

Minimax may be easier to explain in the context of a turn-based zero-sum game, i.e. a game (like chess or tic-tac-toe) where players compete with each other (as opposed for instance to a collaborative game).

Zero-sum two player games can be used to model decisions that minimize risk, assuming that the worst will happen if it can. In other words, one the two players represents the decision maker, and the other player represents “bad luck”.

Numerous extensions and heuristics have been devise for Minimax. Here we only focus on the algorithm in its basic form.

Winning strategy #

Let Alice and Bob be our two players.

Let us generalize this observation.

In a turn-based two player game, a sequence of moves can be viewed as a list of board states, whose head is the initial board state.

The tree that consists of all these lists represents all possible sequences of moves from the initial board state.

Example. In the following tree, the root is a board state (of an imaginary game), and each branch represents a possible sequence of moves. Alice’s possible moves are the green edges, and Bob’s possible moves are the red edges.

The numbers on the leaves represent the payoff for Alice:

• 9 if this is a winning state for Alice, and
• 0 if this is a winning state for Bob.

Warning. In such a tree, several nodes may represent the same board state (e.g. in a chess game, where different sequences of moves may lead to the same board state).

Observation. In both exercises above, we were able to determine that Alice had already won the game, regardless of Bob’s actions. Intuitively, this holds iff:

• there is a move for Alice such that,
  • for every possible move of Bob,
    • there is a move for Alice such that,
      • for every possible move of Bob,
        • …
          • either:
            • there is a move for Alice that produces a winning state for Alice, or
            • every possible move of Bob produces a winning state for Alice.

This observation leads to a natural recursive definition.

Terminology. In our tree, let us assuming that the root has depth $0$. We call a node existential if its depth is even, and universal if its depth is odd.

Existential (resp. universal) nodes are the ones where Alice (resp. Bob) plays.

Definition. A node $n$ is a winning node (for Alice) if:

• it represents a winning state for Alice, or
• $n$ is existential and some child of $n$ is a winning node, or
• $n$ is universal and all children of $n$ are a winning nodes.

Naive algorithm #

Let us start with a naive algorithm for games where:

• the height of the tree is finite (as opposed to chess for instance, where there can be infinite sequences of moves).
• each leaf is a winning state for either Alice or Bob (as opposed to tic-tac-toe for instance, where there can be a draw).

In such a game, every node of the tree must be a winning node for Alice or for Bob. In order to determine this, we can intuitively propagate labels up the tree:

Let us assume that nodes in our tree are instance of the following class Node.

Notation.

If nodes is an array of nodes and f a function that takes a node as argument, we will use:

$\qquad$ [ f(n) | n in nodes ]

for the array obtained by applying f to each element of nodes.

Observation. Let n be a non-leaf node whose children have label 0 or 9. Then:

• there exists a child of n with label 9 iff max [ c.label | c in n.children ] = 9
• every child of $n$ is labeled with 9 iff min [ c.label | c in n.children ] = 9

Using this observation and our definition of a winning node (above), we can write the following recursive method maxiMin (in pseudocode). It takes an existential node as input, and returns:

• 9 if this node is a winning node for Alice, or
• 0 if this node is a winning node for Bob.

// existential node
int maxiMin(Node n){
    // base case (leaf node)
    if(n.children.length == 0){
        return n.label
    }
    // inductive case: return the largest label computed for a child
    return max [ miniMax(c) | c in n.children ]
}

// universal node
int miniMax(Node n){
    // base case (leaf node)
    if(n.children.length == 0){
        return n.label
    }
    // inductive case: return the least label computed for a child
    return min [ maxiMin(c) | c in n.children ]
}

In this algorithm, the method miniMax takes a universal node as input, and its return value has the same meaning as maximin (i.e. 9 if the node is a winning node for Alice, or 0 if it is a winning node for Bob).

Note. The code can be (slightly) factorized by writing a unique recursive method, with an additional boolean argument that indicates whether the input node is existential or universal.

This is usually how the algorithm is presented. We used two methods instead for readability.

Application #

In practice, in order to apply this algorithm to a game, the class Node is unnecessary. Instead, we can use:

• an auxiliary procedure possibleMoves that compute the “children of a node”, i.e. takes as argument a board state, and enumerates all board states that can be reached from it in one move.
• an auxiliary procedure score that returns the “label of a leaf node”. This procedure takes a state as input, and determines whether this state is a winning state for Alice or Bob.

The method maximim becomes:

int maxiMin(State s){
    Set<State> children = possibleMoves(s)

    // base case (leaf node)
    if(children.size == 0){
        return score(s)
    }
    // inductive case: return the largest label computed for a child
    return max [ miniMax(c) | c in children ]
}

And similarly for miniMax.

Then Alice can decide her next move by calling miniMax(c) for each successor state c of the current state, and select one of the states with the highest score.

Generalization #

Arbitrary weights #

The Minimax algorithm can be generalized to scenarios where a leaf node may not represent a winning state for Alice or Bob. For instance, in order to model tic-tac-toe, we may label some leaves with the value 4 for a draw.

More generally, any function score that assigns a score to a node can be used, as long as it assigns a maximal value to a winning state for Alice, and a minimal value to a winning state for Bob.

The algorithm is unchanged.

Large or infinite trees #

Warning Minimax can be prohibitive for games with an important tree height (since the number of board states to explore may grow exponentially with the height of the tree).

Besides, Minimax does not terminate if the tree has infinite branches (for instance in a chess game).

This is why the tree of game states is usually explored up to a certain depth.

Example. Deep Blue (the first program that defeated a chess world champion) was only looking 12 moves ahead.

The algorithm becomes:

// existential node
int maxiMin(State s, int depth){

    Set<State> children = possibleMoves(s)

    // base case
    if(children.size == 0 | depth == 0){
        return score(s)
    }
    // inductive case: return the largest label computed for a child
    return max [ miniMax(c, depth - 1) | c in children ]
}

// universal node
int miniMax(Node n, int depth){

    Set<State> children = possibleMoves(s)

    // base case
    if(children.size == 0 | depth == 0){
        return score(s)
    }
    // inductive case: return the least label computed for a child
    return min [ maxiMin(c, depth - 1) | c in children ]
}

Optimization #

A variety of optimization techniques have been developed for Minimax. For instance:

• keeping track of visited board states (recall that different nodes in our tree may represent the same board state),
• alpha-beta pruning.

These are beyond the scope of this course.