Sacensību meklēšana ir meklēšana, kurā mēs pārbaudām problēmu, kas rodas, cenšoties plānot pasaulei priekšā un citi aģenti plāno pret mums.

atgriešanas veids java

• Iepriekšējās tēmās mēs esam pētījuši meklēšanas stratēģijas, kas ir saistītas tikai ar vienu aģentu, kura mērķis ir atrast risinājumu, kas bieži izpaužas darbību secības formā.
• Taču var būt dažas situācijas, kad vairāk nekā viens aģents meklē risinājumu vienā meklēšanas telpā, un šī situācija parasti rodas spēlējot spēli.
• Vidi ar vairāk nekā vienu aģentu sauc par vairāku aģentu vide , kurā katrs aģents ir otra aģenta pretinieks un spēlē viens pret otru. Katram aģentam ir jāņem vērā cita aģenta darbība un šīs darbības ietekme uz viņu darbību.
• Tātad, Meklējumi, kuros divi vai vairāki spēlētāji ar pretrunīgiem mērķiem mēģina izpētīt vienu un to pašu risinājuma meklēšanas laukumu, tiek saukti par pretrunīgu meklēšanu, ko bieži sauc par spēlēm. .
• Spēles tiek modelētas kā meklēšanas problēma un heiristiskā novērtēšanas funkcija, un šie ir divi galvenie faktori, kas palīdz modelēt un atrisināt spēles AI.

AI spēļu veidi:

Perfekta informācija:Spēle ar perfektu informāciju ir tā, kurā aģenti var ieskatīties visā dēlī. Aģentiem ir visa informācija par spēli, un viņi var arī redzēt viens otra kustības. Piemēri ir šahs, dambrete, iet utt.Nepilnīga informācija:Ja spēlē aģentiem nav visas informācijas par spēli un viņi nezina, kas notiek, šāda veida spēles sauc par spēli ar nepilnīgu informāciju, piemēram, tic-tac-toe, Battleship, blind, Bridge utt.Deterministiskās spēles:Deterministiskās spēles ir tās spēles, kurās ir ievērots stingrs spēļu modelis un noteikumu kopums, un ar tām nav saistīta nejaušība. Piemēri ir šahs, dambrete, go, tic-tac-toe utt.Nedeterministiskas spēles:Nedeterminētas ir tās spēles, kurās ir dažādi neparedzami notikumi un kurās ir nejaušības vai veiksmes faktors. Šo nejaušības vai veiksmes faktoru ievada vai nu kauliņi, vai kārtis. Tie ir nejauši, un katra darbības reakcija nav fiksēta. Šādas spēles sauc arī par stohastiskām spēlēm.
Piemērs: bekgemons, monopols, pokers utt.

Piezīme. Šajā tēmā mēs apspriedīsim deterministiskās spēles, pilnībā novērojamo vidi, nulles summu un to, kur katrs aģents darbojas alternatīvi.

Nulles summas spēle

• Nulles summas spēles ir pretrunīga meklēšana, kas ietver tīru konkurenci.
• Nulles summas spēlē katra aģenta ieguvums vai lietderības zudums ir precīzi līdzsvarots ar cita aģenta lietderības zaudējumiem vai ieguvumiem.
• Viens spēles spēlētājs cenšas maksimāli palielināt vienu vērtību, bet otrs mēģina to samazināt.
• Katrs viena spēlētāja gājiens spēlē tiek saukts par kārtu.
• Šahs un tic-tac-toe ir nulles summas spēles piemēri.

Nulles summas spēle: iegultā domāšana

Nulles summas spēle ietvēra iegultu domāšanu, kurā viens aģents vai spēlētājs mēģina izdomāt:

• Ko darīt.
• Kā izlemt pārvietošanos
• Jādomā arī par pretinieku
• Pretinieks arī domā, ko darīt

Katrs no spēlētājiem cenšas noskaidrot pretinieka reakciju uz viņu rīcību. Tas prasa iegultu domāšanu vai atpakaļejošu spriešanu, lai atrisinātu spēles problēmas AI.

Problēmas formalizēšana:

Spēli var definēt kā AI meklēšanas veidu, ko var formalizēt no šādiem elementiem:

Sākotnējais stāvoklis:Tas norāda, kā spēle ir iestatīta sākumā.Spēlētājs(-i):Tas norāda, kurš spēlētājs ir pārvietojies stāvokļa telpā.Darbība(s):Tas atgriež likumīgo kustību kopumu stāvokļa telpā.Rezultāts(-i, a):Tas ir pārejas modelis, kas nosaka kustību rezultātu stāvokļa telpā.Termināļa tests(-i):Termināļa tests ir patiess, ja spēle ir beigusies, pretējā gadījumā tā ir nepatiesa jebkurā gadījumā. Stāvokli, kurā spēle beidzas, sauc par termināla stāvokļiem.Lietderība(-as, p):Lietderības funkcija sniedz galīgo skaitlisko vērtību spēlei, kas beidzas ar termināļa stāvokļiem s spēlētājam p. To sauc arī par atmaksas funkciju. Šaha gadījumā iznākums ir uzvara, zaudējums vai neizšķirts, un tā izmaksas vērtības ir +1, 0, ½. Un tic-tac-toe lietderības vērtības ir +1, -1 un 0.

Spēļu koks:

Spēļu koks ir koks, kurā koka mezgli ir spēles stāvokļi, bet koka malas ir spēlētāju kustības. Spēles koks ietver sākotnējo stāvokli, darbību funkciju un rezultāta funkciju.

Piemērs: Tic-Tac-Toe spēļu koks:

Nākamajā attēlā ir parādīta spēles koka daļa, kas paredzēta tic-tac-toe spēlei. Tālāk ir minēti daži spēles galvenie punkti:

• Ir divi spēlētāji MAX un MIN.
• Spēlētājiem ir alternatīvs gājiens un viņi sāk ar MAX.
• MAX palielina spēles koka rezultātu
• MIN samazina rezultātu.

Paskaidrojuma piemērs:

• No sākotnējā stāvokļa MAX ir 9 iespējamās kustības, jo viņš sāk pirmais. MAX vieta x un MIN vieta o, un abi spēlētāji spēlē pārmaiņus, līdz mēs sasniedzam lapas mezglu, kur vienam spēlētājam ir trīs pēc kārtas vai visi laukumi ir aizpildīti.
• Abi spēlētāji aprēķinās katru mezglu, minimax, minimax vērtību, kas ir vislabākā sasniedzamā lietderība pret optimālo pretinieku.
• Pieņemsim, ka abi spēlētāji labi apzinās tic-tac-toe un spēlē labāko spēli. Katrs spēlētājs dara visu iespējamo, lai neļautu citam uzvarēt. MIN spēlē pret Maksu.
• Tātad spēļu kokā mums ir Max slānis, MIN slānis, un katrs slānis tiek saukts kā Slānis . Max vieta x, tad MIN liek o, lai neļautu Max uzvarēt, un šī spēle turpinās līdz termināla mezglam.
• Šajā gadījumā MIN uzvar, MAX uzvar, vai arī rezultāts ir neizšķirts. Šis spēļu koks ir visa iespēju meklēšanas telpa, kurā MIN un MAX pārmaiņus spēlē tic-tac-toe.

Tādējādi pretrunīgā minimax procedūras meklēšana darbojas šādi:

• Tās mērķis ir atrast optimālo stratēģiju, lai MAX varētu uzvarēt spēli.
• Tas atbilst dziļuma meklēšanas pieejai.
• Spēles kokā optimālais lapu mezgls varētu parādīties jebkurā koka dziļumā.
• Izplatiet minimālās maksimālās vērtības līdz kokam, līdz tiek atklāts termināļa mezgls.

Dotajā spēļu kokā optimālo stratēģiju var noteikt no katra mezgla minimax vērtības, ko var uzrakstīt kā MINIMAX(n). MAX dod priekšroku pāriet uz maksimālās vērtības stāvokli un MIN dod priekšroku pāriet uz minimālās vērtības stāvokli, tad: