Bei der kontradiktorischen Suche untersuchen wir das Problem, das entsteht, wenn wir versuchen, im Voraus zu planen, während andere Agenten gegen uns planen.

• In früheren Themen haben wir die Suchstrategien untersucht, die nur mit einem einzelnen Agenten verbunden sind, der darauf abzielt, die Lösung zu finden, die oft in Form einer Abfolge von Aktionen ausgedrückt wird.
• Es kann jedoch Situationen geben, in denen mehr als ein Agent im selben Suchraum nach der Lösung sucht, und diese Situation tritt normalerweise beim Spielen auf.
• Die Umgebung mit mehr als einem Agenten wird als bezeichnet Multiagentenumgebung , bei dem jeder Agent ein Gegner eines anderen Agenten ist und gegeneinander spielt. Jeder Agent muss die Aktion anderer Agenten und die Auswirkung dieser Aktion auf ihre Leistung berücksichtigen.
• Also, Suchen, bei denen zwei oder mehr Spieler mit widersprüchlichen Zielen versuchen, denselben Suchraum nach der Lösung zu erkunden, werden als kontradiktorische Suchen bezeichnet, oft auch als Spiele bezeichnet .
• Spiele werden als Suchproblem und heuristische Bewertungsfunktion modelliert. Dies sind die beiden Hauptfaktoren, die bei der Modellierung und Lösung von Spielen in der KI helfen.

Arten von Spielen in der KI:

Perfekte Informationen:Ein Spiel mit den perfekten Informationen ist das, bei dem Agenten in das komplette Spielbrett hineinsehen können. Agenten haben alle Informationen über das Spiel und können auch die Spielzüge der anderen sehen. Beispiele sind Schach, Dame, Go usw.Unvollkommene Informationen:Wenn die Agenten in einem Spiel nicht alle Informationen über das Spiel haben und nicht wissen, was vor sich geht, werden solche Spiele als Spiele mit unvollständigen Informationen bezeichnet, wie z. B. Tic-Tac-Toe, Battleship, Blind, Bridge usw.Deterministische Spiele:Deterministische Spiele sind Spiele, die einem strengen Muster und Regelwerk folgen und mit denen keine Zufälligkeit verbunden ist. Beispiele sind Schach, Dame, Go, Tic-Tac-Toe usw.Nichtdeterministische Spiele:Nicht deterministisch sind Spiele, die verschiedene unvorhersehbare Ereignisse aufweisen und einen Zufalls- oder Glücksfaktor haben. Dieser Zufalls- oder Glücksfaktor wird entweder durch Würfel oder Karten eingeführt. Diese sind zufällig und jede Aktionsreaktion ist nicht festgelegt. Solche Spiele werden auch als stochastische Spiele bezeichnet.
Beispiel: Backgammon, Monopoly, Poker usw.

Hinweis: In diesem Thema besprechen wir deterministische Spiele, eine vollständig beobachtbare Umgebung, Nullsummenspiele und die Frage, wo jeder Agent alternativ agiert.

Nullsummenspiel

• Bei Nullsummenspielen handelt es sich um eine kontradiktorische Suche, bei der es um reinen Wettbewerb geht.
• Im Nullsummenspiel wird der Nutzengewinn oder -verlust jedes Agenten genau durch die Nutzenverluste oder -gewinne eines anderen Agenten ausgeglichen.
• Ein Spieler des Spiels versucht, einen einzelnen Wert zu maximieren, während ein anderer Spieler versucht, ihn zu minimieren.
• Jeder Zug eines Spielers im Spiel wird als „Ply“ bezeichnet.
• Schach und Tic-Tac-Toe sind Beispiele für ein Nullsummenspiel.

Nullsummenspiel: Eingebettetes Denken

Das Nullsummenspiel beinhaltet eingebettetes Denken, bei dem ein Agent oder Spieler versucht herauszufinden:

• Was zu tun.
• So entscheiden Sie über den Umzug
• Muss auch an seinen Gegner denken
• Auch der Gegner überlegt, was er tun soll

Jeder Spieler versucht herauszufinden, wie sein Gegner auf seine Aktionen reagiert. Dies erfordert eingebettetes Denken oder Rückwärtsdenken, um die Spielprobleme in der KI zu lösen.

Formalisierung des Problems:

Ein Spiel kann als eine Art Suche in der KI definiert werden, die aus den folgenden Elementen formalisiert werden kann:

Ausgangszustand:Es legt fest, wie das Spiel zu Beginn aufgebaut ist.Spieler:Es gibt an, welcher Spieler sich im Zustandsraum bewegt hat.Aktionen):Es gibt die Menge der legalen Bewegungen im Zustandsraum zurück.Ergebnis(e, a):Es handelt sich um das Übergangsmodell, das das Ergebnis von Bewegungen im Zustandsraum angibt.Terminal-Test(s):Der Endtest ist wahr, wenn das Spiel vorbei ist, andernfalls ist er in jedem Fall falsch. Der Zustand, in dem das Spiel endet, wird als Endzustand bezeichnet.Dienstprogramm(e, p):Eine Utility-Funktion gibt den endgültigen numerischen Wert für ein Spiel an, das für Spieler p in den Endzuständen s endet. Sie wird auch Auszahlungsfunktion genannt. Beim Schach sind die Ergebnisse ein Sieg, eine Niederlage oder ein Unentschieden und die Auszahlungswerte sind +1, 0, ½. Und für Tic-Tac-Toe sind die Nutzenwerte +1, -1 und 0.

Spielbaum:

Ein Spielbaum ist ein Baum, in dem die Knoten des Baums die Spielzustände und die Kanten des Baums die Bewegungen der Spieler darstellen. Der Spielbaum umfasst den Anfangszustand, die Aktionsfunktion und die Ergebnisfunktion.

Beispiel: Tic-Tac-Toe-Spielbaum:

Die folgende Abbildung zeigt einen Teil des Spielbaums für das Tic-Tac-Toe-Spiel. Im Folgenden sind einige wichtige Punkte des Spiels aufgeführt:

• Es gibt zwei Spieler MAX und MIN.
• Die Spieler sind abwechselnd an der Reihe und beginnen mit MAX.
• MAX maximiert das Ergebnis des Spielbaums
• MIN minimiert das Ergebnis.

Beispielerklärung:

• Vom Ausgangszustand aus hat MAX 9 mögliche Züge, da er als Erster anfängt. MAX platziert x und MIN platziert o, und beide Spieler spielen abwechselnd, bis wir einen Blattknoten erreichen, an dem ein Spieler drei in einer Reihe hat oder alle Felder gefüllt sind.
• Beide Spieler berechnen für jeden Knoten den Minimax-Wert, der den bestmöglichen Nutzen gegen einen optimalen Gegner darstellt.
• Angenommen, beide Spieler sind sich des Tic-Tac-Toe bewusst und spielen den besten Spielzug. Jeder Spieler tut sein Bestes, um zu verhindern, dass ein anderer gewinnt. MIN tritt im Spiel gegen Max an.
• Im Spielbaum haben wir also eine Ebene von Max, eine Ebene von MIN, und jede Ebene wird als bezeichnet Lagen . Max platziert x, dann setzt MIN o, um zu verhindern, dass Max gewinnt, und dieses Spiel geht bis zum Endknoten weiter.
• Dabei gewinnt entweder MIN, MAX oder es steht unentschieden. Dieser Spielbaum ist der gesamte Suchraum der Möglichkeiten, in dem MIN und MAX Tic-Tac-Toe spielen und sich abwechselnd abwechseln.

Daher funktioniert die kontradiktorische Suche nach dem Minimax-Verfahren wie folgt:

• Ziel ist es, die optimale Strategie für MAX zu finden, um das Spiel zu gewinnen.
• Es folgt dem Ansatz der Tiefensuche.
• Im Spielbaum könnte der optimale Blattknoten in jeder Tiefe des Baums erscheinen.
• Geben Sie die Minimax-Werte an den Baum weiter, bis der Endknoten erkannt wird.

In einem gegebenen Spielbaum kann die optimale Strategie aus dem Minimax-Wert jedes Knotens bestimmt werden, der als MINIMAX(n) geschrieben werden kann. MAX bewegt sich lieber in einen Zustand mit maximalem Wert und MIN zieht lieber in einen Zustand mit minimalem Wert über, dann: