Chapter 10 Algorithm Design Techniques

10.1 Greedy Algorithms

10.1.1 A Simple Scheduling Problem

Let the jobs in the schedule be . The first job finishes in time . The second job finishes after . From this, we see that the total cost, , of the schedule is

The first sum is independent of the job ordering, so only the second sum affects the total cost.

The Multiprocessor Case

The algorithm to solve the multiprocessor case is to start jobs in order, cycling through processors. It is not hard to show that no other ordering can do better, although if the number of processors evenly divides the number of jobs , there are many optimal orderings.

Even if does not divide exactly, there can still be many optimal solutions, even if all the job times are distinct.

Minimizing the Final Completion Time

Although this schedule does not have minimum mean completion time, it has merit in that the completion time of the entire sequence is earlier. If the same user owns all these jobs, then this is the preferable method of scheduling. Although these problems are very similar, this new problem turns out to be NP-complete; it is just another way of phrasing the knapsack or bin-packing problems. Thus, minimizing the final completion time is apparently much harder than minimizing the mean completion time.

10.1.2 Huffman Codes

Character	Code	Frequency	Total Bits
a	000	10	30
e	001	15	45
i	010	12	36
s	011	3	9
t	100	4	12
space	101	13	39
newline	110	1	3
Total			174

This data structure is sometimes referred to as a trie. If character is at depth and occurs times, then the cost of the code is equal to

By placing the newline symbol one level higher at its parent, this tree is a full tree: All nodes either are leaves or have two children.

It does not matter if the character codes are different lengths, as long as no character code is a prefix of another character code. Such an encoding is known as a prefix code.

Putting these facts together, we see that our basic problem is to find the full binary tree of minimum total cost, where all characters are contained in the leaves.

Character	Code	Frequency	Total Bits
a	001	10	30
e	01	15	30
i	10	12	24
s	00000	3	15
t	0001	4	16
space	11	13	26
newline	00001	1	5
Total			146

Huffman’s Algorithm

We will assume that the number of characters is . Huffman’s algorithm can be described as follows: We maintain a forest of trees. The weight of a tree is equal to the sum of the frequencies of its leaves. times, select the two trees, and , of smallest weight, breaking ties arbitrarily, and form a new tree with subtrees and .

The encoding information must be transmitted at the start of the compressed file, since otherwise it will be impossible to decode. For small files, the cost of transmitting this table will override any possible savings in compression, and the result will probably be file expansion.

The first pass collects the frequency data and the second pass does the encoding. This is obviously not a desirable property for a program dealing with large files.

10.1.3 Approximate Bin Packing

We will consider some algorithms to solve the bin-packing problem. These algorithms will run quickly but will not necessarily produce optimal solutions.

We are given times of sizes . All sizes satisfy . The problem is to pack these items in the fewest number of bins, given that each bin has unit capacity.

Online Algorithms

Next Fit

When processing any item, we check to see whether it fits in the same bin as the last item. If it does, it is placed there; otherwise, a new bin is created. This algorithm is incredibly simple to implement and runs in linear time.

First Fit

The first fit strategy is to scan the bins in order and place the new item in the first bin that is large enough to hold it.

Best Fit

Instead of placing a new item in the first spot that is found, it is placed in the tightest spot among all bins.

Off-line Algorithms

The major problem with all the online algorithms is that it is hard to pack the large items, especially when they occur late in the input. The natural way around this is to sort the items, placing the largest items first. We can then apply first fit or best fit, yielding the algorithms first fit decreasing and best fit decreasing, respectively.

---

Lemma 10.1.

Let the items have (sorted in decreasing order) input sizes , respectively, and suppose that the optimal packing is bins. Then all items that first fit decreasing places in extra bins have size at most .

Proof.

Suppose the th item is the first placed in bin . We need to show that . We will prove this by contradiction. Assume .

It follows that , since the sizes are arranged in sorted order. From this it follows that all bins have at most two items each.

Consider the state of the system after the st item is placed in a bin, but before the th item is placed. We now want to show that (under the assumption that ) the first bins are arranged as follows: First there are some bins with exactly one element, and then the remaining bins have two elements.

Suppose there were two bins and , such that , has two items, and has one item. Let and be the two items in , and let be the item in . , since was placed in the earlier bin. , by similar reasoning. Thus, . This implies that could be placed in by . By our assumption this is not possible. Thus, if , then, at the time that we try to process , the first bins are arranged such that the first have one element and the next have two elements.

To prove the lemma we will show that there is no way to place all the items in bins, which contradicts the premise of the lemma.

Clearly, no two items can be placed in one bin, by any algorithm, since if they could, first fit would have done so too. We also know that first fit has not placed any of the items of size into the first bins, so none of them fit. Thus, in any packing, specifically the optimal packing, there must be bins that do not contain these items. It follows that the items of size must be contained in some set of bins, and from previous considerations, the total number of such items is .

The proof is completed by noting that if , there is no way for to be placed in one of these bins. Clearly, it cannot go in one of the bins, since if it could, then first fit would have done so too. To place it in one of the remaining bins requires distributing items into the bins. Thus, some bin would have to have three items, each of which is larger than , a clear impossibility.

This contradicts the fact that all the sizes can be placed in bins, so the original assumption must be incorrect. Thus, .

---

---

Lemma 10.2.

The number of objects placed in extra bins is at most .

Proof.

Assume that there are at least objects placed in extra bins. We know that , since all the objects fit in bins. Suppose that is filled with total weight for . Suppose the first extra objects have sizes . Then, since the items in the first bins plus the first extra items are a subset of all the items, it follows that

$$
\sum^{N}{i=1}s_i \ge \sum^{M}{j=1}W_j + \sum^{M}{j=1}x_j \ge \sum^{M}{j=1}(W_j + x_j)
$$

Now , since otherwise the item corresponding to would have been placed in . Thus

$$
\sum^{N}{i=1}s_i > \sum^{M}{j=1}1 > M
$$

But this is impossible if the items can be placed in bins. Thus, there can be at most extra items.

---

10.2 Divide and Conquer

Traditionally, routines in which the text contains at least two recursive calls are called divide-and-conquer algorithms, while routines whose text contains only one recursive call are not. We generally insist that the subproblems be disjoint.

10.2.1 Running Time of Divide-and-Conquer Algorithms

---

Theorem 10.6.

The solution to the equation , where and , is

Proof.

We will assume that is a power of ; thus, let . Then and . Let us assume , and ignore the constant factor in . Then we have

If we divide through by , we obtain the equation

We can apply this equation for other values of , obtaining

Virtually all the terms on the left cancel the leading terms on the right, yielding

Thus

If , then the sum is a geometric series with ratio smaller than . Since the sum of infinite series would converge to a constant, this finite sum is also bounded by a constant

If , then each term in the sum is . Since the sum contains terms and implies that ,

Finally, if , then the terms in the geometric series are larger than

---

As an example, mergesort has and . The second case applies, giving the answer . If we solve three problems, each of which is half the original size, and combine the solutions with additional work, then and . Case applies here, giving a bound of . An algorithm that solved three half-sized problems, but required work to merge the solution, we would have an running time, since the third case would apply.

---

Theorem 10.7.

The solution to the equation , where and is

---

---

Theorem 10.8.

If , then the solution to the equation is .

---

10.2.2 Closest-Points Problem

Either the closest points are both in , or they are both in , or one is in and the other is in . Let us call these distances and .

We can compute and recursively. The problem, then, is to compute . Since we would like an solution, we must be able to compute with only additional work.

Let . The first observation is that we only need to compute if improves on . If is such a distance, then the two points that define must be within of the dividing line; we will refer to this area as a strip.

10.2.3 The Selection Problem

Reducing the Average Number of Comparisons

A sample of elements is chosen from the elements. Let be some number, which we will choose later so as to minimize the average number of comparisons used by the procedure. We find the th and th smallest elements in . Almost certainly, the th smallest element in will fall between and , so we are left with a selection problem on elements. With low probability, the th smallest element does not fall in this range, and we have considerable work to do. However, with a good choice of and , we can ensure, by the laws of probability, that the second case does not adversely affect the total work.

10.2.4 Theoretical Improvements for Arithmetic Problems

Multiplying Integers

If and . Let us break and into two halves, Then and .

Notice that this equation consists of four multiplications, and , which are each half the size of the original problem . The multiplications by and amount to the placing of zeros. This and the subsequent additions add only additional work.

We see that , so, unfortunately, we have not improved the algorithm. To achieve a subquadratic algorithm, we must use less than four recursive calls. The key observation is that

Thus, instead of using two multiplications to compute the coefficient of , we can use one multiplication, plus the result of two multiplications that have already been performed.

and so we obtain .

Matrix Multiplication

The basic idea of Strassen’s algorithm is to divide each matrix into four quadrants

We could then perform eight by matrix multiplications and four by matrix additions. The matrix additions take time. If the matrix multiplications are done recursively, then the running time satisfies

We see that .

Strassen used a strategy similar to the integer multiplication divide-and-conquer algorithm and showed how to use only seven recursive calls by carefully arranging the computations. The seven multiplications are

Once the multiplications are performed, the final answer can be obtained with eight more additions.

It is straightforward to verify that this tricky ordering produces the desired values. The running time now satisfies the recurrence

The solution of this recurrence is .

As usual, there are details to consider, such as the case when is not a power of , but these are basically minor nuisances. Strassen’s algorithm is worse than the straightforward algorithm until is fairly large. It does not generalize for the case where the matrices are sparse (contain many zero entries), and it does not easily parallelize. When run with floating-point entries, it is less stable numerically than the classic algorithm. Thus, it has only limited applicability. Nevertheless, it represents an important theoretical milestone and certainly shows that in computer science, as in many other fields, even though a problem seems to have an intrinsic complexity, nothing is certain until proven.

10.3 Dynamic Programming

Any recursive mathematical formula could be directly translated to a recursive algorithm, but the underlying reality is that often the compiler will not do justice to the recursive algorithm, and an inefficient program results. When we suspect that this is likely to be the case, we must provide a little more help to the compiler, by rewriting the recursive algorithm as a nonrecursive algorithm that systematically records the answers to the subproblems in a table. One technique that makes use of this approach is known as dynamic programming.

10.3.1 Using a Table Instead of Recursion

public static int fib(int n) {
    if (n <= 1)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

Since to compute , all that is needed is and , we only need to record the two most recently computed Fibonacci numbers. This yields the algorithm:

public static int fibonacci(int n) {
    if (n <= 1)
        return 1;

    int last = 1;
    int nextToLast = 1;
    int answer = 1;

    for (int i = 2; i <= n; i++) {
        answer = last + nextToLast;
        nextToLast = last;
        last = answer;
    }

    return answer;
}

public static double eval(int n) {
    if (n == 0)
        return 1.0;
    else {
        double sum = 0.0;
        for (int i = 0; i < n; i++)
            sum += eval(i);
        return 2.0 * sum / n + n;
    }
}

The recursive calls duplicate work. In this case, the running time satisfies . Solving for , we find that it grows exponentially. By using a table, we obtain the program. This program avoids the redundant recursive calls and runs in .

public static double eval(int n) {
    double[] c = new double[n + 1];

    c[0] = 1.0;
    for (int i = 1; i <= n; i++) {
        double sum = 0.0;
        for (int j = 0; j < i; j++)
            sum += c[j];
        c[i] = 2.0 * sum / i + i;
    }

    return c[n];
}

10.3.2 Ordering Matrix Multiplications

Suppose we are given four matrices, and , of dimensions and . Although matrix multiplication is not commutative, it is associative, which means that the matrix product can be parenthesized, and thus evaluated, in any order.

• : multiplications.
• : multiplications.
• : multiplications.
• : multiplications.
• : multiplications.

It might be worthwhile to perform a few calculations to determine the optimal ordering. Unfortunately, none of the obvious greedy strategies seems to work. Moreover, the number of possible orderings grows quickly. Suppose we define to be this number. Then and , as we have seen. In general,

To see this, suppose that the matrices are , and the last multiplication performed is . Then there are ways to compute and ways to compute .

The solution of this recurrence is the well-known Catalan numbers, which grow exponentially. Nevertheless, this counting argument provides a basis for a solution that is substantially better than exponential. Let be the number of columns in matrix for . Then has rows, since otherwise the multiplications are not valid. We will define to be the number of rows in the first matrix, .

Suppose is the number of multiplications required to multiply . For consistency, . Suppose the last multiplication is , where . Then the number of multiplications used is .

If we define to be the number of multiplications required in an optimal ordering, then, if ,

This equation implies that if we have an optimal multiplication arrangement of , the subproblems and cannot be performed suboptimally.

However, since there are only approximately values of that ever need to be computed, it is clear that a table can be used to store these values. Further examination shows that if , then the only values that are needed in the computation of satisfy . This tells us the order in which we need to compute the table.

public static void optMatrix(int[] c, long[][] m, int[][] lastChange) {
    int n = c.length - 1;

    for (int left = 1; left <= n; left++)
        m[left][left] = 0;
    for (int k = 1; k < n; k++)
        for (int left = 1; left <= n - k; left++) {
            int right = left + k;
            m[left][right] = INFINITY;
            for (int i = left; i < right; i++) {
                long thisCost = m[left][i] + m[i + 1][right] + c[left - 1] * c[i] * c[right];

                if (thisCost < m[left][right]) {
                    m[left][right] = thisCost;
                    lastChange[left][right] = i;
                }
            }
        }
}

10.3.3 Optimal Binary Search Tree

We are given a list of words, , and fixed probabilities of their occurrence. The problem is to arrange these words in a binary search tree in a way that minimizes the expected total access time. In a binary search tree, the number of comparisons needed to access an element at depth is , so if is placed at depth , then we want to minimize .

Word	Probability
a	0.22
am	0.18
and	0.20
egg	0.05
if	0.25
the	0.02
two	0.08

The first tree was formed using a greedy strategy. The word with the highest probability of being accessed was placed at the root. The left and right subtrees were then formed recursively. The second tree is the perfectly balanced search tree. Neither of these trees is optimal, as demonstrated by the existence of the third tree.

This is initially surprising, since the problem appears to be very similar to the construction of a Huffman encoding tree, which, as we have already seen, can be solved by a greedy algorithm. Construction of an optimal binary search tree is harder, because the data are not constrained to appear only at the leaves, and also because the tree must satisfy the binary search tree property.

A dynamic programming solution follows from two observations. Once again, suppose we are trying to place the (sorted) words into a binary search tree. Suppose the optimal binary search tree has as the root, where . Further, both of these subtrees must also be optimal, since otherwise they could be replaced by optimal subtrees. Thus, we can write a formula for the cost of an optimal binary search tree.

If , then the cost of the tree is ; this is the null case, which we always have for binary search trees. Otherwise, the root costs . Each node in these subtrees is one level deeper from than from their respective roots, so we must add $\sum^{i-1}{j=Left}p_j\sum^{Right}{j=i+1}p_j$.

$$
\begin{align}
C_{Left,Right} &= \min_{Left \le i \le Right} { p_i + C_{Left,i-1} + C_{i+1,Right} + \sum^{i-1}{j=Left}p_j + \sum^{Right}{j=i+1}p_j } \
&= \min_{Left \le i \le Right} { C_{Left,i-1} + C_{i+1,Right} + \sum^{Right}_{j=Left}p_j }
\end{align}
$$

10.3.4 All-Pairs Shortest Path

Dijkstra’s algorithm provides the idea for the dynamic programming algorithm: we select the vertices in sequential order. We will define to be the weight of the shortest path from to that uses only as intermediates. By this definition, , where is if is not an edge in the graph. Also, by definition, is the shortest path from to in the graph.

When we can write a simple formula for .

The time requirement is once again .

/**
 * a[][] contains the adjacency matrix with
 * a[i][i] presumed to be zero.
 * d[] contains the values of the shortest path.
 */
public static void allPairs(int[][] a, int[][] d, int[][] path) {
    int n = a.length;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            d[i][j] = a[i][j];
            path[i][j] = NOT_A_VERTEX;
        }

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    path[i][j] = k;
                }
}

10.4 Randomized Algorithms

The worst-case running time of a randomized algorithm is often the same as the worst-case running time of the nonrandomized algorithm. The important difference is that a good randomized algorithm has no bad inputs, but only bad random numbers.

Randomized algorithms were used implicitly in perfect and universal hashing.

10.4.1 Random Number Generators

Actually, true randomness is virtually impossible to do on a computer, since these numbers will depend on the algorithm and thus cannot possibly be random. Generally, it suffices to produce pseudorandom numbers, which are numbers that appear to be random.

The simplest method to generate random numbers is the linear congruential generator, which was first described by Lehmer in 1951. Numbers are generated satisfying

To start the sequence, some value of must be given. This value is known as the seed. If , then the sequence is far from random, but if and are correctly chosen, then any other is equally valid. If is prime, then is never .

This sequence has a period of , which is as large as possible (by the pigeonhole principle). If is prime, there are always choices of that give a full period of . Some choices of do not.

Lehmer suggested the use of the -bit prime . For this prime, is one of the many values that gives a full-period generator.

It is also common to return a random real number in the open interval .

public class Random {
    private static final int A = 48271;
    private static final int M = 2147483647;

    private int state;

    public Random() {
        state = System.currentTimeMillis() % Integer.MAX_VALUE;
    }

    public int randomIntWRONG() {
        return state = (A * state) % M;
    }

    public double random0_1() {
        return (double)randomInt() / M;
    }
}

The problem with this class is that the multiplication could overflow; although this is not an error, it affects the result and thus the pseudorandomness. Schrage gave a procedure in which all the calculations can be done on a -bit machine without overflow. We compute the quotient and remainder of and define these as and , respectively.

Since , we can replace the leading and obtain

Since , it follows that . Thus, we obtain

The term is either or , because both terms are integers and their difference lies between and . Thus, we have

A quick check shows that because , all the remaining terms can be calculated without overflow (this is one of the reasons for choosing ). Furthermore, only if the remaining terms evaluate to less than zero.

Many libraries have generators based on the function

where is chosen to match the number of bits in the machine’s integer, and is odd. Unfortunately, these generators always produce values of that alternate between even and odd.

10.4.2 Skip Lists

A linked list in which every other node has an additional link to the node two ahead of it in the list. Because of this, at most nodes are examined in the worst case.

We can extend this idea. Every fourth node has a link to the node four ahead. Only nodes are examined.

Every th node has a link to the node ahead of it. The total number of links has only doubled, but now at most nodes are examined during a search. It is not hard to see that the total time spent for a search is , because the search consists of either advancing to a new node or dropping to a lower link in the same node. Notice that the search in this data structure is essentially a binary search.

When it comes time to insert a new element, we allocate a new node for it. We must at this point decide what level the node should be. We choose the level of the node randomly, in accordance with this probability distribution.

10.4.3 Primality Testing

---

Theorem 10.10. (Fermat’s Lesser Theorem)

If is prime, and , then .

---

If , then we can be certain that is not prime. On the other hand, if the equality holds, then is probably prime. For instance, the smallest that satisfies but is not prime isbut is not prime is .

We can attempt to randomize the algorithm as follows: Pick at random. If and , we find that .

Although this seems to work, there are numbers that fool even this algorithm for most choices of . One such set of numbers is known as the Carmichael numbers. These are not prime but satisfy for all that are relatively prime to . The smallest such number is .

---

Theorem 10.11.

If is prime and , the only solutions to are .

Proof.

implies that . This implies . Since is prime, , and must divide either or .

---

10.5 Backtracking Algorithms

Many other bad arrangements are discarded early, because an undesirable subset of the arrangement is detected. The elimination of a large group of possibilities in one step is known as pruning.

10.5.1 The Turnpike Reconstruction Problem

Suppose we are given points, , located on the -axis. is the coordinate of . Let us further assume that and the points are given from left to right. These points determine (not necessarily unique) distances between every pair of points of the form . It is clear that if we are given the set of points, it is easy to construct the set of distances in This set will not be sorted, but if we are willing to settle for an time bound, the distances can be sorted, too. The turnpike reconstruction problem is to reconstruct a point set from the distances. Just as factoring seems harder than multiplication, the reconstruction problem seems harder than the construction problem.

Let be the set of distances, and assume that .

Since , we know that . We start the algorithm by setting . Clear, , since is the largest element in . We remove from .

The largest remaining distance is , which means that either or . By symmetry, we can conclude that the choice is unimportant, since either both choices lead to solutions (which are mirror images of each other), or neither do, so we can set without affecting the solution. We then remove the distances and from , obtaining

Since is the largest value in , either or . If , then the distances and must also be present in . On the other hand, if we set , then and must be present in . These distances are also in , so we have no guidance on which choice to make. Thus, we try one and see if it leads to a solution. If it turns out that it does not, we can come back and try the other. We set .

Now the largest distance is , so either or . But if , then , which is impossible, since is no longer in . On the other hand, if then , and . This is also impossible, since only appears once in . Thus, this line of reasoning leaves no solution, so we backtrack.

Since failed to produce a solution, we try . If this also fails, we give up and report no solution.

Once again, so we obtain

A decision tree representing the actions taken to arrive at the solution. Instead of labeling the branches, we have placed the labels in the branches’ destination nodes. A node with an asterisk indicates that the points chosen are inconsistent with the given distances; nodes with two asterisks have only impossible nodes as children, and thus represent an incorrect path.

boolean turnpike(int[] x, DistSet d, int n) {
    x[1] = 0;
    x[n] = d.deleteMax();
    x[n - 1] = d.deleteMax();
    if (d.contains(x[n] - x[n - 1])) {
        d.remove(x[n] - x[n - 1]);
        return place(x, d, n, 2, n - 2);
    } else
        return false;
}

boolean place(int[] x, DistSet d, int n, int left, int right) {
    int dmax;
    boolean found = false;

    if (d.isEmpty())
        return true;

    dmax = d.findMax();

    // 1 <= j < left && right < j <= n
    if (isRangeExistInD(1, left, d, j -> x[j] - dmax) && isRangeExistInD(right + 1, n + 1, d, j -> x[j] -> dmax)) {
        x[right] = dmax;
        range(1, left).addList(range(right + 1, n + 1)).forEach(j -> d.remove(Math.abs(x[j] - dmax)));
        found = place(x, d, n, left, right - 1);

        if (!found)
            range(1, left).addList(range(right + 1, n + 1)).forEach(j -> d.insert(Math.abs(x[j] - dmax)));
    }

    if (!found && isRangeExistInD(1, left, d, j -> x[n] - dmax - x[j]) && isRangeExistInD(right + 1, n + 1, d, j -> x[n] - dmax - x[j])) {
        x[left] = x[n] - dmax;
        range(1, left).addList(range(right + 1, n + 1)).forEach(j -> d.remove(Math.abs(x[n] - dmax - x[j])));
        found = place(x, d, n, left + 1, right);

        if (!found)
            range(1, left).addList(range(right + 1, n + 1)).forEach(j -> d.insert(Math.abs(x[n] - dmax - x[j])));
    }

    return found;
}

Of course, backtracking happens, and if it happens repeatedly, then the performance of the algorithm is affected. This can be forced to happen by construction of a pathological case. Experiments have shown that if the points have integer coordinates distributed uniformly and randomly from , where , then, almost certainly, at most one backtrack is performed during the entire algorithm.

10.5.2 Games

Minimax Strategy

The more general strategy is to use an evaluation function to quantify the “goodness” of a position. A position that is a win for a computer might get the value of ; a draw could get ; and a position that the computer has lost would get a . A position for which this assignment can be determined by examining the board is known as a terminal position.

If a position is not terminal, the value of the position is determined by recursively assuming optimal play by both sides. This is known as a minimax strategy, because one player (the human) is trying to minimize the value of the position, while the other player (the computer) is trying to maximize it.

A successor position of is any position that is reachable from by playing one move. If the computer is to move when in some position , it recursively evaluates the value of all the successor positions. The computer chooses the move with the largest value; this is the value of . To evaluate any successor position , all of ’s successors are recursively evaluated, and the smallest value is chosen. This smallest value represents the most favorable reply for the human player.

class MoveInfo {
    public int move;
    public int value;

    public MoveInfo(int m, int v) {
        move = m;
        value = v;
    }
}

class TicTacToe {
    public MoveInfo findCompMove() {
        int i, responseValue;
        int value, bestMove = 1;
        MoveInfo quickWinInfo;

        if (fullBoard())
            value = DRAW;
        else if ((quickWinInfo = immediateCompWin()) != null)
            return quickWinInfo;
        else {
            value = COMP_LOSS;
            for (i = 1; i <= 9; i++)
                if (isEmpty(board(i))) {
                    place(i, COMP);
                    responseValue = findHumanMove().value;
                    unplace(i);

                    if (responseValue > value) {
                        value = responseValue;
                        bestMove = i;
                    }
                }
        }

        return new MoveInfo(bestMove, value);
    }

    public MoveInfo findHumanMove() {
        int i, responseValue;
        int value, bestMove = 1;
        MoveInfo quickWinInfo;

        if (fullBoard())
            value = DRAW;
        else if ((quickWinInfo = immediateHumanWin()) != null)
            return quickWinInfo;
        else {
            value = COMP_WIN;
            for (i = 1; i <= 9; i++) {
                if (isEmpty(board(i))) {
                    place(i, HUMAN);
                    responseValue = findCompMove().value;
                    unplace(i);

                    if (responseValue < value) {
                        value = responseValue;
                        bestMove = i;
                    }
                }
            }
        }

        return new MoveInfo(bestMove, value);
    }
}

The most costly computation is the case where the computer is asked to pick the opening move. Since at this stage the game is a forced draw, the computer selects square . A total of positions were examined, and the calculation took a few seconds.

For more complex games, such as checkers and chess, it is obviously infeasible to search all the way to the terminal nodes. In this case, we have to stop the search after a certain depth of recursion is reached.

Nevertheless, for computer chess, the single most important factor seems to be number of moves of look-ahead the program is capable of. This is sometimes known as ply; it is equal to the depth of the recursion.

The basic method to increase the look-ahead factor in game programs is to come up with methods that evaluate fewer nodes without losing any information. One method which we have already seen is to use a table to keep track of all positions that have been evaluated. The data structure that records this is known as a transposition table; it is almost always implemented by hashing.

Pruning

This is commonly referred to as a game tree. We have avoided the use of this term until now, because it is somewhat misleading: No tree is actually constructed by the algorithm. The game tree is just an abstract concept.

Here shows the evaluation of the same game tree, with several (but not all possible) unevaluated nodes. Almost half of the terminal nodes have not been checked. We show that evaluating them would not change the value at the root.

First, consider node . At this point, we are still in findHumanMove and are contemplating a call to findCompMove on . However, we already know that findHumanMove will return at most , since it is a min node. On the other hand, its max node parent has already found a sequence that guarantees . Nothing that does can possibly increase this value. Therefore, does not need to be evaluated. This pruning of the tree is known as pruning.

/**
 * alpha = COMP_LOSS and beta = COMP_WIN
 */
public MoveInfo findCompMove(int alpha, int beta) {
    int i, responseValue;
    int value, bestMove = 1;
    MoveInfo quickWinInfo;

    if (fullBoard())
        value = DRAW;
    else if ((quickWinInfo = immediateCompWin()) != null)
        return quickWinInfo;
    else {
        value = alpha;
        for (i = 1; i <= 9 && value < beta; i++) {
            if (isEmpty(board(i))) {
                place(i, COMP);
                responseValue = findHumanMove(value, beta).value;
                unplace(i);

                if (responseValue > value) {
                    value = responseValue;
                    bestMove = i;
                }
            }
        }
    }

    return new MoveInfo(bestMove, value);
}