Adversarial search je pretraga u kojoj ispitujemo problem koji nastaje kada pokušavamo planirati ispred svijeta, a drugi agenti planiraju protiv nas.

nizovi java

• U prethodnim temama proučavali smo strategije pretraživanja koje su povezane samo s jednim agentom koji ima za cilj pronaći rješenje koje se često izražava u obliku niza radnji.
• No, mogu postojati neke situacije u kojima više od jednog agenta traži rješenje u istom prostoru pretraživanja, a to se obično događa tijekom igranja igrica.
• Okolina s više od jednog agenta naziva se kao okruženje s više agenata , u kojem je svaki agent protivnik drugog agenta i igraju jedan protiv drugog. Svaki agent treba uzeti u obzir djelovanje drugog agenta i učinak tog djelovanja na njihovu izvedbu.
• Tako, Pretrage u kojima dva ili više igrača s proturječnim ciljevima pokušavaju istražiti isti prostor za traženje rješenja nazivaju se suparnička pretraživanja, često poznata kao igre .
• Igre su modelirane kao problem pretraživanja i funkcija heurističke evaluacije, a to su dva glavna čimbenika koji pomažu u modeliranju i rješavanju igara u umjetnoj inteligenciji.

Vrste igara u AI:

Savršene informacije:Igra sa savršenim informacijama je ona u kojoj agenti mogu pogledati cijelu ploču. Agenti imaju sve informacije o igri, a mogu vidjeti i poteze jedni drugih. Primjeri su šah, dama, go itd.Nesavršena informacija:Ako agenti u igri nemaju sve informacije o igri i nisu upoznati sa onim što se događa, takve igre se nazivaju igrama s nesavršenim informacijama, kao što su tic-tac-toe, Battleship, blind, Bridge itd.Determinističke igre:Determinističke igre su one igre koje slijede strogi obrazac i skup pravila za igre i s njima nema nasumičnosti. Primjeri su šah, dama, go, tic-tac-toe itd.Nedeterminističke igre:Nedeterminističke su one igre koje imaju razne nepredvidive događaje i imaju faktor slučajnosti ili sreće. Ovaj faktor slučajnosti ili sreće uvode kocke ili karte. Oni su nasumični i svaki odgovor na akciju nije fiksan. Takve igre se također nazivaju stohastičke igre.
Primjer: Backgammon, Monopoly, Poker, itd.

Napomena: u ovoj temi raspravljat ćemo o determinističkim igrama, potpuno vidljivom okruženju, nultom zbroju i gdje svaki agent djeluje alternativno.

Igra s nultim zbrojem

• Igre s nultom sumom su suparnička potraga koja uključuje čisto natjecanje.
• U igri nultog zbroja dobit ili gubitak korisnosti svakog agenta točno je uravnotežen s gubicima ili dobicima korisnosti drugog agenta.
• Jedan igrač u igri pokušava maksimizirati jednu vrijednost, dok je drugi igrač pokušava minimizirati.
• Svaki potez jednog igrača u igri naziva se slojem.
• Šah i tic-tac-toe primjeri su igre s nultom sumom.

Igra nulte sume: ugrađeno razmišljanje

Igra nulte sume uključivala je ugrađeno razmišljanje u kojem jedan agent ili igrač pokušava shvatiti:

• Što uraditi.
• Kako se odlučiti za potez
• Mora misliti i na protivnika
• Protivnik također razmišlja što učiniti

Svaki od igrača pokušava saznati odgovor svog protivnika na njihove akcije. To zahtijeva ugrađeno razmišljanje ili rezoniranje unatrag da bi se riješili problemi igre u AI.

Formalizacija problema:

Igra se može definirati kao vrsta pretraživanja u umjetnoj inteligenciji koja se može formalizirati od sljedećih elemenata:

Početno stanje:Određuje kako je igra postavljena na početku.Igrač(i):Određuje koji se igrač pomaknuo u prostoru stanja.Radnja(e):Vraća skup legalnih poteza u prostoru stanja.Rezultat(i, a):To je prijelazni model koji specificira rezultat pomaka u prostoru stanja.Terminalni test(ovi):Test terminala je istinit ako je igra gotova, inače je u svakom slučaju lažan. Stanje u kojem igra završava naziva se terminalno stanje.Korisnost(i, p):Funkcija korisnosti daje konačnu numeričku vrijednost za igru ​​koja završava u terminalnim stanjima s za igrača p. Također se naziva funkcija isplate. Za šah, ishodi su pobjeda, poraz ili remi, a njegove vrijednosti isplate su +1, 0, ½. A za tic-tac-toe, vrijednosti korisnosti su +1, -1 i 0.

Stablo igre:

Stablo igre je stablo u kojem su čvorovi stabla stanja igre, a rubovi stabla potezi igrača. Stablo igre uključuje početno stanje, funkciju radnji i funkciju rezultata.

Primjer: Stablo igre Tic-Tac-Toe:

Sljedeća slika prikazuje dio stabla igre za igru ​​tic-tac-toe. Slijede neke ključne točke igre:

• Postoje dva igrača MAX i MIN.
• Igrači imaju alternativni red i počinju s MAX.
• MAX maksimizira rezultat stabla igre
• MIN minimizira rezultat.

Primjer objašnjenja:

• Iz početnog stanja, MAX ima 9 mogućih poteza jer počinje prvi. MAX stavlja x, a MIN stavlja o, i oba igrača igraju naizmjenično dok ne dođemo do čvora lista gdje jedan igrač ima tri u nizu ili su sva polja popunjena.
• Oba igrača će izračunati svaki čvor, minimax, minimax vrijednost koja je najbolja moguća korisnost protiv optimalnog protivnika.
• Pretpostavimo da su oba igrača dobro upoznata s tic-tac-toe i igraju najbolju igru. Svaki igrač daje sve od sebe da spriječi drugog da pobijedi. MIN djeluje protiv Maxa u igri.
• Dakle, u stablu igre imamo sloj Max, sloj MIN, a svaki se sloj naziva as Prometovati . Max stavlja x, zatim MIN stavlja o kako bi spriječio Maxa da pobijedi, a ova igra se nastavlja do terminalnog čvora.
• U ovom slučaju ili MIN pobjeđuje, MAX pobjeđuje ili je neriješeno. Ovo stablo igre cijeli je prostor pretraživanja mogućnosti koje MIN i MAX igraju tic-tac-toe i naizmjenično se izmjenjuju.

Stoga kontradiktorna pretraga za minimax postupak funkcionira na sljedeći način:

• Cilj mu je pronaći optimalnu strategiju za pobjedu MAX-a u igri.
• Slijedi pristup pretraživanja najprije u dubinu.
• U stablu igre optimalni lisni čvor mogao bi se pojaviti na bilo kojoj dubini stabla.
• Širite minimalne vrijednosti do stabla dok se ne otkrije terminalni čvor.

U danom stablu igre, optimalna strategija može se odrediti iz minimax vrijednosti svakog čvora, koja se može napisati kao MINIMAX(n). MAX radije prelazi u stanje maksimalne vrijednosti, a MIN radije prelazi u stanje minimalne vrijednosti tada: