Oyunlar nəzəriyyəsi və statistik həllər.

Oyunçunun hərəkət seçimi adlanır hərəkət. Hərəkətlər var şəxsi(oyunçu şüurlu şəkildə qərar verir) və təsadüfi(oyunun nəticəsi oyunçunun iradəsindən asılı deyil). Oyunçunun hansı hərəkəti etməli olduğunu müəyyən edən qaydalar toplusu adlanır strategiya. Strategiyalar var təmiz(qeyri-təsadüfi oyunçu qərarları) və qarışıq(strategiya təsadüfi dəyişən kimi qəbul edilə bilər).

yəhər nöqtəsi

AT oyun nəzəriyyəsi S. t. ( yəhər elementi) sütunun ən böyük elementidir oyun matrisləri, bu da müvafiq sıranın ən kiçik elementidir (in iki nəfərlik sıfır cəmi oyunu). Bu nöqtədə, buna görə də, bir oyunçunun maksimumu digərinin minimumuna bərabərdir; S. t. bir məqam var tarazlıq.

Minimaks teoremi

Minimax strategiyası deyilir Minimax strategiyası.

Oyunçulara ən "ehtiyatlı" maksimum və minimaks strategiyalarının seçimini diktə edən prinsip adlanır. Minimax prinsipi. Bu prinsip hər bir oyunçunun rəqibin əks məqsədinə çatmağa çalışdığı ağlabatan fərziyyədən irəli gəlir.

Oyunçu rəqibin əlverişsiz hərəkət edəcəyini düşünərək öz hərəkətlərini seçir, yəni. zərər verməyə çalışacaq.

Zərər funksiyası

Zərər funksiyası statistik qərarlar nəzəriyyəsində müşahidə edilən məlumatlar əsasında düzgün qərar qəbul edilməməsi nəticəsində yaranan itkiləri xarakterizə edən funksiyadır. Müdaxilə fonunda siqnal parametrinin qiymətləndirilməsi problemi həll edilirsə, itki funksiyası arasında uyğunsuzluğun ölçüsüdür. əsl dəyər təxmin edilən parametr və parametr qiymətləndirməsi

Oyunçunun Optimal Qarışıq Strategiyası verilmiş ehtimallarla eyni şəraitdə oyunun çoxsaylı təkrarlarında onun xalis strategiyalarının tətbiqlərinin tam dəstidir.

Oyunçunun qarışıq strategiyası verilmiş ehtimallarla eyni şəraitdə oyunun bir neçə dəfə təkrarlanması halında onun xalis strategiyalarının tətbiqinin tam dəstidir.

1. Əgər cərgənin bütün elementləri başqa sətrin müvafiq elementlərindən böyük deyilsə, onda ilkin cərgə ödəniş matrisindən silinə bilər. Sütunlar üçün də eynilə.

2. Oyunun qiyməti unikaldır.

Sənəd: tutaq ki, 2 oyunun qiyməti var v və , cütdə və müvafiq olaraq əldə edilir, sonra

3. Əgər qazanc matrisinin bütün elementlərinə eyni ədəd əlavə olunarsa, o zaman optimal qarışıq strategiyalar dəyişməyəcək və oyunun qiyməti bu rəqəmlə artacaq.

Sənəd:
, harada

4. Ödəniş matrisinin bütün elementləri sıfıra bərabər olmayan eyni ədədə vurularsa, oyunun qiyməti bu rəqəmə vurulacaq və optimal strategiyalar dəyişməyəcək.

A oyunçusunun qarışıq strategiyası SA p1, p2, ..., pi, ..., pm ehtimalları ilə A1, A2, ..., Am təmiz strategiyalarının tətbiqidir və ehtimalların cəmi 1-ə bərabərdir: A oyunçusunun qarışıq strategiyaları matris və ya sətir kimi yazılır SA = (p1, p2, ..., pi, ..., pm) Eynilə, B oyunçusunun qarışıq strategiyaları da işarələnir: , və ya, SB = (q1, q2, ..., qi, ..., qn ), burada strategiyaların görünmə ehtimallarının cəmi 1-ə bərabərdir: Təmiz strategiyalar qarışıq olanların xüsusi halı hesab oluna və 1-in xalis strategiyaya uyğun gəldiyi sətir kimi verilə bilər. Minimax prinsipinə əsasən oyunun optimal həlli (və ya həlli) müəyyən edilir: bu, S*A, S*B ümumi halda qarışıq, aşağıdakı xüsusiyyətlərə malik olan optimal strategiyaların cütüdür: oyunçulardan biri əməl edərsə. onun optimal strategiyasına uyğunlaşarsa, ondan kənara çıxmaq digəri üçün sərfəli ola bilməz. Optimal həllə uyğun gəlir v oyunun dəyəri adlanır. Oyunun qiyməti bərabərsizliyi ödəyir: ? ? v? ? (3.5) harada? və? - oyunun aşağı və yuxarı qiymətləri. Oyun nəzəriyyəsinin aşağıdakı əsas teoremi etibarlıdır - Neyman teoremi. Hər bir oyun sonu var ən azı bir optimal həll, bəlkə də arasında qarışıq strategiyalar. S*A = (p*1, p*2, ..., p*i, ..., p*m) və S*B = (q*1, q*2, ..., q* olsun. i, ..., q*n) - optimal strategiyalar cütü. Əgər xalis strategiya sıfırdan fərqli ehtimalla optimal qarışıq strategiyaya daxil edilirsə, o zaman aktiv adlanır. Aktiv strategiyalar haqqında teorem etibarlıdır: əgər oyunçulardan biri öz optimal qarışıq strategiyasına əməl edərsə, ikinci oyunçu öz aktiv strategiyalarından kənara çıxmasa, qazanc dəyişməz və v oyunun dəyərinə bərabər qalır. Bu teorem böyük praktik əhəmiyyətə malikdir - yəhər nöqtəsi olmadıqda optimal strategiyaların tapılması üçün xüsusi modellər verir. Sonlu oyunun ən sadə halı olan 2×2 oyununu nəzərdən keçirək. Belə bir oyunun yəhər nöqtəsi varsa, optimal həll bu nöqtəyə uyğun gələn bir cüt təmiz strategiyadır. Oyun nəzəriyyəsinin əsas teoreminə uyğun olaraq, yəhər nöqtəsi olmayan bir oyun, optimal həll mövcuddur və S*A = (p*1, p*2) və S*B cüt qarışıq strategiyaları ilə müəyyən edilir. = (q*1, q*2) . Onları tapmaq üçün biz aktiv strategiyalar haqqında teoremdən istifadə edirik. Əgər A oyunçusu optimal S "A strategiyasına sadiq qalırsa, B oyunçusunun hansı aktiv strategiyadan istifadə etməsindən asılı olmayaraq, onun orta qazancı v oyunun qiymətinə bərabər olacaq. 2 × 2 oyun üçün rəqibin istənilən xalis strategiyası yəhər nöqtəsi olmadıqda aktivdir.A oyunçusunun qazancı (B oyunçusunun itkisi) - təsadüfi dəyişən, gözlənilən dəyər(orta) oyunun qiymətidir. Buna görə də, A oyunçusunun orta qazancı (optimal strategiya) rəqibin həm 1-ci, həm də 2-ci strategiyaları üçün v-yə bərabər olacaqdır. Oyun qazanc matrisi ilə verilsin, əgər A oyunçusunun orta qazancı, əgər optimal qarışıq strategiyadan istifadə edirsə və B oyunçusu B1 xalis strategiyasından istifadə edirsə (bu, P qazanc matrisinin 1-ci sütununa uyğundur) oyunun qiyməti v: a11 p*1+ a21 p*2 = v. 2-ci oyunçu B2 strategiyasından istifadə edərsə, A oyunçusu eyni orta gəliri alır, yəni. a12 p*1+ a22 p*2= v. p * 1 + p * 2 = 1 olduğunu nəzərə alaraq, optimal strategiya S "A və v oyunun dəyərini təyin etmək üçün tənliklər sistemi əldə edirik: (3.6) Bu sistemi həll edərək, optimal strategiyanı (3.7) və əldə edirik. oyunun dəyəri (3.8) SВ* - B oyunçusunun optimal strategiyasını taparkən aktiv strategiyalar haqqında teoremi tətbiq edərək, əldə edirik ki, A oyunçusunun istənilən xalis strategiyası üçün (A1 və ya A2) B oyunçusunun orta itkisi bərabərdir. oyunun qiyməti v, yəni (3.9) Sonra optimal strategiya düsturlarla müəyyən edilir: (3.10 )

İqtisadiyyatda riyazi metodlar və modellər

Matris oyunları

Giriş

İqtisadi təcrübədə tez-tez müxtəlif tərəflərin fərqli məqsədlər güddüyü vəziyyətlər yaranır. Məsələn, satıcı ilə alıcı, təchizatçı ilə istehlakçı, bank və əmanətçi münasibətləri və s. Belə münaqişəli vəziyyətlər təkcə iqtisadiyyatda deyil, digər fəaliyyətlərdə də yaranır. Məsələn, şahmat, dama, domino, loto və s.

Oyun- bu riyazi model bir neçə istifadə edərək ən azı iki şəxsin iştirak etdiyi münaqişə vəziyyəti müxtəlif yollarla məqsədlərinizə çatmaq üçün. Oyun adlanır buxar otağı, iştirak edən iki oyunçu varsa. Oyun adlanır antaqonist bir oyunçunun qazancı digərinin itkisinə bərabərdirsə. Buna görə də, oyunu müəyyən etmək üçün bir oyunçunun müxtəlif vəziyyətlərdə qazanclarını dəqiqləşdirmək kifayətdir.

Mövcud vəziyyətdən asılı olaraq oyunçunun hərəkət edə biləcəyi hər hansı bir üsul deyilir strategiya. Hər bir oyunçunun müəyyən bir strategiya dəsti var. Strategiyaların sayı məhduddursa, oyun çağırılır final, əks halda - sonsuz . Strategiyalar deyilir təmiz, oyunçuların hər biri təsadüfi deyil, müəyyən bir şəkildə yalnız bir strategiya seçsə.

Oyun qərarı qane edən strategiya seçməkdir optimallıq şərti. Bu şərt bir oyunçunun əldə etməsidir maksimum qalibiyyət, ikincisi öz strategiyasına sadiq qalarsa. Əksinə, ikinci oyunçu alır minimum itki, əgər birinci oyunçu öz strategiyasına sadiq qalırsa. Belə strategiyalar adlanır optimal . Bu minvalla, Oyunun məqsədi hər bir oyunçu üçün optimal strategiyanı müəyyən etməkdir.

Təmiz strategiyalarda oynamaq

İki oyunçu ilə bir oyun düşünün AMMA və AT. Gəlin oyunçunu fərz edək AMMA Bu var m strategiyalar A 1, A 2, ..., A m, və oyunçu AT Bu var n strategiyalar B 1 , B 2 , … , B n . Biz oyunçunun seçimi olduğunu düşünürük AMMA strategiyalar Və mən , amma oyunçu AT strategiyalar Bj oyunun nəticəsini unikal şəkildə müəyyənləşdirir, yəni. qalib aij oyunçu AMMA və qalibiyyət b ij oyunçu AT. Burada i=1,2,…,m, j=1,2,…,n.

Ən sadə iki oyunçu oyunu antaqonist oyundur. , olanlar. oyunçuların maraqlarının birbaşa zidd olduğu oyun. Bu vəziyyətdə oyunçuların qazancları bərabərliklə əlaqələndirilir

b ij =-a ij

Bu bərabərlik o deməkdir ki, oyunçulardan birinin qazancı digərinin itkisinə bərabərdir. Bu halda, yalnız oyunçulardan birinin, məsələn, oyunçunun qazancını nəzərə almaq kifayətdir. AMMA.

Hər bir cüt strategiya A i və B j matçda qələbə aij oyunçu AMMA. Bütün bu ödənişləri sözdə şəklində yazmaq rahatdır ödəniş matrisi

Bu matrisin sıraları oyunçunun strategiyalarına uyğundur AMMA, və sütunlar oyunçunun strategiyalarıdır AT.Ümumiyyətlə, belə bir oyun adlanır (m×n)-oyun.

Misal 1 iki oyunçu AMMA və AT sikkə atmaq. Əgər sikkənin tərəfləri eynidirsə, o zaman qalibdir AMMA, yəni. oyunçu AT oyunçuya pul ödəyir AMMA bəzi məbləğ 1-ə bərabərdir və uyğun gəlmirsə, B oyunçusu qalib gəlir, yəni. əksinə, oyunçu AMMA oyunçuya pul ödəyir AT eyni miqdar , bərabərdir 1. Ödəniş matrisi yaradın.

Həll. Tapşırığa görə

Oyunçuların optimal xalis strategiyaları qarışıq strategiyalardan məcburi vahid p i = 1, q i = 1 olması ilə fərqlənir. Məsələn: P(1,0), Q(1,0). Burada p 1 = 1, q 1 = 1.

Tapşırıq 1
Ödəniş matrisinə əsaslanaraq, ciddi dominantlıq prinsipindən istifadə edərək optimal təmiz strategiyaları tapın. Cavab olaraq P*, Q* vektorlarını yazın.

Matrix Game kalkulyatorundan istifadə edərək bütün problemləri həll edirik.

Güman edirik ki, I oyunçu öz strategiyasını öz qazancını maksimuma çatdıracaq şəkildə, II oyunçu isə strategiyasını I oyunçunun qazancını minimuma endirəcək şəkildə seçir.

p 1 = 1
p2 = 0
Oyunun qiyməti, y = 1
İndi B oyunçusunun minimaks strategiyasını müvafiq tənliklər sistemini yazmaqla tapa bilərik
q 1 = 1
q1 + q2 = 1
Bu sistemi həll edərək, tapırıq:
q1 = 1.
Cavab:
Oyun qiyməti: y = 1, oyunçuların strategiya vektorları:
Q(1, 0), P(1, 0)

∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (1 1) + (2 0) = 1 = v
M(P 2 ;Q) = (-2 1) + (-2 0) = -2 ≤ v
M(P;Q 1) = (1 1) + (-2 0) = 1 = v
M(P;Q 2) = (2 1) + (-2 0) = 2 ≥ v

Satır və sütunlar orijinal matrisdən çıxarıldığı üçün tapılan ehtimal vektorları aşağıdakı kimi yazıla bilər:
P(1,0,0,0)
Q(0,1,0,0)

Tapşırıq 2
Ödəniş matrisindən istifadə edərək, oyunun aşağı və yuxarı qiymətini tapın. Yəhər nöqtəsi olduqda, optimal təmiz strategiyaların P*, Q* vektorlarını yazın.

Tapşırıq 3
Ödəniş matrisindən istifadə edərək optimal strategiyaların P*, Q* vektorlarını və oyunun qiymətini tapın. Hansı oyunçu qalibdir?

A oyunçusunun maksimal optimal strategiyası N nöqtəsinə uyğundur, bunun üçün aşağıdakı tənliklər sistemini yazmaq olar:
p1 = 0
p2 = 1
Oyunun qiyməti, y = -2
İndi B oyunçusuna daha çox itki verən B 1 ,B 3 ,B 4 strategiyasını aradan qaldıraraq müvafiq tənliklər sistemini yazmaqla B oyunçusunun minimaks strategiyasını tapa bilərik və buna görə də q 1 = 0,q 3 = 0,q 4 = 0 .
-2q 2 = -2
q2 = 1
Bu sistemi həll edərək, tapırıq:
q2 = 1.
Cavab:
Oyun qiyməti: y = -2, oyunçuların strategiya vektorları:
Q(0, 1, 0, 0), P(0, 1)
4. Strategiya optimallıq meyarından istifadə edərək oyun həllinin düzgünlüyünü yoxlayın.
∑a ij q j ≤ v
∑a ij p i ≥ v
M(P 1 ;Q) = (-6 0) + (-6 1) + (2 0) + (4 0) = -6 ≤ v
M(P 2 ;Q) = (2 0) + (-2 1) + (7 0) + (-1 0) = -2 = v
M(P;Q 1) = (-6 0) + (2 1) = 2 ≥ v
M(P;Q 2) = (-6 0) + (-2 1) = -2 = v
M(P;Q 3) = (2 0) + (7 1) = 7 ≥ v
M(P;Q 4) = (4 0) + (-1 1) = -1 ≥ v
Bütün bərabərsizliklər bərabərlik və ya ciddi bərabərsizliklər kimi ödənilir, buna görə də oyunun həlli düzgün tapılır.

Tapşırıq 4
Suala ətraflı cavab verin

Fizika-texnika fakültəsini bitirsəm də, universitetdə mənə oyun nəzəriyyəsi oxumadılar. Amma mən daxil olduğum üçün tələbəlik illəriƏvvəlcə üstünlük, sonra körpüdə çox oynadım, oyun nəzəriyyəsi ilə maraqlandım və kiçik bir dərsliyi mənimsədim. Və bu yaxınlarda saytın oxucusu Mixail bir oyun nəzəriyyəsi problemini həll etdi. Tapşırığın mənə dərhal verilmədiyini anlayaraq, oyun nəzəriyyəsi ilə bağlı biliklərimi yaddaşımda təzələmək qərarına gəldim. Mən sizə kiçik bir kitab təklif edirəm - oyun nəzəriyyəsi elementlərinin məşhur təqdimatı və matris oyunlarının həlli üçün bəzi üsullar. O, demək olar ki, heç bir sübut ehtiva etmir və nəzəriyyənin əsas müddəalarını nümunələrlə göstərir. Kitab riyaziyyatçı və elmin populyarlaşdırıcısı Elena Sergeevna Wentzel tərəfindən yazılmışdır. Sovet mühəndislərinin bir neçə nəsli onun "Ehtimal nəzəriyyəsi" dərsliyindən öyrənmişdir. Yelena Sergeevna İ.Qrekova təxəllüsü ilə də bir neçə ədəbi əsər yazmışdır.

Elena Ventzel. Oyun nəzəriyyəsinin elementləri. – M.: Fizmətqız, 1961. – 68 s.

Yüklə qısa xülasə formatda və ya

§ 1. Oyun nəzəriyyəsinin mövzusu. Əsas anlayışlar

Bir sıra praktiki problemləri həll edərkən (iqtisadiyyat, hərbi məsələlər və s.) bir-birinə zidd məqsədlər güdən iki (və ya daha çox) döyüşən tərəfin olduğu vəziyyətləri və onlardan birinin hər bir hərəkətinin nəticəsini təhlil etmək lazımdır. tərəflər rəqibin hansı hərəkət kursunu seçməsindən asılıdır. Biz belə halları “münaqişə vəziyyətləri” adlandıracağıq.

Müxtəlif təcrübə sahələrindən münaqişə vəziyyətlərinə dair çoxsaylı misallar çəkmək olar. Döyüş əməliyyatları zamanı yaranan istənilən vəziyyət münaqişə vəziyyətlərinə aiddir: döyüşən tərəflərin hər biri düşmənin uğur qazanmasının qarşısını almaq üçün əlində olan bütün tədbirləri görür. Münaqişəli vəziyyətlərə silah sistemi, onun döyüş istifadə üsulları seçərkən və ümumiyyətlə, hərbi əməliyyatların planlaşdırılması zamanı yaranan vəziyyətlər də daxildir: bu sahədə qərarların hər biri düşmənin bizə ən az sərfəli olan hərəkətləri əsasında qəbul edilməlidir. . İqtisadiyyat sahəsində bir sıra situasiyalar (xüsusilə azad rəqabət şəraitində) konfliktli situasiyalara aiddir; döyüşən tərəf kimi ticarət firmaları, sənaye müəssisələri və s.

Belə vəziyyətlərin təhlili ehtiyacı xüsusi riyazi aparatı həyata keçirdi. Oyun nəzəriyyəsi əslində münaqişə vəziyyətlərinin riyazi nəzəriyyəsindən başqa bir şey deyil. Nəzəriyyənin məqsədi münaqişə vəziyyətində rəqiblərin hər birinin rasional hərəkət kursuna dair tövsiyələr hazırlamaqdır. Təcrübədən birbaşa götürülmüş hər bir münaqişə vəziyyəti çox mürəkkəbdir və onun təhlili çoxsaylı təsadüfi amillərin olması ilə mürəkkəbləşir. Vəziyyətin riyazi təhlilini mümkün etmək üçün ikinci dərəcəli, təsadüfi amillərdən mücərrədləşmək və vəziyyətin sadələşdirilmiş, rəsmiləşdirilmiş modelini qurmaq lazımdır. Belə bir modeli “oyun” adlandıracağıq.

Oyun real münaqişə vəziyyətindən onun dəqiq müəyyən edilmiş qaydalara uyğun aparılması ilə fərqlənir. Bəşəriyyət sözün hərfi mənasında oyun olan konflikt vəziyyətlərinin belə rəsmiləşdirilmiş modellərindən çoxdan istifadə edir. Buna misal olaraq şahmat, dama, kart oyunları və s. Bütün bu oyunlar məlum qaydalara uyğun davam edən və bu və ya digər oyunçunun “qələbəsi” (qalibiyyəti) ilə bitən rəqabət xarakteri daşıyır.

Belə formal tənzimlənən, süni təşkil edilən oyunlar ən çox olur uyğun material oyun nəzəriyyəsinin əsas anlayışlarını təsvir etmək və mənimsəmək. Bu cür oyunların təcrübəsindən götürülmüş terminologiya digər münaqişə vəziyyətlərinin təhlilində də istifadə olunur: onlara cəlb olunan tərəflər şərti olaraq "oyunçular" adlanır və toqquşmanın nəticəsi tərəflərdən birinin "qalibiyyəti" adlanır.

Oyunda iki və ya daha çox rəqibin maraqları toqquşa bilər; birinci halda, oyun "ikiqat", ikincidə - "çox" adlanır. Çoxlu oyunun iştirakçıları onun gedişində koalisiya yarada bilərlər - daimi və ya müvəqqəti. İki daimi koalisiyanın iştirakı ilə çoxlu oyun bir cüt oyuna çevrilir. Cütlənmiş oyunlar ən böyük praktik əhəmiyyətə malikdir; Burada özümüzü yalnız belə oyunları nəzərdən keçirməklə məhdudlaşdırırıq.

Elementar oyun nəzəriyyəsinin təqdimatına bəzi əsas anlayışların formalaşdırılması ilə başlayaq. İki oyunçunun A və B-nin əks maraqlarla iştirak etdiyi bir cüt oyunu nəzərdən keçirəcəyik. “Oyun” dedikdə biz A və B tərəflərinin bir sıra hərəkətlərindən ibarət hadisəni nəzərdə tuturuq. Oyunun riyazi təhlilə məruz qalması üçün oyunun qaydaları dəqiq şəkildə tərtib edilməlidir. "Oyun qaydaları" hər iki tərəfin hərəkətləri üçün mümkün variantları, hər bir tərəfin digərinin davranışı haqqında malik olduğu məlumatların miqdarını, "hərəkətlərin" növbələşmə ardıcıllığını (məşğulluq zamanı qəbul edilən fərdi qərarlar) tənzimləyən şərtlər sistemi deməkdir. oyun), həmçinin bu hərəkət dəstinə səbəb olan oyunun nəticəsi və ya nəticəsi. Bu nəticə (qalibiyyət və ya itki) həmişə kəmiyyətlə ifadə edilmir, lakin adətən müəyyən ölçü miqyasını təyin etməklə onu ifadə etmək mümkündür. müəyyən sayda. Məsələn, şahmat oyununda qalibiyyət şərti olaraq +1, məğlubiyyət -1, heç-heçə 0 qiyməti təyin edilə bilər.

Bir oyunçu digərinin itirdiyini qazanırsa, oyun sıfır məbləğli oyun adlanır, yəni. hər iki tərəfin ödənişlərinin cəmi sıfırdır. Sıfır məbləğli oyunda oyunçuların maraqları birbaşa əksdir. Burada yalnız belə oyunları nəzərdən keçirəcəyik.

Sıfır məbləğli oyunda oyunçulardan birinin qazancı digərinin qazancı ilə bərabər olduğu üçün əks işarə, onda, açıq-aydın, belə bir oyunu təhlil edərkən, oyunçulardan yalnız birinin qazancını nəzərə almaq olar. Məsələn, A oyunçusu olsun. Gələcəkdə rahatlıq üçün şərti olaraq A tərəfini “biz”, B tərəfini isə “rəqib” adlandıracağıq.

Bu halda A tərəfi (“biz”) həmişə “qalib”, B tərəfi (“rəqib”) isə “uduzmuş” hesab olunacaq. Bu formal şərt ilk oyunçu üçün heç bir real üstünlük demək deyil; ödəmə işarəsi tərsinə çevrildikdə onun əksi ilə əvəz olunduğunu görmək asandır.

Zamanla oyunun inkişafını bir sıra ardıcıl mərhələlərdən və ya "hərəkətlərdən" ibarət olaraq təqdim edəcəyik. Oyun nəzəriyyəsində hərəkət oyun qaydaları ilə nəzərdə tutulmuş variantlardan birinin seçilməsidir. Hərəkətlər şəxsi və təsadüfi bölünür. Şəxsi hərəkət, müəyyən bir vəziyyətdə mümkün olan hərəkətlərdən birini və onun həyata keçirilməsini oyunçulardan birinin şüurlu seçimidir. Şəxsi hərəkətə misal olaraq şahmat oyunundakı hər hansı bir hərəkəti göstərmək olar. Növbəti hərəkəti yerinə yetirərək, oyunçu lövhədə parçaların müəyyən bir düzülüşü üçün mümkün olan variantlardan birini şüurlu şəkildə seçir. Hər bir şəxsi gediş üçün mümkün variantlar toplusu oyun qaydaları ilə tənzimlənir və hər iki tərəfin əvvəlki hərəkətlərinin cəmindən asılıdır.

Təsadüfi hərəkət oyunçunun qərarı ilə deyil, təsadüfi seçim mexanizmi ilə həyata keçirilən bir sıra imkanlar arasından seçimdir (bir sikkə atmaq, zər atmaq, kartları qarışdırmaq və satmaq və s.). Məsələn, ilk kartı üstünlük verilən oyunçulardan birinə vermək 32 bərabər mümkün variantla təsadüfi bir hərəkətdir. Oyunun riyazi olaraq müəyyən edilməsi üçün oyun qaydaları hər bir təsadüfi hərəkət üçün mümkün nəticələrin ehtimal paylanmasını müəyyən etməlidir.

Bəzi oyunlar yalnız təsadüfi hərəkətlərdən (saf şans oyunları adlanır) və ya yalnız şəxsi hərəkətlərdən (şahmat, dama) ibarət ola bilər. Çoxluq kart oyunları oyunlara aiddir qarışıq tip, yəni. həm təsadüfi, həm də şəxsi hərəkətləri ehtiva edir.

Oyunlar yalnız hərəkətlərin təbiətinə görə (şəxsi, təsadüfi) deyil, həm də başqasının hərəkətləri ilə bağlı hər bir oyunçu üçün mövcud olan məlumatların xarakteri və miqdarı ilə təsnif edilir. Oyunların xüsusi sinfi "oyunlar" adlanan oyunlardır tam məlumat". Tam məlumatı olan oyun, hər bir oyunçunun hər bir şəxsi hərəkətdə həm şəxsi, həm də təsadüfi bütün əvvəlki hərəkətlərin nəticələrini bildiyi bir oyundur. Tam məlumatı olan oyunlara misal olaraq şahmat, dama və məşhur tic-tac-toe oyununu göstərmək olar.

Praktiki əhəmiyyət kəsb edən oyunların əksəriyyəti tam məlumatı olan oyunlar sinfinə aid deyil, çünki rəqibin hərəkətləri haqqında naməlum olanlar adətən münaqişə vəziyyətlərinin vacib elementidir.

Oyun nəzəriyyəsinin əsas anlayışlarından biri “strategiya” anlayışıdır. Oyunçunun strategiyası oyun zamanı yaranmış vəziyyətdən asılı olaraq verilmiş oyunçunun hər bir şəxsi hərəkəti üçün seçimi birmənalı şəkildə müəyyən edən qaydalar toplusudur. Adətən, hər bir şəxsi hərəkət üçün qərar (seçim) mövcud konkret vəziyyətdən asılı olaraq, oyunun özü tərəfindən oyunçu tərəfindən verilir. Ancaq nəzəri olaraq bütün bu qərarların futbolçu tərəfindən əvvəlcədən verildiyini təsəvvür etsək, məsələ dəyişmir. Bunun üçün oyunçu əvvəlcədən oyunun gedişində bütün mümkün vəziyyətlərin siyahısını tərtib etməli və onların hər biri üçün öz həllini təqdim etməli idi. Prinsipcə (praktik olaraq deyilsə) bu, istənilən oyun üçün mümkündür. Əgər belə bir qərar sistemi qəbul olunarsa, bu, oyunçunun müəyyən strategiya seçməsi demək olacaq.

Strategiya seçmiş oyunçu indi oyunda şəxsən iştirak edə bilməz, ancaq iştirakını hansısa maraqsız şəxsin (hakim) onun üçün müraciət edəcəyi qaydalar siyahısı ilə əvəz edə bilər. Strategiya avtomata konkret proqram şəklində də verilə bilər. Hazırda kompüter şahmatını belə oynayırlar. “Strategiya” anlayışının məna kəsb etməsi üçün oyunda şəxsi hərəkətlər olmalıdır; tək təsadüfi hərəkətlərdən ibarət oyunlarda heç bir strategiya yoxdur.

Mümkün strategiyaların sayından asılı olaraq oyunlar “sonlu” və “sonsuz”a bölünür. Hər bir oyunçunun yalnız məhdud sayda strategiyası varsa, oyunun sonlu olduğu deyilir. A oyunçusunun oynadığı son oyun m strategiyalar və oyunçu B n strategiyalar mxn oyunu adlanır.

A və B ("biz" və "rəqib") iki oyunçunun mxn oyununu nəzərdən keçirək. Strategiyalarımızı A 1 , A 2 , …, A m düşmən strategiyalarımızı B 1 , B 2 , …, B n qeyd edəcəyik. Qoy hər tərəf müəyyən strategiya seçsin; bizim üçün A i , rəqib üçün B j olacaq . Əgər oyun yalnız şəxsi hərəkətlərdən ibarətdirsə, onda A i, B j strategiyalarının seçimi oyunun nəticəsini - bizim qazancımızı unikal şəkildə müəyyənləşdirir. ij kimi işarə edək. Əgər oyunda şəxsi, təsadüfi hərəkətlərə əlavə olaraq, A i, B j strategiyaları üçün qazanc bütün təsadüfi hərəkətlərin nəticələrindən asılı olan təsadüfi dəyərdir. Bu halda gözlənilən gəlirin təbii qiymətləndirilməsi onun orta dəyəridir (riyazi gözlənti). Eyni işarə ilə həm qazancın özünü (təsadüfi hərəkətlər olmayan oyunda), həm də onun orta dəyərini (təsadüfi hərəkətlərlə oyunda) qeyd edəcəyik.

Hər bir cüt strategiya üçün qazancın (və ya orta gəlirin) a ij dəyərlərini bizə bildirin. Dəyərlər düzbucaqlı cədvəl (matris) şəklində yazıla bilər, onun sətirləri bizim strategiyalarımıza (A i), sütunlar isə rəqibin strategiyalarına (B j) uyğundur. Belə bir cədvəl ödəniş matrisi və ya sadəcə oyun matrisi adlanır. mxn oyun matrisi Şəkildə göstərilmişdir. bir.

düyü. 1. mxn matrisi

Oyun matrisini ‖a ij ‖ kimi qısaldacağıq. Oyunların bir neçə elementar nümunəsini nəzərdən keçirin.

Misal 1İki oyunçu A və B, bir-birinə baxmadan, bir sikkə üzü yuxarı və ya quyruqlarını masanın üzərinə qoyurlar. Əgər oyunçular eyni tərəfləri seçiblərsə (hər ikisinin gerbi və ya hər ikisinin quyruğu var), onda A oyunçusu hər iki sikkəni götürür; əks halda, onlar oyunçu B tərəfindən alınır. Oyunu təhlil etmək və onun matrisini hazırlamaq tələb olunur. Həll. Oyun yalnız iki hərəkətdən ibarətdir: bizim növbəmiz və rəqibin növbəsi, hər ikisi şəxsi. Oyun tam məlumatı olan oyunlara aid deyil, çünki hərəkət anında onu icra edən oyunçu digərinin nə etdiyini bilmir. Oyunçuların hər birinin yalnız bir şəxsi hərəkəti olduğundan, oyunçunun strategiyası bu tək şəxsi hərəkətdə seçimdir.

Bizim iki strategiyamız var: A 1 - gerbi seçin və A 2 - quyruqları seçin; rəqib eyni iki strategiyaya malikdir: B 1 - gerb və B 2 - quyruq. Beləliklə, bu oyun 2×2 oyunudur. Biz sikkənin uduşunu +1 hesab edəcəyik. Oyun Matrisi:

Bu oyunun nümunəsi ilə, nə qədər elementar olsa da, oyun nəzəriyyəsinin bəzi əsas ideyalarını aydınlaşdırmaq olar. Əvvəlcə fərz edək ki, verilmiş oyun yalnız bir dəfə yerinə yetirilir. O zaman, açıq-aydın, digərlərindən daha ağlabatan oyunçuların hansısa “strategiyaları” haqqında danışmaq mənasızdır. Eyni səbəbdən oyunçuların hər biri istənilən qərarı verə bilər. Ancaq oyun təkrarlananda vəziyyət dəyişir.

Həqiqətən, tutaq ki, biz (A oyunçusu) özümüz üçün hansısa strategiya seçmişik (məsələn, A 1) və ona sadiq qalırıq. Sonra, ilk bir neçə gedişin nəticələrinə əsasən, rəqib strategiyamızı təxmin edəcək və ona bizim üçün ən az əlverişli şəkildə cavab verəcək, yəni. quyruqları seçin. Hər hansı bir strategiya tətbiq etmək bizim üçün açıq-aydın faydasızdır; uduzan olmamaq üçün gah gerb, gah da quyruq seçməliyik. Bununla belə, əgər biz gerbləri və quyruqları müəyyən ardıcıllıqla (məsələn, biri vasitəsilə) növbə etsək, düşmən də bu barədə təxmin edə və bu strategiyaya bizim üçün ən pis şəkildə cavab verə bilər. Aydındır ki, düşmənin strategiyamızı bilməməsini təmin etməyin etibarlı yolu, özümüz əvvəlcədən bilmədiyimiz zaman hər bir hərəkətdə seçimi təşkil etməkdir (bu, məsələn, sikkə atmaqla təmin edilə bilər). Beləliklə, intuitiv əsaslandırma vasitəsi ilə biz oyun nəzəriyyəsinin əsas anlayışlarından birinə - "qarışıq strategiya" konsepsiyasına, yəni. belə ki, "saf" strategiyalar - bu halda A 1 və A 2 - müəyyən tezliklərlə təsadüfi olaraq növbələşir. Bu misalda simmetriya səbəblərinə görə əvvəlcədən aydın olur ki, A 1 və A 2 strategiyaları eyni tezliklə növbələşməlidir; daha mürəkkəb oyunlarda həll mənasızlıqdan uzaq ola bilər.

Misal 2 A və B oyunçuları eyni vaxtda və bir-birindən asılı olmayaraq hər biri üç rəqəmdən birini yazır: 1, 2 və ya 3. Yazılan rəqəmlərin cəmi cütdürsə, B A-ya bu məbləği rublla ödəyir; əgər təkdirsə, onda əksinə, A B-yə bu məbləği ödəyir. Oyunu təhlil etmək və onun matrisini hazırlamaq tələb olunur.

Həll. Oyun iki hərəkətdən ibarətdir; hər ikisi şəxsidir. Bizim (A) üç strategiyamız var: A 1 - 1 yaz; Və 2 - 2 yazın; A 3 - yaz 3. Rəqib (B) eyni üç strategiyaya malikdir. Oyun 3×3 oyundur:

Aydındır ki, əvvəlki vəziyyətdə olduğu kimi, düşmən bizim seçdiyimiz istənilən strategiyaya bizim üçün ən pis şəkildə cavab verə bilər. Həqiqətən də, məsələn, A 1 strategiyasını seçsək, düşmən həmişə ona B 2 strategiyası ilə cavab verəcək; A 2 strategiyası üzrə - B 3 strategiyası; A 3 strategiyası üzrə - B 2 strategiyası; beləliklə, müəyyən strategiyanın hər hansı seçimi bizi istər-istəməz itkiyə aparacaq (ancaq unutmaq olmaz ki, düşmən də eyni sıxıntıdadır). Bu oyunun həlli (yəni dəst ən sərfəli strategiyalar hər iki oyunçu) § 5-də veriləcəkdir.

Misal 3 Bizim ixtiyarımızda üç növ silah var: A 1, A 2, A 3; Düşmənin üç növ təyyarəsi var: B 1, B 2, B 3. Bizim vəzifəmiz təyyarəni vurmaqdır; düşmənin vəzifəsi onu məğlubiyyətsiz saxlamaqdır. A 1 silahlarından istifadə edildikdə, B 1, B 2, B 3 təyyarələri müvafiq olaraq 0,9, 0,4 və 0,2 ehtimallarla vurulur; A 2 ilə silahlandıqda - 0,3, 0,6 və 0,8 ehtimallarla; A 3 ilə silahlandıqda - 0,5, 0,7 və 0,2 ehtimallarla. Vəziyyəti oyun nəzəriyyəsi baxımından formalaşdırmaq tələb olunur.

Həll. Vəziyyəti iki şəxsi hərəkət və bir təsadüfi hərəkətlə 3x3 oyun kimi nəzərdən keçirmək olar. Bizim şəxsi hərəkətimiz silah növünün seçimidir; düşmənin şəxsi hərəkəti - döyüşdə iştirak etmək üçün təyyarə seçimi. Təsadüfi hərəkət - silahdan istifadə; bu hərəkət təyyarənin məğlubiyyəti və ya məğlub olmaması ilə başa çata bilər. Təyyarə vurulduqda qazancımız bir, əks halda isə sıfırdır. Strategiyalarımız üç silah variantıdır; düşmən strategiyaları - üç təyyarə variantı. Verilmiş hər bir strategiya cütü üçün qazancın orta dəyəri müəyyən bir silahla müəyyən bir təyyarəni vurma ehtimalından başqa bir şey deyil. Oyun Matrisi:

Oyun nəzəriyyəsinin məqsədi üçün tövsiyələr hazırlamaqdır ağlabatan davranış oyunçular münaqişə vəziyyətləri, yəni. onların hər birinin “optimal strategiyasının” müəyyən edilməsi. Oyun nəzəriyyəsində oyunçunun optimal strategiyası elə strategiyadır ki, oyun dəfələrlə təkrar edildikdə, verilmiş oyunçuya maksimum mümkün orta qazanc (və ya minimum mümkün orta itki) verir. Bu strategiyanı seçərkən əsaslandırmanın əsasını düşmənin ən azı bizim qədər ağıllı olması və məqsədimizə çatmağımıza mane olmaq üçün hər şeyi etdiyi fərziyyəsi təşkil edir.

Oyun nəzəriyyəsində bütün tövsiyələr bu prinsiplər əsasında hazırlanır; buna görə də hər bir real strategiyada qaçılmaz olaraq mövcud olan risk elementlərini, həmçinin oyunçuların hər birinin mümkün səhv hesablamalarını və səhvlərini nəzərə almır. Oyun nəzəriyyəsi, mürəkkəb bir hadisənin hər hansı bir riyazi modeli kimi, məhdudiyyətlərə malikdir. Bunlardan ən əsası gəlirin süni şəkildə birə endirilməsidir tək. Əksər praktik münaqişə vəziyyətlərində ağlabatan strategiya hazırlayarkən bir deyil, bir neçə ədədi parametrləri - hadisənin uğurunun meyarlarını nəzərə almaq lazımdır. Bir meyara görə optimal olan strategiya digərlərinə görə mütləq optimal deyil. Bununla belə, bu məhdudiyyətləri tanıyaraq və buna görə də oyun üsulları ilə əldə edilən tövsiyələrə kor-koranə riayət etməməklə, oyun nəzəriyyəsinin riyazi aparatından hələ də əsaslı şəkildə istifadə etmək olar, əgər tam olaraq "optimal" olmasa da, istənilən halda "məqbul". strategiya.

§ 2. Oyunun aşağı və yuxarı qiyməti. "Minimax" prinsipi

Şəkildə olduğu kimi mxn oyununu matrislə nəzərdən keçirək. 1. Strategiyamızın nömrəsini i hərfi ilə qeyd edəcəyik; j hərfi rəqibin strategiyasının nömrəsidir. Biz öz qarşımıza optimal strategiyamızı müəyyən etmək vəzifəsini qoymuşuq. Gəlin A 1-dən başlayaraq hər bir strategiyamızı ardıcıl olaraq təhlil edək.

A i strategiyasını seçərkən həmişə rəqibin ona B j strategiyalarından biri ilə cavab verəcəyini gözləməliyik ki, bunun üçün a ij qazancımız minimaldır. Gəlin bu ödəmə dəyərini müəyyən edək, yəni. a ij-də olan ədədlərin ən kiçiyi i-ci xətt. Bunu α i ilə işarələyin:

Burada min (j-də minimum) işarəsi bütün mümkün j üçün bu parametrin dəyərlərinin minimumunu bildirir. α i ədədlərini yazaq; əlavə sütun kimi sağdakı matrisin yanında:

İstənilən A i strategiyasını seçərkən, rəqibin ağlabatan hərəkətləri nəticəsində α i-dən çox qazanmayacağımıza arxalanmalıyıq. Təbii ki, ən ehtiyatlı davranaraq və ən ağlabatan rəqibə arxalanaraq (yəni hər hansı riskdən qaçaraq) α i sayının maksimum olduğu strategiyada dayanmalıyıq. Bu maksimum dəyəri α ilə işarə edirik:

və ya (2.1) düsturu nəzərə alınmaqla,

α dəyəri oyunun aşağı qiyməti adlanır, əks halda - maksimum qazanc və ya sadəcə maksimum. α ədədi matrisin müəyyən cərgəsində yerləşir; Bu xəttə uyğun gələn A oyunçusunun strategiyasına maksimal strategiya deyilir. Aydındır ki, əgər biz maksimum strategiyaya əməl etsək, o zaman bizə rəqibin hər hansı bir davranışı üçün ən azı α-dan az olmamaq şərti ilə qazanc alacağımıza zəmanət verilir. Buna görə də α-nın dəyəri “oyunun aşağı qiyməti” adlanır. Bu, özümüzü ən ehtiyatlı (“təkrarsığorta”) strategiya ilə təmin edə biləcəyimiz zəmanətli minimumdur.

Aydındır ki, oxşar mülahizə rəqib B üçün də aparıla bilər. Rəqib bizim qazancımızı minimuma endirməkdə maraqlı olduğu üçün o, öz strategiyalarının hər birini nöqteyi-nəzərdən nəzərdən keçirməlidir. maksimum qalibiyyət bu strategiya ilə. Buna görə də, matrisin altındakı hər bir sütun üçün maksimum dəyərləri yazacağıq:

və β j minimumunu tapın:

β dəyəri oyunun yuxarı qiyməti adlanır, əks halda - "minimax". Rəqibin minimaks qazancına uyğun strategiyası onun “minimax strategiyası” adlanır. Ən ehtiyatlı minimaks strategiyasına sadiq qalaraq, rəqib özünə aşağıdakılara zəmanət verir: ona qarşı nə etsək də, o, istənilən halda β-dan çox olmayan məbləği itirəcək. Oyunçulara uyğun strategiyaların (maksimum və minimaks) seçimini diktə edən ehtiyatlılıq prinsipi oyun nəzəriyyəsində və onun tətbiqlərində çox vaxt “minimax prinsipi” adlanır. Oyunçuların ən ehtiyatlı maksimum və minimum strategiyaları bəzən işarələnir ümumi termin Minimax strategiyaları.

Nümunələr olaraq, 1-ci Bölmənin 1, 2 və 3 Nümunələri üçün oyunun aşağı və yuxarı qiymətlərini və minimaks strategiyalarını müəyyən edirik.

Misal 1§ 1-in 1-ci nümunəsində oyun aşağıdakı matrislə verilir:

α i və β j dəyərləri sabit və müvafiq olaraq –1 və +1-ə bərabər olduğundan, oyunun aşağı və yuxarı qiymətləri də –1 və +1-ə bərabərdir: α = –1, β = +1 . A oyunçusunun istənilən strategiyası onun maksimumu, B oyunçusunun hər hansı strategiyası isə onun minimum strategiyasıdır. Nəticə mənasızdır: hər hansı strategiyasına sadiq qalaraq, oyunçu A 1-dən çox itirməyəcəyinə zəmanət verə bilər; eyni şey B oyunçusu tərəfindən təmin edilə bilər.

Misal 2§ 1-in 2-ci nümunəsində matrisli bir oyun verilmişdir:

Oyunun aşağı qiyməti α = –3; oyunun yuxarı qiyməti β = 4-dür. Maksimin strategiyamız A 1-dir; sistematik şəkildə tətbiq etməklə, ən azı -3 (ən çox 3 uduzmaq) qazanacağımızı inamla gözləyə bilərik. Rəqibin minimaks strategiyası B 1 və B 2 strategiyalarından hər hansı biridir; onları sistemli şəkildə tətbiq etməklə, o, ən azı 4-dən çox itirməyəcəyinə zəmanət verə bilər. Maksimin strategiyamızdan yayınsaq (məsələn, A 2 strategiyasını seçin), düşmən B 3 strategiyasını tətbiq etməklə bizi buna görə “cəzalandıra” bilər. gəlirimizi -5-ə endirmək; eynilə, rəqibin minimaks strategiyasından geri çəkilməsi onun itkisini 6-ya çatdıra bilər.

Misal 3§ 1-in 3-cü nümunəsində matrisli bir oyun verilmişdir:

Oyunun aşağı qiyməti α = 0,3; yuxarı qiymətləndirmə oyunu β = 0,7. Bizim ən ehtiyatlı (maksimum) strategiyamız A 2-dir; A 2 silahından istifadə edərək, biz bütün hallarda orta hesabla ən azı 0,3-də təyyarəni vuracağımıza zəmanət veririk. Rəqibin ən ehtiyatlı (minimax) strategiyası B 2-dir; bu təyyarədən istifadə edərək düşmən bütün hallarda 0,7-dən çox olmamaqla vurulacağına əmin ola bilər.

Sonuncu misalda birini nümayiş etdirmək rahatdır mühüm əmlak minimax strategiyaları - onların qeyri-sabitliyi. Ən ehtiyatlı (maksimum) strategiyamızı A 2, rəqib isə onun ən ehtiyatlı (minimax) strategiyasını B 2 tətbiq edək. Hər iki rəqib bu strategiyalara əməl etdikcə, orta qazanc 0,6; altdan daha böyükdür, lakin daha kiçikdir yuxarı qiymət oyunlar. İndi fərz edək ki, düşmən bizim A 2 strategiyasından istifadə etdiyimizi öyrəndi; o, dərhal ona B 1 strategiyası ilə cavab verəcək və qazancı 0,3-ə endirəcək. Öz növbəsində, B 1 strategiyasına yaxşı cavabımız var: strategiya A 1 , bizə 0,9 qazanc verir və s.

Beləliklə, hər iki oyunçunun minimaks strategiyalarından istifadə etdiyi vəziyyət qeyri-sabitdir və qarşı tərəfin strategiyası haqqında alınan məlumatla pozula bilər. Bununla belə, minimax strategiyalarının sabit olduğu bəzi oyunlar var. Aşağı qiymətin yuxarı qiymətə bərabər olduğu oyunlar bunlardır: α = β. Oyunun aşağı qiyməti yuxarıya bərabərdirsə, onda onların ümumi məna oyunun xalis dəyəri adlanır (bəzən sadəcə oyunun dəyəri), biz onu ν hərfi ilə işarə edəcəyik.

Məsələni nəzərdən keçirək. 4×4 oyunu matrislə verilsin:

Oyunun aşağı qiymətini tapaq: α = 0,6. Oyunun yuxarı qiymətini tapaq: β = 0,6. Onların eyni olduğu ortaya çıxdı, buna görə oyunun α = β = ν = 0,6-a bərabər xalis dəyəri var. Ödəniş matrisində vurğulanan 0.6 elementi həm öz cərgəsində minimum, həm də sütununda maksimumdur. Həndəsədə oxşar xüsusiyyətə malik olan səthdəki nöqtə (bir koordinat boyunca eyni vaxtda minimum və digəri boyunca maksimum) yəhər nöqtəsi adlanır; analogiyaya görə, bu termin oyun nəzəriyyəsində də istifadə olunur. Bu xüsusiyyətə malik olan matrisin elementi matrisin yəhər nöqtəsi adlanır və oyunun yəhər nöqtəsi olduğu deyilir.

Yəhər nöqtəsi bir cüt minimaks strategiyasına uyğundur (bu misalda A 3 və B 2). Bu strategiyalar optimal adlanır və onların birləşməsi oyunun həllidir. Oyun həllində aşağıdakılar var əlamətdar əmlak. Əgər oyunçulardan biri (məsələn, A) öz optimal strategiyasına əməl edirsə, digər oyunçu isə (B) hər hansı şəkildə öz optimal strategiyasından kənara çıxırsa, o zaman kənara çıxan oyunçu üçün bu heç vaxt sərfəli ola bilməz, belə ki, B oyunçusunun sapması ən yaxşı halda qazancı dəyişməz, ən pis halda isə artıra bilər. Əksinə, əgər B öz optimal strategiyasına sadiq qalırsa və A öz strategiyasından kənara çıxarsa, bu heç bir halda A üçün faydalı ola bilməz.

Bu iddianı yəhər nöqtəsi ilə nəzərdən keçirilən oyunun nümunəsində yoxlamaq asandır. Biz görürük ki, yəhər nöqtəsi olan oyunda minimaks strategiyaları bir növ “sabitliyə” malikdir: əgər bir tərəf öz minimaks strategiyasına əməl edirsə, o zaman digər tərəfin özündən kənara çıxması ancaq sərfəli ola bilər. Qeyd edək ki, bu zaman hər hansı oyunçunun rəqibin öz optimal strategiyasını seçdiyi barədə məlumatlara malik olması oyunçunun öz davranışını dəyişə bilməz: əgər o, öz maraqlarına zidd hərəkət etmək istəmirsə, öz optimal strategiyasına əməl etməlidir. Yəhər nöqtəsi olan oyunda bir cüt optimal strategiya, sanki, “tarazlıq mövqeyi”dir: optimal strategiyadan hər hansı bir sapma, yayınan oyunçunu əlverişsiz nəticələrə gətirib çıxarır, onu ilkin vəziyyətinə qayıtmağa məcbur edir.

Beləliklə, yəhər nöqtəsi olan hər oyun üçün hər iki tərəf üçün aşağıdakı xüsusiyyətlərdə fərqlənən bir cüt optimal strategiya təyin edən bir həll var.

1) Əgər hər iki tərəf öz optimal strategiyalarına sadiq qalırsa, orta qazanc oyunun xalis qiymətinə ν bərabərdir, bu da onun həm aşağı, həm də yuxarı qiymətidir.

2) Əgər tərəflərdən biri öz optimal strategiyasına əməl edərsə, digəri isə özündən kənara çıxarsa, o zaman sapan tərəf bundan ancaq itirə bilər və heç bir halda qazancını artıra bilməz.

Yəhər nöqtəli oyunlar sinfi həm nəzəri, həm də praktiki baxımdan böyük maraq doğurur. Oyun nəzəriyyəsində sübut edilmişdir ki, xüsusən də tam məlumatı olan hər bir oyunun yəhər nöqtəsi var və deməli, hər belə oyunun həlli var, yəni. hər iki tərəf üçün oyunun qiymətinə bərabər orta qazanc verən bir cüt optimal strategiya var. Əgər tam məlumatı olan oyun yalnız şəxsi hərəkətlərdən ibarətdirsə, onda hər bir tərəf öz optimal strategiyasını tətbiq etdikdə, o, həmişə kifayət qədər müəyyən nəticə ilə, yəni oyunun qiymətinə tam bərabər olan gəlirlə başa çatmalıdır.

Tam məlumatı olan bir oyun nümunəsi olaraq nəzərdən keçirin məşhur oyun sikkə yığma ilə dəyirmi masa. İki oyunçu növbə ilə eyni sikkələri dəyirmi masaya qoyur, hər dəfə sikkənin mərkəzinin ixtiyari mövqeyini seçir; Sikkələrin qarşılıqlı örtülməsinə icazə verilmir. Son sikkəni qoyan oyunçu qalib gəlir (başqaları üçün yer qalmadıqda). Aydındır ki, bu oyunun nəticəsi həmişə əvvəlcədən müəyyən edilir və sikkəni birinci yerə qoyan oyunçu üçün etibarlı qələbəni təmin edən dəqiq müəyyən edilmiş strategiya var. Məhz, o, əvvəlcə masanın ortasına bir sikkə qoymalı, sonra isə rəqibin hər bir hərəkətinə simmetrik bir hərəkətlə cavab verməlidir. Bu zaman ikinci oyunçu oyunun əvvəlcədən müəyyən edilmiş nəticəsini dəyişmədən özünü istədiyi kimi apara bilər. Buna görə də, bu oyun yalnız optimal strategiyanı bilməyən oyunçular üçün məna kəsb edir. Şahmat və tam məlumatı olan digər oyunlarda da vəziyyət oxşardır; bu oyunlardan hər hansı birinin yəhər nöqtəsi və oyunçuların hər birinə onun optimal strategiyasını göstərən həlli var; şahmat oyununun həlli təkcə ona görə tapılmır ki, şahmatda mümkün hərəkətlərin kombinasiyalarının sayı çox böyükdür ki, onun gəlir matrisini qurmaq və orada yəhər nöqtəsi tapmaq mümkün olsun.

§ 3. Saf və qarışıq strategiyalar. Qarışıq strategiyalarda oyunun həlli

Praktik əhəmiyyəti olan sonlu oyunlar arasında yəhər nöqtəsi olan oyunlar nisbətən nadirdir; oyunun aşağı və yuxarı qiymətlərinin fərqli olduğu hal daha tipikdir. Belə oyunların matrislərini təhlil edərək belə nəticəyə gəldik ki, əgər hər bir oyunçuya vahid strategiya seçimi verilirsə, o zaman ağlabatan hərəkət edən rəqib əsasında bu seçim minimaks prinsipi ilə müəyyən edilməlidir. Maksimin strategiyamıza sadiq qalaraq, rəqibin hər hansı davranışı üçün özümüzə oyunun aşağı qiymətinə bərabər olan α qazancına zəmanət veririk. Təbii sual yaranır: yalnız bir "təmiz" strategiyadan istifadə etsəniz, bir neçə strategiyanı təsadüfi olaraq əvəz etsəniz, özünüzə α-dan daha yüksək orta qazanc təmin etmək mümkündürmü? Müəyyən tezlik nisbəti ilə təsadüfi qanuna uyğun olaraq bir-birini əvəz edən bir neçə təmiz strategiyanın tətbiqindən ibarət belə birləşmiş strategiyalar oyun nəzəriyyəsində qarışıq strategiyalar adlanır.

Aydındır ki, hər bir təmiz strategiya qarışıq strategiyanın xüsusi halıdır, birindən başqa bütün strategiyalar sıfır tezliklərlə, bu isə 1 tezliyi ilə tətbiq olunur. Məlum olur ki, təkcə təmiz deyil, həm də qarışıq strategiyalar, biz hər sonlu oyun həlli üçün əldə edə bilərik, yəni. bir cüt (ümumiyyətlə qarışıq) strategiyalar ki, hər iki oyunçu onlardan istifadə etdikdə, qazanc oyunun qiymətinə bərabər olacaq və optimal strategiyadan hər hansı birtərəfli yayınma üçün qazanc yalnız əlverişsiz istiqamətdə dəyişə bilər. sapan oyunçu.

Bu ifadə oyun nəzəriyyəsinin əsas teoreminin məzmununu təşkil edir. Bu teorem ilk dəfə 1928-ci ildə fon Neyman tərəfindən sübut edilmişdir. Teoremin məlum sübutları nisbətən mürəkkəbdir; ona görə də biz yalnız onun formulunu təqdim edirik.

Hər sonlu oyunun ən azı bir həlli var (bəlkə də qarışıq strategiyalar sahəsində).

Qərardan əldə edilən gəlir oyunun qiyməti adlanır. Əsas teoremdən belə çıxır ki, hər sonlu oyunun qiyməti var. Aydındır ki, oyunun dəyəri ν həmişə oyunun aşağı dəyəri α ilə oyunun yuxarı dəyəri β arasında olur:

(3.1) α ≤ ν ≤ β

Həqiqətən, α yalnız öz saf strategiyalarımızı tətbiq etməklə özümüz üçün təmin edə biləcəyimiz maksimum zəmanətli gəlirdir. Qarışıq strategiyalar, xüsusi hal kimi, bütün təmiz strategiyaları əhatə etdiyinə görə, xalis, həm də qarışıq strategiyalara icazə verməklə, biz, heç bir halda, imkanlarımızı pisləşdirmirik; deməli ν ≥ α. Eynilə, rəqibin imkanlarını nəzərə alaraq, tələb olunan bərabərsizliyi nəzərdə tutan ν ≤ β olduğunu göstəririk (3.1).

Qarışıq strategiyalar üçün xüsusi qeyd təqdim edək. Məsələn, qarışıq strategiyamız p 1, p 2, p 3 və p 1 + p 2 + p 3 = 1 tezlikləri ilə A 1, A 2, A 3 strategiyalarını tətbiq etməkdən ibarətdirsə, biz bu strategiyanı işarə edəcəyik.

Eynilə, rəqibin qarışıq strategiyası ilə işarələnəcək:

burada q 1 , q 2 , q 3 - B 1 , B 2 , B 3 strategiyalarının qarışıq olduğu tezliklər; q 1 + q 2 + q 3 = 1.

Tutaq ki, S A *, S B * optimal iki qarışıq strategiyadan ibarət oyunun həllini tapdıq. Ümumi halda, müəyyən bir oyunçu üçün mövcud olan bütün təmiz strategiyalar onun optimal qarışıq strategiyasına daxil edilir, lakin onlardan yalnız bəziləri. Biz oyunçunun optimal qarışıq strategiyasına daxil olan strategiyaları onun “faydalı” strategiyaları adlandıracağıq. Məlum oldu ki, oyunun həlli daha bir əlamətdar xüsusiyyətə malikdir: əgər oyunçulardan biri S A * (S B *) optimal qarışıq strategiyasına əməl edərsə, o zaman qazanc eyni qalır və oyunun qiymətinə ν bərabərdir. digər oyunçu onun "faydalı" strategiyalarından kənara çıxmadığı təqdirdə nə edir. O, məsələn, hər hansı "faydalı" strategiyalarını təmiz formada istifadə edə bilər və həmçinin onları istənilən nisbətdə qarışdıra bilər.

§ 4. Oyunların həlli üçün elementar üsullar. Oyunlar 2x2 və 2xn

Əgər mxn oyununda yəhər nöqtəsi yoxdursa, onda həll yolu tapmaq ümumiyyətlə, xüsusilə böyük m və n üçün kifayət qədər çətin məsələdir. Bəzən bu vəzifəni əvvəlcə bəzi lazımsız olanları silməklə strategiyaların sayını azaltmaqla sadələşdirmək olar. Həddindən artıq strategiyalar a) dublikatdır və b) açıq-aşkar faydasızdır. Məsələn, matris oyununu nəzərdən keçirək:

A 3 strategiyasının tam olaraq A 1 strategiyasını təkrarladığını görmək asandır, ona görə də bu iki strategiyadan hər hansı birinin üstündən xətt çəkmək olar. Bundan əlavə, A 1 və A 2 sətirlərini müqayisə edərək, A 2 sətirinin hər bir elementinin A 1 sətirinin müvafiq elementindən kiçik (və ya ona bərabər) olduğunu görürük. Aydındır ki, biz heç vaxt A2 strategiyasından istifadə etməməliyik, bu, açıq-aydın gəlirsizdir. A 3 və A 2-nin üstündən xətt çəkərək, matrisi daha da artırırıq açıq mənzərə. Bundan əlavə, qeyd edirik ki, B 3 strategiyası açıq şəkildə düşmən üçün əlverişsizdir; onu silməklə matrisi son formaya gətiririk:

Beləliklə, 4x4 oyunu dublikat və açıq-aşkar zərərli strategiyaları aradan qaldıraraq 2x3 oyununa endirilir.

Təkrarlanan və açıq-aydın zərərsiz strategiyaların aradan qaldırılması proseduru həmişə oyunun həllindən əvvəl olmalıdır. Həmişə elementar üsullarla həll edilə bilən sonlu oyunların ən sadə halları 2x2 və 2xn oyunlarıdır.

Matrisli 2×2 oyununu nəzərdən keçirək:

Burada iki hal baş verə bilər: 1) oyunun yəhər nöqtəsi var; 2) oyunun yəhər nöqtəsi yoxdur. Birinci halda, həll yolu göz qabağındadır: bu, yəhər nöqtəsində kəsişən bir cüt strategiyadır. Yeri gəlmişkən, qeyd edirik ki, 2 × 2 oyununda yəhər nöqtəsinin olması həmişə ilkin təhlildə aradan qaldırılmalı olan qəsdən əlverişsiz strategiyaların mövcudluğuna uyğun gəlir.

Qoy heç bir yəhər nöqtəsi olmasın və buna görə də oyunun aşağı qiyməti yuxarıya bərabər deyil: α ≠ β. A oyunçusunun optimal qarışıq strategiyasını tapmaq lazımdır:

Rəqibin hərəkətlərindən asılı olmayaraq (əgər o, “faydalı” strategiyalarından kənara çıxmasa), qazanc ν oyunun dəyərinə bərabər olacaq xüsusiyyəti ilə fərqlənir. 2x2 oyununda rəqibin hər iki strategiyası "faydalıdır", əks halda oyunun xalis strategiya sahəsində (yəhər nöqtəsi) həlli olardı. Bu o deməkdir ki, əgər biz optimal strategiyamıza (4.1) sadiq qalsaq, o zaman rəqib orta qazancı ν dəyişmədən özünün hər hansı B 1, B 2 xalis strategiyalarından istifadə edə bilər. Buradan iki tənlik əldə edirik:

ondan p 1 + p 2 = 1 olduğunu nəzərə alaraq alırıq:

Hər hansı tənlikdə (4.2) p 1, p 2 dəyərlərini əvəz etməklə oyunun ν dəyərini tapırıq.

Əgər oyunun qiyməti məlumdursa, o zaman rəqibin optimal strategiyasını müəyyən etmək

bir tənlik kifayətdir, məsələn:

q 1 + q 2 = 1 olduğunu nəzərə alsaq, bizdə:

Misal 1§ 1-in 1-ci nümunəsində nəzərdən keçirilən 2×2 oyununa matrislə həll tapaq:

Oyunda yəhər nöqtəsi yoxdur (α = –1; β = +1) və buna görə də həll qarışıq strategiyalar sahəsində olmalıdır:

Siz p 1, p 2, q 1 və q 2-ni tapmaq lazımdır. p 1 üçün tənliyimiz var

1*p 1 + (–1)(1 – p 1) = (–1)p 1 + 1(1 – p 1)

buradan p 1 = 1/2, p 2 = 1/2.

Eynilə, tapırıq: q 1 = 1/2, q 2 = 1/2, ν = 0.

Buna görə də, oyunçuların hər biri üçün optimal strategiya, hər ikisini eyni dərəcədə tez-tez istifadə edərək, hər iki təmiz strategiyasını təsadüfi olaraq dəyişməkdir; bu halda orta qazanc sıfıra bərabər olacaqdır.

Alınan nəticə əvvəlcədən kifayət qədər aydın idi. Aşağıdakı nümunədə daha çox baxacağıq çətin oyun, bunun həlli o qədər də aydın deyil. Nümunə "fırıldaqçı" və ya "aldatma" oyunları kimi tanınan oyunların ibtidai nümunəsidir. Praktikada münaqişə vəziyyətlərində tez-tez istifadə olunur fərqli yollar düşməni çaşdırmaq (dezinformasiya, yalançı hədəflər qoymaq və s.). Nümunə, sadəliyinə baxmayaraq, olduqca ibrətamizdir.

Misal 2 Oyun aşağıdakı kimidir. İki kart var: bir ace və bir ikili. Oyunçu A onlardan birini təsadüfi çəkir; B hansı kartı çəkdiyini görmür. A ace çəksə, o, bəyan edir: "Mənim asım var" və rəqibdən 1 rubl tələb edir. Əgər A ikili çəkibsə, o zaman ya A 1) "mənim acem var" deyib rəqibdən 1 rubl tələb edə bilər, ya da A 2) ikilisi olduğunu etiraf edib rəqibə 1 rubl ödəyə bilər.

Düşmən, əgər ona könüllü olaraq 1 rubl ödənilirsə, yalnız onu qəbul edə bilər. Ondan 1 rubl tələb edərlərsə, o zaman ya B 1) A oyunçusunun ace olduğuna inanıb ona 1 rubl verə bilər, ya da B 2) A ifadəsinin doğruluğuna əmin olmaq üçün çek tələb edə bilər. belə çıxır ki, A-nın həqiqətən ace var, B A 2 rubl ödəməlidir. Əgər A aldadırsa və onun ikilisi varsa, A oyunçusu B oyunçusuna 2 rubl ödəyir. Oyunu təhlil etmək və oyunçuların hər biri üçün optimal strategiya tapmaq tələb olunur.

Həll. Oyun nisbətən mürəkkəb quruluşa malikdir; o, bir məcburi təsadüfi gedişdən - oyunçu A-nın iki kartdan birini seçməsindən və iki şəxsi hərəkətdən ibarətdir, lakin bu, mütləq həyata keçirilmir. Həqiqətən, əgər A ace çəkibsə, o, heç bir şəxsi hərəkət etmir: ona yalnız bir fürsət verilir - 1 rubl tələb etmək, bunu edir. Bu halda, şəxsi hərəkət - inanmaq və ya inanmamaq (yəni 1 rubl ödəmək və ya verməmək) - oyunçu B-yə ötürülür. Əgər A ilk təsadüfi gediş nəticəsində ikilik aldısa, o zaman ona şəxsi hərəkət verilir. hərəkət edin: 1 rubl ödəyin və ya rəqibi aldatmağa çalışın və 1 rubl tələb edin (qısacası: "aldatmayın" və ya "aldatmayın"). Əgər A birincini seçirsə, onda B yalnız 1 rubl qəbul etməlidir; Əgər A sonuncunu seçibsə, onda B oyunçusuna şəxsi hərəkət verilir: A-ya inanmaq və ya inanmamaq (yəni 1 rubl ödəmək və ya yoxlama tələb etmək).

Hər bir oyunçunun strategiyaları oyunçuya şəxsi hərəkət verildikdə nə edəcəyini bildirən qaydalardır. Aydındır ki, A-nın yalnız iki strategiyası var: A 1 - aldatmaq, A 2 - aldatmamaq. B-nin də iki strategiyası var: B 1 - inanmaq, B 2 - inanma. Oyun matrisini quraq. Bunu etmək üçün biz strategiyaların hər bir kombinasiyası üçün orta gəliri hesablayırıq.

1. A 1 B 1 (A aldadır, B inanır). Əgər A ace aldısa (bunun ehtimalı ½-dir, onda ona şəxsi gediş verilmir; o, 1 rubl tələb edir və B oyunçusu ona inanır; A-nın rublla qazancı 1-dir. Əgər A ikili alırsa (bunun ehtimalı da ½), strategiyasına uyğun olaraq aldadır və 1 rubl tələb edir; ona inanır və ödəyir; qazanc A da 1-ə bərabərdir. Orta qazanc: a 11 = ½ * 1 + ½ * 1 = 1.

2. A 1 B 2 (A aldadır, B inanmır). A-nın asesi varsa, onun şəxsi hərəkəti yoxdur; 1 rubl tələb edir; Strategiyasına görə, o, B-yə inanmır və çek nəticəsində 2 rubl ödəyir (A-nın qazancı +2). Əgər A ikili aldısa, o, strategiyasına görə 1 rubl tələb edir; B, onun sözlərinə görə, inanmır; Nəticədə, A 2 rubl ödəyir (A-nın qazancı -2). Orta qalibiyyət: 12 = ½*(+2) + ½*(–2) = 0.

3. A 2 B 1 (A aldatmaz, B inanır). A ace çəkirsə, o, 1 rubl tələb edir; B öz strategiyasına uyğun olaraq ödəyir; A-nın qazancı +1-dir. A deuce çəkirsə, strategiyasına uyğun olaraq 1 rubl ödəyir; Yalnız B-nin qəbul etməsi qalır (A-nın qazancı -1-dir). Orta qalibiyyət: və 21 = ½*(+1) + ½*(–1) = 0.

4. A 2 B 2 (A aldatmaz, B inanmaz). A ace çəkirsə, o, 1 rubl tələb edir; B çekləri və çek nəticəsində 2 rubl ödəyir (ödəniş +2). A ikili çıxarsa, 1 rubl ödəyir; Yalnız qəbul etmək qalır (ödəmə 1-dir). Orta qalibiyyət: və 22 = ½*(+2) + ½*(–1) = ½.

Oyun matrisini qururuq:

Matrisdə yəhər nöqtəsi yoxdur. Oyunun aşağı qiyməti α = 0, oyunun yuxarı qiyməti β = ½. Qarışıq strategiyalar sahəsində oyuna bir həll tapaq. (4.3) düsturu tətbiq edərək, əldə edirik:

olanlar. Oyunçu A bütün halların üçdə birində ilk strategiyasını (fırıldaq), ikincisini (fırıldaq etmə) bütün halların üçdə ikisində istifadə etməlidir. Eyni zamanda, o, orta hesabla oyunun qiyməti ν = 1/3 qazanacaq.

ν = 1/3 dəyəri, verilən şərtlərdə oyunun A üçün sərfəli, B üçün isə mənfi olduğunu göstərir. Optimal strategiyasından istifadə edərək, A həmişə özünü müsbət orta gəlirlə təmin edə bilər. Nəzərə alın ki, əgər A ən ehtiyatlı (maksimum) strategiyasından istifadə etsəydi (bu halda hər iki strategiya A 1 və A 2 maksimumdur), onun sıfıra bərabər orta gəliri olacaq. Beləliklə, qarışıq strategiyadan istifadə A-ya bu oyun qaydaları çərçivəsində yaranan B-dən üstünlüyünü reallaşdırmaq imkanı verir.

Biz optimal strategiyanı müəyyən edirik B. Bizdə: q 1 *1 + q 2 *0 = 1/3, q 1 = 1/3, q 2 = 2/3. Harada

yəni. oyunçu B bütün halların üçdə birində A-ya inanmalı və ona yoxlamadan 1 rubl, halların üçdə ikisində isə çek verməlidir. Sonra hər oyun üçün orta hesabla 1/3 itirəcək. Minimax xalis strategiyası B 2 istifadə etsəydi (inanmıram), hər oyunda orta hesabla 1/2 itirərdi.

2×2 oyununun həllinə sadə həndəsi şərh vermək olar. Matrisli 2×2 oyun olsun

X oxunun uzunluğu 1 olan kəsiyini götürək (şək. 4.1). Bölmənin sol ucu (absis ilə nöqtə x = 0) A 1 strategiyasını təmsil edəcək; bölmənin sağ ucu (x = 1) - strategiya A 2 . A 1 və A 2 nöqtələri vasitəsilə x oxuna iki perpendikulyar çəkək: ox I– İ və ox II–II. oxda I– İ biz A 1 strategiyası çərçivəsində ödənişləri təxirə salacağıq; oxda II–II- A 2 strategiyası ilə uduşlar. Rəqibin B 1 strategiyasını nəzərdən keçirin; oxlarda iki xal verir I– İ və II–II müvafiq olaraq a 11 və 21 ordinatları ilə. Bu nöqtələrdən B 1 B 1 düz xətti çəkək. Aydındır ki, rəqibin B 1 strategiyası üçün qarışıq strategiyadan istifadə etsək

onda bu halda a 11 p 1 + a 21 p 2 -ə bərabər olan orta qazancımız B 1 B 1 düz xəttində M nöqtəsi ilə təmsil olunacaq; bu nöqtənin absisi p 2-dir. B 1 strategiyası ilə qazancını təsvir edən B 1 B 1 düz xətti şərti olaraq "strategiya B 1" adlandırılacaqdır.

Aydındır ki, B 2 strategiyası tam olaraq eyni şəkildə qurula bilər (Şəkil 4.2).

Biz optimal S A * strategiyasını, yəni minimum qazancın (B-nin hər hansı bir davranışı üçün) maksimuma çevriləcəyi strategiyanı tapmalıyıq. Bunu etmək üçün B 1 , B 2 strategiyaları üçün qazancın aşağı həddi qururuq, yəni. qırıq xətt B 1 NB 2 şəkildə qeyd edilmişdir. 4.2 qalın xətt ilə. Bu aşağı hədd A oyunçusunun hər hansı qarışıq strategiyası üçün minimum qazancını ifadə edəcək; bu minimum qazancın maksimuma çatdığı N nöqtəsi oyunun həllini və qiymətini müəyyən edir. Asanlıqla görmək olar ki, N nöqtəsinin ordinatı oyunun qiyməti ν, onun absissası isə p 2 - optimal qarışıq strategiya S A *-da A 2 strategiyasının tətbiqi tezliyidir.

Bizim vəziyyətimizdə oyunun həlli strategiyaların kəsişmə nöqtəsi ilə müəyyən edilirdi. Lakin bu, həmişə belə olmayacaq; şək. Şəkil 4.3, strategiyaların kəsişməsinin olmasına baxmayaraq, həllin hər iki oyunçu üçün (A 2 və B 2) təmiz strategiyalar verdiyi və oyunun qiymətinin ν = a 22 olduğu halı göstərir. Bu halda, matrisin yəhər nöqtəsi var və A 1 strategiyası açıq-aydın gəlirsizdir, çünki rəqibin hər hansı təmiz strategiyası üçün A 2-dən daha kiçik gəlir verir.

Düşmənin qəsdən əlverişsiz bir strategiyası olduğu halda, həndəsi şərh Şəkil 1-də göstərilən formaya malikdir. 4.4.

Bu halda, qazancın aşağı həddi B 1 strategiyası ilə üst-üstə düşür, B 2 strategiyası açıq şəkildə rəqib üçün sərfəli deyil.

Həndəsi şərh oyunun aşağı və yuxarı qiymətlərini də vizuallaşdırmağa imkan verir (Şəkil 4.5).

Nümunə vermək üçün 1 və 2-ci misallarda nəzərdən keçirilən 2×2 oyunlarının həndəsi şərhlərini quraq (Şəkil 4.6 və 4.7).

Biz gördük ki, istənilən 2×2 oyunu elementar fəndlərlə həll etmək olar. İstənilən 2xn oyunu eyni şəkildə həll edilə bilər. burada bizim cəmi iki strategiyamız var və düşmənin özbaşına sayı var.

Gəlin iki strategiyamız olsun: A 1 , A 2 , və düşmən - n strategiyaları: B 1 , B 2 , ..., B n . ‖a ij ‖ matrisi verilmişdir; iki sıra və n sütundan ibarətdir. İki strategiyada olduğu kimi, problemə həndəsi şərh veririk; Rəqibin n strategiyası n düz xəttlə təmsil olunacaq (Şəkil 4.8). Ödənişin aşağı sərhədini (poliline B 1 MNB 2) qururuq və maksimum ordinat ilə N nöqtəsini tapırıq. Bu nöqtə oyunun həllini verir (strategiya ) N nöqtəsinin ordinatı oyunun qiymətinə ν, absis isə A 2 strategiyasının р 2 tezliyinə bərabərdir.

Bu halda rəqibin optimal strategiyası iki “faydalı” strategiyanın qarışığından istifadə etməklə əldə edilir: N nöqtəsində kəsişən B 2 və B 4. B 3 strategiyası açıq-aydın gəlirsizdir, B 1 strategiyası isə S A optimal strategiyası ilə gəlirsizdir. *. Əgər A optimal strategiyasına sadiq qalırsa, B-nin hansı “faydalı” strategiyasından istifadə etməsindən asılı olmayaraq, qazanc dəyişməyəcək, lakin B B 1 və ya B 3 strategiyalarına keçərsə, dəyişəcək. Oyun nəzəriyyəsində sübut edilmişdir ki, istənilən sonlu oyun mxn-nin hər iki tərəfin “faydalı” strategiyalarının sayı m və n iki ədədinin ən kiçiyindən çox olmayan həlli var. Xüsusilə, bundan belə çıxır ki, 2xm oyununda həmişə hər iki tərəfdən ikidən çox "faydalı" strategiyanın iştirak etdiyi bir həll var.

Həndəsi şərhdən istifadə edərək, istənilən 2xm oyununu həll etmək üçün sadə bir yol verə bilərsiniz. Birbaşa rəsmdən N nöqtəsində kəsişən bir cüt "faydalı" düşmən strategiyası B j və B k tapırıq (əgər ikidən çox strategiya N nöqtəsində kəsişirsə, onlardan hər hansı ikisini götürürük). Biz bilirik ki, əgər A oyunçusu optimal strategiyasına sadiq qalırsa, o zaman qazanc B-nin onun “faydalı” strategiyalarından istifadə etdiyi nisbətdən asılı deyildir.

Bu tənliklərdən və p 2 = 1 - p 1 şərtindən p1, p2 və oyunun ν qiymətini tapırıq. Oyunun qiymətini bilməklə, dərhal optimal strategiyanı təyin edə bilərsiniz oyunçu B. Bunun üçün, məsələn, tənlik həll edilir: q j a 1 j + q k a 1 k = ν, burada q j + q k = 1. Bizim m strategiyamız olduğu və düşmənin yalnız ikisi olduğu halda, açıq-aydın, problem tamamilə oxşar şəkildə həll edilir; qeyd etmək kifayətdir ki, qazanc işarəsini tərsinə çevirməklə A oyunçusunu “qalib”dən “uduzan”a çevirmək olar. Ödəniş işarəsini dəyişdirmədən oyunu həll etmək mümkündür; onda problem birbaşa B üçün həll edilir, lakin aşağı deyil, yuxarı nəticə həddi qurulur (Şəkil 4.9). Sərhəddə minimum ordinata malik N nöqtəsi axtarılır, bu oyun ν qiymətidir.

Praktiki əhəmiyyət kəsb edən oyunların sadələşdirilmiş nümunələri olan 2×2 və 2xm oyunlarının bir neçə nümunəsini nəzərdən keçirin və həll edin.

Misal 3 A tərəfi düşmən B bölgəsinə iki bombardmançı göndərir I və II; I qarşısında uçur II- arxada. Bombardmançılardan biri - hansının bomba daşımalı olduğu əvvəlcədən məlum deyil, digəri müşayiət funksiyasını yerinə yetirir. Düşmən bölgəsində bombardmançılar B tərəfdən qırıcının hücumuna məruz qalır. Bombardmançılar müxtəlif dərəcəli atəşli toplarla silahlanıblar. Bir qırıcı arxadan bombardmançıya hücum edərsə II, onda yalnız bu bombardmançının topları ona atəş açır; ön bombardmançıya hücum edərsə, hər iki bombardmançının toplarından ona atəş açılır. Birinci halda döyüşçünün vurulma ehtimalı 0,3, ikinci halda isə 0,7-dir.

Əgər qırıcı bombardmançı müdafiə atəşi ilə vurulmayıbsa, o zaman seçdiyi hədəfi 0,6 ehtimalla vurur. Bombardmançıların vəzifəsi bombanı hədəfə aparmaqdır; döyüşçünün vəzifəsi bunun qarşısını almaqdır, yəni. bombardmançı təyyarəni vur. Tərəflərin optimal strategiyalarını seçmək tələb olunur:

a) A tərəfi üçün: hansı bombardmançı daşıyıcı kimi istifadə edilməlidir?

b) B tərəfi üçün: hansı bombardmançı hücuma keçməlidir?

Həll. Bizdə 2×2 oyununun sadə bir işi var; qalibiyyət - ehtimal daşıyıcı uğursuzluğu. Strategiyalarımız: A 1 - daşıyıcı - bombardmançı I; 2 - daşıyıcı - bombardmançı II. Düşmən strategiyaları: B 1 - bombardmançı hücuma məruz qalır I; 2-də - bombardmançı hücumlar II. Oyun matrisini tərtib edək, yəni. strategiyaların hər bir kombinasiyası üçün orta gəliri tapın.

1. A 1 B 1 (daşıyıcı I, hücum etdi I). Bombardmançılar qırıcını vursalar və ya vurmasalar, daşıyıcı vurulmayacaq, lakin hədəfinə çatmayıb: a 11 = 0,7 + 0,3 * 0,4 = 0,82.

2. A 2 B 1 (daşıyıcı II, hücum etdi I). a 21 = 1

3. A 1 B 2 (daşıyıcı I, hücum etdi II). A 12 = 1

4. A 2 B 2 (daşıyıcı II, hücum etdi II). A 22 \u003d 0,3 + 0,7 * 0,4 \u003d 0,58

Oyun matrisinin forması var:

Oyunun aşağı qiyməti 0,82; yuxarı qiymət 1. Matrisin yəhər nöqtəsi yoxdur; qarışıq strategiyalar sahəsində həll axtarırıq. Bizdə:

p 1 * 0,82 + p 2 * 1 = ν

p1 *1 + p2 *0,58 = v

p 1 = 0,7; p 2 \u003d 0.3

Bizim optimal strategiyamız bəli, yəni daşıyıcı kimi daha tez-tez seçmək lazımdır I, Necə II. Oyunun dəyəri ν = 0,874-dir. ν-i bilərək, q 1 və q 2 - rəqibin optimal strategiyası S B *-də B 1 və B 2 strategiyalarının tezliklərini təyin edirik. Bizdə: q 1 * 0,82 + q 2 * 1 \u003d 0,874 və q 2 \u003d 1 - q 1, buradan q 1 \u003d 0,7; q 2 \u003d 0,3, yəni düşmənin optimal strategiyası .

Misal 4 A tərəfi obyektə hücum edir, B tərəfi onu müdafiə edir. A tərəfində iki təyyarə var; B tərəfində üç zenit silahı var. Hər bir təyyarə güclü silah daşıyıcısıdır; obyektin vurulması üçün ən azı bir təyyarənin ona keçməsi kifayətdir. Yan tərəf Təyyarə obyektə üç istiqamətdən hər hansı biri ilə yaxınlaşmağı seçə bilər: I, II, III(Şəkil 4.10). Düşmən (B tərəfi) hər hansı silahını istənilən istiqamətə yerləşdirə bilər; eyni zamanda, hər bir silah yalnız müəyyən bir istiqamətə aid olan kosmos sahəsini vurur və qonşu istiqamətlərdən atəş açmır. Hər bir silah yalnız bir təyyarəni atəşə tuta bilər; atəşə tutulan təyyarənin vurulması ehtimalı 1. A tərəfi silahların harada yerləşdirildiyini bilmir; B tərəfi təyyarələrin haradan gələcəyini bilmir. A tərəfinin vəzifəsi obyekti vurmaqdır; B tərəfinin vəzifəsi onun məğlubiyyətinin qarşısını almaqdır. Oyun üçün bir həll tapın.

Həll. Oyun 2×3 oyundur. Qazanc - obyektə dəymə ehtimalı. Mümkün strategiyalarımız bunlardır: A 1 - hər birinə bir təyyarəni iki fərqli istiqamətə göndərin. A 2 - hər iki təyyarəni eyni istiqamətə göndərin. Düşmən strategiyaları: B 1 - hər istiqamətə bir silah qoyun; B 2 - iki silahı bir istiqamətə, birini isə digərinə qoyun; 3-də - hər üç silahı bir istiqamətə qoyun. Oyunun matrisini düzəldirik.

1. A 1 B 1 (təyyarələr boyunca uçur müxtəlif istiqamətlər; silahlar bir-bir yerləşdirilir). Aydındır ki, bu vəziyyətdə heç bir təyyarə obyektə keçməyəcək: a 11 = 0.

2. A 2 B 1 (təyyarələr bir istiqamətdə birlikdə uçur; silahlar bir-bir düzülür). Aydındır ki, bu vəziyyətdə bir təyyarə atəşsiz obyektə keçəcək: və 21 = 1.

3. A 1 B 2 (təyyarə bir-bir uçur; düşmən iki istiqaməti müdafiə edir, üçüncüsü isə müdafiəsiz qoyur). Ən azı bir təyyarənin obyektə keçməsi ehtimalı onlardan birinin qorunmayan istiqamət seçməsi ehtimalına bərabərdir: və 12 = 2/3.

4. A 2 B 2 (təyyarə bir istiqamətdə birlikdə uçur; düşmən bir istiqaməti iki silahla, birini isə birlə müdafiə edir, yəni əslində bir istiqaməti qoruyur və ikisini müdafiəsiz qoyur). Ən azı bir təyyarənin obyektə çatma ehtimalı bir cüt təyyarənin həqiqətən qorunmayan istiqamət seçməsi ehtimalına bərabərdir: a 22 = 2/3.

5. A 1 B 3 (təyyarələr bir-bir uçur; düşmən üç silahla yalnız bir istiqaməti müdafiə edir): a 13 = 1.

6. A 2 B 3 (hər iki təyyarə birlikdə uçur; düşmən üç silahla yalnız bir istiqaməti müdafiə edir). Obyektin vurulması üçün təyyarə qorunmayan istiqamət seçməlidir: a 23 = 2/3.

Oyun Matrisi:

Matrisdən görünür ki, B 3 strategiyası B 2 ilə müqayisədə açıq-aydın gəlirsizdir (bu, əvvəlcədən qərara alına bilərdi). B 3 strategiyasını kəsməklə oyun 2x2 oyununa endirilir:

Matrisdə yəhər nöqtəsi var: oyunun aşağı qiyməti 2/3 yuxarı ilə üst-üstə düşür. Eyni zamanda qeyd edirik ki, bizim üçün (A) A 1 strategiyası açıq-aydın gəlirsizdir. Nəticə: hər iki tərəf A və B həmişə öz saf strategiyalarından istifadə etməlidirlər A 2 və B 2 , yəni. cütün göndərildiyi istiqaməti təsadüfi seçərək təyyarələri 2-yə göndərməliyik; düşmən öz silahlarını bu şəkildə yerləşdirməlidir: iki - bir istiqamətdə, biri - başqa istiqamətə və bu istiqamətlərin seçimi də təsadüfi aparılmalıdır (burada, gördüyümüz kimi, "saf strategiyalar" artıq şans elementini ehtiva edir. ). Bu optimal strategiyaları tətbiq etməklə, biz həmişə 2/3 sabit orta gəlir əldə edəcəyik (yəni, obyekt 2/3 ehtimalı ilə vurulacaq). Qeyd edək ki, oyunun tapılan həlli unikal deyil; təmiz strategiyalardakı həllə əlavə olaraq, p 1 \u003d 0-dan p 1 \u003d 1/3-ə qədər optimal olan A oyunçusunun bir sıra qarışıq strategiyaları mövcuddur (Şəkil 4.11).

Məsələn, A 1 və A 2 strategiyalarımızı 1/3 və 2/3 nisbətində tətbiq etsək, eyni orta qazancın 2/3 nisbətində əldə ediləcəyini birbaşa yoxlamaq asandır.

Misal 5Əvvəlki nümunədəki kimi eyni şərtlər, lakin bizim üçün dörd hücum istiqaməti mümkündür və düşmənin dörd silahı var.

Həll. Hələ iki mümkün strategiyamız var: A 1 - təyyarələri bir-bir göndərin, A 2 - iki təyyarəni birlikdə göndərin. Düşmənin beş mümkün strategiyası var: B 1 - hər istiqamətə bir silah qoyun; B 2 - iki silahı iki fərqli istiqamətə qoyun; 3-də - iki silahı bir istiqamətə və bir-bir qoyun - digər ikisinə; 4-də - üç silahı bir istiqamətə, birini isə digərinə qoyun; 5-də - bütün dörd silahı bir istiqamətə qoyun. B 4 , B 5 strategiyaları açıq-aşkar faydasız olduğu üçün əvvəlcədən ləğv ediləcək. Əvvəlki nümunəyə bənzər şəkildə mübahisə edərək, oyun matrisini qururuq:

Oyunun aşağı qiyməti 1/2, yuxarı 3/4-dür. Matrisdə yəhər nöqtəsi yoxdur; həll qarışıq strategiyalar sahəsindədir. Həndəsi şərhdən istifadə edərək (Şəkil 4.12) düşmənin "faydalı" strategiyalarını ayırırıq: B 1 və B 2.

P 1 və p 2 tezlikləri tənliklərdən müəyyən edilir: p 1 * 0 + (1 - p 1) * 1 = ν və p 1 * 5/6 + (1 - p 1) * 1/2 = ν; buradan p 1 = 3/8; p2 = 5/8; ν = 5/8, yəni. optimal strategiyamızdır . Ondan istifadə edərək, özümüzə 5/8 nisbətində orta hesabla qalib gələcəyimizə zəmanət veririk. Oyunun qiymətini ν = 5/8 bilərək, rəqibin "faydalı" strategiyalarının q 1 və q 2 tezliklərini tapırıq: q 1 * 0 + (1 - q 1) * 5/6 = 5/8 , q 1 = ¼, q 2 = ¾. Optimal düşmən strategiyası: .

Misal 6 A tərəfinin iki A 1 və A 2 strategiyası, B tərəfinin dörd B 1, B 2, B 3 və B 4 strategiyası var. Oyun matrisinin forması var:

Oyun üçün bir həll tapın.

Həll. Aşağı oyun qiyməti 3; yuxarı 4. Həndəsi şərh (Şəkil 4.13) B oyunçusunun faydalı strategiyalarının B 1 və B 2 və ya B 2 və B 4 olduğunu göstərir:

Oyunçu A sonsuz sayda optimal qarışıq strategiyaya malikdir: optimal strategiyada p 1 1/5 ilə 4/5 arasında dəyişə bilər. Oyunun dəyəri ν = 4-dür. Oyunçu B xalis optimal B 2 strategiyasına malikdir.

§ 5. Ümumi üsullar son oyun həlləri

İndiyə qədər biz çox sadə şəkildə həll edilə bilən və rahat və illüstrativ həndəsi şərhi qəbul edən 2xn tipli ən elementar oyunları nəzərdən keçirdik. Ümumi halda mxn oyununun həlli kifayət qədər çətin məsələdir və məsələnin mürəkkəbliyi və onun həlli üçün tələb olunan hesablamaların miqdarı m və n-in artması ilə kəskin şəkildə artır. Bununla belə, bu çətinliklər fundamental xarakter daşımır və yalnız bir sıra hallarda praktiki olaraq qeyri-mümkün ola bilən çox böyük həcmli hesablamalarla əlaqələndirilir. Həllin tapılması metodunun əsas cəhəti istənilən m üçün eyni qalır.

Bunu 3xn oyununun nümunəsi ilə izah edək. Gəlin buna həndəsi bir şərh verək - artıq məkandır. A 1, A 2 və A 3 strategiyalarımızdan üçü təyyarədə üç nöqtə ilə təmsil olunacaq hoy; birincisi mənşəyində yerləşir (şək. 5.1), ikinci və üçüncüsü baltalar üzərində uzanır Oh və OU başlanğıcdan 1 məsafədə.

Baltalar A 1, A 2 və A 3 nöqtələri vasitəsilə çəkilir I – I, II – II və III – III, müstəviyə perpendikulyar hoy. oxda I – Iödənişlər baltalar üzrə A 1 strategiyası ilə təxirə salınır II – II və III – III- A 2, A 3 strategiyaları üçün gəlirlər. Hər bir düşmən strategiyası B j baltaları kəsən bir təyyarə ilə təmsil olunacaq I – I, II – II və III – III müvafiq A 1 , A 2 və A 3 strategiyaları və B j strategiyası üçün ödənişlərə bərabər seqmentlər . Düşmənin bütün strategiyalarını belə quraraq, A 1, A 2 və A 3 üçbucağının üzərindən bir təyyarə ailəsi alırıq (şək. 5.2). Bu ailə üçün, 2xn vəziyyətində etdiyimiz kimi, daha aşağı ödəmə həddi də qurmaq olar və bu sərhəddə N nöqtəsini tapa bilərsiniz. maksimum hündürlük təyyarənin üstündə hoy. Bu hündürlük oyunun qiyməti olacaq ν.

Optimal S A * strategiyasında A 1 , A 2 və A 3 strategiyalarının p 1 , p 2 , p 3 tezlikləri N nöqtəsinin koordinatları (x, y) ilə müəyyən ediləcək, yəni: p 2 = x, p 3 = y, p 1 = 1 - p 2 - p 3. Bununla belə, belə bir həndəsi konstruksiya, hətta 3xn işi üçün belə, həyata keçirmək asan deyil və çox vaxt və təxəyyül tələb edir. Oyunun ümumi vəziyyətində isə o, m ölçülü fəzaya köçürülür və bütün görünmə qabiliyyətini itirir, baxmayaraq ki, bəzi hallarda həndəsi terminologiyanın istifadəsi faydalı ola bilər. Təcrübədə mxn oyunlarını həll edərkən həndəsi analogiyalardan deyil, hesablama analitik üsullarından istifadə etmək daha rahatdır, xüsusən də bu üsullar kompüterlərdə problemin həlli üçün uyğun olan yeganə üsuldur.

Bütün bu üsullar mahiyyət etibarilə ardıcıl sınaqlarla problemin həllinə qədər azaldılır, lakin sınaqların ardıcıllığını sifariş etmək ən qənaətcil şəkildə həllə aparan alqoritm qurmağa imkan verir. Burada mxn oyunlarının həlli üçün bir hesablama metodu - sözdə "xətti proqramlaşdırma" metodu üzərində qısaca dayanacağıq. Bunun üçün əvvəlcə mxn oyununun həllini tapmaq probleminin ümumi açıqlamasını veririk. mxn oyunu A oyunçunun m strategiyası A 1 , А 2 , …, A m və B oyunçunun n strategiyası B 1 , B 2 , …, B n verilsin və ‖a i j ‖ qazanc matrisi verilir. Oyunun həllini tapmaq tələb olunur, yəni. A və B oyunçularının iki optimal qarışıq strategiyası

burada p 1 + p 2 + ... + p m = 1; q 1 + q 2 + ... + q n = 1 (p i və q j ədədlərinin bəziləri sıfıra bərabər ola bilər).

Optimal strategiyamız S A *bizə rəqibin hər hansı davranışı üçün ν-dən az olmayan, optimal davranışı üçün isə ν-ə bərabər gəlir təmin etməlidir (strategiya S B *). Eynilə, S B * strategiyası düşmənə hər hansı davranışımız üçün ν-dən çox olmayan və optimal davranışımız üçün ν-ə bərabər itki verməlidir (strategiya S A *).

Bu halda oyunun ν dəyərinin dəyəri bizə məlum deyil; bəzilərinə bərabər olduğunu fərz edəcəyik müsbət rəqəm. Bunu fərz etsək, əsaslandırmanın ümumiliyini pozmuruq; ν > 0 olması üçün ‖a i j ‖ matrisinin bütün elementlərinin qeyri-mənfi olması açıq-aydın kifayətdir. Buna həmişə ‖a i j ‖ elementlərinə kifayət qədər böyük müsbət qiymət əlavə etməklə nail olmaq olar. L; isə oyunun qiyməti artacaq L, lakin həll yolu dəyişmir.

Optimal strategiyamızı S A * seçək. O zaman rəqibin B j strategiyası üçün orta qazancımız bərabər olacaq: a j = p 1 a 1j + p 2 a 2j + … + p m a mj . Optimal strategiyamız S A * rəqibin hər hansı davranışı üçün ν-dən az olmayan gəlir təmin edən xüsusiyyətə malikdir; buna görə də a j ədədlərindən hər hansı biri ν-dən kiçik ola bilməz. Bir sıra şərtlər alırıq:

(5.1) bərabərsizlikləri müsbət qiymət ν ilə bölürük və işarə edirik

Onda (5.1) şərtləri kimi yazmaq olar

burada ξ 1 , ξ 2 , …, ξ m mənfi olmayan ədədlərdir. p 1 + p 2 + ... + p m = 1 olduğundan, ξ 1 , ξ 2 , ..., ξ m kəmiyyətləri şərti ödəyir.

(5.3) ξ 1 + ξ 2 + … + ξ m = 1/ν.

Biz zəmanətli qələbəmizi mümkün qədər yüksək etmək istəyirik; açıq-aydın, zaman sağ hissə bərabərlik (5.3) minimum qiyməti alır. Beləliklə, oyunun həllinin tapılması məsələsi aşağıdakı riyazi məsələyə endirilir: qeyri-mənfi kəmiyyətləri ξ 1 , ξ 2 , …, ξ m qane edən şərtləri müəyyən etmək (5.2), belə ki, onların cəmi Φ = ξ 1 + ξ 2 + … + ξ m minimal idi.

Adətən, ekstremal dəyərlərin (maksimumlar və minimumlar) tapılması ilə bağlı məsələlərin həlli zamanı funksiya diferensiallaşdırılır və törəmələr sıfıra bərabər tutulur. Ancaq bu vəziyyətdə belə bir texnika faydasızdır, çünki minimuma endirilməli olan Φ funksiyası xəttidir və bütün arqumentlərə görə törəmələri birinə bərabərdir, yəni. heç vaxt itməz. Nəticə etibarilə, arqumentlərin və şərtlərin qeyri-mənfilik tələbi ilə müəyyən edilən arqumentlərin dəyişmə regionunun sərhəddində haradasa funksiyanın maksimumuna çatır (5.2). Fərqləndirmədən istifadə edərək ekstremal dəyərləri tapmaq üsulu, məsələn, 2xn oyunlarını həll edərkən etdiyimiz kimi, oyunun həlli üçün aşağı (və ya minimum yuxarı) qazanc sərhədinin maksimumunun müəyyən edildiyi hallarda da uyğun deyil. Həqiqətən də, aşağı sərhəd düz xətlərin seqmentlərindən ibarətdir və maksimuma törəmənin sıfıra bərabər olduğu nöqtədə deyil (belə bir nöqtə ümumiyyətlə yoxdur), intervalın sərhəddində və ya nöqtədə çatır. düz seqmentlərin kəsişmə nöqtəsi.

Praktikada kifayət qədər tez-tez rast gəlinən belə məsələləri həll etmək üçün riyaziyyatda xüsusi xətti proqramlaşdırma aparatı hazırlanmışdır. Xətti proqramlaşdırma problemi aşağıdakı kimi qoyulur. Xətti tənliklər sistemi verilmişdir:

ξ 1 , ξ 2 , …, ξ m , şərtləri ödəyən (5.4) və eyni zamanda ξ 1 , ξ 2 kəmiyyətlərinin verilmiş homojen xətti funksiyasını minimuma endirməklə kəmiyyətlərin mənfi olmayan qiymətlərini tapmaq tələb olunur. …, ξ m (xətti forma): Φ = c 1 ξ 1 + c 2 ξ 2 + … + c m ξ m

Yuxarıda qoyulan oyun nəzəriyyəsi probleminin c 1 = c 2 = ... = c m = 1 üçün xətti proqramlaşdırma probleminin xüsusi hal olduğunu görmək asandır. İlk baxışdan belə görünə bilər ki, şərtlər (5.2) (5.4) şərtlərinə ekvivalent deyil, çünki bərabər işarələrin əvəzinə bərabərsizlik işarələrini ehtiva edir. Bununla belə, yeni uydurma qeyri-mənfi dəyişənlər z 1 , z 2 , …, z n və şərtləri (5.2) formada yazmaqla bərabərsizlik əlamətlərindən xilas olmaq asandır:

Minimumlaşdırılacaq Φ forması Φ = ξ 1 + ξ 2 + … + ξ m-dir. Xətti proqramlaşdırma aparatı nisbətən az sayda ardıcıl nümunə ilə tələblərə cavab verən ξ 1 , ξ 2 , …, ξ m dəyərlərini seçməyə imkan verir. Daha aydınlıq üçün burada bu aparatın istifadəsini birbaşa konkret oyunların həlli materialında nümayiş etdirəcəyik.

Misal 1§ 1-in 2-ci misalında verilmiş 3 × 3 oyununun həllini matrislə tapmaq tələb olunur:

Bütün ij-i mənfi olmayan etmək üçün matrisin bütün elementlərinə L = 5 əlavə edirik.Matrisi alırıq:

Bu halda oyunun qiyməti 5 artacaq, lakin qərar dəyişməyəcək.

Optimal strategiya S A * müəyyən edək. Şərtlər (5.2) formaya malikdir:

burada ξ 1 = p 1 / ν, ξ 2 = p 2 / ν, ξ 3 = p 3 / ν. Bərabərsizlik işarələrindən xilas olmaq üçün z 1 , z 2 , z 3 dummy dəyişənləri təqdim edirik; (5.6) şərtləri aşağıdakı kimi yazıla bilər:

Xətti forma Φ belədir: Φ = ξ 1 + ξ 2 + ξ 3 və mümkün qədər kiçik olmalıdır. Əgər hər üç B strategiyası “faydalıdır”sa, onda hər üç saxta dəyişən z 1 , z 2 , z 3 yox olacaq (yəni, hər bir B j strategiyası ilə oyunun qiymətinə ν bərabər gəlir əldə ediləcək). Amma hələ də hər üç strategiyanın “faydalı” olduğunu söyləməyə əsasımız yoxdur. Bunu yoxlamaq üçün Φ şəklini z 1 , z 2 , z 3 dummy dəyişənləri ilə ifadə etməyə çalışaq və onları sıfıra bərabər tutaraq formanın minimumunu əldə edib-etmədiyimizə baxaq. Bunun üçün ξ 1 , ξ 2 , ξ 3 dəyişənlərinə münasibətdə (5.7) tənliklərini həll edirik (yəni ξ 1 , ξ 2 , ξ 3-ü z 1 , z 2 , z 3 dummy dəyişənləri ilə ifadə edirik. ):

ξ 1 , ξ 2 , ξ 3-ü əlavə etməklə əldə edirik: Φ = 1/5 + z 1 /20 + z 2 /10 + z 3 /20. Burada bütün z üçün əmsallar müsbətdir; deməli, z 1 , z 2 , z 3-ün sıfırdan yuxarı istənilən artımı yalnız Φ formasının artmasına səbəb ola bilər və biz onun minimal olmasını istəyirik. Buna görə də Φ formasını minimuma endirən z 1 , z 2 , z 3 qiymətləri z 1 = z 2 = z 3 = 0-dır. Buna görə də Φ formasının minimum qiyməti: 1/ν = 1 /5, oyunun qiyməti buradan ν = 5. Sıfır dəyərləri z 1 , z 2 , z 3 düsturlarına əvəz edərək (5.8) tapırıq: ξ 1 = 1/20, ξ 2 = 1/10, ξ 3 = 1/20 və ya onları ν ilə çarparaq, p 1 \u003d 1/4, p 2 \u003d 1/2, p 3 \u003d 1/4. Beləliklə, optimal A strategiyası tapılır: , yəni. bütün halların dörddə birində 1 rəqəmini, halların yarısında 2, qalan dörddə birində isə 3 rəqəmini yazmalıyıq.

Oyunun qiymətini bilməklə ν = 5, biz artıq edə bilərik məlum yollar rəqibin optimal strategiyasını tapın . Bunu etmək üçün hər hansı iki "faydalı" strategiyamızdan istifadə edirik (məsələn, A 2 və A 3) və tənlikləri yazırıq:

9q 1 + 11 (1-q 2 -q 1) = 5,

buradan q 1 = q3 = 1/4; q 2 \u003d 1/2. Rəqibin optimal strategiyası bizimlə eyni olacaq: . İndi orijinal (çevrilməmiş) oyuna qayıdın. Bunun üçün yalnız matrisin elementlərinə əlavə olunan ν = 5 oyunun dəyərindən L = 5 dəyərini çıxarmaq lazımdır. Biz orijinal oyunun qiymətini alırıq v 0 = 0. Buna görə də, hər iki tərəfin optimal strategiyaları sıfıra bərabər olan orta gəliri təmin edir; oyun hər iki tərəf üçün eyni dərəcədə faydalı və ya zərərlidir.

Misal 2 A idman klubunun A 1 , A 2 və A 3 komandasının tərkibi üçün üç variantı var . B klubu - həmçinin üç variant B 1, B 2 və B 3. Yarışda iştirak üçün ərizə verərkən heç bir klub rəqibin hansı heyəti seçəcəyini bilmir. A klubunda qalib gəlmə ehtimalı müxtəlif variantlar Keçmiş görüşlərin təcrübəsindən təxminən məlum olan heyətlər matris tərəfindən verilir:

Ən yüksək orta qələbə sayına nail olmaq üçün klubların bir-biri ilə görüşlərdə komandaların hər birinin meydana çıxması tezliyini tapın.

Həll. Oyunun aşağı qiyməti 0,4; yuxarı 0,6; qarışıq strategiyalar sahəsində həll axtarırıq. Kəsrlərlə məşğul olmamaq üçün matrisin bütün elementlərini 10-a vururuq; bu halda oyunun qiyməti 10 dəfə artacaq və qərar dəyişməyəcək. Matris alırıq:

Şərtlər (5.5) formaya malikdir:

və minimum şərt Φ = ξ 1 + ξ 2 + ξ 3 = min.

Rəqibin hər üç strategiyasının “faydalı” olub-olmadığını yoxlayırıq. Bir fərziyyə olaraq əvvəlcə z 1 , z 2 , z 3 dummy dəyişənlərinin sıfıra bərabər olduğunu fərz edirik və yoxlamaq üçün ξ 1 , ξ 2 , ξ 3 üçün (5.10) tənliklərini həll edirik:

(5.12) 136Φ = 30 +13z 1 +18z 2 – 51z 3

Formula (5.12) göstərir ki, z 1 və z 2 dəyişənlərinin qəbul edilən sıfır qiymətindən artırılması yalnız Φ-ni artıra bilər, z 3-ün artırılması isə Φ-ni azalda bilər. Bununla belə, z 3 artımı diqqətlə aparılmalıdır ki, z 3-dən asılı olaraq ξ 1 , ξ 2 , ξ 3 dəyərləri bu halda mənfi olmasın. Buna görə də, bərabərliklərin sağ tərəflərində (5.11) z 1 və z 2 dəyərlərini sıfıra bərabər qoyduq və z 3 dəyərini məqbul həddə qədər artıracağıq (ξ 1 dəyərlərindən hər hansı birinə qədər, ξ 2 , ξ 3 yox olur). İkinci bərabərlikdən (5.11) görünür ki, z 3 artımı ξ 2 dəyəri üçün “təhlükəsizdir” - o, yalnız bundan artır. ξ 1 və ξ 3 dəyərlərinə gəldikdə, burada z 3 artımı yalnız müəyyən bir həddə qədər mümkündür. ξ 1 dəyəri z 3 = 10/23-də yox olur; ξ 3 kəmiyyəti daha əvvəl yox olur, artıq z 3 = 1/4-də. Buna görə də, z 3-ə onun maksimum icazə verilən qiymətini z 3 = 1/4 verməklə, ξ 3 qiymətini də sıfıra çevirəcəyik.

Φ formasının z 1 = 0, z 2 = 0, ξ 3 = 0 olduqda minimuma çevrilib-keçmədiyini yoxlamaq üçün biz qalan (sıfırdan fərqli) dəyişənləri z 1 , z 2 , ξ 3 ilə guya sıfıra bərabər ifadə edirik. . (5.10) tənlikləri ξ 1 , ξ 2 və z 3 -ə görə həll edərək, alırıq:

(5.13) 32Φ = 7 + Зz 1 + 4z 2 + ξ 3

(5.13) düsturundan görünə bilər ki, z 1 , z 2 , ξ 3-də onların qəbul edilən sıfır dəyərlərindən artıq hər hansı artım yalnız Φ formasını artıra bilər. Buna görə də oyunun həlli tapılır; z 1 = z 2 = ξ 3 = 0 qiymətləri ilə müəyyən edilir, buradan ξ 1 = 1/32, ξ 2 = 3/16, z 3 = 1/4. (5.13) düsturu ilə əvəz edərək, oyunun qiymətini tapırıq ν: 32Φ = 7 = 32/ν; v = 32/7. Bizim optimal strategiyamız: . "Faydalı" strategiyalar (A 1 və A 2 kompozisiyaları) 1/7 və 6/7 tezlikləri ilə tətbiq edilməlidir; tərkibi A 3 - heç vaxt istifadə edilməməlidir.

Rəqibin optimal strategiyasını tapmaq üçün, ümumi halda, aşağıdakıları etmək olar: qazanc işarəsini tərsinə çevirmək, matris elementlərini qeyri-mənfi etmək üçün L sabit dəyərini əlavə etmək və rəqib üçün problemi həll etmək. özümüz üçün həll etdiyimiz kimi. Bununla belə, ν oyunun dəyərini artıq bilməyimiz işi bir qədər asanlaşdırır. Bundan əlavə, bu konkret vəziyyətdə problem həlldə yalnız iki "faydalı" düşmən strategiyasının B 1 və B 2-nin iştirak etməsi ilə daha da sadələşdirilir, çünki z 3 dəyəri sıfıra bərabər deyil və buna görə də, B 3 strategiyası ilə oyunun qiymətinə çatılmır. A oyunçusunun hər hansı “faydalı” strategiyasını seçməklə, məsələn, A 1, q 1 və q 2 tezliklərini tapmaq olar. Bunun üçün 8q 1 + 2(1 - q 1) = 32/7 tənliyini yazırıq, buradan q 1 = 3/7, q 2 = 4/7; Rəqibin optimal strategiyası belə olardı: , yəni. düşmən B 3 kompozisiyasından istifadə etməməli, B 1 və B 2 kompozisiyaları isə 3/7 və 4/7 tezlikləri ilə istifadə edilməlidir.

Orijinal matrisə qayıdaraq, oyunun həqiqi dəyərini təyin edirik ν 0 = 32/7:10 = 0,457. Bu o deməkdir ki, at böyük rəqəmlər görüşlərdə A klubunun qələbələrinin sayı bütün görüşlərin 0,457-si olacaq.

§ 6. Oyunların həlli üçün təxmini üsullar

Çox vaxt praktiki məsələlərdə oyunun dəqiq həllini tapmağa ehtiyac yoxdur; oyunun qiymətinə yaxın orta gəlir verən təxmini həll yolu tapmaq kifayətdir. Oyunun qiyməti haqqında təxmini bilik ν artıq matrisin sadə təhlilini və oyunun aşağı (α) və yuxarı (β) qiymətlərinin tərifini verə bilər. Əgər α və β yaxındırsa, praktiki olaraq dəqiq həll axtarmağa ehtiyac yoxdur və bunun üçün təmiz minimaks strategiyalarını seçmək kifayətdir. α və β-nın yaxın olmadığı hallarda, oyunların həlli üçün ədədi üsullardan istifadə edərək praktik həll əldə edilə bilər, onlardan iterasiya metodunu qısaca vurğulayacağıq.

İterasiya metodunun ideyası aşağıdakı kimidir. A və B rəqiblərinin bir-birinə qarşı strategiyalarından istifadə etdiyi “fikir təcrübəsi” oynanılır. Təcrübə hər birində verilmiş oyun matrisinə malik elementar oyunlar ardıcıllığından ibarətdir. Bu onunla başlayır ki, biz (oyunçu A) təsadüfi olaraq strategiyalarımızdan birini seçirik, məsələn, A i . Düşmən buna öz strategiyası ilə cavab verir B j , bizim üçün ən az faydalı olan, yəni. A i strategiyası üçün gəliri minimuma endirir. Biz bu hərəkətə A k strategiyamızla cavab veririk ki, bu da rəqib B j strategiyasından istifadə etdikdə maksimum orta gəliri verir. Sonrakı - yenidən düşmənin növbəsi. O, A i və A k cütlüyümüzə B j strategiyası ilə cavab verir ki, bu da bizə bu iki strategiya (A i, A k) üçün ən kiçik orta gəliri verir və s. İterativ prosesin hər bir addımında hər bir oyunçu digər oyunçunun hər hansı bir hərəkətinə öz strategiyası ilə cavab verir, onun bütün əvvəlki hərəkətləri üçün optimaldır, bəzi qarışıq strategiyalar kimi qəbul edilir, burada xalis strategiyalar müəyyən edilmiş nisbətlərə uyğun nisbətlərdə təmsil olunur. onların tətbiqi tezliyi.

Belə bir üsul, sanki, oyunçuların əsl praktiki “məşq” modelidir, o zaman ki, onların hər biri təcrübə ilə rəqibin davranışını yoxlayır və ona özünə sərfəli şəkildə cavab verməyə çalışır. Öyrənmə prosesinin belə təqlidi kifayət qədər uzun müddət davam edərsə, onda bir cüt hərəkətə (ibtidai oyun) orta qazanc oyunun qiymətinə meylli olacaq və tezliklər p 1 ... p m ; Bu püşkatmada oyunçuların strategiyalarının qarşılaşdığı q 1 … q n optimal strategiyaları müəyyən edən tezliklərə yaxınlaşacaq. Hesablamalar göstərir ki, metodun yaxınlaşması çox ləng gedir, lakin bu, yüksək sürətli kompüterlər üçün maneə deyil.

İterativ metodun tətbiqini əvvəlki bəndin 2-ci nümunəsində həll edilmiş 3×3 oyununun timsalında təsvir edək. Oyun matrislə verilir:

Cədvəl 6.1 təkrarlama prosesinin ilk 18 addımını göstərir. Birinci sütun elementar oyunun nömrəsini verir (hərəkət cütü) n; ikincidə - nömrə i oyunçu A-nın seçilmiş strategiyası; sonrakı üçdə - birinci üçün "kumulyativ mənfəət" n rəqibin strategiyaları ilə oyunlar B 1 , B 2 , B 3 . Bu dəyərlərin ən kiçiyi vurğulanır. Sonrakı nömrə gəlir j rəqibin seçdiyi strategiya və müvafiq olaraq, yığılmış qazanc n A 1 , A 2 , A 3 strategiyaları olan oyunlarda bu dəyərlərin maksimumu yuxarıdan vurğulanır. Vurğulanmış dəyərlər digər oyunçunun cavab strategiyasının seçimini müəyyənləşdirir. Aşağıdakı sütunlar ardıcıl olaraq göstərilir: minimum orta qazanc ν minimum yığılmış qazancın oyunların sayına bölünməsinə bərabərdir n; maksimum toplanmış qələbəyə bölünən maksimum orta qələbəyə bərabərdir n, və onların arifmetik ortası ν* = (ν + )/2. Artımla n hər üç dəyər ν və ν* oyunun dəyərinə ν yaxınlaşacaq, lakin ν* dəyəri təbii olaraq ona nisbətən daha sürətli yaxınlaşacaq.

Cədvəl 6.1.

Nümunədən göründüyü kimi, iterasiyaların yaxınlaşması çox yavaşdır, lakin belə kiçik bir hesablama belə oyunun qiymətinin təxmini dəyərini tapmağa və "faydalı" strategiyaların yayılmasını aşkar etməyə imkan verir. Hesablama maşınlarından istifadə edərkən metodun dəyəri əhəmiyyətli dərəcədə artır. Oyunların həllinin iterativ üsulunun üstünlüyü ondan ibarətdir ki, strategiyaların sayı artdıqca hesablamaların həcmi və mürəkkəbliyi nisbətən zəif artır. m və n.

§ 7. Bəzi sonsuz oyunların həlli üsulları

Sonsuz oyun, tərəflərdən ən azı birinin sonsuz strategiya dəstinə malik olduğu bir oyundur. Bu cür oyunları həll etmək üçün ümumi üsullar hələ işlənməmişdir. Bununla belə, təcrübə üçün, nisbətən sadə həlli qəbul edən bəzi xüsusi hallar maraq doğura bilər. Hər birinin sonsuz (hesabsız) strategiyaları olan iki rəqib A və B-nin oyununu nəzərdən keçirək; oyunçu A üçün bu strategiyalar uyğun gəlir müxtəlif mənalar daimi dəyişən parametr X, və B üçün - parametr saat. Bu halda, ‖a ij ‖ matrisinin əvəzinə, oyun iki davamlı dəyişən arqumentin bəzi funksiyası ilə müəyyən edilir. a (x, y), biz bunu ödəmə funksiyası adlandıracağıq (qeyd edək ki, funksiyanın özü a (x, y) davamlı olmaq lazım deyil). qazanmaq funksiyası a(x, y) həndəsi şəkildə hansısa səthlə təmsil oluna bilər a (x, y) arqument dəyişdirmə sahəsinin üstündə (x, y)(Şəkil 7.1)

Ödəniş funksiyasının təhlili a(x, y)ödəniş matrisinin təhlilinə bənzər şəkildə həyata keçirilir. Birincisi, oyunun aşağı qiyməti α tapılır; çünki bu, hər biri üçün müəyyən edilir X minimum funksiya a(x, y) hamı üçün saat: , onda hamı üçün bu dəyərlərin maksimumu axtarılır X(maksimum):

Oyunun yuxarı qiyməti (minimax) eyni şəkildə müəyyən edilir:

α = β olduğu halı nəzərdən keçirək. Oyunun qiyməti ν həmişə α ilə β arasında olduğundan, onların ümumi dəyəri ν-dir. α = β bərabərliyi səthi ifadə edir a(x, y) yəhər nöqtəsi var, yəni koordinatları x 0, y 0 olan belə bir nöqtə var ki, burada a(x, y) eyni zamanda minimumdur saat və maksimum X(Şəkil 7.2).

Məna a(x, y) bu nöqtədə oyunun qiyməti ν: ν = a(x 0, y 0). Yəhər nöqtəsinin olması bu sonsuz oyunun təmiz strategiya həllinə malik olması deməkdir; x 0, y 0 optimal xalis A və B strategiyalarıdır. Ümumi halda, α ≠ β olduqda, oyun yalnız qarışıq strategiyalar (bəlkə də yeganə deyil) regionunda həll yoluna malik ola bilər. Sonsuz oyunlar üçün qarışıq strategiya strategiyalar üçün müəyyən ehtimal paylanmasına malikdir X və saat təsadüfi dəyişənlər kimi qəbul edilir. Bu paylanma davamlı ola bilər və sıxlıqlarla müəyyən edilə bilər f 1 (X) və f 2 (y); diskret ola bilər və sonra optimal strategiyalar bəzi sıfırdan fərqli ehtimallarla seçilmiş fərdi təmiz strategiyalar toplusundan ibarətdir.

Sonsuz oyunun yəhər nöqtəsi olmadığı halda, oyunun aşağı və yuxarı qiymətlərinin vizual həndəsi şərhini vermək mümkündür. Ödəniş funksiyası olan sonsuz bir oyunu nəzərdən keçirək a(x, y) və strategiyalar x, y, baltaların seqmentlərini davamlı olaraq doldurmaq (x 1, x 2) və (1-də, 2-də). Oyunun daha aşağı qiymətini müəyyən etmək üçün α, səthə "baxmaq" lazımdır a(x, y) oxun tərəfdən saat, yəni. düz layihələndirin hoa(Şəkil 7.3). Tərəflərdən x \u003d x 1 və x \u003d x 2 düz xətləri ilə, yuxarıdan və aşağıdan isə K B və K N əyriləri ilə məhdudlaşdırılmış müəyyən bir rəqəm alırıq. Oyunun aşağı qiyməti α, açıq-aydın, başqa bir şey deyil. əyrisinin maksimum ordinatından K N.

Eynilə, β oyununun yuxarı qiymətini tapmaq üçün səthə “baxmaq” lazımdır a(x, y) oxun tərəfdən X(səthi müstəviyə proyeksiya edin uOa) və proyeksiyanın K B yuxarı sərhədinin minimum ordinatını tapın (şək. 7.4).

Sonsuz oyunların iki elementar nümunəsini nəzərdən keçirək.

Misal 1 A və B oyunçularının hər birinin saysız-hesabsız mümkün strategiyaları var X və saat, və 0 ≤ x ≤ 1; 0 ≤ y ≤ 1. a üçün ödəmə funksiyası a (x, y) - (x - y) 2 ifadəsi ilə verilir. Oyun üçün bir həll tapın.

Həlli.a(x,y) səthi parabolik silindrdir (şəkil 7.5) və yəhər nöqtəsi yoxdur. Oyunun aşağı qiymətini müəyyən edək; hər kəs üçün açıqdır X; deməli = 0. Oyunun yuxarı qiymətini müəyyən edək. Bunu etmək üçün biz sabit tapırıq saat

Bu halda, maksimum həmişə intervalın sərhəddində əldə edilir (x = 0 və ya x = 1 olduqda), yəni. y 2 kəmiyyətlərinə bərabərdir; (1 - y) 2 , daha böyükdür. Bu funksiyaların qrafiklərini təsvir edək (şək. 7.6), yəni. səthin proyeksiyası a(x, y) təyyarəyə uOa. Şəkildəki qalın xətt. 7.6 funksiyanı göstərir. Aydındır ki, onun minimum dəyəri y = 1/2-də əldə edilir və 1/4-ə bərabərdir. Buna görə oyunun yuxarı qiyməti β = 1/4-dir. Bu halda oyunun yuxarı qiyməti ν oyunun qiyməti ilə üst-üstə düşür. Həqiqətən, A oyunçusu qarışıq strategiya S A = tətbiq edə bilər , x = 0 və x = 1 həddindən artıq dəyərləri eyni tezliklərə daxil edilir; onda hər hansı strategiya üçün B oyunçusunun A oyunçusu üçün orta qazancı: ½y 2 + ½(1 - y) 2 olacaq. Bu dəyərin hər hansı bir dəyər üçün olduğunu yoxlamaq asandır saat 0 və 1 arasında ¼-dən az olmayan dəyər var: ½y 2 + ½(1 - y) 2 ≥ ¼.

Beləliklə, A oyunçusu bu qarışıq strategiyadan istifadə edərək, oyunun yuxarı qiymətinə bərabər bir qazanc əldə edə bilər; çünki oyunun qiyməti yuxarı qiymətdən çox ola bilməz bu strategiya S A optimaldır: S A = S A *.

B oyunçusunun optimal strategiyasını tapmaq qalır. Aydındır ki, əgər ν oyununun qiyməti β oyununun yuxarı qiymətinə bərabərdirsə, B oyunçusunun optimal strategiyası həmişə onun xalis minimaks strategiyası olacaqdır ki, bu da ona möcüzəni təmin edir. oyunun yuxarı qiyməti. Bu halda belə bir strategiya y 0 = ½-dir. Həqiqətən də, bu strategiya ilə A oyunçusu nə edirsə etsin, onun qazancı ¼-dən çox olmayacaq. Bu, aşkar bərabərsizlikdən (x - ½) 2 = x(x -1) + ¼ ≤ ¼ gəlir.

Misal 2 A tərəfi ("biz") düşmənin B təyyarəsinə atəş açır. Atəşdən yayınmaq üçün düşmən bir qədər yüklənmə ilə manevr edə bilər saat, onun öz mülahizəsinə görə dəyərlər əlavə edə biləcəyi saat= 0 (düzxətli hərəkət) qədər saat = saatmaks(maksimum əyrilik dairəsi boyunca uçuş). güman edirik saatmaksölçü vahidi, yəni. qoyaq saatmaks= 1. Düşmənlə mübarizədə mərminin uçuşu zamanı hədəfin hərəkəti haqqında bu və ya digər fərziyyələrə əsaslanan nişangahlardan istifadə edə bilərik. Həddindən artıq yükləmə X bu hipotetik manevrdə 0-dan 1-ə qədər istənilən qiymətə bərabər olduğunu qəbul etmək olar. Bizim vəzifəmiz düşməni vurmaqdır; düşmənin vəzifəsi məğlubiyyətsiz qalmaqdır. Məlumat üçün məğlub olma ehtimalı X və saat təqribən düsturla ifadə olunur: a(x, y) = , harada saat- düşmən tərəfindən həddindən artıq yüklənmə; x - baxışda nəzərə alınan həddindən artıq yükləmə. Hər iki tərəf üçün optimal strategiyaları müəyyən etmək tələb olunur.

Həll. Aydındır ki, p = 1 təyin etsək, oyunun həlli dəyişmir. Ödəniş funksiyası a(x, y)Şəkildə göstərilən səthlə təmsil olunur. 7.7.

Bu silindrik bir səthdir, generatorları koordinat bucağının bisektoruna paraleldir. hoy, və generatrisə perpendikulyar olan bir müstəvi ilə kəsişmə normal paylanma əyrisi növünün əyrisidir. Yuxarıda təklif olunan oyunun aşağı və yuxarı qiymətinin həndəsi şərhindən istifadə edərək, β = 1 (Şəkil 7.8) və (Şəkil 7.9) tapırıq. Oyunun yəhər nöqtəsi yoxdur; həlli qarışıq strategiyalar sahəsində axtarılmalıdır. Problem əvvəlki misaldakı problemə bir qədər bənzəyir. Həqiqətən, kiçik dəyərlər üçün k funksiya funksiya kimi davranır –(x – y) 2, və əvvəlki misalın həllində A və B oyunçularının rolları əks olunarsa, oyunun həlli alınacaq; olanlar. optimal strategiyamız xalis strategiya x = 1/2 olacaq və rəqibin optimal strategiyası S B = eyni tezlikdə y = 0 və y = 1 ekstremal strategiyalarından istifadə etmək olacaq. Bu o deməkdir ki, biz həmişə əhatə dairəsindən istifadə etməliyik, həddən artıq yüklənmə üçün hesablanmış x = 1/2 və düşmən bütün halların yarısında heç bir manevrdən istifadə etməməlidir və yarısında - maksimum mümkün manevr.

düyü. 7.8 Şek. 7.9.

Bu həllin k ≤ 2 üçün etibarlı olacağını sübut etmək asandır. Həqiqətən də, rəqibin strategiyası üçün orta gəlir S B = və bizim strategiyamızdır. X funksiyası ilə ifadə edilir , k ≤ 2 dəyərləri üçün x = 1/2-də bir maksimuma malikdir, oyunun aşağı qiymətinə α bərabərdir. Buna görə də, S B strategiyasının tətbiqi rəqibə α-dan çox olmayan itkiyə zəmanət verir, buradan aydın olur ki, α - oyunun daha aşağı qiyməti - oyunun qiyməti ν.

k > 2 üçün a(x) funksiyası iki maksimuma malikdir (Şəkil 7.10), x 0 və 1 - x 0 nöqtələrində təxminən x = 1/2 simmetrik olaraq yerləşir və x 0-ın qiyməti k-dən asılıdır.

Aydındır ki, at k\u003d 2 x 0 \u003d 1 - x 0 \u003d ½; artması ilə k x 0 və 1 - x 0 nöqtələri bir-birindən uzaqlaşır, həddindən artıq nöqtələrə (0 və 1) yaxınlaşır. Buna görə də oyunun həlli k-dan asılı olacaq. Gəlin k-nin xüsusi qiymətini təyin edək, məsələn, k = 3 və oyunun həllini tapaq; Bunun üçün a(x) əyrisinin maksimumunun x 0 absisini təyin edirik. a(x) funksiyasının törəməsini sıfıra bərabər tutaraq, x 0-ı təyin etmək üçün tənlik yazırıq:

Bu tənliyin üç kökü var: x \u003d 1/2 (minimuma çatdığı yer) və maksimuma çatıldığı x 0, 1 - x 0. Tənliyi ədədi olaraq həll edərək, təxminən x 0 ≈ 0,07 tapırıq; 1 - x 0 ≈ 0,93.

Bu vəziyyətdə oyunun həllinin aşağıdakı strategiya cütü olduğunu sübut edək:

Bizim strategiyamız və düşmənin strategiyası ilə saat orta gəlirdir

0-da minimum a 1 (y) tapın< у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем

y = 1/2 təyin etdikdə alırıq

1 (0)-dan böyük olan; buna görə də oyunun qiyməti 1 (0)-dan az deyil:

İndi deyək ki, rəqib S B * strategiyasından, biz isə x strategiyasından istifadə edirik. Sonra orta qazanc olacaq

Lakin biz x 0-ı dəqiq seçmişik ki, x = x 0-da (7.2) ifadənin maksimumuna çatsın; Nəticədə,

olanlar. S B * strategiyasından istifadə edən rəqib 0,530-dan çox itkinin qarşısını ala bilər; buna görə də ν = 0,530 oyunun qiymətidir və S A * və S B * strategiyaları həlli verir. Bu o deməkdir ki, biz eyni tezlikdə x = 0,07 və x = 0,93 olan nişangahlardan istifadə etməliyik və düşmən eyni tezlikdə və maksimum yüklənmə ilə manevr etməməlidir.

Qeyd edək ki, qazanc ν = 0.530 oyunun aşağı qiymətindən nəzərəçarpacaq dərəcədə böyükdür , maksimum strategiyamızı x 0 = 1/2 tətbiq etməklə özümüz təmin edə bilərik.

Biri praktik yollar sonsuz oyunların həlli onların sonlulara təxmini endirilməsidir. Bu halda, hər bir oyunçu üçün bütün mümkün strategiyalar şərti olaraq bir strategiyada birləşdirilir. Bu şəkildə, əlbəttə ki, oyunun yalnız təxmini həlli əldə edilə bilər, lakin əksər hallarda dəqiq bir həll tələb olunmur.

Bununla belə, nəzərə almaq lazımdır ki, bu texnikanı tətbiq edərkən, qarışıq strategiyalar bölgəsində həllər hətta orijinal sonsuz oyunun həllinin təmiz strategiyalarda mümkün olduğu hallarda da görünə bilər, yəni. sonsuz oyunun yəhər nöqtəsi olduqda. Əgər sonsuz oyunu sonluya endirməklə, yalnız iki qonşu “faydalı” strategiyanı özündə birləşdirən qarışıq həll əldə edilirsə, onda onların arasında orijinal sonsuz oyun aralığının xalis strategiyasını tətbiq etməyə çalışmağın mənası var.

Sonda qeyd edirik ki, sonlu oyunlardan fərqli olaraq, sonsuz oyunların həlli olmaya bilər. Heç bir həlli olmayan sonsuz bir oyuna misal verək. İki oyunçunun hər biri istənilən tam ədədi adlandırır. adlı daha çox digərindən 1 rubl alır. Hər ikisi eyni nömrəyə zəng edərsə, oyun heç-heçə başa çatır. Oyunun açıq şəkildə həlli ola bilməz. Bununla belə, həlli mütləq mövcud olan sonsuz oyun sinifləri var.