Search

Modern game programs gain their power from extending the knowledge coded into their evaluation functions through tree search. This is where the machine's "intelligence" is located. Before we get into the mechanics of game trees, though, let us first discuss what they are.

Search Tree

The diagram above shows a portion of the game tree for Noughts and Crosses. In the diagram, the arrows indicate moves. At the top of the tree is the starting position. The next level contains the various possible moves for O (obviously some have been omitted for space reasons). The next level contains all possible replies by X, followed by possible replies by O, and so forth. Each level (or move by one player) is referred to as a ply, while the various positions in the tree are called nodes. A node in which the game is finished is called a leaf node.

Minimax
Tree search generally works by assigning scores to the leaf nodes - perhaps 1 for a win by O, -1 for a win by X or 0 for a draw. One then backs up one ply, and considers the scores in the child nodes from the perspective of the side to move. Assuming that the side to move is playing to win, the score at the parent node is equal to the best child score from the perspective of the side to move at the parent node. In this way, the scores are "backed up" the tree to the root node. The computer will then make the move with the highest score from it's perspective at the root node. Given this kind of win/lose/draw evaluation at the leaf nodes of the full game tree, the computer can play perfectly.

It is obvious that in Noughts and Crosses, the entire game tree is only nine ply deep. In addition, the number of available moves ("branching factor") decrements with each additional ply. This makes the size of the game tree conveniently small - in fact, there are less than a million possible positions in the tree. However, in a game like Morabaraba the branching factor does not decrease, and in fact can increase in the mid-game (where captures may introduce significant branching) and the endgame (where "flying cows" introduce large amounts of branching). In addition, the game tree is considerably deeper - although I haven't done the analysis, 50 ply or more seems quite reasonable. Due to the astronomical number of nodes involved, therefore, it may be computationally infeasible to exhaustively analyse the tree to its full depth, even if you own a supercomputer - although note that the game tree for Nine Men's Morris has been solved by a combination of retrograde analysis and search. However, you certainly can't even come close in any reasonable period of time. For this reason, game programmers compromise by searching the tree only to a limited depth. Obviously, the nodes at this limited depth are much more difficult to score accurately, and in fact Morabaraba software will generally use an evaluation function which "guesses" to what extent White or Black has an advantage. This guess is based on heuristics programmed into the evaluation function.

Even so, however, the game tree grows exponentially with each extra ply. It is therefore impossible with the limited storage available to build a game tree of any useful size in the computer's memory. That's where Minimax comes in. The Minimax algorithm is a piece of intense cuteness first described by Claude Shannon in 1950, which enables a program to navigate the game tree one "line" (series of moves) at a time, scoring the leaf nodes and backing the scores up the game tree as it goes. This is achieved by recursively calling itself for each child node up to a defined maximum depth. Negamax is a small modification, where each return value from a recursive call is negated. This simplifies choosing the best move from the side-to-move's perspective, as the largest value is always the best, whichever side is to move. Consider the following Negamax pseudocode:

 

Function Negamax(Depth as integer) as integer
If Depth = 0
Score = Evaluation of Position
else
Generate List of Moves
Score = -INFINITY
For each Move in the move list
Execute the Move
MoveScore = -Negamax(Depth -1)
If MoveScore > Score the Score = MoveScore
Undo the Move
Next
End If
Return Score
End Function

By calling Negamax with some value for depth on each move available in the root node, you will obtain a score for each move - you simply need to make the move with the best score.

At this point I should mention some performance considerations. Your evaluation function is called for each leaf node - at the widest portion of the tree. It is therefore almost certain to be called a massive number of times, making speed critical in this area. It is generally true that a more accurate evaluation function will run slower, and some balance needs to be found. It is also true that a relatively simple evaluation function, applied to a tree of reasonable depth, can produce surprisingly sophisticated results. The process of searching the tree "enriches" the knowledge contained in the evaluation function. This is called artificial intelligence.

Alpha-Beta Pruning
Alpha-beta pruning is a cunning device whereby the effective branching factor of the tree search is reduced, while guaranteeing the same result as a full Minimax search of the same depth. This is achieved by "pruning" (omitting) irrelevant portions of the game tree. Although it is generally considered difficult to wrap your brain around alpha-beta, it is definitely worthwhile: the experts say that when implemented properly, alpha-beta can double the depth of your search within the same time limits. Given equivalent evaluation functions, an eight-ply search will shred a four-ply search.

AlphaBeta Search

Imagine you're doing a minimax search of the tree given above. You've searched f, and found it's children's evaluations to be 11, 12, 7 and 9; at this level of search, it is the first player to move. We would expect him to choose the best of these values (12), and so the minimax value of f is 12.

Next, you start searching g. It's first child returns a value of 15. Whatever happens, therefore, you know that the value of g will be at least 15. However, you know the since f is only worth 12, at node b player 2 will always select f's score of 12 rather than going for a score of at least 15. In this way, we do not have to evaluate the rest of g's children; we can prune them, secure in the knowledge that we are not changing the ultimate evaluation. Now imagine that the pruned children of g in fact contain subtrees of their own - by pruning these, we have saved a considerable amount of labour. Consider the diagram below:

Deep Prune

Continuing from the previous example, we've found that g, h and I are all better than 12, so we know that the overall evaluation for b is 12. Now we search node c, and two levels down we see an evaluation of 10 at node n.

We can use a more complicated line of reasoning to prune again. We know that n will return 10 or smaller. We don't know whether this value of 10 or smaller will be returned at j as well, or whether one of j's other children will be better. If a value of 10 or smaller is returned from j to c, we can prune at c because it has a better sibling (b). So in this case, further exploration of n's children is pointless. In the other case, where one of j's other children returns a value better than 10, further exploration of n's children is also pointless. So we can safely prune n's other children as soon as we see 10.

In general, when a returned value is better than the value of a sibling an even number of levels up in the tree, we can return immediately. This is called a cutoff. If we pass the minimum value of any of these siblings in as a parameter beta to the search, we can do this pruning very efficiently. We also use another parameter alpha to keep track of the siblings at odd levels of the tree. As you will see in the pseudocode below, based on the negamax code given previously, we simply swap the values of alpha and beta as we recurse down the tree.

 

Function AlphaBeta(Depth as integer, Alpha as integer, Beta as integer) as integer

If (Depth = 0) or (game is over)
Score = Evaluation of Position
else
Generate List of Moves
Sort List of Moves
For each Move in the move list
Execute the Move
MoveScore = -AlphaBeta(Depth -1, -Beta, -Alpha)
Undo the Move
If MoveScore >= Beta return MoveScore
If MoveScore > Alpha then Alpha = MoveScore
Next
End If
Return Alpha
End Function

Something which may be a little enigmatic in this pseudocode is the "sort list of moves" step. The idea here is that by considering the best moves first, we will get more cutoffs when considering weaker moves. In this way, the alpha-beta algorithm becomes most efficient. Unfortunately, though, we do not know which is the best move - that's why we're doing this search! The answer is of course to guess the value of each move. This can be done in several different ways; you could use your evaluation function to guess the value of each move, or you could use a shallow alpha-beta search to obtain a more accurate result. You should experiment with this to find the right performance balance. Often slowing things down a bit by ordering the move list properly can actually shorten the search because of the increased number of cutoffs.

Time Control
A critical question, with both MiniMax and alpha-beta, is this: how do I know how deep to search? Obviously, you want to go as deep as you can, in order to arrive at the best level of play. However, if your search exceeds the time control, you will forfeit the game. It is very difficult to know before starting the search how long a search of any given depth will take. The solution used by competitive AI programs is called iterative deepening. The idea is to start with a shallow search and increment the search depth and re-search the position until time runs out. In this case, when time does run out, you will have a good move to make - the result of the last completed search.

Most will immediately object that it's enormously wasteful to do a 2-ply, then a 3-ply, then a 4-ply, then an n-ply search, but it really isn't that bad. In the first instance, the last search will likely take more time than all of the previous searches together. The cost of doing the shallow searches is quite small, especially when weighed against the possibility of forfeiting the game. In the second instance, results of earlier searches can be used to sort the move list at the root node more accurately, thus obtaining more cutoffs in the deeper search. This may even reduce the overall search time.

Refinements
A number of refinements have been suggested and tried. These include the killer and history heuristics, aspiration search, the null move, memory-enhanced test (MTD(f) ), NegaScout and others. These are usually a small modification of the alpha-beta algorithm which seeks to reduce the size of the tree searched. The utility and riskiness of many of them is still the subject of great contention, and therefore they are not discussed here. Should you wish to look into these, a great deal of material is available on the Internet.