Minimax spiegato per un'idiota

Question

Ho sprecato la mia intera giornata cercando di utilizzare l'algoritmo minimax per fare un tictactoe imbattibile AI. Ho perso qualcosa lungo la strada (cervello fritto).

Non sto cercando il codice qui, solo una spiegazione migliore di dove ho sbagliato.

Ecco il mio codice corrente (il metodo minimax restituisce sempre 0 per qualche motivo):

from copy import deepcopy


class Square(object):
    def __init__(self, player=None):
        self.player = player

    @property
    def empty(self):
        return self.player is None


class Board(object):
    winning_combos = (
        [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
        [0, 4, 8], [2, 4, 6],
    )

    def __init__(self, squares={}):
        self.squares = squares
        for i in range(9):
            if self.squares.get(i) is None:
                self.squares[i] = Square()

    @property
    def available_moves(self):
        return [k for k, v in self.squares.iteritems() if v.empty]

    @property
    def complete(self):
        for combo in self.winning_combos:
            combo_available = True
            for pos in combo:
                if not pos in self.available_moves:
                    combo_available = False
            if combo_available:
                return self.winner is not None
        return True

    @property
    def player_won(self):
        return self.winner == 'X'

    @property
    def computer_won(self):
        return self.winner == 'O'

    @property
    def tied(self):
        return self.complete == True and self.winner is None

    @property
    def winner(self):
        for player in ('X', 'O'):
            positions = self.get_squares(player)
            for combo in self.winning_combos:
                win = True
                for pos in combo:
                    if pos not in positions:
                        win = False
                if win:
                    return player
        return None

    @property
    def heuristic(self):
        if self.player_won:
            return -1
        elif self.tied:
            return 0
        elif self.computer_won:
            return 1

    def get_squares(self, player):
        return [k for k,v in self.squares.iteritems() if v.player == player]

    def make_move(self, position, player):
        self.squares[position] = Square(player)

    def minimax(self, node, player):
        if node.complete:
            return node.heuristic
        a = -1e10000
        for move in node.available_moves:
            child = deepcopy(node)
            child.make_move(move, player)
            a = max([a, -self.minimax(child, get_enemy(player))])
        return a


def get_enemy(player):
    if player == 'X':
        return 'O'
    return 'X'

Answer 1

La funzione completa non funziona come previsto, causando giochi da dichiarare legate prima di tutto può succedere. Ad esempio, considerare questa configurazione:

>> oWinning = {
 1: Square('X'),
 3: Square('O'), 4: Square('X'),
 6: Square('O'), 8: Square('X'),
}
>> nb = Board(oWinning)
>> nb.complete
True
>> nb.tied
True

Questa dovrebbe essere una vittoria per il computer sulla prossima mossa. Invece, dice che il gioco è legato.

Il problema è che la logica in totale, in questo momento, i controlli per vedere se tutte le piazze in una combo sono gratuiti. Se qualcuno di loro non sono, si presuppone che che combinata non può essere vinta con. Quello che deve fare è controllare se eventuali posizioni in che combo sono occupati, e finché tutte quelle combinazioni sono o Nessuno o lo stesso giocatore, che combo devono essere considerati ancora disponibile.

per es.

def available_combos(self, player):
    return self.available_moves + self.get_squares(player)

@property
def complete(self):
    for player in ('X', 'O'):
        for combo in self.winning_combos:
            combo_available = True
            for pos in combo:
                if not pos in self.available_combos(player):
                   combo_available = False
            if combo_available:
                return self.winner is not None
    return True

Ora che ho provato questo correttamente con il codice aggiornato sto ottenendo il risultato atteso di questo banco di prova:

>>> nb.minimax(nb, 'O')
-1
>>> nb.minimax(nb, 'X')
1

Answer 2

Passaggio 1: Costruisci il tuo albero gioco

A partire dalla scheda corrente genera tutte le possibili mosse del tuo avversario può fare. Poi per ciascuno di questi generare tutte le possibili mosse che si possono fare. Per Tic-Tac-Toe semplicemente continuare fino a quando non si può giocare. In altri giochi in genere si interrompe dopo un certo tempo o la profondità.

Questo sembra un albero, disegnare da soli su un pezzo di carta, cartone corrente in alto, tutte le mosse dell'avversario uno strato sottostante, tutte le possibili mosse in risposta uno strato sottostante, ecc.

Passaggio 2: Score tutte le schede in fondo l'albero

Per un gioco semplice come Tic-Tac-Toe portarsi in vantaggio per 0 se si perde, 50 cravatta, 100 vittoria.

Passaggio 3: propagare il punteggio contro l'albero

Questo è dove il min-max entrano in gioco. Il punteggio di un bordo in precedenza senza punteggio dipende dai suoi figli e che arriva a giocare. Si supponga sia tu che il tuo avversario sceglie sempre la mossa migliore possibile allo stato dato. La mossa migliore per l'avversario è la mossa che dà il punteggio peggiore. Allo stesso modo, la tua mossa migliore è la mossa che ti dà il punteggio più alto. In caso di l'avversario di turno, si sceglie il bambino con il punteggio minimo (che massimizza il suo vantaggio). Se è il tuo turno si assume farete la mossa migliore possibile, in modo da scegliere il massimo.

Passo 4: Scegli il tuo mossa migliore

Ora gioca la mossa che si traduce nel miglior punteggio propagato tra tutti i possibili giochi dalla posizione corrente.

Prova su un pezzo di carta, se a partire da un bordo bianco è troppo per iniziare da qualche posizione avanzata Tic-Tac-Toe.

ricorsione Usando: Molto spesso questo può essere semplificato utilizzando la ricorsione. La funzione "scoring" viene chiamata ricorsivamente a ciascuna profondità ea seconda se la profondità è pari o dispari si seleziona massima o minima rispettivamente per tutte le possibili mosse. Quando non si muove sono possibili valuta il punteggio statica del consiglio di amministrazione. soluzioni ricorsivi (ad esempio il codice di esempio) possono essere un po 'più complicato da afferrare.

Answer 3

Come già sapete l'idea di Minimax è di profonda ricerca per il miglior valore, supponendo che l'avversario sarà sempre giocare in movimento con il valore peggiore (peggiore per noi, quindi è meglio per loro).

L'idea è, si cercherà di dare un valore ad ogni posizione. La posizione in cui si è perdere negativo (non vogliamo che) e la posizione in cui si vince è positivo. L'utente si assume sarete sempre provare per la posizione più alta del valore, ma anche assumere l'avversario sarà sempre puntare alla posizione più bassa del valore, che ha il peggior risultato per noi, e il meglio per loro (vincono, si perde). Così ti metti nei loro panni, provare a giocare buono come si può come loro, e assumono lo faranno.
Quindi, se si scopre di avere possibili due mosse, quello che dà loro la possibilità di vincere o di perdere, uno con un conseguente disegnare in ogni caso, si assume se ne andranno per la mossa che avrà a vincere se li si lascia fare quello. Quindi è meglio andare per il sorteggio.

Ora, per una visione più "algoritmica".

Immaginate la vostra griglia è quasi pieno ad eccezione di due posizioni possibili.
Consideriamo che cosa accade quando si gioca il primo:
L'avversario giocherà l'altra. E 'la loro possibile solo mossa in modo da non considerare altre mosse da loro. Guardate il risultato, associare un valore risultante (+ 8 se ha vinto, 0 se pareggio, -8 in caso di smarrimento: per tic tac toe si può rappresentare come quelli +1 0 e -1)
. Consideriamo ora cosa succede quando si gioca il secondo:
(Stessa cosa qui, l'avversario ha una sola mossa, sguardo alla posizione risultante, il valore della posizione).

È necessario scegliere tra le due mosse. E 'la nostra mossa, quindi vogliamo il miglior risultato (questo è il "massimo" in minimax). Scegliere quello con il risultato più alto come il nostro "migliore" mossa. Questo è tutto per l'esempio "2 si sposta da un capo".

Ora immaginate di avere non 2 ma 3 si muove a sinistra.
Il principio è lo stesso, si desidera assegnare un valore a ciascuno dei vostri 3 possibili mosse, in modo da poter scegliere la migliore.
Così si inizia prendendo in considerazione uno dei tre mosse.
Si è ora nella situazione di cui sopra, con solo 2 possibili mosse, ma è il turno dell'avversario. Poi si inizia a considerare una delle possibili mosse per l'avversario, come abbiamo fatto in precedenza. Allo stesso modo, si guarda a ciascuna delle possibili mosse, e trovi un valore esito per entrambi. E 'la mossa dell'avversario, quindi diamo per scontato che giocheranno la mossa "migliore" per loro, quello con la peggiore affluenza per noi, quindi è quella con il minor valore (questo è il "minimo" in minimax). Ignorare l'altra; assumono giocheranno quello che hai trovato era meglio per loro comunque. Questo è ciò che la vostra mossa produrrà, quindi è il valore assegnato al primo dei tre mosse.

Ora si consideri ognuno degli altri possibili 2 mosse. Si dà loro un valore nello stesso modo. E dai vostri tre mosse, si sceglie quello con il valore massimo.

Consideriamo ora cosa succede con 4 mosse. Per ciascuno dei vostri 4 mosse, si guarda cosa succede per le 3 mosse del tuo avversario, e per ognuno di essi si assumono essi scegliere quello che ti dà il peggior risultato possibile del meglio delle 2 mosse rimanenti per voi.

Si vede dove questo è diretto. Per valutare una mossa n passi dalla fine, si guarda a quello che può accadere per ciascuna delle n possibili mosse, cercando di dare loro un valore in modo da poter scegliere il migliore. Nel processo, si dovrà cercare di trovare la mossa migliore per il giocatore che gioca a n-1: l'avversario, e scegliere il passo con il valore minore. Nel processo di valutazione del movimento n-1, si deve scegliere tra le possibili n-2 si sposta, che sarà la nostra, e si assume giocheremo così come possiamo in questa fase. Ecc.

Questo è il motivo per cui questo algoritmo è intrinsecamente ricorsivo. Qualunque sia n, al passo n valutare tutte le misure possibili a n-1. Sciacquare e ripetere.

Per oggi tic-tac-toe macchine sono abbastanza potenti per calcolare tutti i risultati possibili destra fuori dall'inizio di The gioco, perché ci sono solo poche centinaia di loro. Quando si guarda per la sua attuazione per un gioco più complesso, si dovrà smettere di calcolo ad un certo punto, perché ci vorrà troppo tempo. Così, per un gioco complesso, si avrà anche a scrivere il codice che decide se continuare alla ricerca di tutte le possibili prossime mosse o per cercare di dare un valore alla posizione ora e tornare presto. Significa si avrà anche per calcolare un valore per la posizione che non è definitivo - per esempio per gli scacchi si sarebbe prendere in considerazione come materiale molto più ogni avversario è sulla scheda, le possibilità immediate di controllo senza compagno, quante tessere di controllare e tutti, il che lo rende non banale.