Motstridende søk er et søk, der vi undersøker problemet som oppstår når vi prøver å planlegge i forkant av verden og andre agenter planlegger mot oss.

• I tidligere emner har vi studert søkestrategiene som kun er knyttet til en enkelt agent som tar sikte på å finne den løsningen som ofte kommer til uttrykk i form av en sekvens av handlinger.
• Men det kan være noen situasjoner der mer enn én agent søker etter løsningen i samme søkerom, og denne situasjonen oppstår vanligvis i spill.
• Miljøet med mer enn én agent betegnes som multi-agent miljø , der hver agent er motstander av en annen agent og spiller mot hverandre. Hver agent må vurdere handlingen til andre agenter og effekten av denne handlingen på deres ytelse.
• Så, Søk der to eller flere spillere med motstridende mål prøver å utforske det samme søkerommet for løsningen, kalles motstridende søk, ofte kjent som spill .
• Spill er modellert som et søkeproblem og heuristisk evalueringsfunksjon, og dette er de to hovedfaktorene som bidrar til å modellere og løse spill i AI.

Typer spill i AI:

Perfekt informasjon:Et spill med perfekt informasjon er det der agenter kan se inn i hele brettet. Agenter har all informasjon om spillet, og de kan også se hverandre bevege seg. Eksempler er sjakk, dam, Go osv.Ufullkommen informasjon:Hvis agenter i et spill ikke har all informasjon om spillet og ikke er klar over hva som skjer, kalles slike typer spill spillet med ufullkommen informasjon, for eksempel tic-tac-toe, Battleship, blind, Bridge, etc.Deterministiske spill:Deterministiske spill er de spillene som følger et strengt mønster og sett med regler for spillene, og det er ingen tilfeldighet knyttet til dem. Eksempler er sjakk, dam, Go, tic-tac-toe, etc.Ikke-deterministiske spill:Ikke-deterministiske er de spillene som har forskjellige uforutsigbare hendelser og har en faktor av sjanse eller flaks. Denne faktoren tilfeldighet eller flaks introduseres av enten terninger eller kort. Disse er tilfeldige, og hver handlingsrespons er ikke fast. Slike spill kalles også stokastiske spill.
Eksempel: Backgammon, Monopol, Poker, etc.

Merk: I dette emnet vil vi diskutere deterministiske spill, fullt observerbart miljø, nullsum og hvor hver agent opptrer alternativt.

Nullsumspill

• Nullsumspill er motstridende søk som involverer ren konkurranse.
• I nullsum-spill er hver agents gevinst eller tap av nytte nøyaktig balansert med tap eller gevinster av nytte av en annen agent.
• Én spiller i spillet prøver å maksimere én enkelt verdi, mens en annen spiller prøver å minimere den.
• Hvert trekk av én spiller i spillet kalles som ply.
• Sjakk og tikken er eksempler på et nullsumspill.

Nullsumspill: Innebygd tenkning

Nullsumspillet innebar innebygd tenkning der en agent eller spiller prøver å finne ut:

• Hva å gjøre.
• Hvordan bestemme flyttingen
• Må tenke på motstanderen også
• Motstanderen tenker også hva han skal gjøre

Hver av spillerne prøver å finne ut hvordan motstanderen reagerer på deres handlinger. Dette krever innebygd tenkning eller bakoverresonnement for å løse spillproblemene i AI.

array java

Formalisering av problemet:

Et spill kan defineres som en type søk i AI som kan formaliseres av følgende elementer:

annet hvis java

Opprinnelige tilstand:Den spesifiserer hvordan spillet er satt opp ved starten.Spiller(e):Den spesifiserer hvilken spiller som har beveget seg i delstatsområdet.Handling(er):Det returnerer settet med lovlige trekk i statens rom.Resultat(er, a):Det er overgangsmodellen, som spesifiserer resultatet av bevegelser i tilstandsrommet.Terminal-test(er):Terminaltesten er sann hvis spillet er over, ellers er den i alle fall falsk. Staten der spillet slutter kalles terminaltilstander.Verktøy(er, p):En verktøyfunksjon gir den endelige numeriske verdien for et spill som ender i terminaltilstander s for spiller p. Det kalles også utbetalingsfunksjon. For sjakk er utfallet seier, tap eller uavgjort, og utbetalingsverdiene er +1, 0, ½. Og for tic-tac-toe er nytteverdiene +1, -1 og 0.

Spilltre:

Et spilltre er et tre der nodene til treet er spilltilstandene og kantene på treet er bevegelsene til spillerne. Spilltre involverer starttilstand, handlingsfunksjon og resultatfunksjon.

Eksempel: Tic-Tac-Toe spilltre:

Følgende figur viser en del av vilttreet for tic-tac-toe-spill. Følgende er noen hovedpunkter i spillet:

• Det er to spillere MAX og MIN.
• Spillere har en alternativ tur og starter med MAX.
• MAX maksimerer resultatet av spilltreet
• MIN minimerer resultatet.

Eksempel forklaring:

relasjonell enhet

• Fra starttilstanden har MAX 9 mulige trekk da han starter først. MAX plass x og MIN plass o, og begge spillere spiller vekselvis til vi kommer til en bladnode hvor en spiller har tre på rad eller alle rutene er fylt.
• Begge spillerne vil beregne hver node, minimax, minimax-verdien som er det best oppnåelige verktøyet mot en optimal motstander.
• Anta at begge spillerne er godt klar over tikken og spiller det beste spillet. Hver spiller gjør sitt beste for å forhindre at en annen vinner. MIN spiller mot Max i spillet.
• Så i spilltreet har vi et lag med Max, et lag med MIN, og hvert lag kalles som Ply . Maks plass x, så setter MIN o for å forhindre at Max vinner, og dette spillet fortsetter til terminalnoden.
• I dette er enten MIN seire, MAX vinner, eller det er uavgjort. Dette spill-treet er hele søkerommet av muligheter som MIN og MAX spiller tikk-tac-toe og bytter på vekselvis.

Derfor fungerer kontradiktorisk søk ​​etter minimax-prosedyren som følger:

• Målet er å finne den optimale strategien for at MAX skal vinne spillet.
• Den følger tilnærmingen til Dybde-først-søk.
• I vilttreet kan optimal bladknute vises på hvilken som helst dybde av treet.
• Spred minimaksverdiene opp til treet til terminalnoden oppdages.

I et gitt spilltre kan den optimale strategien bestemmes fra minimumsverdien til hver node, som kan skrives som MINIMAX(n). MAX foretrekker å gå til en tilstand med maksimal verdi og MIN foretrekker å gå til en tilstand med minimumsverdi da: