Obviously, the number of positions arising even after only a few moves grows very fast; in most midgame positions, each players have about ten moves each, so to look ahead only nine moves (a search to depth nine in programmer lingo) results in a billion (10^9) positions to investigate. Fortunately, in can be proved mathematically that a program need not consider all these positions in order to find the best move. Instead a procedure called alpha-beta pruning, invented in the mid-70's by Donald Knuth and others, is used which greatly reduces the number of positions which need be examined. The key idea is the following: If the opponent has a response to one of my moves which is strong enough to prove that the move I was considering cannot possibly be the best move, there is no point looking for even stronger responses - I will not play into that variation anyway. When formalized, this simple observation greatly reduces the number of positions that need to be searched. Variations of this algorithm are used in all strong Othello programs (as well as programs for other board games such as chess and checkers). Zebra typically only considers 100'000 - 500'000 positions when looking 9 moves ahead; a great reduction compared to the 1'000'000'000 positions which would have to be considered without alpha-beta pruning. Zebra uses a variation called aspiration nega-scout, invented by Alexander Reinefeld.
In addition to the alpha-beta algorithm, Zebra also uses a selective search mechanism. The idea is very simple and resembles the thinking of human players: In most positions, many moves are obviously bad and need only be looked at long enough to determine that they are bad. This is usually implemented as follows: When searching a position to depth 12 (i.e., 12 moves ahead), Zebra starts by searching all moves available to depth 4 and discards the moves which seemed really bad when searched to depth 4. The remaining moves are searched to depth 12. The concept of "really bad" is formalized by generating lots of statistics of how well a search to depth 4 predicts the result of a search to depth 12. This procedure is called Multi Prob-Cut and was invented by Michael Buro. The example above uses the "cut pair" 4/12; Zebra uses 15 different cut pairs corresponding to search depths 3 - 18.
The search algorithms described above enable Zebra to look 18 - 27 moves ahead in the midgame, often finding subtle tactical traps that only the top computer opponents are able to detect. The search speed is about 1'300'000 - 1'500'000 positions/second in the midgame and 4'000'000 - 7'000'000 positions/second in the endgame. (These numbers are obtained on an AMD Thunderbird/1.33GHz.)