Einführung

Zuvor schrieb ich einen Artikel Machen wir Othello mit wxPython. Zu diesem Zeitpunkt habe ich keine anständige Computer-KI implementiert, daher werde ich versuchen, sie etwas anständiger zu gestalten. Dieses Mal werden wir eine Spielstrategie namens Min-Max-Strategie vorstellen, die wir gerade studiert haben. Ich würde es gerne umsetzen und gegeneinander spielen.

Dinge die zu tun sind

Ändern Sie das in Vorheriger Artikel erstellte wxPython Othello.

Stellen Sie den Spielmodus von Computer gegen Computer auf zwei Arten von KI-Kämpfen ein
Spielen Sie Computer gegen Computer eine bestimmte Anzahl von Malen und können Sie die Gewinnrate anzeigen
Erstellen Sie eine KI ohne Vorausschau
1 Erstellen Sie eine Vorausschau-KI
Erstellen Sie eine KI, um die Min-Max-Strategie auszuführen

Der gesamte implementierte Quellcode befindet sich im GitHub "alpha-beta" -Zweig. Bitte besorgen Sie sich die neueste Version.

Undercard

Machen Sie Comp vs Comp zu einer Übereinstimmung zwischen zwei Arten von KI

Ich habe einen Schalter namens comp_ai vorbereitet und ihn beim Einschalten des Computers umgeschaltet, um die KI zu wechseln. comp_ai versucht zufällig [1, -1] als Anfangswert auszuwählen. Im Fall von vs Man ist es auf comp_ai = 0 festgelegt.

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

Spielen Sie Comp vs Comp-Kämpfe eine bestimmte Anzahl von Malen und können Sie die Gewinnrate anzeigen

Überprüfen Sie dazu die GUI. Es wird unten rechts hinzugefügt. Wählen Sie Computer vs Computer, geben Sie die Anzahl der Loops ein und drücken Sie "Comp vs Comp Loop", um Comp vs Comp eine bestimmte Anzahl von Malen auszuführen und die Anzahl der Gewinne für jede KI anzuzeigen. Die Zahlen unten sind die Anzahl der AI-A-Siege, die Anzahl der AI-B-Siege und die Anzahl der Draws.

Abgesehen davon bricht [GUI unter Windows 10 zusammen](http://qiita.com/kanlkan/items/5e6f2e63de406f46b3b1#%E5%8B%95%E4%BD%9C%E7%A2%BA%E8%AA%8D % E7% 92% B0% E5% A2% 83) Als Gegenmaßnahme wurde die GUI mit einem Panel und einer Komponente ohne Verwendung von Sizer neu erstellt. Ohne Sizer ist das Layout schwierig. .. .. Warum funktioniert Sizer unter Windows 10 nicht richtig? Bitte lassen Sie es mich wissen, wenn Sie es wissen.

Erstellen Sie KI ohne Vorausschau

Kein Ausblick, das heißt, entscheiden Sie den Ort, an dem der Stein zufällig platziert werden soll, von allen Stellen, an denen Sie ihn platzieren können.

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

1 Erstellen Sie eine Vorausschau-KI

1 Schauen Sie nach vorne, dh platzieren Sie es an der Stelle, an der die Anzahl der Steine des Gegners, die beim Platzieren von Steinen genommen werden können, am größten ist. (In Othellos Standardstein scheint es besser zu sein, ihn in die Position zu bringen, in der die Steine, die genommen werden können, im Frühstadium am wenigsten sind ... Nun, das ist mir egal.)

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

Hauptgeschichte

Min-Max-Strategie (Min-Max-Methode)

Die Min-Max-Strategie ist eine Methode zur Untersuchung aller Zweige bis zu wenigen Zügen, vorausgesetzt, der Zustandsübergang des Spielbaums wird so vorangetrieben, als ob jeder die bestmögliche Aktion ausführt. Versuchen wir als Beispiel, den besten Zug mit Schwarz als Sie selbst zu finden. Erster Zug = schwarzer Zug, denken Sie an bis zu 3 Züge. In diesem Fall ist die Stelle, an der Sie es in die schwarze Kurve setzen können, der hellblaue Kreis, und die Anzahl der Steine, die umgedreht werden können, ist die Anzahl im Kreis. Wenn Schwarz einen Zug von σ00 wählt, sind der Ort, an dem er in die nächste weiße Runde gesetzt wird, und die Anzahl der Steine, die genommen werden können, wie folgt. Wenn Weiß einen Zug mit σ10 wählt, sind der Ort, an dem er in die nächste schwarze Runde gesetzt wird, und die Anzahl der Steine, die genommen werden können, wie folgt. Wenn Sie auf diese Weise einen Spielbaum mit bis zu 2 Schergen schreiben, sieht dieser wie folgt aus. Der Bewertungswert der schwarzen Drehung von 2 Schergen ist die maximale Anzahl von Steinen, die genommen werden können (Maximalwert von σ20 bis σ24). Die niedrigere Zahl im Kreis in der Spalte "Schwarz 2" ist der Bewertungswert. Als nächstes wird der Auswertungswert an die Spalte von "Weiß 1" weitergegeben, die die weiße Wendung des ersten Zuges ist. Weiß wählt auch seinen besten Zug, daher sollte er den Zug wählen, der die Bewertung in der Spalte "Schwarz 2" minimiert. Mit anderen Worten wird der minimale Bewertungswert von "Schwarz 2" an die Spalte "Weiß 1" weitergegeben. Als nächstes wird der Bewertungswert von "weiß 1" nach "schwarz 1" weitergegeben. Im Gegensatz zur vorherigen Zeit sollte Schwarz seine Hand so wählen, dass sein Bewertungswert maximiert wird, sodass er den maximalen Bewertungswert von "Weiß 1" propagiert. Wenn Sie so denken, können Sie den ersten Zug von Schwarz entscheiden. Dies wird als Min-Max-Strategie bezeichnet, da die Bewegung durch Wiederholen der minimalen und maximalen Bewertungswerte bestimmt wird. In diesem Beispiel ändert sich der Auswertungswert mit keiner Hand von σ00 auf σ03, sodass er auf irgendeine Weise platziert werden kann. Dies scheint intuitiv richtig zu sein, da der Ort, an dem Sie es mit Ihrer ersten Hand platzieren können, punktsymmetrisch ist. Es war ein Beispiel dafür, wie man es etwas interessanter macht. In Anbetracht der zweiten Hälfte des Spiels wird der Baum sehr groß, daher habe ich den ersten Zug als Beispiel genommen.

Implementierung

Ich werde versuchen, es umzusetzen. Der Grund, warum die max_depth von minMax 2 ist, obwohl es 3 vor dem Lesen ist, ist, dass der endgültige Auswertungswert in computeAi_MinMax_3 weitergegeben wird. Geben Sie also die Zahl minus 1 in das Argument ein.

    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

Ein wenig überflüssiger Teil blieb übrig, aber ich konnte ihn ordentlich implementieren. Es dauerte jedoch lange, bis wir hier waren. .. ..

KI-zu-KI-Kampf

Lass uns 100 Schlachten zwischen AIs spielen. Der erste und der zweite Angriff werden zufällig festgelegt.

Min-Max_3-Vorausschau gegen keine Vorausschau
Min-Max_3-Vorausschau gegen 1 Vorausschau

Das Ergebnis ist wie folgt.

Min-Max 70 Siege, 25 Niederlagen, 5 Unentschieden
Min-Max 48 Siege, 48 Niederlagen, 4 Unentschieden

Oh, die Min-Max-Strategie ist nicht sehr stark. Ich denke die Implementierung ist korrekt. Ist es eine Erleichterung, ohne Vorausschau zu gewinnen? Diese Min-Max-Strategie ist übrigens sehr zeitaufwändig. Bitte beachten Sie, dass es je nach Leistung Ihres PCs etwa 10 Minuten dauert, bis Sie 100 Schlachten spielen, wenn Sie Computer gegen Computer mit Ihren eigenen Händen spielen. In Zukunft werde ich versuchen, die αβ-Strategie zu implementieren, um sie zu beschleunigen, indem ich den Suchbereich der Min-Max-Strategie einschränke.

Nachtrag

Ein möglicher Grund, warum die Min-Max-Strategie nicht funktionierte, war, dass jeder Stein mit +1 bewertet wurde. Wiegen Sie daher jeden Platz. Ich verstehe, dass der Bewertungswert irgendwie hoch zu sein scheint, aber es war ein bisschen ein Stolperstein, also habe ich auf diese Seite verwiesen. http://uguisu.skr.jp/othello/5-1.html

Gewichten Sie es also wie folgt und ändern Sie es so, dass Sie einen Gewinn erzielen können.

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

Lass uns nochmal spielen.

Min-Max_3-Vorausschau gegen keine Vorausschau
Min-Max_3-Vorausschau gegen 1 Vorausschau
1 Vorausschau gegen keine Vorausschau