People, like computers, use searching algorithms. Here’s one familiar to any parent—the ransack search. As searching algorithms go, it’s atrocious, but that doesn’t stop three-year-olds. The particular variant described here can be attributed to Gwilym Hayward, who is much older than three years and should know better. The algorithm is as follows:

This particular search can take infinitely long to terminate: it will never recognize for certain if the element being searched for is not present. (Termination is an important consideration for any search.) Additionally, the random replacement destroys any cached location information that any other person might have about the order of the collection. That does not stop children of all ages from using it.

The ransack search is not recommended. My mother said so.

How do you find a particular item in an unordered pile of papers? You look at each item until you find the one you want. This is a linear search. It is so simple that programmers do it all the time without thinking of it as a search.

Here’s a Perl subroutine that linear searches through an array for a string match:^[22]

# $index = linear_string( @array, $target )
#      @array is (unordered) strings
#      on return, $index is undef or else $array[$index] eq $target

sub linear_string {
    my ($array, $target) = @_;

    for ( my $i = @$array; $i--; ) {
        return $i if $array->[$i] eq $target;
    }
    return undef;
}

Often this search will be written inline. There are many variations depending upon whether you need to use the index or the value itself. Here are two variations of linear search; both find all matches rather than just the first:

# Get all the matches.
@matches = grep { $_ eq $target } @array;

# Generate payment overdue notices.
foreach $cust (@customers) {
    # Search for overdue accounts.
    next unless $cust->{status} eq "overdue";
    # Generate and print a mailing label.
    print $cust->address_label;
}

Linear search takes time—it’s proportional to the number of elements. Before it can fail, it has to search every element. If the target is present, on the average, half of the elements will be examined before it is found. If you are searching for all matches, all elements must be examined. If there are a large number of elements, this time can be expensive.

Nonetheless, you should use linear search unless you are dealing with very large arrays or very many searches; generally, the simplicity of the code is more important than the possible time savings.

How do you look up a name in a phone book? A common method is to stick your finger into the book, look at the heading to determine whether the desired page is earlier or later. Repeat with another stab, moving in the right direction without going past any page examined earlier. When you’ve found the right page, you use the same technique to find the name on the page—find the right column, determine whether it is in the top or bottom half of the column, and so on.

That is the essence of the binary search: stab, refine, repeat.

The prerequisite for a binary search is that the collection must already be sorted. For the code that follows, we assume that ordering is alphabetical. You can modify the comparison operator if you want to use numerical or structured data.

A binary search “takes a stab” by dividing the remaining portion of the collection in half and determining which half contains the desired element.

Here’s a routine to find a string in a sorted array:

# $index = binary_string( @array, $target )
#        @array is sorted strings
#    on return,
#        either (if the element was in the array):
#           # $index is the element
#           $array[$index] eq $target
#        or (if the element was not in the array):
#           # $index is the position where the element should be inserted
#           $index == @array or $array[$index] gt $target
#           splice( @array, $index, 0, $target ) would insert it
#               into the right place in either case
#
sub binary_string {
     my ($array, $target) = @_;# $low is first element that is not too low;
     # $high is the first that is too high
     #
     my ( $low, $high ) = ( 0, calar@$array ));
# Keep trying as long as there are elements that might work.
     #
     while ( $low < $high ) {
         # Try the middle element.
use integer;
         my $cur = ($low+$high)/2;
         if ($array->[$cur] lt $target) {
             $low  = $cur + 1;                     # too small, try higher
         } else {
             $high = $cur;                         # not too small, try lower

     }
     return $low;
}
# example use:
my $index = binary_string( @keywords, $word );
if( $index < @keywords && $keywords[$index] eq $word ) {
    # found it: use $keywords[$index]
    ...
} else {
    # It's not there.
# You might issue an error
    warn "unknown keyword $word";
    ...
# or you might insert it.
    splice( @keywords, $index, 0, $word );
    ...
}

This particular implementation of binary search has a property that is sometimes useful: if there are multiple elements that are all equal to the target, it will return the first.

A binary search takes time—either to find a target or to determine that the target is not in the array. (If you have the extra cost of sorting the array, however, that is an operation.) It is tricky to code binary search correctly—you could easily fail to check the first or last element, or conversely try to check an element past the end of the array, or end up in a loop that checks the same element each time. (Knuth, in The Art of Computer Programming: Sorting and Searching, section 6.2.1, points out that the binary search was first documented in 1946 but the first algorithm that worked for all sizes of array was not published until 1962.)

One useful feature of the binary search is that you can use it to find a range of elements with only two searches and without copying the array. For example, perhaps you want all of the transactions that happened in February. Searching for a range looks like this:

# ($index_low, $index_high) =
#   binary_range_string( @array, $target_low, $target_high );
#      @array is sorted strings
#      On return:
#         $array[$index_low..$index_high] are all of the
#           values between $target_low and $target_high inclusive
#           (if there are no such values, then $index_low will
#           equal $index_high+1, and $index_low will indicate
#           the position in @array where such a value should
#           be inserted, i.e., any value in the range should be
#           inserted just before element $index_low

sub binary_range_string {
    my ($array, $target_low, $target_high) = @_;
    my $index_low  = binary_string( $array, $target_low );
    my $index_high = binary_string( $array, $target_high );

    --$index_high
        if $index_high == @$array ||
                            $array->[$index_high] gt $target_high;

    return ($index_low,$index_high);
}
($Feb_start, $Feb_end) = binary_range_string(@year, '0201', '0229'),

The binary search method suffers if elements must be added or removed after you have sorted the array. Inserting or deleting an element into or from an array without disrupting the sort generally requires copying many of the elements of the array. This condition makes the insert and delete operations instead of .

This algorithm is recommended as long as the following are true:

It could also be used with a separate list of the inserts and deletions as part of a compound strategy if there are relatively few inserts and deletions. After binary searching and finding an entry in the main array, you would perform a linear search of the deletion list to verify that the entry is still valid. Alternatively, after binary searching and failing to find an element, you perform a linear search of the addition list to confirm that the element still does not exist. This compound approach is O((log N) + K) where K is the number of inserts and deletes. As long as K is much smaller than N (say, less than log N) this approach is workable.

A significant speedup to binary search can be achieved. When you are looking in a phone book for a name like “Anderson”, you don’t take your first guess in the middle of the book. Instead, you begin a short way from the beginning. As long as the values are roughly evenly distributed throughout the range, you can help binary search along, making it a proportional search. Instead of computing the index to be halfway between the known upper and lower bounds, you compute the index that is the right proportion of the distance between them—conceptually, for your next guess you would use:

                (target - $array->[low])           
(high-low)  ________________________________ + low     
            ($array->[high] - $array->[low])

To make proportional search work correctly requires care. You have to map the result to an integer—it’s hard to look up element 34.76 of an array. You also have to protect against the cases when the value of the high element equals the value of the low element so that you don’t divide by zero. (Note also that we are treating the values as numbers rather than strings. Computing proportions on strings is much messier, as you can see in the next code example.)

A proportional search can speed the search up considerably, but there are some problems:

To illustrate the last problem, suppose the array contains a million and one elements—all of the integers from 1 to 1,000,000, and then 1,000,000,000,000. Now, suppose that you search for 1,000,000. After determining that the values at the ends are 1 and 1,000,000,000,000, you compute that the desired position is about one millionth of the interval between them, so you check the element $array[1] since 1 is one millionth of the distance between indices 0 and 1,000,000. At each stage, your estimate of the element’s location is just as badly off, so by the time you’ve found the right element, you’ve tested every other element first. Some speedup! Add this danger to the extra cost of computing the new index at each stage, and even more lustre is lost. Use proportional search only if you know your data is well distributed. Later in this chapter, Section 5.2.10 shows how this example could be handled by making the proportional search part of a mixed strategy.

Computing proportional distances between strings is just the sort of “simple modification” (hiding a horrible mess) that authors like to leave as an exercise for the reader. However, with a valiant effort, we resisted that temptation:

sub proportional_binary_string_search {
    my ($array, $target) = @_;

    # $low is first element that is not too low;
    # $high is the first that is too high
    # $common is the index of the last character tested for
    #    equality in the elements at $low-1 and $high.
    #    Rather than compare the entire string value, we only
    #    use the "first different character".
    #    We start with character position -1 so that character
    #    0 is the one to be compared.
    #
    my ( $low, $high, $common ) = ( 0, scalar(@$array), -1 );

    return 0 if $high == -1 || $array->[0] ge $target;
    return $high if $array->[$high-1] lt $target;
    --$high;

    my ($low_ch,  $high_ch,  $targ_ch ) = (0, 0);
    my ($low_ord, $high_ord, $targ_ord);

    # Keep trying as long as there are elements that might work.
    #
    while( $low < $high ) {
        if ($low_ch eq $high_ch) {
            while ($low_ch eq $high_ch) {
                return $low if $common == length($array->[$high]);
                ++$common;
                $low_ch  = substr( $array->[$low],  $common, 1 );
                $high_ch = substr( $array->[$high], $common, 1 );
            }
            $targ_ch = substr( $target, $common, 1 );
            $low_ord  = ord( $low_ch  );
            $high_ord = ord( $high_ch );
            $targ_ord = ord( $targ_ch );
        }
        # Try the proportional element (the preceding code has
        # ensured that there is a nonzero range for the proportion
        # to be within).

        my $cur = $low;
        $cur += int( ($high - 1 - $low) * ($targ_ord - $low_ord)
                        / ($high_ord - $low_ord) );
        my $new_ch = substr( $array->[$cur], $common, 1 );
        my $new_ord = ord( $new_ch );

        if ($new_ord < $targ_ord
                || ($new_ord == $targ_ord
                    && $array->[$cur] lt $target) ) {
            $low  = $cur+1;       # too small, try higher
            $low_ch  = substr( $array->[$low], $common, 1 );
            $low_ord = ord( $low_ch );
        } else {
            $high = $cur;         # not too small, try lower
            $high_ch  = $new_ch;
            $high_ord = $new_ord;
        }
    }
    return $low;
}

The binary tree data structure was introduced in Chapter 2. As long as the tree is kept balanced, finding an element in a tree takes time, just like binary search in an array. Even better, it only takes to perform an insert or delete operation, which is a lot less than the required to insert or delete an element in an array.

Binary searching is for both sorted lists and balanced binary trees, so as a first approximation they are equally usable. Here are some guidelines:

Binary trees provide performance, but it’s tempting to use wider trees—a tree with three branches at each node would have [] performance, four branches performance, and so on. This is analogous to changing a binary search to a proportional search—it changes from a division by two into a division by a larger factor. If the width of the tree is a constant, this does not reduce the order of the running time; it is still . What it does do is reduce by a constant factor the number of tree nodes that must be examined before finding a leaf. As long as the cost of each of those tree node examinations does not rise unduly, there can be an overall saving. If the tree width is proportional to the number of elements, rather than a constant width, there is an improvement, from to . We already discussed using lists and hashes in Section 5.1, they provide “trees” of one level that is as wide as the actual data. Next, though, we’ll discuss bushier structures that do have the multiple levels normally expected of trees.

If the key is sparse rather than dense, then sometimes a multilevel array can be effective. Break the key into chunks, and use an array lookup for each chunk. In the portions of the key range where the data is especially sparse, there is no need to provide an empty tree of subarrays—this will save some wasted space. For example, if you were keeping information for each day over a range of years, you might use arrays representing years, which are subdivided further into arrays representing months, and finally into elements for individual days:

# $value = datetab( $table, $date )
# datetab( $table, $date, $newvalue )
#
# Look up (and possibly change) a value index by a date.
# The date is of the form "yyyymmdd", year(1990-), month(1-12),
# day(1-31).

sub datetab {
    my ($tab, $date, $value) = @_;
    my ($year, $month, $day) = ($date =~ /^(dddd)(dd)(dd)$/)
        or die "Bad date format $date";

    $year -= 1990;
    --$month; --$day;
    if (@_ < 3) {
        return $tab->[$year][$month][$day];
    } else {
        return $tab->[$year][$month][$day] = $value;
    }
}

You can use a variant on the same technique even if your data is a string rather than an integer. Such a breakdown is done on some Unix systems to store the terminfo database, a directory of information about how to control different kinds of terminals. This terminal information is stored under the directory /usr/lib/terminfo. Accessing files becomes slow if the directory contains a very large number of files. To avoid that slowdown, some systems keep this information under a two-level directory. Instead of the description for vt100 being in the file /usr/lib/terminfo/vt100, it is placed in /usr/lib/terminfo/v/vt100. There is a separate directory for each letter, and each terminal type with that initial is stored in that directory. CPAN uses up to two levels of the same method for storing user IDs—for example, the directory K/KS/KSTAR has the entry for Kurt D. Starsinic.

Another wide tree algorithm is the B-tree. It uses a multilevel tree structure. In each node, the B-tree keeps a list of pairs of values, one pair for each of its child branches. One value specifies the minimum key that can be found in that branch, the other points to the node for that branch. A binary search through this array can determine which one of the child branches can possibly contain the desired value. A node at the bottom level contains the actual value of the keyed item instead of a list. See Figure 5-1 for the structure of a B-tree.

Figure 5-1. Sample B-tree

B-trees are often used for very large structures such as filesystem directories—structures that must be stored on disk rather than in memory. Each node is constructed to be a convenient size in disk blocks. Constructing a wide tree this way satisfies the main requirement of data stored on file, which is to minimize the number of disk accesses. Because disk accesses are much slower than in-memory operations, we can afford to use more complicated data processing if it saves accesses. A B-tree node, read in one disk operation, might contain references to 64 subnodes. A binary tree structure would require six times as many disk accesses, but these disk accesses totally dwarf the cost of the B-tree’s binary search through the 64 elements.

If you’ve installed Berkeley DB (available at http://www.sleepycat.com/db)on your machine, using B-trees from Perl is easy:

use DB_File;tie %hash, "DB_File", $filename, $flags, $mode, $DB_BTREE;

This binds %hash to the file $filename, which keeps its data in B-tree format. You add or change items in the file simply by performing normal hash operations. Examine perldoc DB_File for more details. Since the data is actually in a file, it can be shared with other programs (or used by the same program when run at different times). You must be careful to avoid concurrent reads and writes, either by never running multiple programs at once if one of them can change the file, or by using locks to coordinate concurrent programs. There is an added bonus: unlike a normal Perl hash, you can iterate through the elements of %hash (using each, keys, or values) in order, sorted by the string value of the key.

The DB_File module, by Paul Marquess, has another feature: if the value of $filename is undefined when you tie the hash to the DB_File module, it keeps the B-tree in memory instead of in a file.

Alternatively, you can keep B-trees in memory using Mark-Jason Dominus’ BTree module, which is described in The Perl Journal, Issue #8. It is available at http://www.plover.com/~mjd/perl/BTree/BTree.pm.

Here’s an example showing typical hash operations with a B-tree:

use BTree;

my $tree = BTree->new( B => 20 );

# Insert a few items.
while ( my ( $key, $value ) = each %hash ) {
    $tree->B_search(
        Key    => $key,
        Data   => $value,
        Insert => 1 );
}

# Test whether some items are in the tree.
foreach ( @test ) {
    defined $tree->B_search( Key => $_ )
        ? process_yes($_)
        : process_no($_);
}

# Update an item only if it exists, do nothing if it doesn't.
$tree->B_search(
    Key     => 'some key',
    Data    => 'new value',
    Replace => 1 );

# Create or update an item whether it exists or not.
$tree->B_search(
    Key     => 'another key',
    Data    => 'a value',
    Insert  => 1,
    Replace => 1 );

If your key values are not consistently distributed, you might find that a mixture of search techniques is advantageous. That familiar address book uses a sorted list (indexed by the initial letter) and then a linear, unsorted list within each page.

The example that ruined the proportional search (the array that included numbers from 1 through 1,000,000 as well as 1,000,000,000,000) would work really well if it used a three-level structure. A hybrid search would replace the binary search with a series of checks. The first check would determine whether the target was the Saganesque 1,000,000,000,000 (and return its index), and a second check would determine if the number was out of range for 1 .. 1,000,000 (saying “not found”). Otherwise, the third level would return the number (which is its own index in the array):

sub sagan_and_a_million {
    my $desired = shift;

    return 1_000_001 if $desired == 1_000_000_000_000;
    return undef if $desired < 0 || $desired > 1_000_000;
    return $desired;
}

This sort of search structure can be used in two situations. First, it is reasonable to spend a lot of effort to find the optimal structure for data that will be searched many times without modification. In that case, it might be worth writing a routine to discover the best multilevel organization. The routine would use lists for ranges in which the key space was completely filled, proportional search for areas where the variance of the keys was reasonably small, bushy trees or binary search lists for areas with large variance in the key distribution. Splitting the data into areas effectively would be a hard problem.

Second, the data might lend itself to a natural split. For example, there might be a top level indexed by company name (using a hash), a second level indexed by year (a list), and a third level indexed by company division (another hash), with gross annual profit as the target value:

$profit = $gross->{$company}[$year]{$division};

Perhaps you can imagine a tree structure in which each node is an object that has a method for testing a match. As the search progresses down the tree, entirely different match techniques might be used at each level.

Choosing a search algorithm is intimately tied to choosing the structure that will contain your data collection. Consider these factors as you make your choices:

Table 5-1 lists a number of viable data structures and their fitness for searching.

Table 5-1 give no recommendations for searches made on multiple, different keys. Here are some general approaches to dealing with multiple search keys:

Since we are using games for examples, we’ll assume a standard game interface for all game evaluations. We need two types of objects for the game interface—a position and a move.

A position object will contain data to define all necessary attributes of the game at one instant during a particular game (where pieces are located on the board, whose turn it is, etc.). It must have the following methods:

A move object is much simpler. It must contain data sufficient to define all necessary attributes of a move, as determined by the needs of the position object’s make_move method, but the internal details of a move object are unimportant as far as the following algorithms are concerned (in fact, a move need not be represented as an object at all unless the make_move method expects it to be).

Here is a game interface definition for tic-tac-toe:

# tic-tac-toe game package
package tic_tac_toe;

    $empty = ' ';
    @move = ( 'X', 'O' );
    # Map X and O to 0 and 1.
    %move = ( 0=>0, 1=>1, 'X'=>0, 'O'=>1 );

    # new( turn, board )
    #
    # To create a new tic-tac-toe game:
    #    tic_tac_toe->new( )
    ## This routine is also used internally to create the position
    # that will occur after a move, switching whose turn it is and
    # adding a move to the board:
    #    $board = ... adjust current board for the selected move
    #    tic_tac_toe->new( 1 - $self->{turn}, $board )
    sub new {
        my ( $pkg, $turn, $board ) = @_;
        $turn = 0 unless defined $turn;
        $turn = $move{$turn};
        $board = [ ($empty) x 9 ] unless defined $board;
        my $self = { turn => $turn, board => $board };
        bless $self, $pkg;
        $self->evaluate_score;

        return $self;
    }

    # We cache the score for a position, calculating it once when
    # the position is first created.  Give the value from the
    # viewpoint of the player who just moved.
    #
    # scoring:
    #       100 win for current player (-100 for opponent)
    #        10 for each unblocked 2-in-a-row (-10 for opponent)
    #         1 for each unblocked 1-in-a-row (-1 for opponent)
    #         0 for each blocked row
    sub evaluate_score {
        my $self  = shift;
        my $me    = $move[1 - $self->{turn}];
        my $him   = $move[$self->{turn}];
        my $board = $self->{board};
        my $score = 0;

        # Scan all possible lines.
        foreach $line (
                [0,1,2], [3,4,5], [6,7,8],   # rows
                [0,3,6], [1,4,7], [2,5,8],   # columns
                [0,4,8], [2,4,6] )           # diagonals
        {
            my ( $my, $his );
            foreach (@$line) {
                my $owner = $board->[$_];

                ++$my if $owner eq $me;
                ++$his if $owner eq $him;
            }

            # No score if line is blocked.
            next if $my && $his;

            # Lost.
            return $self->{score} = -100 if $his == 3;

            # Win can't really happen, opponent just moved.
            return $self->{score} = 100 if $my == 3;
# Count 10 for 2 in line, 1 for 1 in line.
            $score +=
                ( -10, -1, 0, 1, 10 )[ 2 + $my - $his ];
        }

        return $self->{score} = $score;
    }

    # Prepare to generate all possible moves from this position.
    sub prepare_moves {
        my $self = shift;

        # None possible if game is already won.
        return undef if abs($self->{score}) == 100;

        # Check whether there are any possible moves:
        $self->{next_move} = -1;
        return undef unless defined( $self->next_move );

        # There are.  Next time we'll return the first one.
        return $self->{next_move} = -1;
    }

    # Determine the next move possible from the current position.
    # Return undef when there are no more moves possible.
    sub next_move {
        my $self = shift;

        # Continue returning undef if we've already finished.
        return undef unless defined $self->{next_move};

        # Check each square from where we last left off, skipping
        # squares that are already occupied.
        do {
            ++$self->{next_move}
        } while $self->{next_move} <= 8
            && $self->{board}[$self->{next_move}] ne $empty;

        $self->{next_move} = undef if $self->{next_move} == 9;
        return $self->{next_move};
    }

    # Create the new position that results from making a move.
    sub make_move {
        my $self = shift;
        my $move = shift;

        # Copy the current board, changing only the square for the move.
        my $myturn = $self->{turn};
        my $newboard = [ @{$self->{board}} ];
        $newboard->[$move] = $move[$myturn];

        return tic_tac_toe->new(1 - $myturn, $newboard);
    }

    # Get the cached evaluation of this position.
    sub evaluate {
        my $self = shift;

        return $self->{score};
    }

    # Display the position.
    sub description {
        my $self = shift;
        my $board = $self->{board};
        my $desc = "@$board[0..2]
@$board[3..5]
@$board[6..8]
";
        return $desc;
    }

    sub best_rating {
        return 101;
    }

The technique of generating and analyzing all of the possible states of a situation is called exhaustive search. An exhaustive search is the generative analog of linear search—try everything until you succeed or run out of things to try. (Exhaustive search has also been called the British Museum Search, based on the light-hearted idea that the only way to find the most interesting object in the British Museum is to plod through the entire museum and examine everything. If your data structure, like the British Museum, does not order its elements according to how interesting they are, this technique may be your only hope.)

Consider a program that plays chess. If you were determined to use a lookup search, you might want to start by generating a data structure containing all possible chess positions. Positions could be linked wherever a legal move leads from one position to another. Then, identify all of the final positions as “win for white,” “win for black,” or “tie,” labeling them W, B, and T, respectively. In addition, when a link leads to a labeled position, label the link with the same letter as the position it leads to.

Next, you’d work backwards from identified positions. If a W move is available from a position where it is white’s turn to move, label that position W too (and remember the move that leads to the win). That determination can be made regardless of whether the other moves from that position have been identified yet—white can choose to win rather than move into unknown territory. (A similar check finds positions where it is black’s move and a B move is available.) If there is no winning move available, a position can only be identified if all of the possible moves have been labeled. In such a case, if any of the available moves is T, so is the position; but if all of the possible moves are losers, so is the position (i.e., B if it is white’s turn, or W if it is black’s turn). Repeat until all positions have been labeled.

Now you can write a program to play chess with a lookup search—simply lookup the current position in this data structure, and make the preferred move recorded there, an operation. Congratulations. You have just solved chess. White’s opening move will be labeled W, T, or B. Quick, publish your answer—no one has determined yet whether white has a guaranteed win (although it would come as quite a shock if you discovered that black does).

There are a number of problems, however. Obviously, we skipped a lot of detail—you’d need to use a number of algorithms from Chapter 8, to manage the board positions and the moves between them. We’ve glossed over the possibilities of draws that occur because of repeated positions—more graph algorithms to find loops so that we can check them to see whether either player would ever choose to leave the loop (because he or she would have a winning position).

But the worst problem is that there are a lot of positions. For white’s first move, there are 20 different possibilities. Similarly, for black’s first move. After that, the number of possible moves varies—as major pieces are exposed, more moves become available, but as pieces are captured, the number decreases.

A rough estimate says that there are about 20 choices for each possible turn, and a typical game lasts about 50 moves, which gives 20⁵⁰ positions (or about 10⁶⁵). Of course, there are lots of possible games that go much longer than the “typical” game, so this estimate is likely quite low.^[24] If we guess that a single position can be represented in 32 bytes (8 bytes for a bitmap showing which squares are occupied, 4 bits for each occupied square to specify which piece is there, a few bits for whose turn it is, the number of times the position has been reached, and “win for white,” “win for black,” “tie,” or “not yet determined,” and a very optimistic assumption that the links to all of the possible successor positions can be squeezed into the remaining space), then all we need is about 10⁵⁶) 32-gigabyte disk drives to store the data. With only an estimated 10⁷⁰) protons in the universe, that may be difficult.

It will take quite a few rotations of our galaxy to generate all of those positions, so you can take advantage of bigger disk drives as they become available. Of course, the step to analyze all of the positions will take a bit longer. In the meantime, you might want to use a less complete analysis for your chess program.

The exponential growth of the problem’s size makes that technique unworkable for chess, but it is tolerable for tic-tac-toe:

use tic_tac_toe;        # defined earlier in this chapter

# exhaustive analysis of tic-tac-toe
sub ttt_exhaustive {

    my $game = tic_tac_toe->new( );

    my $answer = ttt_analyze( $game );
    if ( $answer > 0 ) {
        print "Player 1 has a winning strategy
";
    } elsif ( $answer < 0 ) {
        print "Player 2 has a winning strategy
";
    } else {
        print "Draw
";
    }
}

# $answer = ttt_analyze( $game )
#    Determine whether the other player has won.  If not,
#    try all possible moves (from $avail) for this player.
sub ttt_analyze {
    my $game = shift;

    unless ( defined $game->prepare_moves ) {
        # No moves possible.  Either the other player just won,
        # or else it is a draw.
        my $score = $game->evaluate;
        return -1 if $score < 0;
        return 0;
    }

    # Find result of all possible moves.
    my $best_score = -1;

    while ( defined( $move = $game->next_move ) ) {
        # Make the move negating the score
        #   - what's good for the opponent is bad for us.
        my $this_score = - ttt_analyze( $game->make_move( $move ) );

        # evaluate
        $best_score = $this_score if $this_score > $best_score;
    }

    return $best_score;
}

Running this:

print &ttt_exhaustive, "
";

produces:

Draw

As a comment on just how exhausting such a search can be, the tic-tac-toe exhaustive search had to generate 549,946 different game positions. More than half, 294,778, were partial positions (the game was not yet complete). Less than half, 209,088, were wins for one player or the other. Only a relative few, 46,080, were draw positions—yet with good play by both players, the game is always a draw. This run took almost 15 minutes. A human can analyze the game in about the same time—but not if they do it by exhaustive search.

Exhaustive search can be used for nongame generative searches, too, of course. Nothing about it depends upon the alternating turns common to games. For that matter, the definition of exhaustive search is vague. The exact meaning of “try everything” depends upon the particular problem. Each problem has its own way of trying everything, and often many different ways.

For many problems, exhaustive search is the best known method. Sometimes, it is known to be the best possible method. For example, to find the largest element in an unsorted collection, it is clear that you have to examine every element at least once. When that happens for a problem that grows exponentially, the problem is called intractable. For an intractable problem, you cannot depend on being able to find the best solution. You might find the best solution for some special cases, but generally you have to lower your sights—either accept an imperfect solution or be prepared to have no solution at all when you run out of time. (We’ll describe one example, the Traveling Salesman problem, later in this chapter.)

There are a number of known classes of really hard problems. The worst are called “undecidable”—no correct solution can possibly exist. The best known is the Halting Problem.^[25]

There are also problems that are intractable. They are solvable, but all known solutions take exponentially long—e.g., 0(2^N). Some of them have been proven to require an exponentially long time to solve. Others are merely believed to require an exponentially long time.

We are not going to list all of the intractable problems—that subject could fill a whole book.^[26]

One example of an intractable problem is the Traveling Salesman problem. Given a list of cities and the distances between them, find the shortest route that takes the salesman to each of the cities on the list and then back to his original starting point. An exhaustive search requires checking N! different routes to see which is the shortest. As it happens, exhaustive search is the only method known to solve this problem. You’ll see this problem discussed further in Chapter 8.

When a problem is too large for exhaustive search, other approaches can be used. They tend to resemble bushy tree searches. A number of partial solutions are generated, and then one or some of them are selected as the basis for the next generative stage.

For some problems, such approaches can lead to a correct or best possible answer. For intractable problems, however, the only way to be certain of getting the best possible answer is exhaustive search. In these cases, the available alternative approaches only give approximations to the best answer—sometimes with a guarantee that the approximate answer is close to the best answer (for some specific definition of “close”). With other problems all you can do is to try a few different approximations and hope at least one provides a tolerable result. For example, for the Traveling Salesman problem, some solutions form a route by creating chains of nodes with relatively short connections and then choosing the minimum way of joining the endpoints of those chains into a loop. In some cases, Monte Carlo methods can be applied—generating some trial solutions in a random way and selecting the best.^[27]

It is not always easy to know whether a particular problem is intractable. For example, it would appear that a close relative of the Traveling Salesman problem would be finding a minimum cost spanning tree—a set of edges that connects all of the vertices with no loops and with minimum total weight for the edges. But, this problem is not intractable; it can be solved rather easily, as you’ll see in Section 8.8.6.2.

Instead of an exhaustive search of the entire game, chess programs typically look exhaustively at only the next few moves and then perhaps look a bit deeper for some special cases. The variety of techniques used for chess can also be used in other programs—not only in other game programs but also in many graph problems.

# Usage:
#    To choose the next move:
#        ($moves,$score) = minimax($position,$depth)
#    You provide a game position object, and a maxmimum depth
#    (number of moves) to be expanded before cutting off the
#    move generation and evaluating the resulting position.
#    There are two return values:
#     1: a reference to a list of moves (the last element on the
#        list is the position at the end of the sequence - either
#        it didn't look beyond because $depth moves were found, or
#        else it is a terminating position with no moves posible.
#     2: the final score

sub minimax {
    my ( $position, $depth ) = @_;

    # Have we gone as far as permitted or as far as possible?
    if ( $depth-- and defined($position->prepare_moves) ) {
        # No - keep trying additional moves from $position.
        my $move;
        my $best_score = -$position->best_rating;
        my $best_move_seq;

        while ( defined( $move = $position->next_move ) ) {
            # Evaluate the next move.
            my ( $this_move_seq, $this_score ) =
                minimax(
                    $position->make_move($move),
                    $depth );
            # Opponent's score is opposite meaning of ours.
            $this_score = -$this_score;
            if ( $this_score > $best_score ) {
                $best_score = $this_score;
                $best_move_seq = $this_move_seq;
                unshift ( @$best_move_seq, $move );
            }
        }

        # Return the best one we found.
        return ( $best_move_seq, $best_score );

    } else {
        # Yes - evaluate current position, no move to be taken.
        return ( [ $position ], -$position->evaluate );
    }
}

use tic_tac_toe;

my $game = tic_tac_toe->new( );

my ( $moves, $score ) = minimax( $game, 2 );
my $my_move = $moves->[0];
print "I move: $my_move
";

I move: 4

# Usage:
#    To minimize the next move:
#        ($move,$score) = ab_minimax($position,$depth)
#    You provide a game position object, and a maxmimum depth
#    (number of moves) to be expanded before cutting off the
#    move generation and evaluating the resulting position.

sub ab_minimax {
    my ( $position, $depth, $alpha, $beta ) = @_;

    defined ($alpha) or $alpha = -$position->best_rating;
    defined ($beta)  or $beta  =  $position->best_rating;

    # Have we gone as far as permitted or as far as possible?
    if ( $depth-- and defined($position->prepare_moves) ) {
        # no - keep trying additional moves from $position
        my $move;
        my $best_score = -$position->best_rating;
        my $best_move_seq;
        my $alpha_cur = $alpha;

        while ( defined($move = $position->next_move) ) {
            # Evaluate the next move.
            my ( $this_move_seq, $this_score ) =
                ab_minimax( $position->make_move($move),
                                $depth, -$beta, -$alpha_cur );
            # Opponent's score is opposite meaning from ours.
            $this_score = -$this_score;
            if ( $this_score > $best_score ) {
                $best_score = $this_score;
                $alpha_cur = $best_score if $best_score > $alpha_cur;
                $best_move_seq = $this_move_seq;
                unshift ( @$best_move_seq, $move );

                # Here is the alpha-beta pruning.
                #    - quit when someone else is ahead!
                last if $best_score >= $beta;
            }
        }

        # Return the best one we found.
        return ( $best_move_seq, $best_score );

    } else {
        # Yes - evaluate current position, no move to be taken.
        return ( [ $position ], -$position->evaluate );
    }
}

use tic_tac_toe;

my $game = tic_tac_toe->new( );

my ( $moves, $score ) = ab_minimax( $game, 2 );
my $my_move = $moves->[0];
print "I move: $my_move
";

I move: 4

use tic_tac_toe;        # defined earlier in this chapter

# exhaustive analysis of tic-tac-toe using a transpose table
sub ttt_exhaustive_table {

    my $game = tic_tac_toe->new( );

    my $answer = ttt_analyze_table( $game );
    if ( $answer > 0 ) {
        print "Player 1 has a winning strategy
";
    } elsif ( $answer < 0 ) {
        print "Player 2 has a winning strategy
";
    } else {
        print "Draw
";
    }
}

@cache = ( );

# $answer = ttt_analyze_table( $game )
#    Determine whether the other player has won.  If not,
#    try all possible moves (from $avail) for this player.
sub ttt_analyze_table {
    my $game = shift;
    my $move = shift;

    # Compute id - the index for the current position.
    #    Treat the board as a 9-digit base 3 number.  Each square#    contains 0 if it is unoccupied, 1 or 2 if it has been
    #    taken by one of the players.
    if( ! defined $move ) {
        # Empty board.
        $game->{id} = 0;
    } else {
        # A move is being tested, add its value to this id of
        # the starting position.
        my $id = $game->{id} + ($game->{turn}+1)*(3**$move);
        if( defined( my $score = $cache[$id] ) ) {
            # That resulting position was previously analyzed.
            return -1 if $score < 0;
            return 0;
        }
        my $prevgame = $game;
        # A new position - analyze it.
        $game = $game->make_move( $move );
        $game->{id} = $id;
    }

    unless ( defined $game->prepare_moves ) {
        # No moves possible.  Either the other player just won,
        # or else it is a draw.
        my $score = $game->evaluate;
        $cache[$game->{id}] = $score;
        return -1 if $score < 0;
        return 0;
    }

    # Find result of all possible moves.
    my $best_score = -1;

    while ( defined( $move = $game->next_move ) ) {
        # Make the move negating the score
        #   - what's good for the opponent is bad for us.
        my $this_score = - ttt_analyze_table( $game, $move );

        # evaluate
        $best_score = $this_score if $this_score > $best_score;
    }

    $cache[$game->{id}] = $best_score;
    return $best_score;
}

Game situations differ from other generative search situations in that they have adversaries. This makes the analysis more complicated because the goal flips every half-turn. Some algorithms, like minimax, apply only to such game situations. Other algorithms, like exhaustive search, can be applied to any type of situation. Still others apply only when, unlike in games, there is a single fixed goal.

All kinds of dynamic searches have to concern themselves with the search order among multiple choices. There is actually a continuum of ordering techniques. At one extreme is depth-first search; at the other extreme is breadth-first search.

They differ in the order that possibilities are examined. A breadth-first search examines all of the possible first choices, then all of the possible second choices (from any of the first choices), and so on. This is much like the way that an incoming tide covers a beach, extending its coverage across the entire beach with each wave, and then a bit further with each subsequent wave. A depth-first search, on the other hand, examines the first possible first choice, the first possible second choice (resulting from that first choice), the first third choice (resulting from that second choice), and so on. This is more like an octopus examining all of the nooks and crannies in one coral opening before moving on to check whether the next might contain a tasty lunch. The two searches are shown in Figure 5-2.

Figure 5-2. Breadth-first versus depth-first

The minimax algorithm is necessarily depth-first to some extent—it examines a single sequence of moves all of the way down to a final position (or the maximum depth). Then, it evaluates that position and backs up to try the next choice for the final move. The choice of depth controls the extent to which it is depth first. We already saw how chess has an exponentially huge number of positions—a completely depth-first traversal would never accomplish anything useful in a reasonable amount of time. Using a depth of 1, then a depth of 2, and so on, actually turns it into a breadth-first series of searches.

Whether depth-first or breadth-first is a better answer depends upon the particular problem. If most choices lead to an acceptable answer and at about the same depth, then a depth-first search will generally be much faster—it finds one answer quickly while a breadth-first search will have almost found many answers before it completely finds any one answer. On the other hand, if there are huge areas that do not contain an acceptable answer, then breadth-first is safer. Suppose that you wanted to determine whether, starting on your home web page, you could follow links and arrive at another page on your site. Going depth-first takes the chance that you may happen to reach the “my favorite links” page and never get back to your own site again. This would be like having that poor octopus try to completely examine a hole that lead down to the bottom of the Marianas Trench and never finding the smorgasboard of tender morsels in the shallower hole a few meters away. You will normally prefer breadth-first—it is rare to use depth-first without a limit (such as the depth argument to our minimax implementation).

Here are two routines for depth-first and breadth-first searches. They use a similar interface as the minimax routines earlier. They require that a position object provide one additional method, is_answer, which returns true if the position is a final answer to the original problem.

# $final_position = depth_first( $position )
sub depth_first {
    my @positions = shift;

    while ( my $position = pop( @positions ) ) {
        return $position if $position->is_answer;

        # If this was not the final answer, try each position that
        # can be reached from this one.
        $position->prepare_moves;
        my $move;
while ( $move = $position->next_move ) {
            push ( @positions, $position->make_move($move) );
        }
    }
    # No answer found.
    return undef;
}

# $final_position = breadth_first( $position )
sub breadth_first {
    my @positions = shift;

    while ( my $position = shift( @positions ) ) {
        return $position if $position->is_answer;

        # If this was not the final answer, try each position that
        # can be reached from this one.
        $position->prepare_moves;
        my $move;
        while ( $move = $position->next_move ) {
            push ( @positions, $position->make_move($move) );
        }
    }
    # No answer found.
    return undef;
}

The two routines look very similar. The only difference is whether positions to examine are extracted from @positions using a shift or a pop. Treating the array as a stack or a queue determines the choice between depth and breadth. Other algorithms use this same structure but with yet another ordering technique to provide an algorithm that is midway between these two. We will see a couple of them shortly.

Branch and bound

As you consider partial solutions that may be part of the optimum answer, you will keep a “cost so far” value for them. You can then easily keep the cost of each solution updated by adding the cost of the next leg of the search.

Consider Figure 5-3, a map that shows the roads between the town of Urchin and the nearby town of Sula Center. The map shows the distance and the speed limit of each road. Naturally, you never exceed the speed limit on any road, and we’ll also assume that you don’t go any slower. What is the fastest route? From the values on the map, we can compute how long it takes to drive along each road:

Start Point	End Point	Distance	Speed Limit	Travel Time
Urchin	Wolfbane Corners	54 km	90 km/h	36 min.
Wolfbane Corners	Sula Center	30 km	90 km/h	20 min.
Urchin	Sula Junction	50 km	120 km/h	25 min.
Sula Junction	Sula Center	21 km	90 km/h	14 min.

Figure 5-3. Map of towns with distances and speeds

When solving such problems, you can always examine the position that has the lowest cost-so-far and generate the possible continuations from that position. This is a reasonable way of finding the cheapest route. When the position with the lowest cost-so-far is the final destination, then you have your answer. All positions considered previously were not yet at the destination, while all positions not yet considered have a cost that is the same or worse. You now know the best route. This method is called branch and bound.

This method lies in between breadth-first and depth-first: it’s a greedy algorithm, choosing the cheapest move so far discovered, regardless of whether it is deep or shallow. To implement this requires that a position object provide a method for cost-so-far. We’ll have it inherit it from the Heap::Elem object interface. Keeping the known possible next positions on a heap, instead of a stack or queue, makes it easy to find the smallest:

# $final_position = branch_and_bound( $start_position )
sub branch_and_bound {
    my $position;

    use Heap::Fibonacci;

    my $positions = Heap::Fibonacci->new;

    $positions->add( shift );

    while ( $position = $positions->extract_minimum ) ) {
        return $position if $position->is_answer;

        # That wasn't the answer.
        # So, try each position that can be reached from here.
        $position->prepare_moves;
        my $move;
        while ( $move = $position->next_move ) {
            $positions->add( $position->make_move($move) );
        }
    }
    # No answer found.
    return undef;
}

Let’s define an appropriate object for a map route. We’ll only define here the facets of the object that deal with creating a route, using the same interface we used earlier for generating game moves. (In a real program, you’d add more methods to make use of the route once it’s been found.)

package map_route;

use Heap::Elem;

@ISA = qw(Heap::Elem);

# new - create a new map route object to try to create a
#     route from a starting node to a target node.
#
# $route = map_route->new( $start_town, $finish_town );
sub new {
    my $class = shift;
    $class    = ref($class) || $class;
    my $start = shift;
    my $end   = shift;

    return $class->SUPER::new(
        cur          => $start,
        end          => $end,
        cost_so_far  => 0,
        route_so_far => [$start],
    );
}

# cmp - compare two map routes.
#
# $cmp = $node1->cmp($node2);
sub cmp {
    my $self  = shift;
    my $other = shift;

    return $self->{cost_so_far} <=> $other->{cost_so_far};
}

# is_answer - does this route end at the destination (yet)
#
# $boolean = $route->is_answer;
sub is_answer {
    my $self = shift;
    return $self->{cur} eq $self->{end};
}

# prepare_moves - get ready to look at all valid roads.
#
# $route->prepare_moves;
sub prepare_moves {
    my $self = shift;
    $self->{edge} = -1;
}

# next_move - find next usable road.
#
# $move = $route->next_move;
sub next_move {
    my $self = shift;
    return $self->{cur}->edge( ++$self->{edge} );
}

# make_move - create a new route object that extends the
#     current route to travel the specified road.
#
# $route_new = $route->make_move( $move );
sub make_move {
    my $self = shift;
    my $edge = shift;
    my $next = $edge->dest;
    my $cost = $self->{cost_so_far} + $edge->cost;

    return $self->SUPER::new(
        cur          => $next,
        end          => $self->{end},
        cost_so_far  => $cost,
        route_so_far => [ @{$self->{route_so_far}}, $edge, $next ],
    );
}

This example needs more code, but it’s already getting too long. It needs a class for towns (nodes) and a class for roads (edges). The class for towns requires only one method to be used in this code: $town->edge($n) should return a reference to one of the roads leading from $town (or undef if $n is higher than the index of the last road). The class for roads has two methods: $road->dest returns the town at the end of that road, and $road->cost returns the time required to traverse that road. We omit the code to build town and road objects from the previous table. You can find relevant code in Chapter 8.

With those additional classes defined and initialized to contain the map in Figure 5-3, and references to the towns Urchin and Sula Center in the variables $urchin and $sula, respectively, you would find the fastest route from Urchin to Sula Center with this code:

$start_route = map_route->new( $urchin, $sula );
$best_route = branch_and_bound( $start_route );

When this code is done, the branch_and_bound function uses its heap to continually process the shortest route found so far. Initially, the only route is the route of length 0—we haven’t left Urchin. The following table shows how entries get added to the heap and when they get examined. In each iteration of the outer while loop, one entry gets removed from the heap, and a number of entries get added:

Iteration Added	Iteration Removed	Cost So Far	Route So Far
0	1	0	Urchin
1	2	25	Urchin → Sula Junction
1	3	36	Urchin → Wolfbane Corners
2	4 (success)	39	Urchin → Sula Junction → Sula Center
2	never	50	Urchin → Sula Junction → Urchin
3	never	44	Urchin → Wolfbane Corners → Sula Center
3	never	72	Urchin → Wolfbane Corners → Urchin

So, the best route from Urchin to Sula Center is to go through Wolfbane Corners.

The A* algorithm

The branch and bound algorithm can be improved in many cases if at each stopping point you can compute a minimum distance remaining to the final goal. For instance, on a road map the shortest route between two points will never be shorter than the straight line connecting those points (but it will be longer if there is no road that follows that straight line).

Instead of ordering by cost-so-far, the A* algorithm orders by the total of cost-so-far and the minimum remaining distance. As before, it doesn’t stop when the first road that leads to the target is seen, but rather when the first route that has reached the target is the next one to consider. When the next path to consider is already at the target, it must have a minimum remaining distance of 0 (and this “minimum” is actually exact). Because we require that minima never be higher than the correct value, no other postions need be examined—there might be unexamined answers that, at a minimum, are equal, but none of them can be better. This algorithm provides savings over branch and bound whenever there are positions that haven’t been considered yet have a cost so far that is less than the final cost, but whose minimum remainder is sufficiently high that it needn’t be considered.

In Figure 5-4, the straight-line distances provide part of a lower bound on the shortest possible time. The other limit to use is the maximum speed limit found anywhere on the map—120 km/h. Using these values gives a minimum cost: the time from any point to Sula Center must be at least as much as this “crow’s flight” distance driven at that maximum speed:

Location	Straight Line Distance	Minimum Cost
Urchin	50 km	25 min.
Sula Junction	4 km	2 min.
Wolfbane Corners	8 km	4 min.
Sula Center	0 km	0 min.

Figure 5-4. Minimum time determined by route “as the crow flies”

The code for A* is almost identical to branch and bound—in fact, the only difference is that the cmp metric adds the minimum remaining cost to cost_so_far. This requires that map objects provide a method to compute a minimum cost—straight line distance to the target divided by maximum speed limit. So, the only difference is that the cmp function is changed to the following:

package map_route_min_possible;

@ISA = qw(map_route);

# cmp - compare two map routes.
#
# $cmp = $node1->cmp($node2);
# Compare two heaped positions.
sub cmp {
    my $self   = shift->[0];
    my $other  = shift->[0];
    my $target = $self->{end};
    return  ($self->{cost_so_far} + $self->{cur}->min_cost($target) )
        <=> ($other->{cost_so_far} + $other->{cur}->min_cost($target) );
}

# To use A* searching:
$start_route = map_route_min_possible->new( $urchin, $sula );
$best_route = branch_and_bound( $start_route );

Because the code is nearly identical, you can see that branch and bound is just a special case of A*. It always uses a minimum remaining cost of 0. That’s the most conservative way of meeting the requirement that the minimum mustn’t exceed the true remaining cost; as we see in the following table, the more aggressive minimum speeds up the search process:

Iteration Added	Iteration Removed	Cost So Far	Minimum Remaining	Comparison Cost	Route So Far
0	1	0	25	25	Urchin
1	2	25	2	27	Urchin → Sula Junction
1	never	36	4	40	Urchin → Wolfbane Corners
2	never	50	25	75	Urchin → Sula Junction → Urchin
2	3 (success)	39	0	39	Urchin → Sula Junction → Sula Center

Notice that this time only three routes are examined. Routes from Wolfbane Corners are never examined because even if there was a perfectly straight maximum-speed highway between them, it would still be longer than the route through Sula Junction. While the A* algorithm only saves one route generation on this tiny map, it can save far more on a larger graph. You will see additional algorithms for this type of problem in Chapter 8.