Improving Minimax Algorithm

Question

Currently I'm working on an Othello/Reversi game in c++. I have it "finished" except that the Minimax algorithm I'm using for the Computer player is painfully slow when I set it at a depth that produces a semi-challenging AI.

The basic setup of my game is that the board is represented by a 2-dimensional array, with each cell on the board assigned a value in the array (xMarker, oMarker, or underscore).

Here's the minimax algorithm so far:

signed int Computer::simulate(Board b, int depth, int tempMarker) {

if (depth > MAX_DEPTH || b.gameOver()) {
    int oppMarker = (marker == xMarker) ? oMarker : xMarker;
    return b.countForMarker(marker) - b.countForMarker(oppMarker);
}

//if we're simulating  our turn, we want to find the highest value (so we set our start at -64)
//if we're simulating the opponent's turn, we want to find the lowest value (so we set our start at 64)
signed int start = (tempMarker == marker) ? -64 : 64;

for (int x = 0; x < b.size; x++) {
    for (int y = 0; y < b.size; y++) {

        if (b.markerArray[x][y] == underscore) {

            Board *c = b.duplicate();

            if(c->checkForFlips(Point(x,y), tempMarker, true) > 0) {

                int newMarker = (tempMarker == xMarker) ? oMarker : xMarker;
                int r = simulate(*c, depth+1, newMarker);

                //'marker' is the marker assigned to our player (the computer), if it's our turn, we want the highest value
                if (tempMarker == marker) {
                    if(r > start) start = r;
                } else {
                //if it's the opponent's turn, we want the lowest value
                    if(r < start) start = r;
                }

            }

            delete c;

        }

    }
}

return start;

}

The function checkForFlips() returns the number of flips that would result from playing at the given cell. MAX_DEPTH is set to 6 at the moment, and it's quite slow (maybe about 10-15 seconds per play)

The only idea I've come up with so far would be to store the tree each time, and then pick up from where I left off, but I'm not sure how to go about implementing that or if it would be too effective. Any ideas or suggestions would be appreciated!

Answer 1

Calculating minimax is slow. The first possible optimization is alpha-beta pruning: http://en.wikipedia.org/wiki/Alpha-beta_pruning

Answer 2

You shouldn't duplicate board, that's very inefficient. Make the move before you call yourself recursively, but save enough information to undo the same move after you return from the recursive call. That way you only need one board.

But Shiroko is right, alpha-beta pruning is the first step.