Verwenden Sie die Minimax-Suche nach Kartenspielen mit unvollständigen Informationen

Question

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

Das Kartenspiel besteht eigentlich aus 4 Spielern.Um also Minimax etc. nutzen zu können, vereinfache ich das Spiel „mich“ gegen die „anderen“.Nach jedem „Zug“ können Sie die aktuelle Zustandsbewertung objektiv am Spiel selbst ablesen.Wenn alle 4 Spieler die Karte gelegt haben, gewinnt der Spieler mit der höchsten Kartenzahl – und die Werte der Karten zählen.

Da man nicht genau weiß, wie die Kartenverteilung zwischen den anderen 3 Spielern ist, dachte ich, dass man alle möglichen Verteilungen („Welten“) mit den Karten simulieren muss, die nicht die eigenen sind.Du hast 12 Karten, die anderen 3 Spieler haben insgesamt 36 Karten.

Mein Ansatz ist also dieser Algorithmus, wo player ist eine Zahl zwischen 1 und 3, die die drei Computerspieler symbolisiert, für die das Programm möglicherweise Zü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 (gelegte Karten) berechnen.Das ist natürlich zu viel!

Meine Fragen sind also:

1. Ist die Umsetzung überhaupt korrekt?Kann man so ein Spiel simulieren?Insbesondere in Bezug auf die unvollständigen Informationen?
2. Wie können Sie den Algorithmus in Bezug auf Geschwindigkeit und Arbeitsbelastung verbessern?
3. Kann ich beispielsweise die Menge möglicher Bewegungen auf eine zufällige Menge von 50 % reduzieren, um die Geschwindigkeit zu verbessern und gleichzeitig gute Ergebnisse beizubehalten?
4. ich fand UCT-Algorithmus eine gute Lösung sein (vielleicht).Kennen Sie diesen Algorithmus?Können Sie mir bei der Umsetzung helfen?

Answer 1

Die von Ihnen implementierte Minimax-Suche ist der falsche Ansatz für Spiele, bei denen so viel Unsicherheit herrscht.Da Sie die Kartenverteilung unter den anderen Spielern nicht kennen, wird Ihre Suche exponentiell viel Zeit mit der Suche nach Spielen verbringen, die angesichts der tatsächlichen Kartenverteilung nicht stattfinden könnten.

Ich denke, ein besserer Ansatz wäre es, mit guten Spielregeln zu beginnen, wenn man nur wenig oder gar keine Informationen über die Hände der anderen Spieler hat.Dinge wie:

1. Wenn Sie in einer Runde als Erster spielen, spielen Sie Ihre niedrigste Karte, da Sie kaum eine Chance haben, die Runde zu gewinnen.
2. Wenn Sie als Letzter in einer Runde spielen, spielen Sie Ihre niedrigste Karte aus, die die Runde gewinnt.Wenn Sie die Runde nicht gewinnen können, spielen Sie Ihre niedrigste Karte.

Sorgen Sie dafür, dass sich Ihr Programm zunächst nicht mit der Suche beschäftigt, sondern halten Sie sich einfach an diese Regeln und lassen Sie es davon ausgehen, dass alle anderen Spieler diese Heuristiken ebenfalls verwenden. Da das Programm beobachtet, welche Karten der erste und der letzte Spieler jeder Runde spielen, kann es eine Tabelle mit Informationen über die Karten erstellen, die jeder Spieler wahrscheinlich hält.Z.B.Eine 9 hätte diese Runde gewonnen, aber Spieler 3 hat sie nicht gespielt, also darf er keine Karten mit der Zahl 9 oder höher haben.Wenn Informationen über die Hand jedes Spielers gesammelt werden, wird der Suchraum schließlich auf den Punkt beschränkt, an dem eine Minimax-Suche möglicher Spiele nützliche Informationen über die nächste zu spielende Karte liefern könnte.

Answer 2

Ich möchte Details klarstellen, auf die in der akzeptierten Antwort nicht wirklich eingegangen wird.

In vielen Kartenspielen können Sie die unbekannten Karten ausprobieren, die Ihr Gegner haben könnte, anstatt sie alle zu generieren.Bei dieser Stichprobe können Sie Informationen wie kurze Farben und die Wahrscheinlichkeit, bestimmte Karten bisher zu halten, berücksichtigen, um die Wahrscheinlichkeit jeder möglichen Hand zu gewichten (jede Hand ist eine mögliche Welt, die wir unabhängig lösen).Anschließend lösen Sie jede Hand mithilfe einer perfekten Informationssuche.Der beste Zug über all diese Welten hinweg ist oft der beste Zug insgesamt – mit einigen Einschränkungen.

Bei Spielen wie Poker wird das nicht so gut funktionieren – hier dreht sich alles um die versteckten Informationen.Sie müssen Ihre Aktionen genau ausbalancieren, um die Informationen über Ihre Hand verborgen zu halten.

Aber bei Spielen wie trickbasierten Kartenspielen funktioniert das ziemlich gut – vor allem, weil ständig neue Informationen preisgegeben werden.Wirklich gute Spieler haben sowieso eine gute Vorstellung davon, was jeder hält.Daher basieren einigermaßen starke Skat- und Bridge-Programme auf diesen Ideen.

Wenn Sie die zugrunde liegende Welt vollständig lösen können, ist das am besten, aber wenn nicht, können Sie Minimax oder UCT verwenden, um den besten Zug in jeder Welt auszuwählen.Es gibt auch Hybridalgorithmen (ISMCTS), die versuchen, diesen Prozess zu vermischen.Seien Sie vorsichtig mit den Behauptungen hier.Einfache Sampling-Ansätze sind einfacher zu programmieren – Sie sollten den einfacheren Ansatz vor einem komplexeren ausprobieren.

Hier sind einige Forschungsarbeiten, die weitere Informationen darüber liefern, wann der Stichprobenansatz für unvollständige Informationen gut funktioniert hat:

Den Erfolg von Perfect Information Monte Carlo Sampling bei der Suche nach Wildbäumen verstehen (In diesem Artikel wird analysiert, wann der Stichprobenansatz wahrscheinlich funktioniert.)

Verbesserung der Zustandsbewertung, Inferenz und Suche in trickbasierten Kartenspielen (Dieser Artikel beschreibt die Verwendung von Sampling im Skat)

Unvollkommene Informationen in einem rechenintensiven Spiel (In diesem Artikel wird das Sampling in Bridge beschrieben.)

Informationssatz Monte-Carlo-Baumsuche (In diesem Artikel werden Stichprobenentnahme und UCT/Monte-Carlo-Baumsuche zusammengeführt, um die Probleme der ersten Referenz zu vermeiden.)

Das Problem bei regelbasierten Ansätzen in der akzeptierten Antwort besteht darin, dass sie keine Rechenressourcen nutzen können, die über das hinausgehen, was zum Erstellen der ursprünglichen Regeln erforderlich ist.Darüber hinaus sind regelbasierte Ansätze durch die Leistungsfähigkeit der Regeln, die Sie schreiben können, begrenzt.Suchbasierte Ansätze können die Leistungsfähigkeit der kombinatorischen Suche nutzen, um ein viel stärkeres Spiel zu erzeugen als der Autor des Programms.