Kontradiktorno iskanje je iskanje, pri katerem preučujemo problem, ki nastane, ko poskušamo načrtovati pred svetom in drugi agenti načrtujejo proti nam.

• V prejšnjih temah smo preučevali iskalne strategije, ki so povezane le z enim samim agentom, katerega cilj je najti rešitev, ki je pogosto izražena v obliki zaporedja dejanj.
• Vendar pa lahko pride do nekaterih situacij, ko več kot en agent išče rešitev v istem iskalnem prostoru, in ta situacija se običajno pojavi med igranjem iger.
• Okolje z več kot enim agentom se imenuje kot okolje z več agenti , v katerem je vsak agent nasprotnik drugega agenta in igra drug proti drugemu. Vsak agent mora upoštevati delovanje drugega agenta in učinek tega dejanja na njihovo uspešnost.
• Torej, Iskanja, pri katerih dva ali več igralcev s nasprotujočimi si cilji poskuša raziskati isti iskalni prostor za rešitev, se imenujejo kontradiktorna iskanja, pogosto znana kot igre .
• Igre so modelirane kot problem iskanja in funkcija hevrističnega vrednotenja, to pa sta dva glavna dejavnika, ki pomagata pri modeliranju in reševanju iger v AI.

Vrste iger v AI:

Popolne informacije:Igra s popolnimi informacijami je tista, v kateri lahko agenti pogledajo celotno tablo. Agenti imajo vse informacije o igri in lahko vidijo tudi poteze drug drugega. Primeri so šah, dama, go itd.Nepopolne informacije:Če agenti v igri nimajo vseh informacij o igri in niso seznanjeni z dogajanjem, se takšne igre imenujejo igre z nepopolnimi informacijami, kot so tic-tac-toe, Battleship, blind, Bridge itd.Deterministične igre:Deterministične igre so tiste igre, ki sledijo strogemu vzorcu in nizu pravil za igre in z njimi ni povezana nobena naključnost. Primeri so šah, dama, go, tic-tac-toe itd.Nedeterministične igre:Nedeterministične so tiste igre, ki imajo različne nepredvidljive dogodke in dejavnik naključja ali sreče. Ta faktor naključja ali sreče uvedejo kocke ali karte. Ti so naključni in vsak odziv na dejanje ni določen. Take igre imenujemo tudi stohastične igre.
Primer: Backgammon, Monopoly, Poker itd.

Opomba: V tej temi bomo razpravljali o determinističnih igrah, popolnoma opazljivem okolju, ničelni vsoti in o tem, kje vsak agent deluje alternativno.

Igra z ničelno vsoto

• Igre z ničelno vsoto so tekmovalno iskanje, ki vključuje čisto konkurenco.
• V igri z ničelno vsoto je dobiček ali izguba koristnosti vsakega agenta natančno uravnotežena z izgubami ali dobički koristnosti drugega agenta.
• En igralec v igri poskuša povečati eno samo vrednost, drugi igralec pa jo poskuša zmanjšati.
• Vsaka poteza enega igralca v igri se imenuje ply.
• Šah in tic-tac-toe sta primera igre z ničelno vsoto.

Igra ničelne vsote: vgrajeno razmišljanje

Igra Zero-sum je vključevala vgrajeno razmišljanje, v katerem en agent ali igralec poskuša ugotoviti:

• Kaj storiti.
• Kako se odločiti za potezo
• Misliti mora tudi na nasprotnika
• Tudi nasprotnik razmišlja, kaj storiti

Vsak od igralcev poskuša ugotoviti odziv svojega nasprotnika na njihova dejanja. To zahteva vgrajeno razmišljanje ali sklepanje za nazaj, da bi rešili težave pri igri v AI.

Formalizacija problema:

Igro je mogoče opredeliti kot vrsto iskanja v AI, ki jo je mogoče formalizirati z naslednjimi elementi:

Začetno stanje:Določa, kako je igra nastavljena na začetku.Igralec(-i):Določa, kateri igralec se je premaknil v prostoru stanja.Dejanja:Vrne nabor zakonitih potez v prostoru stanja.Rezultat(i, a):Je prehodni model, ki podaja rezultat premikov v prostoru stanj.Terminalni test(i):Terminalni test je resničen, če je igre konec, drugače je v vsakem primeru false. Stanje, kjer se igra konča, imenujemo terminalna stanja.Pripomoček(i, p):Funkcija uporabnosti daje končno številčno vrednost za igro, ki se konča v končnih stanjih s za igralca p. Imenuje se tudi funkcija izplačila. Za šah so izidi zmaga, poraz ali remi, njegove vrednosti izplačila pa so +1, 0, ½. In za tic-tac-toe so vrednosti uporabnosti +1, -1 in 0.

Igralno drevo:

Drevo igre je drevo, kjer so vozlišča drevesa stanja igre, robovi drevesa pa so poteze igralcev. Drevo igre vključuje začetno stanje, funkcijo dejanj in funkcijo rezultata.

Primer: Drevo igre Tic-Tac-Toe:

pvr polna oblika

Naslednja slika prikazuje del igralnega drevesa za igro tic-tac-toe. Sledi nekaj ključnih točk igre:

• Igralca sta MAX in MIN.
• Igralci so na vrsti in začnejo z MAX.
• MAX poveča rezultat drevesne igre
• MIN minimizira rezultat.

Primer razlage:

• Iz začetnega stanja ima MAX 9 možnih potez, saj začne prvi. MAX postavi x in MIN postavi o in oba igralca igrata izmenično, dokler ne dosežemo listnega vozlišča, kjer ima en igralec tri v vrsti ali so vsa polja zapolnjena.
• Oba igralca bosta izračunala vsako vozlišče, minimax, minimalno vrednost, ki je najboljša dosegljiva uporabnost proti optimalnemu nasprotniku.
• Recimo, da se oba igralca dobro zavedata tik-tak-toe in igrata najboljšo igro. Vsak igralec se po svojih najboljših močeh trudi preprečiti drugemu zmagati. MIN nastopa proti Maxu v igri.
• V drevesu igre imamo torej plast Max, plast MIN in vsaka plast se imenuje as Ply . Max postavi x, nato MIN postavi o, da Maxu prepreči zmago, in ta igra se nadaljuje do vozlišča terminala.
• Pri tem bodisi zmaga MIN, zmaga MAX ali pa je neodločeno. To drevo iger je celoten prostor iskanja možnosti, ki jih MIN in MAX igrajo tik-tak-toe in se izmenjujejo.

Zato kontradiktorno iskanje postopka minimax deluje na naslednji način:

• Cilj je najti optimalno strategijo za zmago MAX-a.
• Sledi pristopu iskanja najprej v globino.
• V drevesu igre se lahko optimalno listno vozlišče pojavi na kateri koli globini drevesa.
• Razširite minimalne vrednosti do drevesa, dokler ni odkrito terminalsko vozlišče.

V danem igralnem drevesu lahko optimalno strategijo določimo iz minimalne vrednosti vsakega vozlišča, ki jo lahko zapišemo kot MINIMAX(n). MAX se raje premakne v stanje največje vrednosti, MIN pa se raje premakne v stanje najmanjše vrednosti, potem: