Parallelizing Minimax with alpha-beta pruning using MPI

Question

I am currently busy with a project that requires you to use the minimax with AB pruning. I have successfully implemented a serial version of the program

//Assume maximizing player is WHITE
int minimax_move(int *current_board, int player, int *chosen_move, int alpha, int beta) {
    int *moves_list;//capture the moves for a board
    int moves_len;
    int opponent = BLACK;
    if (player == BLACK) {
        opponent = WHITE;
    }

    get_moves_list(current_board,&moves_list,&moves_len,player);    
    //No Move to be generated
    if (moves_list[0] == 0) {
        *chosen_move = -1;
    } else {
        //Remember the best move
        int best_move_value = INT_MIN;
        int best_move = moves_list[1];

        //Try all the moves
        for (int i = 1; i <= moves_len; i++) {
            int *temp_board = (int *) malloc(sizeof(int) * BOARDSIZE);
            copy_board(current_board,temp_board);
            apply_move(&temp_board,moves_list[i],player);
            //Initial Call to minimax_value
            int value = minimax_value(temp_board,player,opponent,1,alpha,beta);
            //Remember best move
            if (value > best_move_value) {
                best_move_value = value;
                best_move = moves_list[i];
            }
        }
        //Set the chosen move
        *chosen_move = best_move;
        printc("Chosen Move is: %d\nFrom %s\n",*chosen_move,get_turn_player(player));
    }
    return *chosen_move;
}

//original_turn -> maximizing player
//current_turn -> minimizing_player
//Current turn is what alternates the turn player when simulating move look aheads
//The maximizing player is established in minimax_moves
int minimax_value(int *current_state,int original_turn, int current_turn,int depth,int a,int b) {
    if (depth == MAXDEPTH || is_game_over(current_state)) {
        return evaluate_board(current_state);
    }

    int *moves_list;
    int moves_len;
    int opponent = BLACK;
    if (current_turn == BLACK) {
        opponent = WHITE;
    }

    get_moves_list(current_state,&moves_list,&moves_len,current_turn);
    //if no moves, skip to next player's (opponent) turn
    if (moves_list[0] == 0) {
        return minimax_value(board,original_turn,opponent,depth+1,a,b);
    } else {
        //Remember the best move - Setting the limits
        //For max player
        int best_move_value = INT_MIN;
        int alpha = a;
        int beta = b;
        if (original_turn != current_turn) {
            //original_turn -> max player
            //current_tunr -> min player
            best_move_value = INT_MAX;
        }

        for (int i = 1; i <= moves_len; i++) {
            //Apply a move to the board
            int *temp_board = (int *) malloc(sizeof(int) * BOARDSIZE);
            copy_board(current_state,temp_board);
            apply_move(&temp_board,moves_list[i],current_turn);
            //Recursive calls
            int value = minimax_value(temp_board,original_turn,opponent,depth+1,alpha,beta);
            //Remember best move
            //MAX PLAYER
            if (original_turn == current_turn) {
                if (value > best_move_value) {
                    best_move_value = value;
                }

                if (value > alpha) {
                    alpha = value;
                }
            } else {
                //MIN PLAYER
                if (value < best_move_value) {
                    best_move_value = value;
                }

                if (value < beta) {
                    beta = value;
                }
            }

            //Alpha-Beta pruning
            printc("ALPHA: %d - BETA: %d\n",alpha,beta);
            if (beta <= alpha) {
                printc("\n\nPRUNED\n\n");
                break;
            }
        }
        return best_move_value;
    }
    //return -1; ERROR
}

The project requires me to use MPI to parallelize the minimax algorithm. I have no idea where to start. I have read http://www.pressibus.org/ataxx/autre/minimax/node6.html#SECTION00060000000000000000 but am no closer to solving the problem as I do not understand the psuedo-code written.

My idea was to somehow scatter the moves_list generated in minimax_move() amongst (n-1) slave processes where 1 process will be the master process. However, the first call to minimax_move() yields a move_list of length 3, and we can assume that the number of processors that will be used to run the program will be >= 4.

I would appreciate a starting point on how to solve this as I cannot seem to wrap my head around how I would use MPI to parallelize this. It has to be done using MPI.

Answer 1

Ultimately alpha-beta mini-maxing requires you to score every tree generated by a turn and choose the best one. It sounds like your task is to parallelise the calculation of the scores, you should be able to utilise different processors to score different trees.