Priešinga paieška yra paieška, kurios metu mes nagrinėjame problemą, kuri iškyla, kai bandome planuoti pasaulį anksčiau, o kiti agentai planuoja prieš mus.

• Ankstesnėse temose nagrinėjome paieškos strategijas, kurios yra susietos tik su vienu agentu, kurio tikslas – rasti sprendimą, kuris dažnai išreiškiamas veiksmų sekos forma.
• Tačiau gali pasitaikyti situacijų, kai daugiau nei vienas agentas ieško sprendimo toje pačioje paieškos erdvėje, ir tokia situacija dažniausiai pasitaiko žaidžiant žaidimą.
• Aplinka, kurioje yra daugiau nei vienas agentas, vadinama kaip kelių agentų aplinka , kuriame kiekvienas agentas yra kito agento priešininkas ir žaidžia vienas prieš kitą. Kiekvienas agentas turi atsižvelgti į kito agento veiksmus ir to veiksmo poveikį jų veiklai.
• Taigi, Paieškos, kurių metu du ar daugiau žaidėjų, kurių tikslai yra prieštaringi, bando ištirti tą pačią sprendimo paieškos erdvę, vadinamos priešingomis paieškomis, dažnai vadinamomis žaidimais. .
• Žaidimai modeliuojami kaip paieškos problema ir euristinio vertinimo funkcija, ir tai yra du pagrindiniai veiksniai, padedantys modeliuoti ir spręsti žaidimus naudojant AI.

AI žaidimų tipai:

Tobula informacija:Žaidimas su tobula informacija yra tas, kuriame agentai gali pažvelgti į visą lentą. Agentai turi visą informaciją apie žaidimą ir gali matyti vienas kito judesius. Pavyzdžiai yra šachmatai, šaškės, eiti ir kt.Netobula informacija:Jei žaidime agentai neturi visos informacijos apie žaidimą ir nežino, kas vyksta, tokio tipo žaidimai vadinami žaidimu su netobula informacija, pvz., tic-tac-toe, Battleship, blind, Bridge ir kt.Deterministiniai žaidimai:Deterministiniai žaidimai yra tie žaidimai, kurie vadovaujasi griežtu žaidimų modeliu ir taisyklių rinkiniu ir su jais nesusiję atsitiktinumai. Pavyzdžiai yra šachmatai, šaškės, „Go“, „tic-tac-toe“ ir kt.Nedeterministiniai žaidimai:Nedeterministiniai yra tie žaidimai, kurie turi įvairių nenuspėjamų įvykių ir turi atsitiktinumo ar sėkmės faktorių. Šis atsitiktinumo ar sėkmės veiksnys įvedamas kauliukais arba kortomis. Tai yra atsitiktiniai ir kiekvienas veiksmas nėra fiksuotas. Tokie žaidimai dar vadinami stochastiniais žaidimais.
Pavyzdys: nardai, monopolis, pokeris ir kt.

Pastaba: Šioje temoje aptarsime deterministinius žaidimus, visiškai stebimą aplinką, nulinę sumą ir tai, kur kiekvienas agentas veikia alternatyviai.

Nulinės sumos žaidimas

• Nulinės sumos žaidimai yra priešiška paieška, kuri apima gryną konkurenciją.
• Nulinės sumos žaidime kiekvieno agento naudos pelnas arba praradimas yra tiksliai subalansuotas su kito agento naudos praradimu arba pelnu.
• Vienas žaidimo žaidėjas stengiasi maksimaliai padidinti vieną reikšmę, o kitas bando ją sumažinti.
• Kiekvienas vieno žaidėjo ėjimas žaidime vadinamas sluoksniu.
• Šachmatai ir „tic-tac-toe“ yra nulinės sumos žaidimo pavyzdžiai.

Nulinės sumos žaidimas: integruotas mąstymas

Nulinės sumos žaidimas apėmė integruotą mąstymą, kai vienas agentas ar žaidėjas bando išsiaiškinti:

• Ką daryti.
• Kaip nuspręsti dėl žingsnio
• Reikia pagalvoti ir apie varžovą
• Priešininkas taip pat galvoja, ką daryti

Kiekvienas žaidėjas bando išsiaiškinti savo priešininko reakciją į jų veiksmus. Tam reikia integruoto mąstymo arba atgalinio samprotavimo, kad būtų išspręstos AI žaidimo problemos.

Problemos formalizavimas:

Žaidimą galima apibrėžti kaip AI paieškos tipą, kurį galima formalizuoti iš šių elementų:

Pradinė būsena:Jame nurodoma, kaip žaidimas nustatomas pradžioje.Žaidėjas (-ai):Nurodo, kuris žaidėjas pajudėjo būsenos erdvėje.Veiksmai):Jis grąžina teisėtų žingsnių rinkinį valstybės erdvėje.Rezultatas (-ai, a):Tai perėjimo modelis, nurodantis judesių būsenos erdvėje rezultatą.Terminalo testas (-ai):Terminalo testas yra teisingas, jei žaidimas baigtas, kitu atveju jis yra klaidingas. Būsena, kurioje žaidimas baigiasi, vadinama terminalinėmis būsenomis.Naudingumas (-ai, p):Naudingumo funkcija suteikia galutinę skaitinę reikšmę žaidimui, kuris baigiasi terminalo būsenomis s žaidėjui p. Ji taip pat vadinama išmokėjimo funkcija. Šachmatų atveju rezultatas yra laimėjimas, pralaimėjimas arba lygiosios, o jų išmokėjimo vertės yra +1, 0, ½. O tic-tac-toe naudingumo reikšmės yra +1, -1 ir 0.

Žaidimo medis:

Žaidimo medis yra medis, kuriame medžio mazgai yra žaidimo būsenos, o medžio kraštai yra žaidėjų judesiai. Žaidimo medis apima pradinę būseną, veiksmų funkciją ir rezultato funkciją.

Pavyzdys: Tic-Tac-Toe žaidimų medis:

Toliau pateiktame paveikslėlyje parodyta žaidimo medžio dalis, skirta „tic-tac-toe“ žaidimui. Toliau pateikiami keli pagrindiniai žaidimo punktai:

• Yra du žaidėjai MAX ir MIN.
• Žaidėjai turi alternatyvų eilę ir pradeda nuo MAX.
• MAX maksimaliai padidina žaidimo medžio rezultatą
• MIN sumažina rezultatą.

Paaiškinimo pavyzdys:

• Nuo pradinės būsenos MAX turi 9 galimus judesius, nes pradeda pirmas. MAX vieta x ir MIN vieta o, ir abu žaidėjai žaidžia pakaitomis, kol pasiekiame lapo mazgą, kur vienas žaidėjas turi tris iš eilės arba visi langeliai bus užpildyti.
• Abu žaidėjai apskaičiuos kiekvieną mazgą, minimax, minimax reikšmę, kuri yra geriausia pasiekiama priemonė prieš optimalų priešą.
• Tarkime, kad abu žaidėjai gerai žino „tic-tac-toe“ ir žaidžia geriausią žaidimą. Kiekvienas žaidėjas daro viską, kad kitas nelaimėtų. MIN žaidime veikia prieš Maxą.
• Taigi žaidimų medyje turime Max sluoksnį, MIN sluoksnį ir kiekvienas sluoksnis vadinamas kaip Ply . Max vieta x, tada MIN įdeda o, kad Max nelaimėtų, ir šis žaidimas tęsiasi iki terminalo mazgo.
• Šiuo atveju MIN laimi, MAX laimi arba lygiosios. Šis žaidimų medis yra visa galimybių paieškos erdvė, kurią MIN ir MAX pakaitomis žaidžia „tic-tac-toe“ ir paeiliui.

Taigi priešinga „minimax“ procedūros paieška veikia taip:

• Juo siekiama rasti optimalią strategiją, kaip MAX laimėti žaidimą.
• Jame laikomasi paieškos pagal gylį metodo.
• Žaidimo medyje optimalus lapo mazgas gali atsirasti bet kuriame medžio gylyje.
• Paskleiskite minimalias didžiausias reikšmes iki medžio, kol bus aptiktas galinis mazgas.

Tam tikrame žaidimų medyje optimalią strategiją galima nustatyti pagal kiekvieno mazgo minimax reikšmę, kurią galima parašyti kaip MINIMAX(n). MAX nori pereiti į didžiausios vertės būseną, o MIN – į minimalios vertės būseną, tada: