Quiero usar la búsqueda de minimax (con poda alfa-beta), o más bien la búsqueda de negamax, para hacer que un programa de computadora juegue un juego de cartas.

El juego de cartas en realidad consta de 4 jugadores. Así que para poder usar minimax, etc., simplifico el juego a "yo" contra "otros". Después de cada "movimiento", puedes leer objetivamente la evaluación del estado actual desde el juego. Cuando los 4 jugadores han colocado la carta, el más alto los gana a todos, y los valores de las cartas cuentan.

Como no sabes cómo es exactamente la distribución de cartas entre los otros 3 jugadores, pensé que debes simular todas las distribuciones posibles ("mundos") con las cartas que no son tuyas. Tienes 12 cartas, los otros 3 jugadores tienen 36 cartas en total.

Así que mi enfoque es este algoritmo, dondeplayer es un número entre 1 y 3 que simboliza a los tres jugadores de la computadora para los cuales el programa podría necesitar movimientos. Y-player representa a los oponentes, a saber, todos los otros tres jugadores juntos.

private Card computerPickCard(GameState state, ArrayList<Card> cards) {
    int bestScore = Integer.MIN_VALUE;
    Card bestMove = null;
    int nCards = cards.size();
    for (int i = 0; i < nCards; i++) {
        if (state.moveIsLegal(cards.get(i))) { // if you are allowed to place this card
            int score;
            GameState futureState = state.testMove(cards.get(i)); // a move is the placing of a card (which returns a new game state)
            score = negamaxSearch(-state.getPlayersTurn(), futureState, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
            if (score > bestScore) {
                bestScore = score;
                bestMove = cards.get(i);
            }
        }
    }
    // now bestMove is the card to place
}

private int negamaxSearch(int player, GameState state, int depthLeft, int alpha, int beta) {
    ArrayList<Card> cards;
    if (player >= 1 && player <= 3) {
        cards = state.getCards(player);
    }
    else {
        if (player == -1) {
            cards = state.getCards(0);
            cards.addAll(state.getCards(2));
            cards.addAll(state.getCards(3));
        }
        else if (player == -2) {
            cards = state.getCards(0);
            cards.addAll(state.getCards(1));
            cards.addAll(state.getCards(3));
        }
        else {
            cards = state.getCards(0);
            cards.addAll(state.getCards(1));
            cards.addAll(state.getCards(2));
        }
    }
    if (depthLeft <= 0 || state.isEnd()) { // end of recursion as the game is finished or max depth is reached
        if (player >= 1 && player <= 3) {
            return state.getCurrentPoints(player); // player's points as a positive value (for self)
        }
        else {
            return -state.getCurrentPoints(-player); // player's points as a negative value (for others)
        }
    }
    else {
        int score;
        int nCards = cards.size();
        if (player > 0) { // make one move (it's player's turn)
            for (int i = 0; i < nCards; i++) {
                GameState futureState = state.testMove(cards.get(i));
                if (futureState != null) { // wenn Zug gültig ist
                    score = negamaxSuche(-player, futureState, depthLeft-1, -beta, -alpha);
                    if (score >= beta) {
                        return score;
                    }
                    if (score > alpha) {
                        alpha = score; // alpha acts like max
                    }
                }
            }
            return alpha;
        }
        else { // make three moves (it's the others' turn)
            for (int i = 0; i < nCards; i++) {
                GameState futureState = state.testMove(cards.get(i));
                if (futureState != null) { // if move is valid
                    for (int k = 0; k < nCards; k++) {
                        if (k != i) {
                            GameState futureStateLevel2 = futureState.testMove(cards.get(k));
                            if (futureStateLevel2 != null) { // if move is valid
                                for (int m = 0; m < nCards; m++) {
                                    if (m != i && m != k) {
                                        GameState futureStateLevel3 = futureStateLevel2.testMove(cards.get(m));
                                        if (futureStateLevel3 != null) { // if move is valid
                                            score = negamaxSuche(-player, futureStateLevel3, depthLeft-1, -beta, -alpha);
                                            if (score >= beta) {
                                                return score;
                                            }
                                            if (score > alpha) {
                                                alpha = score; // alpha acts like max
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
            return alpha;
        }
    }
}

Esto parece funcionar bien, pero para una profundidad de 1 (depthLeft=1), el programa ya necesita calcular 50,000 movimientos (tarjetas colocadas) en promedio. ¡Esto es demasiado, por supuesto!

Así que mis preguntas son:

¿Es correcta la implementación? ¿Puedes simular un juego como este? Respecto a la información imperfecta, en especial?¿Cómo se puede mejorar el algoritmo en velocidad y carga de trabajo?¿Puedo, por ejemplo, reducir el conjunto de posibles movimientos a un conjunto aleatorio del 50% para mejorar la velocidad y mantener buenos resultados?encontréAlgoritmo UCT Para ser una buena solución (tal vez). ¿Conoces este algoritmo? ¿Puedes ayudarme a implementarlo?