TechCodeview

Căutarea adversară este o căutare, în care examinăm problema care apare atunci când încercăm să planificăm înaintea lumii și alți agenți planifică împotriva noastră.

• În subiectele anterioare, am studiat strategiile de căutare care sunt asociate doar cu un singur agent care urmărește să găsească soluția care adesea se exprimă sub forma unei secvențe de acțiuni.
• Dar, ar putea exista unele situații în care mai mult de un agent caută soluția în același spațiu de căutare, iar această situație apare de obicei în timpul jocului.
• Mediul cu mai mult de un agent este denumit ca mediu multi-agent , în care fiecare agent este un adversar al celuilalt agent și joacă unul împotriva celuilalt. Fiecare agent trebuie să ia în considerare acțiunea celuilalt agent și efectul acelei acțiuni asupra performanței lor.
• Asa de, Căutările în care doi sau mai mulți jucători cu obiective conflictuale încearcă să exploreze același spațiu de căutare pentru soluție, se numesc căutări adverse, adesea cunoscute ca Jocuri. .
• Jocurile sunt modelate ca o problemă de căutare și o funcție de evaluare euristică, iar aceștia sunt cei doi factori principali care ajută la modelarea și rezolvarea jocurilor în AI.

Tipuri de jocuri în AI:

Informatia perfecta:Un joc cu informațiile perfecte este acela în care agenții se pot uita în întreaga tablă. Agenții au toate informațiile despre joc și se pot vedea, de asemenea, mișcările reciproce. Exemple sunt șah, dame, go etc.Informații imperfecte:Dacă într-un joc agenții nu au toate informațiile despre joc și nu sunt conștienți de ceea ce se întâmplă, astfel de jocuri se numesc joc cu informații imperfecte, cum ar fi tic-tac-toe, Battleship, blind, Bridge etc.Jocuri deterministe:Jocurile deterministe sunt acele jocuri care urmează un model strict și un set de reguli pentru jocuri și nu există nicio aleatorie asociată cu ele. Exemple sunt șahul, damele, Go, tic-tac-toe etc.Jocuri nedeterministe:Nedeterministe sunt acele jocuri care au diverse evenimente imprevizibile și au un factor de șansă sau noroc. Acest factor de șansă sau noroc este introdus fie prin zaruri, fie prin cărți. Acestea sunt aleatorii și fiecare răspuns la acțiune nu este fix. Astfel de jocuri sunt numite și jocuri stocastice.
Exemplu: table, monopol, poker etc.

Notă: În acest subiect, vom discuta despre jocurile deterministe, mediul complet observabil, suma zero și unde fiecare agent acționează alternativ.

Joc cu sumă zero

• Jocurile cu sumă zero sunt căutări adverse care implică concurență pură.
• În jocul cu sumă zero, câștigul sau pierderea de utilitate a fiecărui agent este exact echilibrat de pierderile sau câștigurile de utilitate ale altui agent.
• Un jucător al jocului încearcă să maximizeze o singură valoare, în timp ce alt jucător încearcă să o minimizeze.
• Fiecare mișcare a unui jucător în joc este numită pli.
• Șahul și tic-tac-toe sunt exemple de joc cu sumă zero.

Joc cu sumă zero: gândire încorporată

Jocul cu sumă zero a implicat o gândire încorporată în care un agent sau un jucător încearcă să-și dea seama:

curs de matematică java

• Ce să fac.
• Cum să decizi mutarea
• Trebuie să se gândească și la adversarul său
• Adversarul se gândește și ce să facă

Fiecare dintre jucători încearcă să afle răspunsul adversarului său la acțiunile lor. Acest lucru necesită gândire încorporată sau raționament înapoi pentru a rezolva problemele jocului în AI.

Formalizarea problemei:

Un joc poate fi definit ca un tip de căutare în AI care poate fi formalizat din următoarele elemente:

Stare initiala:Specifică modul în care este configurat jocul la început.Jucător(i):Specifică ce jucător s-a mutat în spațiul de stare.Acțiune(e):Returnează setul de mișcări legale în spațiul de stat.Rezultat(e, a):Este modelul de tranziție, care specifică rezultatul mișcărilor în spațiul de stare.Teste terminale:Testul terminalului este adevărat dacă jocul s-a terminat, altfel este fals în orice caz. Starea în care se termină jocul se numește stări terminale.Utilitate(e, p):O funcție de utilitate oferă valoarea numerică finală pentru un joc care se termină în stările terminale s pentru jucătorul p. Se mai numește și funcție de plată. Pentru șah, rezultatele sunt o victorie, o pierdere sau o remiză, iar valorile sale de câștig sunt +1, 0, ½. Și pentru tic-tac-toe, valorile de utilitate sunt +1, -1 și 0.

Arborele jocului:

Un arbore de joc este un arbore în care nodurile arborelui sunt stările de joc, iar marginile arborelui sunt mișcările jucătorilor. Arborele de joc implică starea inițială, funcția acțiunilor și funcția rezultat.

Exemplu: Arborele jocului Tic-Tac-Toe:

lista comparabila

Următoarea figură arată o parte din arborele jocului pentru jocul tic-tac-toe. Iată câteva puncte cheie ale jocului:

• Sunt doi jucători MAX și MIN.
• Jucătorii au o tură alternativă și încep cu MAX.
• MAX maximizează rezultatul arborelui de joc
• MIN minimizează rezultatul.

Exemplu de explicație:

• Din starea inițială, MAX are 9 mișcări posibile când începe primul. MAX locul x și MIN locul o și ambii jucători joacă alternativ până ajungem la un nod frunză unde un jucător are trei la rând sau toate pătratele sunt umplute.
• Ambii jucători vor calcula fiecare nod, minimax, valoarea minimax care este cea mai bună utilitate realizabilă împotriva unui adversar optim.
• Să presupunem că ambii jucători sunt bine conștienți de tic-tac-toe și joacă cel mai bun joc. Fiecare jucător face tot posibilul pentru a preveni ca altul să câștige. MIN acționează împotriva lui Max în joc.
• Deci, în arborele de joc, avem un strat de Max, un strat de MIN și fiecare strat este numit ca Ply . Max plasează x, apoi MIN pune o pentru a împiedica Max să câștige, iar acest joc continuă până la nodul terminal.
• În acest caz, fie MIN câștigă, MAX câștigă, fie este o remiză. Acest arbore de joc este întregul spațiu de căutare a posibilităților pe care MIN și MAX le joacă tic-tac-toe și iau pe rând alternativ.

Prin urmare, căutarea contradictorie pentru procedura minimax funcționează după cum urmează:

• Acesta își propune să găsească strategia optimă pentru ca MAX să câștige jocul.
• Urmează abordarea căutării în profunzime.
• În arborele de joc, nodul frunzei optim ar putea apărea la orice adâncime a arborelui.
• Propagați valorile minimax până la arbore până când nodul terminal este descoperit.

Într-un arbore de joc dat, strategia optimă poate fi determinată din valoarea minimax a fiecărui nod, care poate fi scrisă ca MINIMAX(n). MAX preferă să treacă într-o stare de valoare maximă și MIN preferă să treacă la o stare de valoare minimă atunci: