Stellen Sie den computer nie verlieren Tic-Tac-Toe

Der Umgang mit dieser Art von problem, ist eines der Erkundung möglicher Zukünfte. In der Regel (für ein Schach-oder Entwürfe AI), die Sie in Betracht ziehen futures eine bestimmte Anzahl von Zügen Voraus sondern weil tic tac toe Spiele sind so kurz, die Sie erkunden können, um das Ende des Spiels.

Konzeptionelle Umsetzung

So erstellen Sie eine verzweigende Struktur:

• Die KI imaginiert sich jeder Legale Zug
• Die KI Sie sich vorstellt, dass der Nutzer jede juristische Bewegung, die Sie machen können, nach jeder Legale Zug
• Dann die KI sich vorstellt, jeder der seinen nächsten juristische bewegt
• etc.

Dann, geht aus der am verzweigten Ende (das am weitesten in der Zeit vorwärts) der Spieler, dessen Spielzug es ist (AI oder user), wählt die Zukunft das beste für Sie (gewinnen, verlieren oder Unentschieden) an jedem verzweigungspunkt. Dann wird es über die Hände an den Spieler weiter oben im Baum (näher an der Gegenwart); jedes mal, wenn die Auswahl der besten Zukunft für den Spieler, dessen imaginäre wiederum ist es, bis schließlich Sie an der ersten Abzweigung Punkt, wo die AI sehen können futures, die spielen hin, es zu verlieren, zeichnen und gewinnen. Es wählt eine Zukunft, in der es gewinnt (oder wenn nicht verfügbar, zieht).

Tatsächlichen Implementierung

Beachten Sie, dass konzeptionell ist dies, was geschieht, aber es ist nicht notwendig, um den ganzen Baum, dann urteilen. Sie kann genauso gut arbeiten, obwohl der Baum immer an den entferntesten Punkten in der Zeit und die Wahl dann.

Hier, dieser Ansatz funktioniert gut mit einer rekursiven Funktion. Jede Ebene der Funktion, die abfragt, allen seinen Zweigen; eine Weitergabe der möglichen Zukunft, die zu Ihnen und gibt -1,0,+1; Auswahl der besten Punktzahl für den aktuellen player an jedem Punkt. Die top-level-wählt das verschieben-ohne wirklich zu wissen, wie jedes der Zukunft läuft, und wie gut Sie geklappt.

Pseudo-code

Ich nehme an, in diesem pseudo-code, der +1 ist AI zu gewinnen, wird 0 Zeichnung, -1 Benutzer verlieren

determineNextMove(currentStateOfBoard)
    currentBestMove= null
    currentBestScore= - veryLargeNumber

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , AI’sMove)
        if score>currentBestScore
            currentBestMove=legalMove
            currentBestScore=score
        end
    end

    make currentBestMove

end

getFutureScoreOfMove(stateOfBoard, playersTurn)

    if no LegalMoves
       return 1 if AI wins, 0 if draw, -1 if user wins
    end


    if playersTurn=AI’sTurn
        currentBestScore= - veryLargeNumber //this is the worst case for AI
    else
        currentBestScore= + veryLargeNumber //this is the worst case for Player
    end

    for each legalMove
        score=getFutureScoreOfMove(stateOfBoardAfterLegalMove , INVERT playersTurn)
        if playersTurn ==AI’sTurn AND score>currentBestScore //AI wants positive score
           currentBestScore=score
        end
        if playersTurn ==Users’sTurn AND score<currentBestScore //user wants negative score
           currentBestScore=score
        end

     end

     return currentBestScore
end

Diese pseudo-code ist nicht egal, was der Ausgangspunkt Bord ist (Sie rufen Sie diese Funktion auf jeden KI-Zug mit dem aktuellen board) und nicht wieder was Weg die Zukunft nehmen (wir können nicht wissen, wenn der Benutzer das Spiel optimal, so dass diese Informationen nutzlos ist), aber es immer wählen, wird der Zug, der geht in Richtung der optimalen Zukunft für die KI.

Überlegungen für größere Probleme

In diesem Fall, wo Sie erforschen, um das Spiel zu Ende ist, ist es offensichtlich, das die bestmögliche Zukunft ist (gewinnen, verlieren oder Unentschieden), aber wenn man nur gehen (zum Beispiel) fünf Züge in die Zukunft, müsste man eine Möglichkeit finden, zu bestimmen, dass; im Schach "oder" Entwürfe " Stück-score ist der einfachste Weg, dies zu tun mit dem Stück position eine nützliche Erweiterung.

InformationsquelleAutor Richard Tingle

tic tac toe gehört zur Gruppe der Spiele, die nicht verloren gehen, wenn Sie wissen, wie zu spielen, so dass für solche Spiele, die Sie nicht brauchen, um Bäume und modifizierte algorithmen zur Sortierung. Zu schreiben, wie Algorithmus, den Sie brauchen nur ein paar Funktionen:

1. CanIWin() um zu überprüfen, ob computer hat 2 in Folge und möglich zu gewinnen.
2. ShouldIBlock() um zu überprüfen, ob der Spieler nicht 2 in Folge und brauchen, um es zu blockieren.

Diese beiden Funktionen müssen aufgerufen werden, in dieser Reihenfolge, wenn es zurück true Sie brauchen, entweder zu gewinnen oder nicht zu lassen, Spieler gewinnen.

Nach, dass Sie brauchen, um andere Berechnungen für unterwegs.

Einer exklusiven situation ist, wenn der computer beginnt das Spiel. Sie müssen wählte die Zelle gehört, die größte Menge von verschiedenen Richtungen (es gibt 8 von Ihnen - 3-horizontale, vertikale und 2 diagonalen). In solchen Algorithmus computer werden immer wählen Sie "Mitte", weil es 4 Richtungen, sollten Sie kleine Möglichkeit zu wählen, die zweite beste option, um Spiel ein wenig attraktiver.

So, wenn Sie in situation, wo einige ausgewählte Teile des Vorstandes und computer zu verschieben, müssen Sie beurteilen jede freie Zelle. (, Wenn die erste oder zweite Funktion zurückgegeben true haben Sie, um eine Aktion vor dem erreichen dieser Stelle!!!). So bewerten Zelle, die Sie brauchen, zu zählen, wie viele open-Richtungen Links auf jede Zelle, auch Sie blockieren müssen mindestens einen Gegner Richtung.

Danach haben Sie ein paar mögliche Zellen, um Ihre Marke. So müssen Sie prüfen, für die notwendigen Schritte-Folge, da haben Sie ein paar Optionen und es kann sein, dass einer von Ihnen führen, Sie zu verlieren. So nach, dass Sie eingestellt haben und Sie können nach dem Zufallsprinzip wählen Sie " verschieben, oder wählen Sie die eins mit der größten Punktzahl.

Ich muss sagen, ähnliche Sache, wie gesagt am Anfang des Beitrags. Größere Spiele haben keine perfekte Strategie und, sagen wir Schach sind viel auf der Grundlage der Muster, sondern auch auf zukunftsorientierte Strategie (für so eine Sache ist mit patricia trie). Also zu summieren, müssen Sie nicht schwierig, algorithmen, nur ein paar Funktionen zu zählen, wie viel Sie gewinnen und der Gegner verliert mit bewegen.

InformationsquelleAutor ST3