Utilizzo di MINIMAX Cerca per giochi di carte con informazioni imperfette

Question

Voglio usare la ricerca minimax (con la potatura alfa-beta), o piuttosto la ricerca di negmax, per creare un programma per computer riprodurre un gioco di carte.

Il gioco delle carte è effettivamente composto da 4 giocatori. Quindi, per poter utilizzare MINIMAX, ecc., Semplifica il gioco a "Me" contro gli "altri". Dopo ogni "mossa", puoi leggere oggettivamente la valutazione dello stato attuale dal gioco stesso. Quando tutti e 4 i giocatori hanno posizionato la carta, il più alto vince tutti - e i valori delle carte contano.

Come non sai come è esattamente la distribuzione delle carte tra gli altri 3 giocatori, pensavo che dovessi simulare tutte le possibili distribuzioni ("Worlds") con le carte che non sono le tue. Hai 12 carte, gli altri 3 giocatori hanno 36 carte in totale.

Quindi il mio approccio è questo algoritmo, dove player è un numero compreso tra 1 e 3 che simboleggia i tre giocatori informatici che il programma potrebbe essere necessario trovare mosse per. E generacodictagcode rappresenta gli avversari, cioè tutti gli altri tre giocatori insieme.

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

.

Questo sembra funzionare bene, ma per una profondità di 1 (-player), il programma deve già calcolare 50.000 mosse (schede posizionate) in media. Questo è troppo, ovviamente!

Quindi le mie domande sono:

.
1. è l'implementazione corretta a tutti? Puoi simulare un gioco come questo? Per quanto riguarda le informazioni imperfette, in particolare?
2. Come puoi migliorare l'algoritmo in velocità e caricare il lavoro?
3. Posso, ad esempio, ridurre il set di possibili mosse a un set casuale del 50% per migliorare la velocità, mantenendo i buoni risultati?
4. Ho trovato Algoritmo UCT per essere una buona soluzione (forse). Conosci questo algoritmo? Puoi aiutarmi a implementarlo?

Answer 1

Cerca in minimax Come hai implementato è l'approccio sbagliato per i giochi dove c'è tanta incertezza. Dal momento che non conosci la distribuzione della carta tra gli altri giocatori, la tua ricerca trascorrerà una quantità esponenziale di tempo che esplora i giochi che non potevano accadere data la giusta distribuzione delle carte.

Penso che un approccio migliore sarebbe iniziare con buone regole per giocare quando hai poca o nessuna informazione sulle mani degli altri giocatori. Cose come:

.
1. Se giochi prima in un round, gioca la tua carta più bassa da quando hai poca probabilità di vincere il round.
2. Se giochi duraturi, gioca la tua carta più bassa che vincerà il round. Se non riesci a vincere il round, allora riproduci la tua carta più bassa.

   Inizialmente il tuo programma non si preoccupi della ricerca e gioca solo da queste regole e che si supponga che tutti gli altri giocatori usino anche queste euristiche. Come il programma osserva quali carte il primo e l'ultimo Giocatori di ogni round Play It può creare una tabella di informazioni sulle carte che ogni giocatore è probabile che venga probabile. Per esempio. A 9 avrebbe vinto questo round, ma il giocatore 3 non lo ha giocato, quindi non deve avere carte 9 o superiore. Poiché le informazioni sono raccolte sulla mano di ciascun giocatore, lo spazio di ricerca sarà alla fine limitato al punto in cui una ricerca di minimax di possibili giochi potrebbe produrre informazioni utili sulla prossima carta da riprodurre.

Answer 2

Voglio chiarire i dettagli che la risposta accettata non entra davvero.

In molti giochi di carte puoi assaggiare le carte sconosciute che il tuo avversario potrebbe avere invece di generare tutti loro. Puoi tenere in considerazione le informazioni come i vestiti corti e la probabilità di tenere determinate carte date giocare finora quando si esegue questo campionamento per il peso della probabilità di ogni possibile mano (ogni mano è un mondo possibile che risolveremo in modo indipendente). Quindi, risolvi ogni mano utilizzando perfette informazioni sulla ricerca. La mossa migliore su tutti questi mondi è spesso la mossa migliore in generale, con un po 'di avvertimento.

In giochi come poker questo non funzionerà molto bene - il gioco è tutto sulle informazioni nascoste. Devi bilanciare con precisione le tue azioni per mantenere le informazioni sulla tua mano nascosta.

Ma, in giochi come giochi di carte trucco, questo funziona abbastanza bene, in particolare poiché le nuove informazioni vengono rivelate tutto il tempo. I giocatori davvero buoni hanno una buona idea di ciò che tutti tiene comunque. Quindi, i programmi di skat e bridge ragionevolmente forti sono stati basati su queste idee.

Se riesci a risolvere completamente il mondo sottostante, è meglio, ma se non puoi, puoi usare MINIMAX o UCT per scegliere la mossa migliore in ogni mondo. Ci sono anche algoritmi ibridi (ISMCT) che cercano di mescolare questo processo insieme. Fai attenzione alle rivendicazioni qui. I semplici approcci di campionamento sono più facili da codificare - dovresti provare l'approccio più semplice prima di uno più complesso.

Ecco alcuni documenti di ricerca che forniranno ulteriori informazioni su quando l'approccio di campionamento alle informazioni imperfetti ha funzionato bene:

Comprensione del successo di informazioni perfette Monte Carlo Campionamento nella ricerca dell'albero di gioco (questa carta analizza quando l'approccio di campionamento è probabile che funzioni.)

miglioramento della valutazione dello stato, dell'inferenza e della ricerca nei giochi di carte da trucco < / a> (questo documento descrive l'uso del campionamento in skat)

Informazioni imperfette in un gioco computazionalmente impegnativo ( Questo documento descrive il campionamento in Bridge)

Informazioni Set Monte Carlo Tree Cerca (questo fisces Campionamento e UCT / Monte Carlo Search per evitare i problemi nel primo riferimento.)

Il problema con gli approcci basati su regole nella risposta accettata è che non possono sfruttare le risorse computazionali oltre a quella necessaria per creare le regole iniziali. Inoltre, gli approcci basati su regole saranno limitati dal potere delle regole che è possibile scrivere. Gli approcci basati sulla ricerca possono utilizzare la potenza della ricerca combinatoria per produrre un gioco molto più forte rispetto all'autore del programma.