Minimax expliqué pour un idiot

Question

J'ai perdu ma journée entière à essayer d'utiliser l'algorithme minimax pour faire un tictactoe imbattable AI. J'ai raté quelque chose le long du chemin (fried cerveau).

Je ne suis pas à la recherche de code ici, juste une explication meilleure de l'endroit où je suis allé mal.

Voici mon code actuel (la méthode minimax retourne toujours 0 pour une raison quelconque):

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

Votre fonction complète ne fonctionne pas comme prévu, entraînant des jeux à égalité avant tout déclarés peut se produire. Par exemple, considérons cette configuration:

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

Cela devrait être une victoire pour l'ordinateur sur le prochain mouvement. Au lieu de cela, il dit que le jeu est lié.

Le problème est que votre logique complète, en ce moment, vérifie si toutes les places dans un combo sont gratuits. Si aucun d'entre eux ne sont pas, il suppose que ce combo ne peut être gagnée avec. Ce qu'il faut faire est de vérifier si des positions dans ce combo sont occupés, et aussi longtemps que tous ces combos sont Aucun ou le même joueur, ce combo doivent être considérés comme encore disponibles.

par exemple.

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

Maintenant que je bien testé cela avec le code mis à jour je reçois le résultat attendu sur ce cas de test:

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

Answer 2

Étape 1: Plantez votre arbre de jeu

À partir de la carte actuelle génère tous les mouvements possibles de votre adversaire peut faire. Ensuite, pour chacun de ces générer tous les mouvements possibles que vous pouvez faire. Pour Tic-Tac-Toe simplement continuer jusqu'à ce que personne ne peut jouer. Dans d'autres jeux que vous allez arrêter généralement après un temps donné ou de la profondeur.

Cela ressemble à un arbre, dessiner vous-même sur un morceau de papier, carton en cours en haut, tout adversaire se déplace une couche ci-dessous, tous vos mouvements possibles en réponse ci-dessous une couche etc.

Étape 2: Score tous les conseils en bas de l'arbre

Pour un simple jeu comme Tic-Tac-Toe le score à 0 si vous perdez, 50 cravate, 100 victoire.

Étape 3: Propager le score l'arbre

est où le min-max entrent en jeu. Le score d'un conseil précédemment unscored dépend de ses enfants et qui arrive à jouer. Supposons que vous et votre adversaire toujours choisir le meilleur mouvement possible à l'état donné. La meilleure chose pour l'adversaire est le mouvement qui donne le plus mauvais score. De même, votre meilleur coup est le mouvement qui vous donne le meilleur score. Dans le cas de l'adversaire au tour, vous choisissez l'enfant avec le score minimum (qui maximise son profit). Si votre tour vous assumez vous le meilleur coup possible, de sorte que vous choisissez le maximum.

Étape 4: Choisissez votre meilleur coup

Jouez maintenant le mouvement qui se traduit par le meilleur score parmi tous vos propagée pièces possibles de la position actuelle.

Essayez sur un morceau de papier, si à partir d'un tableau blanc est trop pour commencer à une position située-Toe Tic-Tac avancé.

Utilisation récursion: Très souvent, cela peut être simplifiée en utilisant récursion. La fonction « score » est appelée de manière récursive à chaque profondeur et en fonction de si oui ou non la profondeur est pair ou impair, il sélectionner respectivement max ou min pour tous les mouvements possibles. En l'absence de mouvements sont possibles, il évalue le score statique du conseil d'administration. solutions récursives (par exemple le code d'exemple) peuvent être un peu plus délicat à saisir.

Answer 3

Comme vous le savez déjà l'idée de Minimax est à la recherche profonde de la meilleure valeur, en supposant que l'adversaire jouera toujours le mouvement avec la plus mauvaise valeur (pire pour nous, le mieux pour eux).

L'idée est, vous allez essayer de donner une valeur à chaque position. La position où vous est négative lose (nous ne voulons pas que) et la position où vous gagnez est positif. Vous assumez vous toujours essayer de la position de valeur la plus élevée, mais vous assumez l'adversaire toujours viser à la position de valeur la plus basse, ce qui a le plus mauvais résultat pour nous, et le meilleur pour eux (ils gagnent, nous perdons). Donc, vous vous mettez dans leurs chaussures, essayer de jouer aussi bien que vous pouvez comme eux, et supposer qu'ils le feront.
Donc, si vous découvrez que vous avez deux mouvements possibles, on leur donne le choix de gagner ou de perdre, un résultat un match nul de toute façon, vous assumez ils iront pour le déménagement qui aura à gagner si vous les laissez faire. Il est donc préférable d'opter pour le tirage au sort.

Maintenant, pour une vue plus "algorithmique".

Imaginez votre grille est presque complète, sauf pour les deux positions possibles.
Pensez à ce qui se passe lorsque vous jouez le premier:
L'adversaire va jouer l'autre. Il est leur seul mouvement possible afin que nous ne devons pas envisager d'autres mouvements d'eux. Regardez le résultat, associer une valeur résultante (+ 8 si gagné, 0 si nul, -8 en cas de perte: pour tic tac toe vous pouvez représenter ceux que +1 0 et -1)
. Considérons maintenant ce qui se passe lorsque vous jouez à la seconde:
(Même chose ici, l'adversaire n'a qu'un seul mouvement, regardez la position résultante, la valeur de la position).

Vous devez choisir entre les deux mouvements. Il est notre déménagement, donc nous voulons le meilleur résultat (ce qui est le « max » dans Minimax). Choisissez celui avec le résultat le plus élevé que notre mouvement « meilleur ». Voilà pour l'exemple « 2 passe de fin ».

Maintenant, imaginez que vous ne l'avez pas 2 mais 3 déplace vers la gauche.
Le principe est le même, que vous souhaitez attribuer une valeur à chacun de vos 3 mouvements possibles, afin que vous puissiez choisir le meilleur.
Vous commencez en considérant l'un des trois mouvements.
Vous êtes maintenant dans la situation ci-dessus, avec seulement deux coups possibles, mais il est le tour de l'adversaire. Ensuite, vous commencez à considérer l'un des mouvements possibles pour l'adversaire, comme nous l'avons fait ci-dessus. De même, vous regardez chacun des mouvements possibles, et vous trouverez une valeur de résultat pour les deux d'entre eux. Il est le mouvement de l'adversaire, donc nous supposons qu'ils vont jouer le « meilleur » bouger pour eux, celui qui a le plus mauvais taux de participation pour nous, il est donc celui qui a la moindre valeur (ce qui est « min » dans Minimax). Ignorer l'autre; supposent qu'ils vont jouer ce que vous avez trouvé était le mieux pour eux de toute façon. C'est ce que votre déménagement donnera, il est donc la valeur que vous attribuez à la première de vos trois coups.

Maintenant que vous considérez chacun de vos autres possibles 2 mouvements. Vous leur donnez une valeur de la même manière. Et à partir de vos trois mouvements, vous choisissez celui avec la valeur maximale.

Considérons maintenant ce qui se passe avec 4 mouvements. Pour chacun de vos 4 coups, vous regardez ce qui se passe pour les 3 mouvements de votre adversaire, et pour chacun d'eux, vous supposez qu'ils choisiront celui qui vous donne le pire résultat possible du meilleur des 2 autres mouvements pour vous.

Vous voyez où cela est dirigé. Pour évaluer un mouvement n étapes de la fin, vous regardez ce qui peut arriver pour chacun des mouvements possibles n, en essayant de leur donner une valeur afin que vous puissiez choisir le meilleur. Dans le processus, vous devrez essayer de trouver le meilleur coup pour le joueur qui joue à n-1: l'adversaire, et choisissez l'étape avec la moindre valeur. Dans le processus d'évaluation du mouvement n-1, vous devez choisir entre les possibles n-2 se déplace, qui sera la nôtre, et supposons que nous allons jouer aussi bien que possible à cette étape. Etc.

Voilà pourquoi cet algorithme est intrinsèquement récursive. Quelle que soit n, à l'étape n vous évaluez toutes les mesures possibles à n-1. Rincer et répéter.

Pour la retransmission de ce tic-tac-toe machines sont assez loin puissants pour calculer tous les résultats possibles tout de suite dès le début de ejeu e, car il n'y a que quelques centaines d'entre eux. Quand vous regardez à mettre en œuvre pour un jeu plus complexe, vous devrez arrêter de calcul à un moment donné parce qu'il prendra trop de temps. Donc, pour un jeu complexe, vous aurez également à écrire du code qui décide de continuer à chercher tous les possibles prochains mouvements ou pour tenter de donner une valeur à la position maintenant et revenir au début. Cela signifie que vous devrez aussi calculer une valeur pour la position non définitif - par exemple pour les échecs que vous prendriez en compte la quantité de matériel chaque adversaire a sur la planche, les possibilités immédiates de contrôle sans compagnon, combien de tuiles que vous contrôlez et tout, ce qui le rend pas trivial.