Welchen Algorithmus für ein Tic-Tac-Toe-Spiel kann ich verwenden, um den "besten Zug" für die KI zu bestimmen?

In einem tic-tac-toe-Implementierung, die ich denke, dass der schwierige Teil ist, um zu bestimmen, den besten Zug gespielt werden, indem die Maschine.

Was sind die algorithmen, die können weiter verfolgt? Ich bin auf der Suche in Implementierungen von einfachen bis zu komplexen. Wie würde ich mich über die Bewältigung dieser Teil des Problems ist?

InformationsquelleAutor der Frage praveen chettypally | 2008-09-24

  1. 53

    Die Strategie von Wikipedia für das spielen ein perfektes Spiel (gewinnen oder zu binden, jedes mal) scheint, wie unkompliziert pseudo-code:

    Zitat von Wikipedia (Tic Tac Toe#Strategie)

    Ein Spieler kann ein perfektes Spiel von Tic-tac-toe (Sieg oder zumindest Unentschieden), wenn Sie wählen Sie den ersten verfügbaren bewegen Sie aus der folgenden Liste, jede Wendung, wie Sie in Newell und Simon (1972) tic-tac-toe-Programm.[6]

    1. Gewinnen: Wenn Sie zwei in einer Reihe, spielen die Dritte, um drei in einer Reihe.

    2. Block: Wenn der Gegner hat zwei in einer Reihe, spielen die Dritte, Sie zu blockieren.

    3. Gabel: Erstellen Sie eine Gelegenheit, wo Sie gewinnen können, gibt es zwei Möglichkeiten.

    4. Block Gegners Gabel:

      Option 1: Erstellen Sie zwei in einer Reihe zu zwingen
      der Gegner in der Verteidigung, wie lange
      wie führen Sie nicht zu Ihnen
      eine Gabel oder zu gewinnen. Zum Beispiel, wenn "X"
      hat eine Ecke, "O" hat das Zentrum, und
      "X" hat die gegenüberliegende Ecke,
      "O" darf nicht spielen eine Ecke, um zu
      gewinnen. (Spielen eine Ecke in diese
      Szenario erzeugt eine Gabel für "X" zu
      win.)

      Option 2: Wenn es eine Konfiguration
      wo kann der Gegner Gabel, block
      dass die Gabel.

    5. Center: Spielen der Mitte.

    6. Gegenüberliegende Ecke: Wenn der Gegner in der Ecke, spielen die gegenüberliegende
      Ecke.

    7. Leere Ecke: Spielen Sie eine leere Ecke.

    8. Leere Seite: Spielen Sie eine leere Seite.

    Erkennen, was eine "Gabel" - situation aussieht, kann man in einem brute-force Art und Weise, wie vorgeschlagen.

    Hinweis: Ein "perfekter" Gegner ist eine nette übung, aber letztlich nicht Wert 'spielen' gegen. Sie können jedoch, ändern Sie die Prioritäten vor, um charakteristische Schwächen auf Gegner Persönlichkeiten.

    InformationsquelleAutor der Antwort bkane

  2. 35

    Was Sie brauchen (für tic-tac-toe oder ein weit schwieriger Spiel wie Schach) ist der minimax-Algorithmusoder die etwas kompliziertere Variante, alpha-beta-pruning. Gewöhnliche naive minimax wird das gut machen, für ein Spiel mit so kleinem Suchraum als tic-tac-toe, aber.

    In einer nussschale, was Sie tun möchten, ist nicht die Suche nach der Bewegung, die die best mögliche Ergebnis für Sie, sondern für die Verschiebung, bei der das schlechtest mögliche Ergebnis möglichst gut ist. Wenn Sie annehmen, dass Ihr Gegner spielt optimal, müssen Sie davon ausgehen, Sie werden den Umzug, der am schlimmsten für Sie, und deshalb nehmen Sie das verschieben-das Minimiert Ihre Maximale Verstärkung.

    InformationsquelleAutor der Antwort Nick Johnson

  3. 14

    Brute-force-Methode zu erzeugen, die jeder einzelne board-und scoring-es basiert auf den Brettern, die es später produziert weiter unten in der Struktur erfordert nicht viel Speicher, vor allem, wenn Sie erkennen, dass ein 90-Grad-board Rotationen sind redundant, da sind flips über die vertikale, horizontale und Diagonale Achse.

    Sobald Sie zu diesem Punkt, es gibt so etwas wie weniger als 1k an Daten in einem Baum-Diagramm, um das Ergebnis beschreiben, und somit der beste Zug für den computer.

    -Adam

    InformationsquelleAutor der Antwort Adam Davis

  4. 7

    Einem typischen algo für tic-tac-toe sollte wie folgt Aussehen:

    Bord : Ein neun-element-Vektor-Vertreter des Vorstands. Wir lagern 2(Angabe
    Leer), 3 (Anzeige-X), oder 5 (Anzeige-O).
    Turn : Eine Ganzzahl, die angibt, welche Bewegung, das Spiel über gespielt werden.
    1. bewegen wird, gekennzeichnet durch 1, zuletzt geändert durch 9.

    Den Algorithmus

    Den Haupt-Algorithmus verwendet die drei Funktionen.

    Make2 : 5 zurückgibt, wenn das mittlere Quadrat der platine leer ist, d.h. wenn board[5]=2. Ansonsten, gibt diese Funktion alle nicht-Eckfeld
    (2,4,6 oder 8).

    Posswin(p) : gibt 0 zurück, wenn der Spieler p nicht gewinnen kann, auf seinen nächsten Schritt, ansonsten gibt die Anzahl der Quadratmeter, stellt einen gewinnzug. Diese Funktion wird Programm zu gewinnen und zu blockieren, Gegner gewinnen. Diese Funktion basiert auf der überprüfung jeder der Zeilen, Spalten und diagonalen. Durch die Multiplikation der Werte von seinem Platz zusammen für eine ganze Zeile (oder Spalte oder Diagonale), die situation von win überprüft werden können. Wenn das Produkt 18 (3 x 3 x 2), dann X gewinnen können. Wenn das Produkt 50 (5 x 5 x 2), dann O gewinnen können. Wenn eine gewinnende Zeile (Spalte oder Diagonale) gefunden wird, wird das leere Quadrat sein kann deter abgebaut und die Zahl der Quadratmeter ist der von dieser Funktion zurückgegeben.

    Go (n): eine Bewegung im Quadrat n. dieses Verfahren setzt Brett [n], um die 3 Drehen, wenn ungerade ist, oder 5, wenn Wiederum auch. Ist es auch-Schritten drehen.

    Der Algorithmus hat eine integrierte Strategie für jeden bewegen. Es macht die ungeraden
    bewegen, wenn es spielt X, die geraden zu bewegen, wenn es spielt O.

    Turn =1 Go(1)   (upper left corner).
Turn =2 If Board[5] is blank, Go(5), else Go(1).
Turn =3 If Board[9] is blank, Go(9), else Go(3).
Turn =4 If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn =5 if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn =6 If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn =7 If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn =8 if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn =9 Same as Turn=7.

    Ich habe es verwendet. Lassen Sie mich wissen, wie Sie die Jungs fühlen.

    InformationsquelleAutor der Antwort Kaushik

  5. 6

    Da Sie nur den Umgang mit einer 3x3 matrix von möglichen Standorten, es wäre ziemlich einfach, schreiben Sie einfach eine Suche durch alle Möglichkeiten, ohne dass Sie Rechenleistung. Für jeden open space, berechnen bis hin zu allen möglichen Ergebnissen nach, dass die Kennzeichnung, dass der Raum (rekursiv, würde ich sagen), dann verwenden Sie das verschieben mit den meisten Möglichkeiten, zu gewinnen.

    Optimierung wäre dies eine Verschwendung von Mühe, wirklich. Obwohl einige einfach sein könnte:

    • Zunächst prüfen, für möglich gewinnt, für
      das andere team, der erste block
      Sie finden (wenn es 2 Spiele
      über sowieso).
    • Immer die Mitte, wenn Sie es öffnen
      (und die bisherige Regelung hat keine
      Kandidaten).
    • Nehmen Sie Ecken vor Seiten (wieder,
      wenn die vorherigen Regeln sind leer)

    InformationsquelleAutor der Antwort billjamesdev

  6. 3

    Können Sie die KI spielen, sich selbst in einige Beispiel-Spiele zu lernen. Verwenden Sie eine betreute Lern-Algorithmus, um ihm zu helfen entlang.

    InformationsquelleAutor der Antwort J.J.

  7. 3

    Einen Versuch, ohne Verwendung eines Spiel-Feld.

    1. zu gewinnen(dein double)
    2. wenn nicht, nicht zu verlieren(Gegner doppelt)
    3. wenn nicht, hast du schon eine Gabel(Doppel -)
    4. wenn nicht, wenn der Gegner eine Gabel
      1. Suche im blockierenden Punkte für möglich Doppel-und Gabel(ultimate win)
      2. wenn die Suche nicht die Gabel in die Blockierung Punkte(was dem Gegner am meisten zu verlieren Möglichkeiten )
      3. wenn nicht nur die Blockierung Punkte(nicht verlieren)
    5. wenn nicht, Suche nach doppelten und Gabel(ultimate win)
    6. wenn die Suche nicht nur für Gabeln, die gibt Gegner die am verlieren Möglichkeiten
    7. wenn nicht, Suche nur für ein Doppel -
    8. wenn nicht tot, Ende, Band, random.
    9. wenn nicht(es bedeutet, dass Ihre erste verschieben)
      1. wenn es der erste Zug des Spiels;
        1. geben dem Gegner die Möglichkeit verlieren(der Algorithmus Ergebnisse in nur Ecken, das gibt 7 verlieren Punkt die Möglichkeit auf Gegner)
        2. oder für das brechen die Langeweile einfach nur Zufall.
      2. wenn es die zweite Bewegung des Spiels;
        1. finden, nur die nicht Punkte zu verlieren(gibt ein wenig mehr Optionen)
        2. oder finden der Punkte in dieser Liste hat die besten chance zu gewinnen(es kann langweilig sein,weil er nur alle Ecken oder benachbarten Ecken oder in die Mitte)

    Hinweis: Wenn Sie die Doppel-und Gabeln, prüfen Sie, ob Ihr Doppel-gibt dem Gegner ein Doppel.wenn es gibt, prüfen Sie, ob das Ihre neue obligatorische Punkt ist die Gabel Liste.

    InformationsquelleAutor der Antwort

  8. 0

    Rang jedes der Felder mit numerischen erzielt. Wenn ein Quadrat genommen wird, sich auf die nächste Wahl (absteigend sortiert nach Rang). Sie gehen zu müssen, wählen Sie eine Strategie (es gibt zwei Hauptgründe für die ersten drei (glaube ich) für die zweite). Technisch könnte man einfach das Programm alle Strategien, und wählen Sie dann eine nach dem Zufallsprinzip. Das würde für einen weniger berechenbaren Gegner.

    InformationsquelleAutor der Antwort Daniel Spiewak

  9. 0

    Diese Antwort setzt Voraus, Sie zu verstehen, die Umsetzung der perfekten Algorithmus für P1 und diskutiert, wie das zu erreichen ist ein Sieg in Bedingungen gegen gewöhnliche menschliche Spieler, die einige Fehler machen werden häufiger als andere.

    Das Spiel der Kurs sollte mit einem Unentschieden enden, wenn beide Spieler spielen optimal. Auf einer menschlichen Ebene, P1 spielen in einer Ecke produziert, gewinnt viel öfter. Aus welchem psychologischen Grund, P2 ist angehaltenem zu denken, dass das spielen in der Mitte ist nicht so wichtig, das ist bedauerlich für Sie, da es die einzige Antwort, die nicht ein Gewinn-Spiel für P1.

    Wenn P2 hat richtig block in der Mitte, P1 sollte, spielen Sie die gegenüberliegende Ecke, weil wieder, aus welchem psychologischen Grund, P2 bevorzugen die Symmetrie spielen eine Ecke, die wieder produziert eine verlorene board für Sie.

    Für jede Bewegung in P1 können zum starten bewegen, es ist eine Bewegung, P2 kann machen, dass wird ein Sieg für P1, wenn beide Spieler spielen optimal danach. In diesem Sinne P1 spielen dürfen, wo auch immer. Der Rand bewegt sind die schwächsten in dem Sinne, dass der größte Anteil der möglichen Antworten auf diese verschieben produzieren eine Attraktion, aber es gibt immer noch Antworten, dass wird ein Sieg für P1.

    Empirisch (genauer gesagt, anekdotisch), die besten P1 ab bewegt zu sein scheinen erste Ecke, zweite Mitte, und die Letzte Flanke.

    Die nächste Herausforderung, die Sie hinzufügen können, in person oder über ein GUI, ist nicht zur Anzeige im board. Ein Mensch kann durchaus an alles erinnern, Stand aber vor der zusätzlichen Herausforderung führt zu einer Präferenz für symmetrische boards, die nehmen weniger Aufwand, sich zu erinnern, was zu dem Fehler, den ich bereits in den ersten Zweig.

    Ich bin eine Menge Spaß auf Partys, ich weiß.

    InformationsquelleAutor der Antwort djechlin

Schreibe einen Kommentar