oreilly.comSafari Books Online.Conferences.


AddThis Social Bookmark Button

Building a Game Engine with Cocoa, Part 3
Pages: 1, 2, 3

A particular implementation of minimax that simplifies the coding a little bit by taking advantage of the zero sum property of a game like LOA is negamax. It works exactly the same as minimax except that there's no need for separate min and max functions. From Wikipedia, the pseudocode for negamax follows:

function negamax(node, depth, alpha, beta)
    if node is a terminal node or depth = 0
        return the heuristic value of node
        foreach child of node
            alpha := max(alpha, -negamax(child, depth-1, -beta, -alpha))
            {the following if statement constitutes alpha-beta pruning}
            if alpha >= beta
                return beta
        return alpha

You should take a moment to convince yourself that if you remove the alpha/beta parameters and the conditional statement that constitutes alpha-beta pruning, then you're left with a search that's exactly equivalent to minimax--the key being that whenever negamax is recursively called, its returned value is inverted, creating a min/max effect.

Our negamax search written in Objective-C looks strikingly similar to the pseudocode and is defined in GameBoard's AlphaBeta category, along with a method for defining a heuristic for a given board position.

- (int)alphaBetaWithDepth:(int)depth andAlpha:(int)alpha andBeta:(int)beta {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    if (depth == 0)
        return [self evaluateBoard];
    NSArray *moves = [self generateMoves];
    NSEnumerator *e = [moves objectEnumerator];
    NSValue *move;
    GameBoardMove gbm;
    while (move = [e nextObject]) {
        [move getValue:&gbm];
        [self makeMove:gbm];
        int val = -[self alphaBetaWithDepth:(depth-1) andAlpha:(-beta) andBeta:(-alpha)];
        [self unmakeMove:gbm];
        if (val > alpha) {
            alpha = val; // best that can be forced on the opponent

            //keep track of which is the current player's best
            if (depth == SEARCH_DEPTH)
                memcpy(&bestMove, &gbm, sizeof(GameBoardMove));    
        if (alpha >= beta) {
            [pool release];
            return beta; // opponent will not allow this.
    [pool release];
    return alpha; // the best we can force on the opponent

Aside from an extra conditional to explicitly keep track of the best move at any given time, the only other addition worth pointing out is Cocoa-specific. It's the first line that explicitly creates an autorelease pool. If you remove the three lines that create and release the pool, you can use top or any other tool that reports memory usage and see that our board game suddenly hogs massive amounts of memory. But why? All of the objects in alphaBetaWithDepth:andAlpha:andBeta should be autoreleased for us, right? Well, yes--except that the recursion taking place is so tight that the event loop never gets a chance to release them. Apple's Management Programming Guide for Cocoa mentions this, and it is a well known issue for scenarios such as these.

The sample heuristic evaluateBoard that's given in GameBoard's AlphaBeta category has the objective of trying to capture as many of the other player's pieces as possible. For LOA, this approach is not a very good one because capturing pieces leaves the opponent with fewer to connect themselves. Still, it is simple enough that it's immediately evident if it's working correctly or not, which is helpful when you're initially implementing your search algorithm. Besides, this is where you come in. Now that the work of developing an infrastructure is in place, you get to take some time to do the fun work of writing a clever heuristic function.

Writing a heuristic for a game like LOA is a lot of fun, because while the objective is to connect all of your pieces together, there are many subtle conditions that you should take into account when evaluating the board. For example, in addition to weighing your score according to how many of your own pieces are connected, you might also want to consider how many "orphan" pieces there are on the board as well. An orphan piece is one that is totally surrounded in such a way that it can't move anywhere--making it impossible to win unless the piece gets rescued first. Mark Winands wrote an entire thesis about searching the space in LOA that takes this and many other factors into consideration. It is a must-have resource if you're doing any work at all with LOA.

Have Fun

Take some time this weekend to cook up a custom heuristic, and play against it to see how well it does. Unless you're planning on making changes to the search algorithm itself, all of your work can probably be done in GameBoard's AlphaBeta category by examining and manipulating the board array. And remember: there's no reason to prematurely optimize. Efficiency is very important in a game tree search, but stick with a shallow search depth (say, three) and make sure your heuristic is good before trying to optimize it. Besides, you can make a number of improvements upon the search itself and the move generation before you optimize your heuristic.

If you do want to start optimizing, however, one obvious place to start is with GameBoard's generateMoves method. Currently, this method is stashing Coord structs into NSArrays by first wrapping them up with the COORD_OBJECT macro. A straightforward improvement would be to redesign generateMoves to take advantage ofthe C++ vector data structure, like GameBoard's Connection category does. Because generateMoves is called for every single node that's evaluated in the search tree, the performance improvement could be quite noticeable.

Although this is the last scheduled article in this series, there's still a lot of room for future enhancement. The UI could be spiffed up, the game tree search could be expanded to something like negascout, optimizations could take place based upon performance profiling, etc. The sky's the limit. If you'd like to see future articles that expand on this framework, or if you have questions about anything, please leave your comments below.

Matthew Russell is a computer scientist from middle Tennessee; and serves Digital Reasoning Systems as the Director of Advanced Technology. Hacking and writing are two activities essential to his renaissance man regimen.

Return to the Mac DevCenter.