How to improve Alpha-beta pruning performance

Question

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;
}

}

Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. "just not works" is not a problem specification. — Prune, Apr 25 '18 at 00:08

seccpur · Answer 1 · 2018-04-26T08:17:00.143

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 ).

How to improve Alpha-beta pruning performance

1 Answers1