TechCodeview

Modstridende eftersøgning er en eftersøgning, hvor vi undersøger det problem, der opstår, når vi forsøger at planlægge forud for verden, og andre agenter planlægger imod os.

• I tidligere emner har vi studeret de søgestrategier, som kun er forbundet med en enkelt agent, der har til formål at finde den løsning, som ofte kommer til udtryk i form af en række handlinger.
• Men der kan være nogle situationer, hvor mere end én agent søger efter løsningen i det samme søgeområde, og denne situation opstår normalt i spil.
• Miljøet med mere end én agent betegnes som multi-agent miljø , hvor hver agent er modstander af en anden agent og spiller mod hinanden. Hver agent skal overveje den anden agents handling og virkningen af ​​denne handling på deres præstation.
• Så, Søgninger, hvor to eller flere spillere med modstridende mål forsøger at udforske det samme søgerum for løsningen, kaldes modstridende søgninger, ofte kendt som spil .
• Spil er modelleret som et søgeproblem og en heuristisk evalueringsfunktion, og det er de to hovedfaktorer, der hjælper med at modellere og løse spil i AI.

Typer af spil i AI:

Perfekt information:Et spil med den perfekte information er det, hvor agenter kan kigge ind i hele brættet. Agenter har alle oplysninger om spillet, og de kan også se hinandens bevægelser. Eksempler er skak, dam, Go osv.Ufuldkommen information:Hvis agenter i et spil ikke har al information om spillet og ikke er klar over, hvad der foregår, kaldes sådanne spil for spillet med ufuldkommen information, såsom tic-tac-toe, Battleship, blind, Bridge osv.Deterministiske spil:Deterministiske spil er de spil, der følger et strengt mønster og et sæt regler for spillene, og der er ingen tilfældighed forbundet med dem. Eksempler er skak, dam, Go, tic-tac-toe osv.Ikke-deterministiske spil:Ikke-deterministiske er de spil, der har forskellige uforudsigelige begivenheder og har en faktor af tilfældighed eller held. Denne faktor af tilfældighed eller held introduceres af enten terninger eller kort. Disse er tilfældige, og hver handlingsreaktion er ikke fast. Sådanne spil kaldes også stokastiske spil.
Eksempel: Backgammon, Monopol, Poker osv.

Bemærk: I dette emne vil vi diskutere deterministiske spil, fuldt observerbart miljø, nulsum, og hvor hver agent handler alternativt.

Nul-sum spil

• Nulsumsspil er modstridende søgninger, som involverer ren konkurrence.
• I nulsumsspil er hver agents gevinst eller tab af nytte nøjagtigt afbalanceret af en anden agents tab eller gevinster af nytte.
• En spiller i spillet forsøger at maksimere en enkelt værdi, mens en anden spiller forsøger at minimere den.
• Hvert træk af en spiller i spillet kaldes som ply.
• Skak og tic-tac-toe er eksempler på et nulsumsspil.

Nulsumsspil: Indlejret tænkning

Zero-sum-spillet involverede indlejret tænkning, hvor en agent eller spiller forsøger at finde ud af:

• Hvad skal man gøre.
• Sådan beslutter du flytningen
• Skal også tænke på sin modstander
• Modstanderen tænker også, hvad han skal gøre

Hver af spillerne forsøger at finde ud af hans modstanders reaktion på deres handlinger. Dette kræver indlejret tænkning eller bagudgående ræsonnement for at løse spilproblemerne i AI.

array java

Formalisering af problemet:

Et spil kan defineres som en type søgning i AI, der kan formaliseres af følgende elementer:

java hvis andet

Oprindelig tilstand:Det specificerer, hvordan spillet er sat op i starten.Spiller(e):Det specificerer, hvilken spiller der har bevæget sig i tilstandsrummet.Handlinger):Det returnerer sættet af lovlige træk i statens rum.Resultat(er, a):Det er overgangsmodellen, som specificerer resultatet af bevægelser i tilstandsrummet.Terminal-test(er):Terminaltesten er sand, hvis spillet er slut, ellers er den under alle omstændigheder falsk. Den tilstand, hvor spillet slutter, kaldes terminaltilstande.Hjælpeprogram(er, p):En hjælpefunktion giver den endelige numeriske værdi for et spil, der ender i terminaltilstande s for spiller p. Det kaldes også payoff-funktion. For skak er udfaldet sejr, tab eller uafgjort, og dets udbetalingsværdier er +1, 0, ½. Og for tic-tac-toe er nytteværdierne +1, -1 og 0.

Spiltræ:

Et spiltræ er et træ, hvor træets noder er spillets tilstande, og træets kanter er spillernes træk. Spiltræ involverer starttilstand, handlingsfunktion og resultatfunktion.

Eksempel: Tic-Tac-Toe spiltræ:

Følgende figur viser en del af vildttræet for tic-tac-toe-vildt. Følgende er nogle nøglepunkter i spillet:

• Der er to spillere MAX og MIN.
• Spillere har en alternativ tur og starter med MAX.
• MAX maksimerer resultatet af spiltræet
• MIN minimerer resultatet.

Eksempel forklaring:

entitetsrelationel

• Fra starttilstanden har MAX 9 mulige træk, da han starter først. MAX placerer x og MIN plads o, og begge spillere spiller skiftevis, indtil vi når en bladknude, hvor en spiller har tre i træk, eller alle felter er fyldt.
• Begge spillere vil beregne hver node, minimax, minimax værdien, som er den bedst opnåelige nytte mod en optimal modstander.
• Antag, at begge spillere er udmærket klar over tikken og spiller det bedste spil. Hver spiller gør sit bedste for at forhindre en anden i at vinde. MIN agerer mod Max i spillet.
• Så i spiltræet har vi et lag af Max, et lag af MIN, og hvert lag kaldes som Ply . Max placerer x, så sætter MIN o for at forhindre Max i at vinde, og dette spil fortsætter indtil terminalknuden.
• I dette enten MIN sejre, MAX sejre, eller det er uafgjort. Dette spil-træ er hele søgerummet af muligheder, som MIN og MAX spiller tik-tac-toe og skiftes til.

Derfor fungerer den modstridende søgning efter minimax-proceduren som følger:

• Det har til formål at finde den optimale strategi for MAX at vinde spillet.
• Den følger tilgangen til Dybde-først-søgning.
• I spiltræet kan en optimal bladknude optræde i enhver dybde af træet.
• Spred minimax-værdierne op til træet, indtil terminalknuden opdages.

I et givet spiltræ kan den optimale strategi bestemmes ud fra minimumsværdien for hver node, som kan skrives som MINIMAX(n). MAX foretrækker at flytte til en tilstand med maksimumværdi, og MIN foretrækker at flytte til en tilstand med minimumværdi, så: