CODEWITHSUNDEEP
artificial-intelligenceminimaxgomoku
Tam Chak Kuen
Tam Chak Kuen

Reputation: 31

How to improve Alpha-beta pruning performance

Here is my code for gomoku AI. So now my AI is currently run over 5 seconds but the time limit is 5 seconds. I am trying to improve the performance so I try move ordering but it seems not works. I calculate the score first in getChildStates(int player) function and then sort the vector into a descending order. But it just not work. Can some body help me?

Also, my depth is two. transpotation table seems not help, so I haven't try it.

int minimax(int depth, GameState state, bool maximizingPlayer, int alpha, int beta)
{
if (depth == 2)
    return state.score;

if (maximizingPlayer)
{
    vector<GameState> children = state.getChildStates(1);
    sort(children.begin(), children.end(), greaterA());

    int best = MIN;

    for (auto& value : children) {



        int val = minimax(depth + 1, value,
            false, alpha, beta);


        int oldBest = best;

        best = max(best, val);
        alpha = max(alpha, best);

        if (depth == 0 && oldBest != best){
            bestMoveX = value.lastMove.x;
            bestMoveY = value.lastMove.y;

        }


        // Alpha Beta Pruning
        if (beta <= alpha)
            break;

    }
    return best;
}
else
{

    vector<GameState> children = state.getChildStates(2);

    sort(children.begin(), children.end(),greaterA());

    int best = MAX;
    // Recur for left and right children
    for (auto& value : children) {
        int val = minimax(depth + 1, value,
            true, alpha, beta);

        best = min(best, val);
        beta = min(beta, best);

        // Alpha Beta Pruning
        if (beta <= alpha)
            break;
    }
    return best;
}

}

Upvotes: 2

Views: 6159

Answers (1)

ObliteratedJillo
ObliteratedJillo

Reputation: 5166

I won't recommend sorting the game states to prioritize the states thereby enabling force move as per set timeout. Even with alpha-beta pruning, the minimax tree may be just too big. For reference you can have a look in the GNU Chess at github. Here are some options to reduce the best move search time:

1) Reduce depth of search.

2) Weed out redundant moves from the possible moves.

3) Use multi-threading in the first ply to gain speed

4) Allow quiescence search mode, so that minimax tree branches could continue generating in the background when the human opponent is still thinking.

5) Instead of generating the minimax tree for every move, you can think about reusable minimax tree where you only pruned moves already made and only continue generating one ply every iteration ( instead of the whole tree, see this article ).

Upvotes: 0

Related Questions