Ich möchte die Minimax-Suche (mit Alpha-Beta-Bereinigung) oder besser Negamax-Suche verwenden, um ein Computerprogramm ein Kartenspiel spielen zu lassen.

Das Kartenspiel besteht eigentlich aus 4 Spielern. Um also Minimax etc. nutzen zu können, vereinfache ich mir das Spiel gegen die "Anderen". Nach jedem "Zug" können Sie die Bewertung des aktuellen Zustands objektiv aus dem Spiel selbst ablesen. Wenn alle 4 Spieler die Karte gelegt haben, gewinnt der Höchste alle - und die Kartenwerte zählen.

Da Sie nicht genau wissen, wie die Verteilung der Karten zwischen den anderen 3 Spielern ist, dachte ich, Sie müssen alle möglichen Verteilungen ("Welten") mit den Karten simulieren, die nicht Ihre sind. Sie haben 12 Karten, die anderen 3 Spieler haben insgesamt 36 Karten.

Mein Ansatz ist also dieser Algorithmus, bei demplayer ist eine Zahl zwischen 1 und 3, die die drei Computerspieler symbolisiert, für die das Programm möglicherweise Spielzüge finden muss. Und-player steht für die Gegner, nämlich alle anderen drei Spieler zusammen.

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

Dies scheint gut zu funktionieren, aber für eine Tiefe von 1 (depthLeft=1) muss das Programm bereits durchschnittlich 50.000 Züge (platzierte Karten) berechnen. Das ist natürlich zu viel!

Meine Fragen sind also:

Ist die Implementierung überhaupt korrekt? Kannst du so ein Spiel simulieren? Insbesondere in Bezug auf die unvollständigen Informationen?Wie können Sie den Algorithmus in Bezug auf Geschwindigkeit und Arbeitsbelastung verbessern?Kann ich zum Beispiel die Anzahl der möglichen Züge auf einen zufälligen Satz von 50% reduzieren, um die Geschwindigkeit zu verbessern und gleichzeitig gute Ergebnisse zu erzielen?ich fandUCT-Algorithmus eine gute lösung sein (vielleicht). Kennen Sie diesen Algorithmus? Können Sie mir bei der Implementierung helfen?