Az ellenérdekű keresés olyan keresés, ahol azt a problémát vizsgáljuk, amely akkor merül fel, amikor megpróbálunk a világ előtt tervezni, és más ügynökök terveznek ellenünk.

• Az előző témakörökben azokat a keresési stratégiákat tanulmányoztuk, amelyek csak egyetlen ágenshez kapcsolódnak, és célja a megoldás megtalálása, amely gyakran cselekvési sorozat formájában fejeződik ki.
• De előfordulhatnak olyan helyzetek, amikor egynél több ügynök keresi a megoldást ugyanazon a keresési területen, és ez a helyzet általában játék közben fordul elő.
• Az egynél több ágenssel rendelkező környezetet nak nevezzük többügynök környezet , amelyben minden ügynök egy másik ügynök ellenfele, és egymás ellen játszanak. Minden ügynöknek figyelembe kell vennie a másik ágens tevékenységét és annak hatását a teljesítményére.
• Így, Azokat a kereséseket, amelyek során két vagy több, egymással ütköző céllal rendelkező játékos ugyanazt a keresési teret próbálja feltárni a megoldásért, ellentmondásos keresésnek nevezik, gyakran játékok néven. .
• A játékok keresési problémaként és heurisztikus kiértékelő függvényként vannak modellezve, és ez a két fő tényező, amely segít a játékok modellezésében és megoldásában az AI-ban.

A mesterséges intelligencia játéktípusai:

Tökéletes információ:A tökéletes információval rendelkező játék az, amelyben az ügynökök belenézhetnek a teljes táblába. Az ügynökök minden információval rendelkeznek a játékról, és láthatják egymás lépéseit is. Ilyen például a sakk, a dáma, a go stb.Tökéletes információ:Ha egy játékban az ügynökök nem rendelkeznek minden információval a játékról, és nincsenek tisztában azzal, hogy mi történik, az ilyen típusú játékokat tökéletlen információkkal rendelkező játéknak nevezik, például tic-tac-toe, Battleship, blind, Bridge stb.Determinisztikus játékok:A determinisztikus játékok azok a játékok, amelyek szigorú mintát és szabályokat követnek a játékokra vonatkozóan, és nem társul hozzájuk véletlenszerűség. Ilyen például a sakk, a dáma, a go, a tic-tac-toe stb.Nem determinisztikus játékok:Nem determinisztikusnak nevezzük azokat a játékokat, amelyekben különféle előre nem látható események vannak, és amelyekben a véletlen vagy a szerencse tényezője is van. Ezt a véletlen vagy szerencse tényezőt kockák vagy kártyák vezetik be. Ezek véletlenszerűek, és az egyes akcióválaszok nem rögzítettek. Az ilyen játékokat sztochasztikus játékoknak is nevezik.
Példa: Backgammon, Monopoly, Póker stb.

Megjegyzés: Ebben a témakörben a determinisztikus játékokat, a teljesen megfigyelhető környezetet, a nulla összeget és azt, hogy az egyes ágensek felváltva működnek-e.

Zéró-összegű játék

• A nulla összegű játékok ellentmondásos keresés, amely tiszta versenyt foglal magában.
• A zéró összegű játékban minden ügynök haszonnyeresége vagy vesztesége pontosan kiegyenlítődik egy másik ügynök hasznosságának veszteségeivel vagy nyereségével.
• A játék egyik játékosa egyetlen értéket próbál maximalizálni, míg a másik játékos megpróbálja minimalizálni.
• A játékban egy játékos minden lépését ply-nek nevezzük.
• A sakk és a tic-tac-toe a nulla összegű játék példái.

Nulla összegű játék: Beágyazott gondolkodás

A nulla összegű játék beágyazott gondolkodást tartalmazott, amelyben az egyik ügynök vagy játékos megpróbálja kitalálni:

• Mit kell tenni.
• Hogyan döntsük el a lépést
• Az ellenfélre is gondolni kell
• Az ellenfél is gondolkodik, mit tegyen

A játékosok mindegyike megpróbálja kideríteni, hogyan reagál az ellenfél tetteire. Ehhez beágyazott gondolkodásra vagy visszamenőleges gondolkodásra van szükség az AI játékproblémáinak megoldásához.

A probléma formalizálása:

A játékot úgy határozhatjuk meg, mint egyfajta keresést az AI-ban, amely a következő elemekből formalizálható:

Kezdeti állapot:Meghatározza, hogy a játék hogyan legyen beállítva az elején.Játékos(ok):Meghatározza, hogy melyik játékos mozdult el az állapottérben.Művelet(ek):Visszaadja a legális lépések halmazát az állapottérben.Eredmény(ek, a):Ez az átmeneti modell, amely az állapottérben történő mozgások eredményét határozza meg.Terminál-teszt(ek):A terminálteszt igaz, ha a játéknak vége, egyébként minden esetben hamis. Azt az állapotot, ahol a játék véget ér, terminális állapotoknak nevezzük.Segédprogram(ok, p):Egy segédfunkció megadja a végső számértéket egy s terminálállapotban végződő játékhoz a p játékos esetében. Kifizető függvénynek is nevezik. A sakk esetében az eredmény győzelem, vereség vagy döntetlen, és a nyeremény értéke +1, 0, ½. A tic-tac-toe esetében pedig a hasznossági értékek +1, -1 és 0.

Játékfa:

A játékfa olyan fa, ahol a fa csomópontjai a játékállapotok, a fa élei pedig a játékosok lépései. A játékfa tartalmazza a kezdeti állapotot, a műveleti funkciót és az eredményfüggvényt.

Példa: Tic-Tac-Toe játékfa:

A következő ábra a tic-tac-toe játék játékfájának egy részét mutatja. Íme néhány kulcsfontosságú pont a játékban:

• Két játékos van MAX és MIN.
• A játékosoknak van egy másik körük, és MAX-mal kezdik.
• A MAX maximalizálja a játékfa eredményét
• A MIN minimalizálja az eredményt.

Példa magyarázat:

• A kezdeti állapottól számítva MAX-nak 9 lehetséges lépése van, mivel először kezd. MAX hely x és MIN hely o, és mindkét játékos felváltva játszik, amíg el nem érünk egy levél csomópontot, ahol az egyik játékosnak három van egy sorban, vagy az összes mező be nem töltődik.
• Mindkét játékos kiszámítja az egyes csomópontokat, a minimax-ot, azt a minimax értéket, amely a legjobb elérhető segédprogram az optimális ellenféllel szemben.
• Tegyük fel, hogy mindkét játékos jól ismeri a tic-tac-toe-t, és a legjobb játékot játssza. Minden játékos mindent megtesz, hogy megakadályozza a másik nyerését. MIN Max ellen lép fel a játékban.
• Tehát a játékfában van egy Max és egy MIN rétegünk, és mindegyik réteg neve: Ply . Max. helyezze el az x-et, majd a MIN beírja az o-t, hogy megakadályozza Max nyerését, és ez a játék a terminál csomópontig folytatódik.
• Ebben vagy MIN nyer, MAX nyer, vagy döntetlen. Ez a játékfa a lehetőségek teljes keresési tere, amelyben MIN és MAX tic-tac-toe-t játszanak, és felváltva váltják egymást.

Ezért a minimax eljárás kontradiktórius keresése a következőképpen működik:

• Célja, hogy megtalálja az optimális stratégiát a MAX számára a játék megnyeréséhez.
• A Mélységben való keresés megközelítését követi.
• A játékfában az optimális levélcsomópont a fa bármely mélységében megjelenhet.
• Addig terjessze a minimax értékeket a fába, amíg a terminálcsomópontot fel nem fedezi.

Egy adott játékfában az egyes csomópontok minimax értékéből határozható meg az optimális stratégia, amit MINIMAX(n)-ként írhatunk fel. A MAX a maximális értékű állapotba, a MIN pedig a minimális értékű állapotba szeretne váltani, majd: