Распараллеливание минимакса с альфа-бета-отсечкой с использованием MPI - PullRequest
Новая
       70

Распараллеливание минимакса с альфа-бета-отсечкой с использованием MPI

0 голосов
/ 28 апреля 2020

В настоящее время я занят проектом, требующим использования минимакса с отсечкой AB. Я успешно реализовал серийную версию программы 

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

В проекте требуется, чтобы я использовал MPI для распараллеливания минимаксного алгоритма. Я понятия не имею, с чего начать. Я прочитал http://www.pressibus.org/ataxx/autre/minimax/node6.html#SECTION00060000000000000000, но не приблизился к решению проблемы, поскольку не понимаю написанного псевдо-кода.

Моя идея состояла в том, чтобы как-то разбросить список move_list, сгенерированный в minimax_move() среди (n-1) подчиненных процессов, где 1 процесс будет основным процессом. Однако первый вызов minimax_move() дает move_list длины 3, и мы можем предположить, что число процессоров, которые будут использоваться для запуска программы, будет> = 4.

Буду признателен отправная точка для решения этой проблемы, поскольку я не могу понять, как бы я использовал MPI для распараллеливания этого. Это должно быть сделано с использованием MPI.

1 Ответ

0 голосов
/ 29 апреля 2020

В конечном счете, альфа-бета мини-максинг требует, чтобы вы оценили каждое дерево, созданное ходом, и выбрали лучшее. Похоже, ваша задача состоит в том, чтобы распараллелить вычисление баллов, вы должны иметь возможность использовать разные процессоры для оценки разных деревьев.

...