Рекурсия MiniMax неверна

Question

Я пытаюсь написать ИИ, чтобы играть в ConnectK (игра для подключения 4, для которой требуется соединить k штук, а сила тяжести может быть включена или выключена). И вот моя функция, чтобы получить лучший ход, используя алгоритм Minimax.

struct MoveNode //This struct is defined in header file 
{ 
    MoveNode() {}; 
    MoveNode(int Score) : score(Score) {} 
    Move move; 
    int score; 
}; 

MoveNode AIShell::getBestMove(int depth, int player) {//Find the best move using MiniMax 
    if (depth <= 0) 
     return MoveNode(heuristic()); 
    else if (boardIsFull() && getWinner() == 0)//Tie 
     return 0; 
    else if (getWinner() == AI_PIECE) 
     return 100000; 
    else if (getWinner() == HUMAN_PIECE) 
     return -100000; 

    std::vector<MoveNode> mds; 

    for (auto i : getMoveList()) {//For each available move 
     MoveNode md; 
     md.move = i; //i is Move(col,row) 
     gameState[i.col][i.row] = player; 
     if (player == AI_PIECE) { 
      md.score = getBestMove(depth - 1, HUMAN_PIECE).score; 
     } 
     else { 
      md.score = getBestMove(depth - 1, AI_PIECE).score; 
     } 
     mds.push_back(md); 
    } 

    //Get the best move after recursion 
    int best_move_index = 0; 
    if (player == AI_PIECE) { 
     int best_score = -1000000; 
     for (int i = 0; i < mds.size(); i++) { 
      if (mds[i].score > best_score) { 
       best_move_index = i; 
       best_score = mds[i].score; 
      } 
     } 
    } else if (player == HUMAN_PIECE) { 
     int best_score = 1000000; 
     for (int i = 0; i < mds.size(); i++) { 
      if (mds[i].score < best_score) { 
       best_move_index = i; 
       best_score = mds[i].score; 
      } 
     } 
    } 
    return mds[best_move_index]; 
} 

Функция getBestMove(), кажется, делает что-то, что я не совсем ожидаю. Функция попытается получить лучший ход перед рекурсией, а поворот AI и поворот человека не будут рекурсивно обрабатываться равномерно. И я потратил довольно много времени на отладку этой функции, но до сих пор не могу понять. Извините за мой плохой английский, но я бы очень признателен за помощь здесь. Заранее спасибо.

Answer 1

Вы возвращаете лучший индекс перемещения. Минимаксное дерево должно возвращать значение узлов (best_score), а не лучший ход. Единственный раз, когда вы должны вернуть лучший ход, - это корневой узел, так что поиск заканчивается, давая вам лучший ход.