introduction

Auparavant, j'ai écrit un article Faisons Othello avec wxPython. À ce moment-là, je n'ai pas implémenté une IA informatique décente, alors je vais essayer de la rendre un peu plus décente. Cette fois, nous allons introduire une stratégie de jeu appelée stratégie Min-Max que nous venons d'étudier. Je voudrais le mettre en œuvre et jouer les uns contre les autres.

Choses à faire

Modifiez le wxPython Othello créé dans Article précédent.

Réglez le mode de jeu Ordinateur contre Ordinateur sur deux types de bataille IA
Jouez à Computer vs Computer un certain nombre de fois et soyez en mesure d'afficher le taux de gain
Créez une IA sans anticipation
1 Créez une IA tournée vers l'avenir
Créez une IA pour mettre en œuvre la stratégie Min-Max

Tout le code source implémenté peut être trouvé dans la branche "alpha-beta" de GitHub, veuillez donc obtenir la dernière version.

Undercard

Faire de Comp vs Comp une correspondance entre deux types d'IA

J'ai préparé un commutateur appelé comp_ai et je l'ai basculé au tour de Computer pour basculer AI. comp_ai essaie de sélectionner aléatoirement [1, -1] comme valeur initiale. Dans le cas de vs Man, il est fixé à comp_ai = 0.

def doComputer(self, my_color):
    self.comp_ai *= -1
    ...

def decideComputerNext(self, pos_list, gain_list): 
    ...
    # Insert a computer's AI here 
    if self.comp_ai >= 0:    # comp_ai == 0 => vs Man mode 
        # Computer AI - A 
    else: 
        # Computer AI - B

    return next_pos

Jouez à des batailles Comp vs Comp un certain nombre de fois et soyez en mesure d'afficher le taux de victoire

Vérifiez l'interface graphique pour cela. Il est ajouté en bas à droite. Sélectionnez Computer vs Computer, entrez le nombre de boucles et appuyez sur "Comp vs Comp Loop" pour effectuer Comp vs Comp un nombre spécifié de fois et afficher le nombre de victoires pour chaque IA. Les chiffres en bas sont le nombre de victoires AI-A, le nombre de victoires AI-B et le nombre de tirages.

En passant, [GUI s'effondre sous Windows 10](http://qiita.com/kanlkan/items/5e6f2e63de406f46b3b1#%E5%8B%95%E4%BD%9C%E7%A2%BA%E8%AA%8D % E7% 92% B0% E5% A2% 83) En guise de contre-mesure, l'interface graphique a été recréée avec un panneau et un composant sans utiliser Sizer. La mise en page est difficile sans Sizer. .. .. Pourquoi Sizer ne fonctionne-t-il pas correctement sur Windows 10? S'il vous plaît laissez-moi savoir si vous savez.

Créez une IA sans anticipation

Pas d'anticipation, c'est-à-dire, décidez de l'endroit où placer la pierre au hasard de tous les endroits où vous pouvez la mettre.

def computerAi_Random(self, pos_list, gain_list): 
    index = random.randint(0, len(pos_list)-1) 
    return pos_list[index]

1 Créez une IA tournée vers l'avenir

1 Regardez devant vous, c'est-à-dire placez-le à l'endroit où le nombre de pierres de l'adversaire qui peuvent être prises lors du placement des pierres est le plus grand. (Dans la pierre standard d'Othello, il semble préférable de la mettre dans la position où les pierres qui peuvent être prises sont les moins précoces ... Eh bien, je m'en fiche.)

def computerAi_1stGainMax(self, pos_list, gain_list): 
    index_list = [] 
    max_gain = max(gain_list) 
    for i, val in enumerate(gain_list): 
        if max_gain == val: 
            index_list.append(i) 
 
    tgt = random.randint(0, len(index_list)-1) 
    return pos_list[index_list[tgt]]

Histoire principale

Stratégie Min-Max (méthode Min-Max)

La stratégie Min-Max est une méthode d'examen de toutes les branches jusqu'à quelques coups, en supposant que la transition d'état de l'arborescence de jeu est avancée comme si l'un l'autre faisait la meilleure action possible. À titre d'exemple, essayons de trouver le meilleur coup avec le noir comme vous-même. Premier coup = tour noir, pensez jusqu'à 3 coups. Dans ce cas, l'endroit où vous pouvez le placer dans le virage noir est le cercle bleu clair, et le nombre de pierres qui peuvent être retournées est le nombre dans le cercle. Ici, si Noir choisit un mouvement de σ00, l'endroit où le placer dans le prochain tour blanc et le nombre de pierres qui peuvent être prises sont les suivants. Ici, si Blanc choisit un coup avec σ10, l'endroit où le placer dans le prochain tour noir et le nombre de pierres qui peuvent être prises sont les suivants. Si vous écrivez une arborescence de jeu jusqu'à 2 sbires de cette manière, ce sera comme suit. La valeur d'évaluation du tour noir de 2 sbires est le nombre maximum de pierres qui peuvent être prises (valeur maximum de σ20 à σ24). Le chiffre le plus bas dans le cercle de la colonne "Noir 2" est la valeur d'évaluation. Ensuite, la valeur d'évaluation est propagée à la colonne "Blanc 1", qui est le tour blanc du premier coup. Blanc choisit également son meilleur coup, il doit donc choisir le coup qui minimise la cote dans la colonne «Noir 2». En d'autres termes, la valeur d'évaluation minimale de «Noir 2» est propagée dans la colonne «Blanc 1». Ensuite, la valeur d'évaluation est propagée de "blanc 1" à "noir 1". Contrairement à la fois précédente, Noir doit choisir sa main pour que sa valeur d'évaluation soit maximisée, donc il propage la valeur d'évaluation maximale de "Blanc 1". En pensant de cette façon, vous pouvez décider du premier mouvement du noir. Elle s'appelle la stratégie Min-Max car le déplacement est déterminé en répétant les valeurs d'évaluation minimale et maximale. Dans cet exemple, la valeur d'évaluation ne change avec aucune main de σ00 à σ03, elle peut donc être placée de quelque manière que ce soit. Cela semble intuitivement correct parce que l'endroit où vous pouvez le mettre avec votre première main est symétrique. C'était un exemple pour le rendre un peu plus intéressant. Compte tenu de la seconde moitié du jeu, la taille de l'arbre devient très grande, j'ai donc pris le premier coup comme exemple.

la mise en oeuvre

J'essaierai de le mettre en œuvre. La raison pour laquelle la valeur max_depth de minMax est de 2 même si elle est de 3 avant la lecture est que la valeur d'évaluation finale est propagée dans computeAi_MinMax_3, alors entrez le nombre moins 1 dans l'argument.

    def computerAi_MinMax_3(self, pos_list, gain_list):
        value = []
        update_pos_list = []
        
        self.log_on = False 
        value = self.minMax(2, 2, pos_list, gain_list)
        for i, pos in enumerate(pos_list):
            if max(value) == value[i]:
                update_pos_list.append(pos)

        self.log_on = True
        tgt = random.randint(0, len(update_pos_list)-1)
        return update_pos_list[tgt]

    def minMax(self, depth, max_depth, pos_list, gain_list):  # depth > 0
        value = []
        next_value = []
        next_pos_list = []
        next_gain_list = []
        self.backUpAllState(self.state_storage_list[depth])
        for pos in pos_list:
            ret =  self.putComputerStone(pos, False)
            next_pos_list, next_gain_list = self.scanPuttableCell()
            if (depth > 1):
                next_value = self.minMax(depth-1, max_depth, next_pos_list, next_gain_list)
                if len(next_value) == 0:
                    value.append(0)
                elif (max_depth - depth) % 2 == 0:
                    value.append(min(next_value))
                else:
                    value.append(max(next_value))
            else:
                if len(next_gain_list) == 0:
                    value.append(0)
                elif (max_depth - depth) % 2 == 0:
                    value.append(min(next_gain_list))
                else:
                    value.append(max(next_gain_list))

            self.restoreAllState(self.state_storage_list[depth])

        return value

Une petite partie redondante est restée, mais j'ai pu la mettre en œuvre proprement. Cependant, il a fallu beaucoup de temps pour arriver ici. .. ..

Bataille AI-AI

Jouons 100 batailles entre IA. Les première et deuxième attaques sont définies de manière aléatoire.

Min-Max_3 anticipé vs pas d'anticipation
Min-Max_3 anticipé vs 1 anticipé

Le résultat est le suivant.

Min-Max 70 victoires, 25 défaites, 5 nuls
Min-Max 48 victoires, 48 défaites, 4 nuls

Oh, la stratégie Min-Max n'est pas très forte. Je pense que la mise en œuvre est correcte. Eh bien, est-ce un soulagement de gagner sans anticipation? À propos, cette stratégie Min-Max prend beaucoup de temps. Si vous souhaitez jouer à Computer vs Computer de vos propres mains, sachez qu'il faudra environ 10 minutes pour jouer 100 batailles, selon les performances de votre PC. À l'avenir, j'essaierai d'implémenter la stratégie αβ pour accélérer en réduisant la plage de recherche de la stratégie Min-Max.

Postscript

Une des raisons possibles pour lesquelles la stratégie Min-Max n'a pas fonctionné était que chaque pierre était évaluée à +1. Par conséquent, pesez chaque place. Je comprends que la valeur d'évaluation semble élevée pour une raison quelconque, mais c'était un peu une pierre d'achoppement, alors j'ai fait référence à ce site. http://uguisu.skr.jp/othello/5-1.html

Alors, pesez-le comme suit et modifiez-le pour obtenir un gain.

gGain = [( 30, -12,  0, -1, -1,  0, -12,  30), \
         (-12, -15, -3, -3, -3, -3, -15, -12), \
         (  0,  -3,  0, -1, -1,  0,  -3,   0), \
         ( -1,  -3, -1, -1, -1, -1,  -3,  -1), \
         ( -1,  -3, -1, -1, -1, -1,  -3,  -1), \
         (  0,  -3,  0, -1, -1,  0,  -3,   0), \
         (-12, -15, -3, -3, -3, -3, -15, -12), \
         ( 30, -12,  0, -1, -1,  0, -12,  30)]
...

    def vecScan(self, pos, reverse_on):
        rev_list = []
        temp_list = []
        gain = 0
        is_hit = 0
        if reverse_on == 0 and self.getCellState(pos,(0,0)) != "green":
            return 0, gain

        if self.now_color == "black":
            rev_color = "white"
        else:
            rev_color = "black"
            
        for v in gVec:
            temp_list = []
            for i in range(1, 8):
                if self.getCellState(pos,(v[0]*i,v[1]*i)) == rev_color:
                    temp_list.append(self.movePos(pos,(v[0]*i, v[1]*i)))
                    if self.getCellState(pos,(v[0]*i+v[0], v[1]*i+v[1])) == self.now_color:
                        is_hit = 1
                        for j in temp_list:
                            rev_list.append(j)
                        break
                else:
                    break
        
        if reverse_on == True:
            if self.log_on == True:
                self.log_textctrl.AppendText("put:" + str(pos) + ", "  + str(rev_list) + " to " + str(self.now_color) + "\n")
            for rev_pos in rev_list:
                self.setCellState(rev_pos, (0,0), self.now_color)
                if self.now_color == "black":
                    self.player_score[0] += 1
                    self.player_score[1] -= 1
                else:
                    self.player_score[1] += 1
                    self.player_score[0] -= 1
                self.updateScoreLabel()
        
        gain = self.calcGain(pos, rev_list)
        return is_hit, gain

    def calcGain(self, pos, rev_list):
        ret_gain = 0
        ret_gain += gGain[pos[0]][pos[1]]

        for rev_pos in rev_list:
            ret_gain += gGain[rev_pos[0]][rev_pos[1]]

        return ret_gain

Jouons encore.

Min-Max_3 anticipé vs pas d'anticipation
Min-Max_3 anticipé vs 1 anticipé
1 anticipation vs non anticipation