Estou trabalhando em uma IA para um jogo e quero usar oMínimo máximo algoritmo com oPoda alfa-beta.

Eu tenho uma idéia aproximada de como funciona, mas ainda não consigo escrever o código do zero, por isso passei os últimos dois dias procurando algum tipo de pseudocódigo online.

Meu problema é que todos os pseudocódigos que encontrei on-line parecem basear-se em encontrar o valor para a melhor jogada, enquanto preciso retornar a melhor jogada em si e não um número.

Meu código atual é baseado neste pseudocódigo (fonte)

minimax(level, player, alpha, beta){  // player may be "computer" or "opponent"
    if (gameover || level == 0)
       return score
    children = all valid moves for this "player"
    if (player is computer, i.e., max's turn){
       // Find max and store in alpha
       for each child {
          score = minimax(level - 1, opponent, alpha, beta)
          if (score > alpha) alpha = score
          if (alpha >= beta) break;  // beta cut-off
       }
       return alpha
    } else (player is opponent, i.e., min's turn)
       // Find min and store in beta
       for each child {
          score = minimax(level - 1, computer, alpha, beta)
          if (score < beta) beta = score
          if (alpha >= beta) break;  // alpha cut-off
       }
       return beta
    }
}

// Initial call with alpha=-inf and beta=inf
minimax(2, computer, -inf, +inf)

Como você pode ver, esse código retorna um número e acho que isso é necessário para fazer tudo funcionar (já que o número retornado é usado durante a recursão).

Por isso, pensei em usar uma variável externa para armazenar a melhor jogada, e foi assim que alterei o código anterior:

minimax(level, player, alpha, beta){  // player may be "computer" or "opponent"
    if (gameover || level == 0)
       return score
    children = all valid moves for this "player"
    if (player is computer, i.e., max's turn){
       // Find max and store in alpha
       for each child {
          score = minimax(level - 1, opponent, alpha, beta)
          if (score > alpha) {
              alpha = score
              bestMove = current child // ROW THAT I ADDED TO UPDATE THE BEST MOVE
          }
          if (alpha >= beta) break;  // beta cut-off
       }
       return alpha
    } else (player is opponent, i.e., min's turn)
       // Find min and store in beta
       for each child {
          score = minimax(level - 1, computer, alpha, beta)
          if (score < beta) beta = score
          if (alpha >= beta) break;  // alpha cut-off
       }
       return beta
    }
}

// Initial call with alpha=-inf and beta=inf
minimax(2, computer, -inf, +inf)

Agora, é assim que faz sentido para mim, porque precisamos atualizar a melhor jogada apenas se for a vez do jogador e se a jogada for melhor que a anterior.

Então, enquanto eu acho que isso está correto (mesmo que eu não tenha 100% de certeza), ofonte também tem umJava implementação que atualiza obestMove mesmo noscore < beta caso e eu não entendo o porquê.

Tentar com essa implementação levou meu código a escolher a melhor jogada do jogador oponente, o que não parece correto (supondo que eu seja o jogador preto, estou procurando a melhor jogada que posso fazer) Estou esperando um movimento "preto" e não um "branco").

Não sei se meu pseudocódigo (o segundo) é a maneira correta de encontrar a melhor jogada usandoMínimo máximo compoda alfa-beta ou se eu precisar atualizar a melhor jogada, mesmo nopontuação <beta caso.

Por favor, fique à vontade para sugerir qualquer novo e melhor pseudocódigo, se preferir, não estou vinculado a nada e não me importo de reescrever algum código, se for melhor que o meu.

EDITAR:

Como não consigo entender as respostas, acho que talvez a pergunta não pergunte o que quero saber, então estou tentando escrevê-la melhor aqui.

Desde que eu queira obter a melhor jogada apenas para um jogador e que esse jogador,qual é o maximizador, é passado para oMínimo máximo funcionar toda vez que eu precisar de uma nova jogada (para queminmax(2, black, a, b) retorna a melhor jogada para o jogador preto enquantominmax(2, white, a ,b) retorna o melhor para o jogador branco), como você alteraria o primeiro pseudocódigo (ou oJava implementação na fonte) para armazenar este dado melhor movimento em algum lugar?

EDIT 2:

Vamos ver se podemos fazê-lo funcionar dessa maneira.

Esta é a minha implementação. Você pode me dizer se está correto?

//PlayerType is an enum with just White and Black values, opponent() returns the opposite player type
protected int minMax(int alpha, int beta, int maxDepth, PlayerType player) {        
    if (!canContinue()) {
        return 0;
    }
    ArrayList<Move> moves = sortMoves(generateLegalMoves(player));
    Iterator<Move> movesIterator = moves.iterator();
    int value = 0;
    boolean isMaximizer = (player.equals(playerType)); // playerType is the player used by the AI        
    if (maxDepth == 0 || board.isGameOver()) {
        value = evaluateBoard();
        return value;
    }
    while (movesIterator.hasNext()) {
        Move currentMove = movesIterator.next();
        board.applyMove(currentMove);
        value = minMax(alpha, beta, maxDepth - 1, player.opponent());
        board.undoLastMove();
        if (isMaximizer) {
            if (value > alpha) {
                selectedMove = currentMove;
                alpha = value;
            }
        } else {
            if (value < beta) {
                beta = value;
            }
        }
        if (alpha >= beta) {
            break;
        }
    }
    return (isMaximizer) ? alpha : beta;
}

EDIT 3:

Nova implementação baseada nas respostas / comentários do @ Codor

private class MoveValue {
    public Move move;
    public int value;

    public MoveValue() {
        move = null;
        value = 0;
    }

    public MoveValue(Move move, int value) {
        this.move = move;
        this.value = value;
    }

    @Override
    public String toString() {
        return "MoveValue{" + "move=" + move + ", value=" + value + '}';
    }

}

protected MoveValue minMax(int alpha, int beta, int maxDepth, PlayerType player) {
    if (!canContinue()) {
        return new MoveValue();
    }
    ArrayList<Move> moves = sortMoves(generateLegalMoves(player));
    Iterator<Move> movesIterator = moves.iterator();
    MoveValue moveValue = new MoveValue();
    boolean isMaximizer = (player.equals(playerType));
    if (maxDepth == 0 || board.isGameOver()) {            
        moveValue.value = evaluateBoard();
        return moveValue;
    }
    while (movesIterator.hasNext()) {
        Move currentMove = movesIterator.next();
        board.applyMove(currentMove);
        moveValue = minMax(alpha, beta, maxDepth - 1, player.opponent());
        board.undoLastMove();
        if (isMaximizer) {
            if (moveValue.value > alpha) {
                selectedMove = currentMove;
                alpha = moveValue.value;
            }
        } else {
            if (moveValue.value < beta) {
                beta = moveValue.value;
                selectedMove = currentMove;
            }
        }
        if (alpha >= beta) {
            break;
        }
    }
    return (isMaximizer) ? new MoveValue(selectedMove, alpha) : new MoveValue(selectedMove, beta);
}

Não sei se entendi direito ou fiz algo errado, mas estou de volta ao problema que tive ao publicar a pergunta:

chamandominMax(Integer.MIN_VALUE, Integer.MAX_VALUE, 1, PlayerType.Black) retorna uma jogada que só pode ser feita pelo jogador branco e não é disso que eu preciso.

Preciso da melhor jogada para o jogador em questão, não da melhor jogada para todo o tabuleiro.