TechCodeview

Motstridig sökning är en sökning, där vi undersöker problemet som uppstår när vi försöker planera inför världen och andra agenter planerar mot oss.

• I tidigare ämnen har vi studerat de sökstrategier som endast är förknippade med en enskild agent som syftar till att hitta den lösning som ofta uttrycks i form av en sekvens av åtgärder.
• Men det kan finnas vissa situationer där mer än en agent söker efter lösningen i samma sökutrymme, och denna situation uppstår vanligtvis i spel.
• Miljö med mer än en agent betecknas som miljö med flera agenter , där varje agent är motståndare till en annan agent och spelar mot varandra. Varje agent måste överväga den andra agentens verkan och effekten av den åtgärden på deras prestation.
• Så, Sökningar där två eller flera spelare med motstridiga mål försöker utforska samma sökutrymme för lösningen kallas motstridiga sökningar, ofta kända som spel .
• Spel är modellerade som ett sökproblem och en heuristisk utvärderingsfunktion, och dessa är de två huvudfaktorerna som hjälper till att modellera och lösa spel i AI.

Typer av spel i AI:

Perfekt information:Ett spel med perfekt information är det där agenter kan titta in i hela tavlan. Agenter har all information om spelet, och de kan också se varandras rörelser. Exempel är schack, dam, Go, etc.Imperfekt information:Om agenter i ett spel inte har all information om spelet och inte är medvetna om vad som händer, kallas sådana spel för spel med ofullkomlig information, såsom tic-tac-toe, Battleship, blind, Bridge, etc.Deterministiska spel:Deterministiska spel är de spel som följer ett strikt mönster och uppsättning regler för spelen, och det finns ingen slumpmässighet förknippad med dem. Exempel är schack, dam, Go, tic-tac-toe, etc.Icke-deterministiska spel:Icke-deterministiska är de spel som har olika oförutsägbara händelser och har en faktor av slump eller tur. Denna faktor av slump eller tur introduceras av antingen tärningar eller kort. Dessa är slumpmässiga och varje åtgärdssvar är inte fast. Sådana spel kallas också för stokastiska spel.
Exempel: Backgammon, Monopol, Poker, etc.

Notera: I det här ämnet kommer vi att diskutera deterministiska spel, fullt observerbar miljö, nollsumma och var varje agent agerar alternativt.

Nollsummespel

• Nollsummespel är motstridiga sökningar som involverar ren konkurrens.
• I nollsummespel är varje agents vinst eller förlust av nytta exakt balanserad av förluster eller vinster av nytta för en annan agent.
• En spelare i spelet försöker maximera ett enda värde, medan en annan spelare försöker minimera det.
• Varje drag av en spelare i spelet kallas ply.
• Schack och tic-tac-toe är exempel på ett nollsummespel.

Nollsummespel: Inbäddat tänkande

Nollsummespelet involverade inbäddat tänkande där en agent eller spelare försöker lista ut:

• Vad ska man göra.
• Hur man bestämmer flytten
• Måste tänka på sin motståndare också
• Motståndaren funderar också på vad han ska göra

Var och en av spelarna försöker ta reda på motståndarens svar på deras handlingar. Detta kräver inbäddat tänkande eller bakåtresonemang för att lösa spelproblemen i AI.

Formalisering av problemet:

Ett spel kan definieras som en typ av sökning i AI som kan formaliseras av följande element:

Initialtillstånd:Den anger hur spelet är uppbyggt i början.Spelare:Den anger vilken spelare som har flyttat i tillståndsutrymmet.Handlingar):Det returnerar uppsättningen av lagliga drag i statens rymd.Resultat, a:Det är övergångsmodellen, som specificerar resultatet av rörelser i tillståndsrummet.Terminal-test(er):Terminaltestet är sant om spelet är över, annars är det falskt i alla fall. Tillståndet där spelet slutar kallas terminaltillstånd.Verktyg(er, p):En hjälpfunktion ger det slutliga numeriska värdet för ett spel som slutar i terminaltillstånd s för spelare p. Det kallas även payoff-funktion. För schack är utfallet en vinst, förlust eller oavgjort och dess utdelningsvärden är +1, 0, ½. Och för tic-tac-toe är nyttovärdena +1, -1 och 0.

Spelträd:

Ett spelträd är ett träd där noder i trädet är speltillstånden och trädets kanter är spelarnas drag. Spelträdet involverar initialtillstånd, åtgärdsfunktion och resultatfunktion.

Exempel: Tic-Tac-Toe spelträd:

Följande figur visar en del av spelträdet för tic-tac-toe-spel. Följande är några viktiga punkter i spelet:

• Det finns två spelare MAX och MIN.
• Spelare har en alternativ tur och börjar med MAX.
• MAX maximerar resultatet av spelträdet
• MIN minimerar resultatet.

Exempel förklaring:

• Från utgångsläget har MAX 9 möjliga drag då han startar först. MAX plats x och MIN plats o, och båda spelarna spelar omväxlande tills vi når en lövnod där en spelare har tre i rad eller alla rutor är fyllda.
• Båda spelarna kommer att beräkna varje nod, minimax, minimaxvärdet som är det bästa möjliga verktyget mot en optimal motståndare.
• Anta att båda spelarna är väl medvetna om tic-tac-toe och spelar det bästa spelet. Varje spelare gör sitt bästa för att förhindra att en annan vinner. MIN agerar mot Max i spelet.
• Så i spelträdet har vi ett lager av Max, ett lager av MIN, och varje lager kallas som Lager . Max placera x, sedan sätter MIN o för att förhindra att Max vinner, och det här spelet fortsätter till terminalnoden.
• I detta är antingen MIN vinster, MAX vinner, eller så är det oavgjort. Det här spelträdet är hela sökutrymmet av möjligheter som MIN och MAX spelar tic-tac-toe och turas om växelvis.

Därför fungerar den kontradiktoriska sökningen efter minimax-proceduren enligt följande:

• Det syftar till att hitta den optimala strategin för att MAX ska vinna spelet.
• Den följer tillvägagångssättet för djup-först-sökning.
• I spelträdet kan optimal lövnod dyka upp på vilket djup som helst av trädet.
• Sprid minimaxvärdena upp till trädet tills terminalnoden upptäcktes.

I ett givet spelträd kan den optimala strategin bestämmas från minimaxvärdet för varje nod, vilket kan skrivas som MINIMAX(n). MAX föredrar att flytta till ett tillstånd med maxvärde och MIN föredrar att flytta till ett tillstånd med lägsta värde då: