Oyun modellərinin konsepsiyası. Ödəniş matrisi

Cüt son oyununu nəzərdən keçirək. Qoy oyunçu A var T təyin edəcəyimiz şəxsi strategiyalar

Qoy oyunçu V var Pşəxsi strategiyalar, biz onları təyin edəcəyik. Deyirlər ki, oyunun bir ölçüsü var T X P.

Oyunçuların hər hansı bir cüt strategiya seçməsi nəticəsində oyunun nəticəsi unikal şəkildə müəyyən edilir, yəni. qazanc a;. oyunçu A(müsbət və ya mənfi) və itirmək (-ah) oyunçu V. Tutaq ki, dəyərlər a.. hər hansı bir cüt strategiya ilə tanınır (A :, B;.). Matris P =(a ..), i = = 1, 2, ..., m j = 1, 2, ..., P, elementləri strategiyalara uyğun gələn uduşlardır A. və Bj,çağırdı ödəniş matrisi, və ya oyunun matrisi. Ümumi forma belə bir matris cədvəldə təqdim olunur. 12.1. Bu cədvəlin sətirləri oyunçunun strategiyalarına uyğundur A, və sütunlar oyunçunun strategiyaları üçündür V.

Cədvəl 12.1

Gəlin növbəti oyun üçün ödəniş matrisi yaradaq.

12.1. Axtarış oyunu.

Oyunçu A iki sığınacaqdan birində (I və II) gizlənə bilər; oyunçu V oyunçu axtarır A, tapsa 1 den penalti alır. vahidlər -dan A,əks halda oyunçuya pul ödəyir A 1 gün vahidlər Oyunun ödəniş matrisini qurmaq lazımdır.

ilə qərar. Ödəniş matrisini tərtib etmək üçün oyunçuların hər birinin davranışını təhlil etməlisiniz. Oyunçu A I sığınacaqda gizlənə bilər - biz bu strategiyanı ilə işarə edirik A v ya kassada II - strategiya A. g Oyunçu V sığınacaq I - strategiyada ilk oyunçu axtara bilər V(və ya kassada II - strategiya V.,.Əgər oyunçu A I gizləndim və orada oyunçu tərəfindən aşkar edildi V, olanlar. bir neçə strategiya həyata keçirilir (Α ν V{), sonra oyunçu A cərimə ödəyir, yəni. a n = -1. Eynilə, biz də əldə edirik a. n = -1 (A 2, V.,). Aydındır ki, strategiyalar (A, V.,) və (A2, / 1,) oyunçuya verin A nəticə 1-dir, buna görə də a P = a. n = I. Beləliklə, 2x2 ölçülü "axtarış" oyunu üçün ödəniş matrisini əldə edirik:

Oyunu nəzərdən keçirin T X P matris ilə P = a j) , i = 1,2, ..., τη; j= 1, 2, ... və ən yaxşı strategiyanı müəyyənləşdirin A saat A v ..., A t) strategiyanın seçilməsi A jy oyunçu A oyunçu hesab etməlidir V strategiyalardan birinə cavab verəcək V., bunun üçün oyunçu üçün qazanc A minimal (oyunçu V oyunçuya "zərər verməyə" çalışır A).

a ilə işarə edək; oyunçunun ən kiçik qazancı A o, L strategiyasını seçdikdə; bütün mümkün oyunçu strategiyaları üçün V(ən kiçik ədəd i-ci xəttödəniş matrisi), yəni.

Bütün ədədlər arasında a (r = 1,2, ..., T)ən böyüyü seçin:. zəng edək amma oyunun sonunda, və ya maksimum qazanc (maksimum). Bu B oyunçusunun istənilən strategiyası üçün A oyunçusunun zəmanətli qazancı. Beləliklə,

(12.2)

Maksiminə uyğun strategiya deyilir maksimum strategiya. Oyunçu V oyunçunun uduşlarını azaltmaqda maraqlıdır A; strategiyanın seçilməsi V.,üçün bu halda mümkün olan maksimum qazancı nəzərə alır A. işarə edirik

Bütün ədədlər arasında β. ən kiçiyini seçin

və β-a zəng edin oyunun ən yüksək qiyməti, və ya Minimax qalibiyyət (minimax). Bu oyunçu B-nin zəmanətli itkisi. Beləliklə,

(12.4)

Minimaksa uyğun strategiya deyilir Minimax strategiyası.

Oyunçulara ən "diqqətli" minimax və maksimal strategiyaların seçimini diktə edən prinsip prinsip adlanır. minimaks. Bu prinsip, hər bir oyunçunun düşmənin əksinə bir məqsədə çatmağa çalışdığı ağlabatan fərziyyədən irəli gəlir. Problem 12.1-də oyunun aşağı və yuxarı qiymətlərini və müvafiq strategiyaları müəyyən edək. Ödəniş matrisini nəzərdən keçirin

12.1 problemindən. L strategiyasını (matrisanın birinci cərgəsi) seçərkən minimum qazanc a, = min (-l; 1) = -1-ə bərabərdir və oyunçunun β1 strategiyasına uyğundur. V. Bir strategiya seçərkən L 2 (matrisin ikinci cərgəsi) minimum ödənişdir a 2 = min (l; -1) = -1, strategiya ilə əldə edilir V.,.

Özünüzə zəmanət maksimum qalibiyyət hər hansı bir oyunçunun strategiyası üçün V, yəni. oyunun aşağı qiyməti a = max (a, a2) = = max (-l; -1) = -1, oyunçu A istənilən strategiyanı seçə bilər: Aj və ya A 2, yəni. onun hər hansı bir strategiyası maksimumdur.

B strategiyasının seçilməsi, (sütun 1), oyunçu V oyunçu olduğunu anlayır A strategiya ilə cavab verəcək A 2 qazancınızı artırmaq üçün (zərər V). Buna görə oyunçunun maksimum itkisi V o, B strategiyasını seçdikdə β, = yoxlayın (-1; 1) = 1-ə bərabərdir.

Eynilə, B oyunçusunun maksimum itkisi (qazanc A) B2 strategiyasını seçdikdə (sütun 2) β2 = max (l; -1) = 1 olur.

Beləliklə, hər hansı bir oyunçunun strategiyası üçün A B oyunçusunun zəmanətli minimum itkisi β = πιίη (β1, β2) = min (l; 1) = 1 - oyunun yuxarı qiyməti.

B oyunçusunun istənilən strategiyası minimumdur. Cədvəlin tamamlanması. 12.1 β sətri ilə; və a; sütunu, cədvəli alırıq. 12.2. Əlavə sətir və sütunların kəsişdiyi yerdə biz yuxarı və aşağı oyun qiymətlərini yazacağıq.

Cədvəl 12.2

Yuxarıda nəzərdən keçirilən 12.1 problemində yuxarı və aşağı oyun qiymətləri fərqlidir: a f β.

Əgər yuxarı və aşağı oyun qiymətləri eynidirsə, o zaman ümumi dəyərüst və aşağı qiymət oyunun α = β = υ adlanır oyunun təmiz qiyməti, və ya oyunun bahasına. Oyun qiymətinə uyğun minimax strategiyaları bunlardır optimal strategiyalar, və onların cəmi - optimal həll, və ya qərar oyunlar. Bu vəziyyətdə oyunçu A maksimum zəmanət alır (oyunçu davranışından asılı olmayaraq V) qazanc υ və oyunçu V minimum zəmanətli (oyunçu L davranışından asılı olmayaraq) itkiyə nail olur υ. Oyunun həlli olduğu deyilir sabitlik, olanlar. oyunçulardan biri öz optimal strategiyasına əməl edirsə, o zaman digərinin optimal strategiyasından kənara çıxması sərfəli ola bilməz.

Cütləşdirmək təmiz strategiyalar A. və V. oyunun optimal həllini o zaman verir ki, uyğun element rt eyni zamanda öz sütununda ən böyüyü və cərgəsində ən kiçik olsun. Belə bir vəziyyət, əgər varsa, deyilir yəhər nöqtəsi(bir istiqamətdə yuxarı, digərində isə aşağı əyilən yəhər səthinə bənzəyir).

işarə edirik A* və V*- yəhər nöqtəsi problemində oyunun həllinə nail olan bir cüt təmiz strategiya. Gəlin hər bir cüt strategiya üzrə ilk oyunçunun qazanc funksiyasını təqdim edək: P (A:, V-) = və at... Sonra, yəhər nöqtəsindəki optimallıq vəziyyətindən ikiqat bərabərsizlik yerinə yetirilir: P (Aj, B *)<Р(А*, В*)<Р(А", В ), bu hamı üçün doğrudur i = 1, 2, ..., m;j = 1, 2, ..., P. Həqiqətən, strategiya seçimi A* optimal strategiyası olan ilk oyunçu V" ikinci oyunçu minimum mümkün qələbəni maksimuma çatdırır: P (A*, B")> P (A G V"), və strategiya seçimi B " birincinin optimal strategiyasına malik ikinci oyunçu maksimum itkini minimuma endirir: P (D, V*)<Р(А", В).

12.2. Ödəniş matrisi ilə verilən oyunun aşağı və yuxarı qiymətini müəyyənləşdirin

Oyunun yəhər nöqtəsi varmı?

Cədvəl 12. 3

Həll. Matrisdən əlavə, cədvəldə bütün hesablamaları aparmaq rahatdır R, təqdim edilmiş a sütunu; və simli)