Fünf Zeilen im Jupyter-Notizbuch

Im Jupyter-Notizbuch werden die Rahmen angezeigt und Sie können sie in fünf Zeilen anordnen. Die fünfäugige KI wird durch die Suche nach Monte-Carlo-Bäumen realisiert und soll gegen Menschen spielen. jupyter notebookの中で五目並べ

Die Größe des Bretts beträgt 5 x 5, und wenn vier Teile vertikal, horizontal und diagonal ausgerichtet sind, gewinnt der Gewinner (der Grund, warum wir es fünfäugig nennen, obwohl es vier ist, ist, dass vieräugig ein anderer Spielname ist). ..

Programmdatei herunterladen

gomoku.ipynb Bestätigte Betriebsumgebung: Microsoft Azure Notebooks Informationen zur Ausführung finden Sie in der ersten Zelle, nachdem Sie die obige Datei mit dem Jupiter-Notizbuch gelesen haben.

Monte Carlo Baumerkundung

Die Monte-Carlo-Baumsuche ist eine Methode, um die Güte jedes Bretts zu simulieren, während ein Baum wächst, dessen Brett ein Knoten (Blatt) ist und dessen Hand von diesem Brett getroffen werden kann, ist eine Kante (Zweig).

Grob gesagt ist es eine Methode, so viel wie möglich an der Tafel vorzulesen, die wahrscheinlich eine bessere Hand ist, aber auch die Tafel zu untersuchen, die nicht viel ausprobiert wurde. Ob ein bestimmtes Board gut oder schlecht für die KI ist, wird durch zufällige Schritte von diesem Board entschieden und welches gewinnt. Diese Methode, zufällig Maßnahmen zu ergreifen, um das Ende zu kennen, wird als Playout bezeichnet.

Führen Sie die folgenden Schritte aus:

Angenommen, es gibt eine Platine (1).
Erstellen Sie einen Suchbaum (2) bis (5) einen Schritt vor (1). Erstellen Sie zu diesem Zeitpunkt nicht dasselbe Board.
Wählen Sie gemäß den folgenden Kriterien eine von (2) bis (5) aus. Wenn es sich um einen Verzweigungsknoten wie (2) und (3) handelt, wiederholt er die Auswahl eines seiner untergeordneten Knoten.
Wenn die Anzahl der Auswahlen des ausgewählten Blattknotens n oder mehr beträgt, erstellen Sie einen Suchbaum weiter von dort entfernt. Wenn nicht, spielen Sie nach dem Zufallsprinzip, um den Gewinner zu ermitteln.
Wenn die Wiedergabe durchgeführt wird, wird das Ergebnis an den oberen Knoten weitergegeben.
Kehren Sie für die angegebene Anzahl von Malen zu Verarbeitung 3 zurück.
Wählen Sie nach der angegebenen Anzahl von Malen die Bewegung mit der höchsten Anzahl von Auswahlen von den untergeordneten Knoten (2) bis (5) auf dem Brett (1) aus und treffen Sie sie tatsächlich.

AI führt die obige Verarbeitung durch, um einen Zug auszuwählen. Führen Sie insbesondere 3 bis 5 Mal so oft aus, wie es die Zeit erlaubt. Es wird gesagt, dass die KI umso stärker ist, je öfter sie ist. Im Fall dieser fünfäugigen KI ist empirisch bekannt, dass eine starke KI erzeugt werden kann, indem die Schritte 3 bis 5 1000 Mal wiederholt werden. Darüber hinaus ist die Bewegung, die AI nach wiederholten Simulationen tatsächlich macht, die Bewegung auf das Board, die am häufigsten simuliert wurde, wie in Referenz [^ 1].

Kriterien für die Auswahl eines Knotens aus untergeordneten Knoten: Die folgende Formel wählt den Knoten mit dem Maximalwert aus.

Q(s,a)+C_p\frac{\sqrt{2\log{n_s}}}{n_{s,a}}

$ Q (s, a) $: Bewertungswert, der der Gewinnrate entspricht, wenn Sie eine Bewegung auf einer bestimmten Brettoberfläche ausführen $ C_p $: Ein Koeffizient, der die Gewinnrate und die Anzahl der Auswahlen in Einklang bringt $ n_ {s} $: Häufigkeit, mit der ein Board s ausgewählt wird $ n_ {s, a} $: Häufigkeit, mit der a von einem bestimmten Board s geschlagen wurde

Übersicht über die Verarbeitung in Jupyter Notebook

Der Bildschirm ist in JavaScript geschrieben und wird im Jupyter Notebook per HTML von IPython angezeigt.

from IPython.display import HTML
html = '''
<div id="dialog" title="Gomoku">
    <div id="canvas-wrapper">
        <canvas id="dlg-canvas"></canvas>
    </div>
    <button id="start">Start</button>
    <div id="status"></div>
</div>
<script>
    $("#dialog").dialog();
</script>
'''
HTML(html)

Erstellen Sie eine Funktion, um zu bestimmen, welche auf einem bestimmten Brett gewinnt (oder ob der Gewinn oder Verlust noch nicht entschieden wurde)

Der Zustand der Karte wird als Array dargestellt, und es wird bestimmt, ob die Rahmen vertikal, horizontal und diagonal angeordnet sind, indem der Index des Arrays manipuliert wird. Details werden in einem anderen Artikel erklärt, der noch nicht veröffentlicht wurde. 盤面のインデックス

#Gewinnerurteil
def judge(cells,length=params["length"],n_pieces=params["n_pieces"]):
    # ....
    return 0

Erstellen Sie eine Klasse, um die Anordnung zu beurteilen, die dieselbe Tafel sein wird

Dieselbe Platine ist eine Platine mit derselben Rahmenanordnung, wenn eine bestimmte Platine von der gegenüberliegenden Seite betrachtet wird. Wenn AI nach einem Zug sucht, hat die Anordnung, die zum gleichen Brett wird, das gleiche Ergebnis, wenn sie sich weiter bewegt. Aus Effizienzgründen ist das gleiche Brett, das als zweites erscheint, das gleiche Verarbeiten Sie das Ziel nicht. Die Details dieses Prozesses werden in einem anderen Artikel beschrieben, der noch nicht veröffentlicht wurde.

#Erstellen Sie im Voraus ein Indexarray mit denselben Board-Fällen
#Eine Klasse, die prüft, ob das Board identisch ist
class cell_comparator:
    # ....
    pass

Trennen Sie den Monte-Carlo-Baumsuchprozess vom fünfäugigen Spielteil

Details werden in einem anderen Artikel angegeben, der noch nicht veröffentlicht wurde.

Der Teil, der von der Art des Spiels abhängt, wird von Class Game implementiert. Durch Austauschen dieses Klassenspiels können Sie die Monte-Carlo-Baumsuche für verschiedene Spiele implementieren.

#Der Teil, der sich je nach Spieltyp ändert
class Game():
    #Treffen Sie eine Siegesentscheidung. Die Spielernummer ist 1-Auf 1 setzen und die Gewinnernummer ausgeben. Gibt 0 zurück, wenn kein Gewinnzustand vorliegt.
    def judge(self,state):
        return 0

    #Vergleichen Sie, ob die beiden Karten gleich sind. Gibt True zurück, wenn sie gleich sind, False, wenn sie unterschiedlich sind.
    def compare(self,state0,state1):
        return False

    #Holen Sie sich den effektiven Zug von der Tafel des Arguments. Hände mit der gleichen Brettoberfläche müssen hier nicht berücksichtigt werden.
    #MTCS ist ein Spiel.Verwenden Sie "Vergleichen", um Züge mit demselben Brett von gültigen Zügen auszuschließen und mit dem Vorgang fortzufahren.
    #Playout mischt diesen effektiven Zug und rückt ihn zufällig vor.
    def actions(self,state):
        return []

    #Machen Sie einen Schritt von der aktuellen Tafel
    # state:Brett, Spieler:Spielernummer zum Handeln, Handeln:was wirst du tun(Bei fünfäugiger Anordnung ist der Ort zu treffen)
    def move(self,state,action):
        return state2
    
    # playout
    def playout(self,state):
        return 0.0 #zeichnen

    #Der Status der Tafel wird aus dem Zeichenausdruck erstellt.
    def str2state(self,state_str):
		return {}
game = Game()

Dies ist der Code für den Monte-Carlo-Baumsuche-Teil. Die Bildschirmverarbeitung von JavaScript ruft die next_ai-Methode von Python auf. Dieser Prozess führt eine Monte-Carlo-Baumsuche durch und gibt den nächsten Zug zurück. Die Anzahl der Simulationen wird durch n bestimmt, das ein Standardargument von 1000 für next_ai hat. Durch Erhöhen dieser Anzahl wird die Anzahl der Simulationen erhöht und die KI gestärkt.

#
#Monte Carlo Baumerkundung
#Verwenden Sie die Siegesprüfung und die Board-Identitätsprüfung in der vorherigen Zelle.
#

#Das Board, das so oft ausgewählt wurde, erstellt untergeordnete Knoten als Erweiterungsprozess, um den Baum zu vergrößern.
exp_limit = 8
#In der Auswahlphase wird der Bewertungswert der Auswahl q+c(n) (q:Bewertungswert der Tafel, c(n)Bewertungswert der Anzahl der Auswahlen)von
#Koeffizient über die Anzahl der Auswahlen
cp = 1.0

#Um das State-Objekt wiederzuverwenden, bereiten Sie ein Array in der globalen Variablen vor und speichern Sie alles dort.
#Der Index in diesem Array ist das CSS des State-Objekts_Es wird vom Index gehalten.
css = []


# class a state representing an condition of all stones on the borad
class State():
    # ....
    pass

# next ai interface
def next_ai(state_str,n=1000):
    #Aktueller Boardzustand(cells), Nächste Runde(-1)Weil der erste Staat bedingungslos expandiert
    # expand=Erstellen Sie ein Statusobjekt mit True.
    cs = State(game.str2state(state_str),expand=True)
    cs.set_css_index(0)
    
    #Fügen Sie den ersten Status zur Statusliste der globalen Variablen hinzu.
    global css
    css = [cs]

    #Select wird so oft ausgeführt. In Auswahl,
    # evaluate, expand, (Implizit)Sie führen ein Backup aus.
    for epoch in range(n):
        cs.select()
        pass
    return cs.solution()

KI-Stärke

Empirisch ist KI mit 1000 Simulationen stärker als Menschen. Wenn der erste Zug KI ist, verliert die zweite Person oft gegen KI, wenn der erste Zug falsch ist. Die KI von 1000 Simulationen macht jedoch manchmal schwache Bewegungen, so dass Menschen zu diesem Zeitpunkt gewinnen können.

AI mit 2000 Simulationen macht fast keine Fehler. Wenn AI der erste Spieler ist, wird AI fast nie verlieren, selbst wenn es ein Unentschieden gibt.

Was macht diese KI?

Wie auch immer, ich wähle zufällig die besten aus. Alles, was KI weiß, ist, dass (1) das Brett mit vier Teilen hintereinander ein Sieg für KI oder Menschen ist und (2) neue Teile nicht auf den Feldern platziert werden können, auf denen die Teile bereits platziert wurden. Die Leute betrachten es als eine Strategie für das Spiel. Wenn Sie beispielsweise in diesem Spiel drei aufeinanderfolgende Teile mit Leerzeichen an beiden Enden erstellen, verhindert der Gegner ein Ende, trifft aber in der nächsten Runde das verbleibende Ende. AI weiß nichts über die Strategie, das Spiel zu entscheiden. Infolgedessen verhält sich die KI so, als ob sie dieses menschliche Wissen kennt, ohne es zu implementieren.

Möglichkeit und Grenzen der Monte-Carlo-Baumerkundung

Sofern es nicht möglich ist, den Suchraum, der alle Zustände der Tafel darstellt, vollständig zu durchsuchen, wird eine Methode verwendet, um auf begrenzte Weise nach Händen zu suchen. Zu diesem Zeitpunkt ist der Unterschied bei der Bestimmung, welche durchsucht werden sollen und welche nicht, der Unterschied in der Suchmethode. Beispielsweise ist es mit einer Methode wie der αβ-Suche nicht möglich zu wissen, wie viel Zeit für die Suche erforderlich ist, ohne tatsächlich zu suchen. Mit anderen Worten, wenn die Suche in der Mitte gestoppt wird, ist dies zu diesem Zeitpunkt oft nicht die optimale Lösung. Andererseits sucht die Monte-Carlo-Baumsuche grundsätzlich von dem Ort aus, an dem die Möglichkeit einer optimalen Lösung hoch ist. Selbst wenn die Suche in der Mitte gestoppt wird, kann daher davon ausgegangen werden, dass in diesem Stadium die optimale Lösung erhalten wird. Diese zeitproportionale Suchleistung ist ein sehr gutes Merkmal, wenn sie tatsächlich als Spiel-KI oder dergleichen verwendet wird.

Auf der anderen Seite kann die Monte-Carlo-Baumsuche, obwohl es natürlich ist, nicht effektiv für das Problem verwendet werden, dass das Ende des Spiels nicht von einem bestimmten Brett, das als Playout bezeichnet wird, erreicht werden kann (schwer zu erreichen). In diesem Playout-Teil kann eine Technik wie Deep Learning wie das Lernen des Endes von einem bestimmten Brett angewendet werden [^ 1].

[PYTHON] Fünfäugige KI bei der Suche nach Monte-Carlo-Bäumen