CODEWITHSUNDEEP
c++algorithm
williamg
williamg

Reputation: 2758

Improving Minimax Algorithm

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!

Upvotes: 5

Views: 4367

Answers (4)

jcolen19
jcolen19

Reputation: 318

The most obvious way to improve it would be through alpha-beta pruning or negascout.

However, if you want to stick with minimax, you can't make it go too fast, as it is a brute force algorithm. One way to improve it would be to change it to Negamax, which would get rid of some of the logic required in this code. Another way would be to use a one dimensional array for the board instead of Board. To make calculations easier, use a length of 100, so the positions are in row-column form(e.g. index 27 is row 2, column 7).

But if you want it to go faster, try pruning.

Upvotes: 0

user180326
user180326

Reputation:

@Shiroko's suggestion is great, but there are more optimization opportunities.

You pass the state of the Board by value, and then copy it inside the loop. I'd pass the Board as a pointer or as const Board& b. If this is still expensive, you could use a poinger to a single board, and reverse every move after you evaluate it. In any case don't allocate it on the heap.

You can also run this algorithm on multiple cores. You will need to write a variation of the for loop at the first level using openmp (or equivalent).

Upvotes: 0

jahhaj
jahhaj

Reputation: 793

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.

Upvotes: 4

Shiroko
Shiroko

Reputation: 1427

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

Upvotes: 5

Related Questions