uy » Axborot byulleteni » Antagonistik matritsali o'yinlar. Uzluksiz strategiyali antagonistik o'yinlar Antagonistik juftlik o'yinida o'yinchilarning maqsadlari

Antagonistik matritsali o'yinlar. Uzluksiz strategiyali antagonistik o'yinlar Antagonistik juftlik o'yinida o'yinchilarning maqsadlari

Nol summali o'yin, unda har bir o'yinchi o'z ixtiyorida cheklangan strategiyalar to'plamiga ega. Matritsa o'yinining qoidalari to'lov matritsasi bilan belgilanadi, uning elementlari birinchi o'yinchining yutug'i bo'lib, ikkinchi o'yinchining ham yo'qotishlari hisoblanadi.

Matritsa o'yini antagonistik o'yindir. Birinchi o'yinchi o'yin narxiga teng bo'lgan maksimal kafolatlangan (ikkinchi o'yinchining xatti-harakatidan qat'iy nazar) yutuqni oladi; xuddi shunday, ikkinchi o'yinchi minimal kafolatlangan yo'qotishga erishadi.

ostida strategiya mavjud vaziyatga qarab o'yinchining har bir shaxsiy harakati uchun harakat tanlashni belgilovchi qoidalar (prinsiplar) yig'indisi tushuniladi.

Endi hamma narsa tartibda va batafsil.

To'lov matritsasi, sof strategiyalar, o'yin narxi

IN matritsa o'yini uning qoidalari belgilanadi to'lov matritsasi .

Ikkita ishtirokchi bo'lgan o'yinni ko'rib chiqing: birinchi o'yinchi va ikkinchi o'yinchi. Birinchi o'yinchi o'z ixtiyorida bo'lsin m sof strategiyalar va ikkinchi o'yinchining ixtiyorida - n toza strategiyalar. O'yin ko'rib chiqilayotgani uchun bu o'yinda g'alaba va mag'lubiyatlar bo'lishi tabiiy.

IN to'lov matritsasi elementlar o'yinchilarning g'alaba va yo'qotishlarini ifodalovchi raqamlardir. Yutuqlar va yo'qotishlar ballar, pul miqdori yoki boshqa birliklarda ifodalanishi mumkin.

Keling, to'lov matritsasini yarataylik:

Agar birinchi o'yinchi tanlasa i- sof strategiya va ikkinchi o'yinchi - j th sof strategiya, keyin birinchi futbolchining to'lovi bo'ladi aij birliklar va ikkinchi o'yinchining yo'qolishi ham aij birliklar.

Chunki aij + (- a ij) = 0, keyin tasvirlangan o'yin nol summali matritsali o'yindir.

Matritsali o'yinning eng oddiy misoli tanga tashlashdir. O'yin qoidalari quyidagicha. Birinchi va ikkinchi o'yinchilar tanga tashlashadi va natijada boshlar yoki dumlar paydo bo'ladi. Agar "boshlar" va "boshlar" yoki "dumlar" yoki "dumlar" bir vaqtning o'zida tashlangan bo'lsa, birinchi o'yinchi bitta birlik yutadi, boshqa hollarda esa u bir birlikdan mahrum bo'ladi (ikkinchi o'yinchi bitta birlik yutadi). . Xuddi shu ikkita strategiya ikkinchi o'yinchining ixtiyorida. Tegishli to'lov matritsasi quyidagicha bo'ladi:

O'yin nazariyasining vazifasi birinchi o'yinchining unga maksimal o'rtacha g'alabani kafolatlaydigan strategiyasini tanlashni, shuningdek, ikkinchi o'yinchining unga maksimal o'rtacha yo'qotishni kafolatlaydigan strategiyasini tanlashni aniqlashdan iborat.

Matritsali o'yinda strategiyani qanday tanlash mumkin?

Keling, to'lov matritsasiga yana qaraylik:

Birinchidan, agar u foydalansa, birinchi o'yinchi uchun yutuq miqdorini aniqlaymiz i sof strategiya. Agar birinchi o'yinchi foydalansa i Agar sof strategiya bo'lsa, ikkinchi o'yinchi shunday sof strategiyadan foydalanadi, deb taxmin qilish mantiqan to'g'ri bo'ladi, buning natijasida birinchi o'yinchining daromadi minimal bo'ladi. O'z navbatida, birinchi o'yinchi unga maksimal g'alabani ta'minlaydigan shunday sof strategiyadan foydalanadi. Ushbu shartlarga asoslanib, biz belgilagan birinchi o'yinchining yutuqlari v1 , chaqirildi maksimal g'alaba yoki o'yinning eng past narxi .

Da bu qiymatlar uchun birinchi o'yinchi quyidagicha harakat qilishi kerak. Har bir satrdan minimal elementning qiymatini yozing va ulardan maksimalni tanlang. Shunday qilib, birinchi o'yinchining g'alabasi minimaldan maksimal bo'ladi. Shuning uchun nom - maksimal g'alaba qozonish. Ushbu elementning qator raqami birinchi o'yinchi tanlagan sof strategiyaning raqami bo'ladi.

Endi ikkinchi o'yinchi foydalansa, yo'qotish miqdorini aniqlaymiz j th strategiyasi. Bunday holda, birinchi o'yinchi o'zining sof strategiyasidan foydalanadi, bunda ikkinchi o'yinchining yo'qolishi maksimal bo'ladi. Ikkinchi o'yinchi o'zining yo'qotilishi minimal bo'lgan sof strategiyani tanlashi kerak. Ikkinchi o'yinchining yo'qolishi, biz buni deb belgilaymiz v2 , chaqirildi minimal yo'qotish yoki o'yinning eng yuqori narxi .

Da o'yin narxi bo'yicha muammolarni hal qilish va strategiyani aniqlash Ikkinchi o'yinchi uchun ushbu qiymatlarni aniqlash uchun quyidagi amallarni bajaring. Har bir ustundan maksimal elementning qiymatini yozing va ulardan minimalni tanlang. Shunday qilib, ikkinchi o'yinchining yo'qolishi maksimaldan minimal bo'ladi. Shuning uchun nom - minimaks g'alaba qozonish. Ushbu elementning ustun raqami ikkinchi o'yinchi tanlagan sof strategiyaning raqami bo'ladi. Agar ikkinchi o'yinchi "minimaks" dan foydalansa, birinchi o'yinchi qanday strategiya tanlashidan qat'i nazar, u dan ortiq yo'qotmaydi. v2 birliklar.

1-misol.

Qatorlarning eng kichik elementlarining eng kattasi 2, bu o'yinning past narxi, birinchi qator unga mos keladi, shuning uchun birinchi o'yinchining maksimal strategiyasi birinchi. Ustunlarning eng katta elementlaridan eng kichigi 5 ga teng, bu o'yinning yuqori narxi, ikkinchi ustun unga mos keladi, shuning uchun ikkinchi o'yinchining minimal strategiyasi ikkinchi.

Endi biz o'yinning pastki va yuqori narxini, maksimal va minimaks strategiyalarini topishni o'rganganimizdan so'ng, ushbu tushunchalarni rasmiy ravishda qanday aniqlashni o'rganish vaqti keldi.

Shunday qilib, birinchi o'yinchi uchun kafolatlangan g'alaba:

Birinchi o'yinchi unga minimal yutuqlarni maksimal darajada ta'minlaydigan sof strategiyani tanlashi kerak. Ushbu daromad (maksimin) quyidagicha belgilanadi:

Birinchi o'yinchi o'zining sof strategiyasidan foydalanadi, shunda ikkinchi o'yinchining yo'qolishi maksimal bo'ladi. Ushbu yo'qotish quyidagicha ifodalanadi:

Ikkinchi o'yinchi o'zining sof strategiyasini tanlashi kerak, shunda uning yo'qotilishi minimal bo'ladi. Ushbu yo'qotish (minimax) quyidagicha ko'rsatilgan:

Xuddi shu seriyadan yana bir misol.

2-misol. To'lov matritsasi bilan matritsali o'yin berilgan

Birinchi o'yinchining maksimal strategiyasini, ikkinchi o'yinchining minimal strategiyasini, o'yinning pastki va yuqori narxini aniqlang.

Yechim. To'lov matritsasining o'ng tomonida biz uning qatorlarida eng kichik elementlarni yozamiz va ularning maksimalini, matritsa ostida esa - ustunlardagi eng katta elementlarni belgilaymiz va ulardan minimalini tanlaymiz:

Chiziqlarning eng kichik elementlaridan eng kattasi 3, bu o'yinning past narxi, ikkinchi qator unga mos keladi, shuning uchun birinchi o'yinchining maksimal strategiyasi ikkinchisidir. Ustunlarning eng katta elementlaridan eng kichigi 5 ga teng, bu o'yinning yuqori narxi, birinchi ustun unga mos keladi, shuning uchun ikkinchi o'yinchining minimal strategiyasi birinchisidir.

Matritsali o'yinlarda egar nuqtasi

Agar o'yinning yuqori va pastki narxlari bir xil bo'lsa, u holda matritsali o'yin egar nuqtasiga ega deb hisoblanadi. Buning aksi ham to'g'ri: agar matritsali o'yinda egar nuqtasi bo'lsa, u holda matritsa o'yinining yuqori va pastki narxlari bir xil bo'ladi. Tegishli element qatordagi eng kichik va ustundagi eng katta va o'yin narxiga teng.

Shunday qilib, agar , u holda birinchi o'yinchining optimal sof strategiyasi va ikkinchi o'yinchining optimal sof strategiyasi hisoblanadi. Ya'ni, bir xil juftlik strategiyalari yordamida teng past va yuqori o'yin narxlariga erishiladi.

Ushbu holatda matritsali o'yin sof strategiyalarda yechimga ega .

3-misol. To'lov matritsasi bilan matritsali o'yin berilgan

O'yinning past narxi o'yinning yuqori narxiga to'g'ri keladi. Shunday qilib, o'yinning narxi 5. Ya'ni. O'yinning narxi egar nuqtasi qiymatiga teng. Birinchi o'yinchining maksimal strategiyasi ikkinchi sof strategiya, ikkinchi o'yinchining minimaks strategiyasi uchinchi sof strategiyadir. Ushbu matritsali o'yinda sof strategiyalarda yechim bor.

Matritsali o'yin muammosini o'zingiz hal qiling va keyin yechimga qarang

4-misol. To'lov matritsasi bilan matritsali o'yin berilgan

O'yinning pastki va yuqori narxini toping. Ushbu matritsa o'yinida egar nuqtasi bormi?

Optimal aralash strategiya bilan matritsali o'yinlar

Ko'pgina hollarda, matritsali o'yinda egar nuqtasi yo'q, shuning uchun mos keladigan matritsali o'yinda sof strategiyalarda hech qanday yechim yo'q.

Lekin u optimal aralash strategiyalarda yechimga ega. Ularni topish uchun siz o'yin bir necha marta takrorlangan deb taxmin qilishingiz kerak, shunda tajribaga asoslanib, qaysi strategiya afzalroq ekanligini taxmin qilishingiz mumkin. Shuning uchun qaror ehtimollik va o'rtacha (matematik kutish) tushunchasi bilan bog'liq. Yakuniy yechimda ham egar nuqtasining analogi (ya'ni o'yinning pastki va yuqori narxlarining tengligi) va ularga mos keladigan strategiyalarning analogi mavjud.

Shunday qilib, birinchi o'yinchi maksimal o'rtacha g'alaba qozonishi va ikkinchi o'yinchi minimal o'rtacha yo'qotishga ega bo'lishi uchun ma'lum bir ehtimollik bilan sof strategiyalardan foydalanish kerak.

Agar birinchi o'yinchi ehtimollik bilan sof strategiyalardan foydalansa , keyin vektor aralash birinchi o'yinchi strategiyasi deb ataladi. Boshqacha qilib aytganda, bu sof strategiyalarning "aralashmasi". Bunday holda, bu ehtimollar yig'indisi bittaga teng:

Agar ikkinchi o'yinchi ehtimollik bilan sof strategiyalardan foydalansa , keyin vektor ikkinchi o'yinchi aralash strategiya deb ataladi. Bunday holda, bu ehtimollar yig'indisi bittaga teng:

Agar birinchi o'yinchi aralash strategiyadan foydalansa p, va ikkinchi o'yinchi - aralash strategiya q, keyin mantiqiy bo'ladi kutilgan qiymat birinchi o'yinchining g'alabasi (ikkinchi o'yinchining mag'lubiyati). Uni topish uchun siz birinchi o'yinchining aralash strategiya vektorini (bir qatorli matritsa bo'ladi), to'lov matritsasi va ikkinchi o'yinchining aralash strategiya vektorini (bir ustunli matritsa bo'ladi) ko'paytirishingiz kerak:

5-misol. To'lov matritsasi bilan matritsali o'yin berilgan

Agar birinchi o'yinchining aralash strategiyasi , ikkinchi o'yinchining aralash strategiyasi bo'lsa, birinchi o'yinchining g'alabasini (ikkinchi o'yinchining mag'lubiyati) matematik kutishini aniqlang.

Yechim. Birinchi o'yinchining g'alabasini (ikkinchi o'yinchining mag'lubiyati) matematik kutish formulasiga ko'ra, u birinchi o'yinchining aralash strategiya vektori, to'lov matritsasi va ikkinchi o'yinchining aralash strategiya vektori mahsulotiga teng:

Birinchi o'yinchi shunday aralash strategiya deb ataladi, agar o'yin etarli miqdorda takrorlansa, unga maksimal o'rtacha daromad keltiradi.

Optimal aralash strategiya ikkinchi o'yinchi shunday aralash strategiya deb ataladi, agar o'yin etarli miqdorda takrorlansa, unga minimal o'rtacha yo'qotishni ta'minlaydi.

Sof strategiyalar uchun maksimal va minimaks belgilariga o'xshab, optimal aralash strategiyalar quyidagicha belgilanadi (va birinchi o'yinchining g'alabasi va ikkinchi o'yinchining mag'lubiyatining o'rtacha matematik kutilishi bilan bog'liq):

Bu holda, funktsiya uchun E egar nuqtasi bor , bu tenglikni anglatadi.

Optimal aralash strategiyalarni va egar nuqtasini topish uchun, ya'ni aralash strategiyalarda matritsali o'yinni hal qilish , siz matritsa o'yinini chiziqli dasturlash masalasiga, ya'ni optimallashtirish masalasiga qisqartirishingiz va tegishli chiziqli dasturlash masalasini hal qilishingiz kerak.

Matritsali o'yinni chiziqli dasturlash muammosiga qisqartirish

Matritsa o'yinini aralash strategiyalarda hal qilish uchun siz to'g'ri chiziq qurishingiz kerak chiziqli dasturlash muammosi Va ikki tomonlama vazifa. Dual masalada chegaralar tizimidagi o'zgaruvchilarning koeffitsientlarini, maqsad funktsiyasidagi o'zgaruvchilarning erkin shartlari va koeffitsientlarini saqlaydigan kengaytirilgan matritsa transpozitsiya qilinadi. Bunda asl masalaning maqsad funksiyasining minimali dual masalada maksimalga mos keladi.

To'g'ridan-to'g'ri chiziqli dasturlash masalasida maqsad funktsiyasi:

To'g'ridan-to'g'ri chiziqli dasturlash masalasida cheklovlar tizimi:

Ikkilamchi masalada maqsad funksiyasi:

Ikkilamchi muammoda cheklovlar tizimi:

To'g'ridan-to'g'ri chiziqli dasturlash masalasining optimal rejasi bilan belgilanadi

dual masalaning optimal rejasi esa bilan belgilanadi

Tegishli optimal rejalar uchun chiziqli shakllarni va bilan belgilaymiz,

va ularni optimal rejalarning tegishli koordinatalarining yig'indisi sifatida topish kerak.

Oldingi paragrafning ta'riflari va optimal rejalar koordinatalariga muvofiq, birinchi va ikkinchi o'yinchilarning quyidagi aralash strategiyalari amal qiladi:

Nazariy matematiklar buni isbotladilar o'yin narxi optimal rejalarning chiziqli shakllari orqali quyidagi tarzda ifodalanadi:

ya'ni optimal rejalar koordinatalari yig'indilarining o'zaro nisbati.

Biz, amaliyotchilar, ushbu formuladan faqat aralash strategiyalarda matritsali o'yinlarni hal qilish uchun foydalanishimiz mumkin. Kabi optimal aralash strategiyalarni topish uchun formulalar mos ravishda birinchi va ikkinchi o'yinchilar:

bunda ikkinchi omillar vektorlardir. Optimal aralash strategiyalar, shuningdek, oldingi paragrafda aniqlaganimizdek, vektorlardir. Shuning uchun raqamni (o'yin narxini) vektorga ko'paytirish (optimal rejalar koordinatalari bilan) biz ham vektorni olamiz.

6-misol. To'lov matritsasi bilan matritsali o'yin berilgan

O'yin narxini toping V va optimal aralash strategiyalar va.

Yechim. Ushbu matritsa o'yiniga mos keladigan chiziqli dasturlash muammosini yaratamiz:

Biz to'g'ridan-to'g'ri muammoni hal qilamiz:

Topilgan koordinatalar yig'indisi sifatida optimal rejalarning chiziqli shaklini topamiz.

O'yin nazariyasida batafsil ishlab chiqilgan eng oddiy holat - bu cheklangan nol yig'indili juftlik o'yini (ikki kishi yoki ikkita koalitsiyaning antagonistik o'yini). Qarama-qarshi manfaatlarga ega ikki o'yinchi A va B ishtirok etadigan G o'yinini ko'rib chiqaylik: birining foydasi boshqasining yo'qotilishiga teng. A o'yinchisining to'lovi qarama-qarshi belgili B o'yinchisining to'loviga teng bo'lganligi sababli, bizni faqat a o'yinchining to'lovi qiziqtirishi mumkin. Tabiiyki, A maksimallashtirishni, B esa a minimallashtirishni xohlaydi.

Oddiylik uchun, keling, o'zimizni o'yinchilardan biri bilan (bu A bo'lsin) aqlan tanishtiramiz va uni "biz", B o'yinchini esa "raqib" deb ataymiz (albatta, bundan A uchun haqiqiy ustunlik yo'q). Keling, bizda mumkin bo'lgan strategiyalar va raqib - mumkin bo'lgan strategiyalar (bunday o'yin o'yin deb ataladi). Agar biz strategiyadan foydalansak va raqib strategiyadan foydalansa, yutuqimizni belgilaymiz

26.1-jadval

Faraz qilaylik, har bir juft strategiya uchun foyda (yoki o'rtacha daromad) bizga ma'lum. Keyin, printsipial jihatdan, o'yinchilarning strategiyalari va mos keladigan daromadlari ro'yxatini ko'rsatadigan to'rtburchaklar jadvalini (matritsani) qurish mumkin (26.1-jadvalga qarang).

Agar bunday jadval tuzilgan bo'lsa, unda ular G o'yini matritsa shakliga tushirilganligini aytishadi (o'yinni bunday shaklga keltirish allaqachon qiyin vazifa bo'lishi mumkin va ba'zida juda ko'p strategiyalar tufayli deyarli imkonsizdir. ). E'tibor bering, agar o'yin matritsa shakliga tushirilsa, u holda ko'p harakatli o'yin aslida bitta harakatli o'yinga qisqartiriladi - o'yinchi faqat bitta harakatni amalga oshirishi kerak: strategiyani tanlang. Biz o'yin matritsasini qisqacha belgilaymiz

Keling, G (4X5) o'yinining matritsa ko'rinishidagi misolini ko'rib chiqaylik. Bizning ixtiyorimizda to'rtta strategiya mavjud (tanlash uchun), dushmanning esa beshta strategiyasi bor. O'yin matritsasi 26.2-jadvalda keltirilgan

Keling, o'ylab ko'raylik, biz (A o'yinchisi) qanday strategiyadan foydalanishimiz kerak? Matritsa 26.2 da "10" vasvasasi bor; biz ushbu "tidbit" ni oladigan strategiyani tanlash vasvasasiga tushdik.

Ammo kuting: dushman ham ahmoq emas! Agar biz strategiyani tanlasak, u bizga g'azablanib, strategiyani tanlaydi va biz "1" achinarli foyda olamiz. Yo'q, siz strategiyani tanlay olmaysiz! Qanday bo'lish kerak? Shubhasiz, ehtiyotkorlik printsipiga asoslanib (va bu o'yin nazariyasining asosiy printsipi), biz minimal daromadimiz maksimal bo'lgan strategiyani tanlashimiz kerak.

26.2-jadval

Bu "mini-maks printsipi" deb ataladi: shunday harakat qilingki, raqibingizning siz uchun eng yomon xatti-harakatlarini hisobga olgan holda, siz maksimal g'alaba qozonasiz.

Keling, 26.2-jadvalni qayta yozamiz va o'ngdagi qo'shimcha ustunga har bir qatorga minimal yutuq qiymatini yozamiz (minimum qator); a satr uchun belgilaymiz (26.3-jadvalga qarang).

26.3-jadval

Barcha qiymatlardan (o'ng ustun) eng kattasi (3) ta'kidlangan. Strategiya unga mos keladi. Ushbu strategiyani tanlab, biz har qanday holatda ham (dushmanning har qanday xatti-harakati uchun) 3 dan kam bo'lmagan g'alaba qozonishimizga ishonch hosil qilishimiz mumkin. Bu qiymat bizning kafolatlangan g'alabamizdir; Ehtiyotkorlik bilan harakat qilsak, bundan kam ololmaymiz, balki ko'proq olamiz).

Ushbu yutuq o'yinning eng past narxi deb ataladi (yoki "maksimin" - minimal yutuqning maksimal qiymati). Biz uni a sifatida belgilaymiz. Bizning holatda

Endi dushmanning nuqtai nazarini va uning sababini olaylik. U qandaydir piyon emas, lekin u ham aqlli! Strategiyani tanlashda u kamroq berishni xohlaydi, lekin u bizning eng yomon xatti-harakatlarimizga ishonishi kerak. Agar u strategiya tanlasa, biz unga javob beramiz va u 10 beradi; agar u tanlasa, biz unga javob beramiz va u beradi va hokazo.26.3-jadvalga qo'shimcha pastki chiziq qo'shamiz va undagi ustunlarning maksimallarini yozamiz.Shubhasiz, ehtiyotkor raqib bu qiymat bo'lgan strategiyani tanlashi kerak. minimal (tegishli qiymat 5 26.3-jadvalda ta'kidlangan) . Bu qiymat P daromadning qiymati bo'lib, undan ko'proq oqilona raqib bizga bermaydi. Bu o'yinning yuqori narxi deb ataladi (yoki "mi-nimax" - maksimal yutuqning minimal qiymati). Bizning misolimizda va dushmanning strategiyasi bilan erishiladi

Shunday qilib, ehtiyotkorlik printsipiga asoslanib (qayta sug'urta qilish qoidasi "har doim eng yomoniga ishoning!"), biz A strategiyasini va dushman strategiyasini tanlashimiz kerak - Bunday strategiyalar "minimax" deb ataladi (minimax printsipidan kelib chiqqan holda). Bizning misolimizdagi ikkala tomon ham o'zlarining minimaks strategiyalariga sodiq qolar ekan, foyda bo'ladi

Endi bir zum tasavvur qilaylik, biz dushman strategiyaga amal qilayotganini bilib oldik. Keling, uni buning uchun jazolaymiz va strategiyani tanlaymiz, biz 5 ta olamiz va bu unchalik yomon emas. Ammo dushman ham muvaffaqiyatsiz emas; unga bizning strategiyamiz ekanligini bilsin , u ham tanlashga shoshiladi, yutuqimizni 2 ga kamaytiradi va hokazo (hamkorlar “strategiyalar bilan yugurishdi”). Qisqasi, bizning misolimizdagi minimaks strategiyalari boshqa tomonning xatti-harakatlari haqidagi ma'lumotlarga nisbatan beqaror; bu strategiyalar muvozanat xususiyatiga ega emas.

Har doim shundaymi? Yo'q har doim emas. 26.4-jadvalda keltirilgan matritsa bilan misolni ko'rib chiqing.

Ushbu misolda o'yinning past narxi yuqori narxga teng: . Bundan nima kelib chiqadi? A va B o'yinchilarining minimaks strategiyalari barqaror bo'ladi. Ikkala o'yinchi ham ularga amal qilgan ekan, to'lov 6 ga teng. Keling, agar (A) raqib (B) B strategiyasiga amal qilishini bilsak nima bo'lishini ko'rib chiqaylik?

26.4-jadval

Ammo mutlaqo hech narsa o'zgarmaydi, chunki strategiyadan har qanday og'ish bizning ahvolimizni yanada yomonlashtirishi mumkin. Xuddi shunday, raqib tomonidan olingan ma'lumotlar uni o'z strategiyasidan chetga chiqishga majburlamaydi.Bir juft strategiya muvozanatlilik xususiyatiga ega (muvozanatli strategiyalar juftligi) va ushbu juft strategiya yordamida erishilgan foyda (bizning holatimizda 6) "matritsaning egar nuqtasi" deb ataladi. Egar nuqtasi va muvozanatli juft strategiya mavjudligining belgisi o'yinning pastki va yuqori narxlarining tengligidir; umumiy qiymati o'yin narxi deb ataladi. Biz uni belgilaymiz

Ushbu daromadga erishiladigan strategiyalar (bu holda) optimal sof strategiyalar deb ataladi va ularning umumiyligi o'yinning echimi deb ataladi. Bunday holda, ular o'yinning o'zi haqida sof strategiyalarda hal qilinishini aytishadi. Ikkala A va B partiyalariga ularning pozitsiyalari eng yaxshi bo'lgan optimal strategiyalari berilishi mumkin. Va agar A o'yinchisi 6 ta g'alaba qozonsa va B o'yinchisi yutqazsa, bu o'yin shartlari: A uchun foydali va B uchun zarar.

O'quvchida savol tug'ilishi mumkin: nima uchun optimal strategiyalar "sof" deb ataladi? Biroz oldinga qarab, biz bu savolga javob beramiz: "aralash" strategiyalar mavjud bo'lib, ular o'yinchi faqat bitta strategiyani emas, balki bir nechtasini tasodifiy kesishgan holda ishlatadi. Shunday qilib, agar biz sof strategiyalarga qo'shimcha ravishda aralash strategiyalarga ruxsat beradigan bo'lsak, har bir cheklangan o'yinda yechim bor - muvozanat nuqtasi. Ammo bu hali muhokama qilinishi kerak.

O'yinda egar nuqtasining mavjudligi qoida emas, aksincha, bu istisno. Aksariyat o'yinlarda egar nuqtasi yo'q. Biroq, har doim egar nuqtasi bo'lgan va shuning uchun sof strategiyalarda hal qilinadigan o'yin turi mavjud. Bular "to'liq ma'lumotga ega o'yinlar" deb ataladi. To'liq ma'lumotga ega bo'lgan o'yin - bu har bir o'yinchi, har bir shaxsiy harakati bilan, uning rivojlanishining butun fonini, ya'ni shaxsiy va tasodifiy barcha oldingi harakatlar natijalarini biladigan o'yin. To'liq ma'lumotga ega o'yinlarga misollar: shashka, shaxmat, tic-tac-toe va boshqalar.

O'yin nazariyasida to'liq ma'lumotga ega bo'lgan har bir o'yinning egar nuqtasi borligi isbotlangan va shuning uchun sof strategiyalarda hal qilinadi. To'liq ma'lumotga ega bo'lgan har bir o'yinda o'yin narxiga teng barqaror daromad keltiradigan bir juft optimal strategiya mavjud va. Agar bunday o'yin faqat shaxsiy harakatlardan iborat bo'lsa, unda har bir o'yinchi o'zining optimal strategiyasidan foydalanganda, u juda aniq tarzda - o'yin narxiga teng g'alaba bilan yakunlanishi kerak. Bu shuni anglatadiki, agar o'yinning echimi ma'lum bo'lsa, o'yinning o'zi o'z ma'nosini yo'qotadi!

To'liq ma'lumotga ega bo'lgan o'yinning oddiy misolini olaylik: ikkita o'yinchi navbatma-navbat nikellarni dumaloq stol ustiga qo'yadi, tanga markazining o'rnini tasodifiy tanlaydi (tangalarning o'zaro bir-biriga yopishishiga yo'l qo'yilmaydi). Oxirgi nikelni qo'ygan kishi g'alaba qozonadi (boshqalar uchun joy qolmaganida). Bu o'yinning natijasi, mohiyatan, oldindan belgilab qo'yilganligini ko'rish oson. Tangani birinchi bo'lib joylashtirgan o'yinchi g'alaba qozonishini ta'minlaydigan ma'lum bir strategiya mavjud.

Ya'ni, u birinchi navbatda stolning o'rtasiga nikel qo'yishi kerak, so'ngra har bir raqibning harakatiga nosimmetrik harakat bilan javob berishi kerak. Shubhasiz, dushman o'zini qanday tutmasin, mag'lubiyatdan qochib qutula olmaydi. Vaziyat shaxmat va umuman to'liq ma'lumotga ega o'yinlar bilan bir xil: matritsa shaklida yozilgan ularning har qandayida egar nuqtasi bor, bu yechim sof strategiyalarda ekanligini anglatadi va shuning uchun bu yechim faqat ma'noga ega. topilmaydi. Aytaylik, shaxmat o‘yini yo har doim oq g‘alaba bilan tugaydi, yoki har doim qora tanlilar g‘alabasi bilan yoki durang bilan tugaydi, lekin biz aniq nima ekanligini hali bilmaymiz (shaxmat ixlosmandlari uchun baxtga). Yana qo'shamiz: biz yaqin kelajakda bilishimiz dargumon, chunki strategiyalar soni shunchalik kattaki, o'yinni matritsa shakliga keltirish va unda egar nuqtasini topish juda qiyin (agar imkonsiz bo'lsa).

Endi o'zimizdan so'raymiz, agar o'yinda egar nuqtasi bo'lmasa, nima qilish kerak: Xo'sh, agar har bir o'yinchi bitta sof strategiyani tanlashga majbur bo'lsa, unda hech narsa qilish kerak emas: biz minimax printsipiga amal qilishimiz kerak. Agar siz o'z strategiyalaringizni "aralashtirsangiz", ularni tasodifiy ba'zi ehtimolliklar bilan almashtira olsangiz, bu boshqa masala. Aralash strategiyalardan foydalanish shu tarzda o'ylangan: o'yin ko'p marta takrorlanadi; o'yinning har bir o'yinidan oldin, o'yinchiga shaxsiy navbat berilganda, u o'z tanlovini tasodifga "ishonib beradi", "qur'a tashlaydi" va paydo bo'lgan strategiyani oladi (biz oldingi bobdan lotni qanday tashkil qilishni allaqachon bilamiz. ).

O'yin nazariyasidagi aralash strategiyalar o'zgaruvchan, moslashuvchan taktikalar modeli bo'lib, o'yinchilarning hech biri ma'lum bir o'yinda raqib o'zini qanday tutishini bilmasa. Ushbu taktika (odatda hech qanday matematik asossiz) ko'pincha karta o'yinlarida qo'llaniladi. Ayni paytda shuni ta'kidlaymizki, o'z xatti-harakatingizni dushmandan yashirishning eng yaxshi usuli - unga tasodifiy belgi berish va shuning uchun nima qilishingizni oldindan bilmaslikdir.

Keling, aralash strategiyalar haqida gapiraylik. Biz mos ravishda A va B o'yinchilarining aralash strategiyalarini belgilaymiz, bu erda (jami bittadan iborat) - A o'yinchisining strategiyalardan foydalanish ehtimoli - B o'yinchisining strategiyalardan foydalanish ehtimoli

Maxsus holatda bittadan tashqari barcha ehtimollar nolga teng bo'lsa va bu bittaga teng bo'lsa, aralash strategiya sofga aylanadi.

O'yin nazariyasining asosiy teoremasi mavjud: har qanday cheklangan ikki kishilik nol yig'indili o'yin kamida bitta yechimga ega - odatda aralashgan optimal strategiyalar juftligi va mos keladigan narx.

O'yinning yechimini tashkil etuvchi optimal strategiyalar juftligi quyidagi xususiyatga ega: agar o'yinchilardan biri o'zining optimal strategiyasiga rioya qilsa, ikkinchisi unikidan chetga chiqishi foydali bo'lmaydi. Ushbu juftlik strategiyasi o'yinda ma'lum bir muvozanat pozitsiyasini hosil qiladi: bir o'yinchi daromadni maksimalga, ikkinchisi - minimalga aylantirmoqchi, har biri o'z yo'nalishi bo'yicha tortadi va ikkalasining ham oqilona harakati bilan muvozanat va barqaror daromad keltiradi. v o'rnatildi. Agar u holda o'yin biz uchun foydali bo'lsa, agar - dushman uchun; o'yin "adolatli" bo'lganda, ikkala ishtirokchi uchun ham bir xil foydali.

Keling, egar nuqtasi bo'lmagan o'yin misolini ko'rib chiqamiz va uning yechimini (isbotsiz) keltiramiz. O'yin quyidagicha: ikkita o'yinchi A va B bir vaqtning o'zida va hech qanday so'z aytmasdan bir, ikki yoki uchta barmoqni ko'rsatadi. Barmoqlarning umumiy soni yutuqni aniqlaydi: agar u juft bo'lsa, A yutadi va B dan shu raqamga teng miqdorni oladi; agar u g'alati bo'lsa, unda, aksincha, A B ga bu raqamga teng miqdorda to'laydi. Futbolchilar nima qilishlari kerak?

Keling, o'yin matritsasini yarataylik. Bitta o'yinda har bir o'yinchi uchta strategiyaga ega: bitta, ikki yoki uchta barmoqni ko'rsatish. 3x3 matritsa 26.5-jadvalda keltirilgan; qo'shimcha o'ng ustun qatorning minimalini, qo'shimcha pastki qator esa ustun maksimalini ko'rsatadi.

O'yinning past narxi strategiyaga mos keladi. Bu shuni anglatadiki, oqilona va ehtiyotkor xatti-harakatlar bilan biz 3 dan ortiq yo'qotmasligimizga kafolat beramiz. Kichik tasalli, lekin baribir ba'zi hujayralarda topilgan, aytaylik, 5 g'alabadan yaxshiroq. matritsadan. Bu biz uchun yomon, o'yinchi L... Ammo keling, o'zimizni taskinlaylik: dushmanning ahvoli bundan ham battarroq ko'rinadi: o'yinning narxi pastroq. oqilona xulq u bizga kamida 4 beradi.

Kirish

Haqiqiy ziddiyatli vaziyatlar har xil turdagi o'yinlarga olib keladi. O'yinlar bir necha jihatdan farqlanadi: ularda ishtirok etadigan o'yinchilar soni, mumkin bo'lgan o'yinchilar soni, mumkin bo'lgan strategiyalar soni, o'yinchilar o'rtasidagi munosabatlarning tabiati, yutuqning tabiati, o'yin turi bo'yicha. yutuq funktsiyalari, harakatlar soni bo'yicha, o'yinchilarni ma'lumot bilan ta'minlash tabiati va boshqalar .d. Keling, o'yin turlarini ularning bo'linishiga qarab ko'rib chiqaylik:

· Strategiyalar soniga ko'ra o'yinlar quyidagilarga bo'linadi final(har bir o'yinchida cheklangan miqdordagi mumkin bo'lgan strategiyalar mavjud) va cheksiz(bu erda o'yinchilardan kamida bittasida cheksiz ko'p strategiya mavjud).

· Yutuqlarning tabiatiga ko'ra, bilan o'yinlar nol summa(o'yinchilarning umumiy kapitali o'zgarmaydi, lekin natijaga qarab o'yinchilar o'rtasida qayta taqsimlanadi) va o'yinlar nolga teng bo'lmagan summa.

· Funktsiyalar turiga ko'ra, o'yindagi yutuqlar quyidagilarga bo'linadi matritsa ( ikki o'yinchining nol yig'indisi cheklangan o'yin bo'lib, unda o'yinchining to'lovi beriladi A matritsa shaklida (matritsaning bir qatori o'yinchining qo'llagan strategiyasi soniga to'g'ri keladi IN, ustun - o'yinchining foydalanilgan strategiyasining soni IN; matritsaning satri va ustunining kesishmasida o'yinchining to'lovi A, qo'llaniladigan strategiyalarga mos keladi.

Matritsali o'yinlar uchun ularning har qandayida yechim borligi isbotlangan va uni o'yinni chiziqli dasturlash muammosiga qisqartirish orqali osongina topish mumkin), bimatritsa o'yin (bu nol bo'lmagan summaga ega ikkita o'yinchining cheklangan o'yini bo'lib, unda har bir o'yinchining to'lovlari tegishli o'yinchi uchun matritsalar bilan alohida beriladi (har bir matritsada bir qator o'yinchining strategiyasiga mos keladi) A, ustun - o'yinchi strategiyalari IN, birinchi matritsadagi satr va ustunning kesishmasida o'yinchining to'lovi joylashgan A, ikkinchi matritsada - o'yinchining yutuqlari IN.

Bimatritsali o'yinlar uchun optimal o'yinchi xatti-harakati nazariyasi ham ishlab chiqilgan, ammo bunday o'yinlarni hal qilish oddiy matritsali o'yinlarga qaraganda qiyinroq. davomiy o'yinlar ( Davomiy Bu har bir o'yinchining to'lov funktsiyasi strategiyalarga qarab uzluksiz bo'lgan o'yin hisoblanadi. Ushbu sinf o'yinlarining echimlari borligi isbotlangan, ammo ularni topish uchun amalda maqbul usullar ishlab chiqilmagan) va boshqalar.

O'yinlarni ajratish uchun boshqa yondashuvlar ham mumkin. Endi to'g'ridan-to'g'ri tadqiqot mavzusiga, ya'ni O'yin nazariyasiga qaytaylik. Birinchidan, keling, ushbu kontseptsiyani aniqlaymiz.

O'yin nazariyasi - qarama-qarshilik sharoitida optimal qarorlar qabul qilishning rasmiy modellarini o'rganadigan matematikaning bo'limi. Bunda konflikt deganda turli tomonlarning ishtirok etishi, turli manfaatlar va shu manfaatlarga mos ravishda o‘zlariga mavjud bo‘lgan harakatlarni tanlash imkoniyatlari bilan ta’minlangan hodisa tushuniladi.To‘qnashuv sharoitida dushmanning o‘zining bo‘lajak harakatlarini yashirish istagi. noaniqlikka ko'tariladi. Aksincha, qaror qabul qilishda noaniqlik (masalan, etarli ma'lumotlarga asoslangan holda) qaror qabul qiluvchi sub'ekt va tabiat o'rtasidagi ziddiyat sifatida talqin qilinishi mumkin. Shu sababli, o'yin nazariyasi noaniqlik sharoitida optimal qarorlar qabul qilish nazariyasi sifatida ham ko'rib chiqiladi. Bu texnologiya, qishloq xo‘jaligi, tibbiyot va sotsiologiya va boshqa fanlar bo‘yicha qaror qabul qilishning ayrim muhim jihatlarini tizimlashtirish imkonini beradi. Konfliktda ishtirok etuvchi tomonlar harakat koalitsiyalari deb ataladi; ular uchun mavjud bo'lgan harakatlar - ularning strategiyalari bo'yicha; mojaroning mumkin bo'lgan natijalari - vaziyatlar.

Nazariyaning maqsadi:

1) o'yindagi optimal xatti-harakatlar.

2) optimal xulq-atvor xususiyatlarini o'rganish

3) uni qo'llash mazmunli bo'lgan shartlarni aniqlash (mavjudlik, o'ziga xoslik va dinamik o'yinlar uchun, nominal izchillik savollari).

4) optimal xulq-atvorni topishning raqamli usullarini qurish.

Iqtisodiy va ijtimoiy kelib chiqadigan muammolarni matematik hal qilish uchun yaratilgan o'yinlar nazariyasini, odatda, fizik va texnik muammolarni hal qilish uchun yaratilgan klassik matematik nazariyalarga qisqartirish mumkin emas. Biroq, klassik matematik usullarning keng doirasi o'yin nazariyasining turli xil o'ziga xos savollarida keng qo'llaniladi.

Bundan tashqari, o'yin nazariyasi bir qator matematik fanlar bilan ichki bog'liqdir. O'yin nazariyasida ehtimollik nazariyasi tushunchalari tizimli va mohiyatan qo'llaniladi. O'yin nazariyasi tilida matematik statistikaning ko'pgina muammolarini shakllantirish mumkin va o'yin nazariyasi qaror qabul qilish nazariyasi bilan bog'liq bo'lganligi sababli, u operatsiyalarni tadqiq qilishning matematik apparatining muhim qismi sifatida qaraladi.

O'yinning matematik tushunchasi juda keng. U salon o'yinlari deb ataladigan o'yinlarni (shu jumladan shaxmat, shashka, GO, karta o'yinlari, domino) o'z ichiga oladi, lekin ko'plab xaridorlar va sotuvchilar bir-biri bilan raqobatlashadigan iqtisodiy tizim modellarini tasvirlash uchun ham ishlatilishi mumkin. Tafsilotlarga kirmasdan, o'yinni keng ma'noda bir yoki bir nechta shaxslar ("o'yinchilar") bir qator o'zgaruvchilarni birgalikda boshqaradigan va har bir o'yinchi qaror qabul qilishda butun guruhning harakatlarini hisobga olishi kerak bo'lgan vaziyat sifatida ta'riflanishi mumkin. Har bir o'yinchiga tushadigan "to'lov" nafaqat o'z harakatlari, balki guruhning boshqa a'zolarining harakatlari bilan ham belgilanadi. O'yin davomida ba'zi "harakatlar" (individual harakatlar) tasodifiy bo'lishi mumkin. Aniq misol - mashhur poker o'yini: kartalarning dastlabki kelishuvi tasodifiy harakatdir. Fokuslarni yakuniy taqqoslashdan oldingi garovlar va qarama-qarshi garovlar ketma-ketligi o'yindagi qolgan harakatlar orqali shakllanadi.

Matematik O'YIN NAZARIYASI sport, karta va boshqa o'yinlarni tahlil qilishdan boshlandi. Aytishlaricha, o'yin nazariyasining kashfiyotchisi, 20-asrning taniqli amerikalik matematiki. Jon fon Neyman o'z nazariyasi uchun g'oyalarni poker o'yinini tomosha qilayotganda o'ylab topdi. "O'yin nazariyasi" nomi shu erdan keladi.

Keling, ushbu mavzuni o'rganishni boshlaylik o'yin nazariyasi rivojlanishining retrospektiv tahlili. Keling, o'yin nazariyasi masalasining tarixi va rivojlanishini ko'rib chiqaylik. Odatda, "oila daraxti" grafik nazariyasi ma'nosida daraxt sifatida ifodalanadi, unda shoxlanish qandaydir bir "ildiz" dan sodir bo'ladi. O'yin nazariyasining nasl-nasabi J. fon Neumann va O. Morgensternning kitobidir. Shuning uchun o'yin nazariyasining matematik fan sifatida tarixiy rivojlanishi tabiiy ravishda uch bosqichga bo'linadi:

Birinchi bosqich- J. von Neumann va O. Morgenstern tomonidan monografiya nashr etilishidan oldin. Buni "pre-monografik" deb atash mumkin. Ushbu bosqichda o'yin hali ham o'z qoidalari bilan mazmunli ma'noda tasvirlangan o'ziga xos musobaqa sifatida ishlaydi. Faqat uning oxirida J. von Neumann mavhum ziddiyatning umumiy modeli sifatida o'yin haqidagi g'oyani ishlab chiqadi. Ushbu bosqichning natijasi bir qator aniq matematik natijalar va hatto kelajakdagi o'yin nazariyasining individual tamoyillarini to'plash edi.

Ikkinchi bosqich J. von Neumann tomonidan monografiyaning o'zi va

O. Morgenstern "O'yin nazariyasi va iqtisodiy xulq-atvori" (1944), u ilgari olingan ko'pgina natijalarni birlashtirgan (ammo, zamonaviy matematik standartlarga ko'ra, juda kam). U birinchi bo'lib o'yinlarga matematik yondashuvni (so'zning aniq va mavhum ma'nosida) tizimli nazariya shaklida taqdim etdi.

Nihoyat, yoqilgan uchinchi bosqich o'yin nazariyasi o'rganilayotgan ob'ektlarga munosabati bilan matematikaning boshqa bo'limlaridan unchalik farq qilmaydi va ular uchun umumiy qonuniyatlarga ko'ra katta darajada rivojlanadi. Shu bilan birga, albatta, uning amaliy qo'llanilishining o'ziga xos xususiyatlari, ham dolzarb, ham mumkin, o'yin nazariyasi yo'nalishlarining shakllanishiga sezilarli ta'sir ko'rsatadi.

Biroq, hatto matematik o'yin nazariyasi ham ba'zi ziddiyatlarning natijasini to'liq bashorat qilishga qodir emas. O'yin (mojaro) natijasining noaniqligining uchta asosiy sababini aniqlash mumkin ko'rinadi.

Birinchidan, bu o'yin harakatining barcha yoki hech bo'lmaganda ko'p variantlarini o'rganish uchun haqiqiy imkoniyat mavjud bo'lgan o'yinlar, ulardan biri g'alaba qozonishga olib keladi. Noaniqlik juda ko'p variantlardan kelib chiqadi, shuning uchun har doim ham mutlaqo barcha variantlarni o'rganish mumkin emas (masalan, yapon o'yini GO, rus va xalqaro shashka, Britaniya reversi).

Ikkinchidan, omillarning o'yinga tasodifiy ta'siri o'yinchilar tomonidan oldindan aytib bo'lmaydi. Bu omillar o'yin natijasiga hal qiluvchi ta'sir ko'rsatadi va faqat kichik darajada o'yinchilar tomonidan nazorat qilinishi va aniqlanishi mumkin. O'yinning yakuniy natijasi faqat kichik, juda ahamiyatsiz darajada o'yinchilarning harakatlari bilan belgilanadi. Tasodifiy sabablarga ko'ra natijasi noaniq bo'lgan o'yinlar qimor o'yinlari deb ataladi. O'yin natijasi har doim ehtimollik yoki taxminiy (ruletka, zar, otish).

Uchinchidan, noaniqlik o'ynayotgan raqib qanday strategiyaga amal qilayotgani haqida ma'lumot yo'qligidan kelib chiqadi. O'yinchilarning raqibning xatti-harakatlaridan bexabarligi asosiy va o'yin qoidalari bilan belgilanadi. Bunday o'yinlar strategik o'yinlar deb ataladi.

O'yinlar nazariyasi "Operatsiyalarni tadqiq qilish" ning muhim bo'limlaridan biri bo'lib, raqobatbardosh xarakterga ega bo'lgan bozor munosabatlaridagi ziddiyatli vaziyatlarda optimal qarorlar qabul qilish uchun matematik modellarning nazariy asoslarini ifodalaydi, bunda bir raqib boshqa tomon ustidan g'alaba qozonadi. boshqasining yo'qotishlari xarajati. Ushbu vaziyat bilan bir qatorda, turli xil qarorlar qabul qilish muammolarini shakllantirishning matematik tavsifini beruvchi Operatsion tadqiqotlar fani doirasida xavf va noaniqlik holatlari ko'rib chiqiladi. Noaniqlik sharoitida shartlarning ehtimoli noma'lum va ular haqida qo'shimcha statistik ma'lumotlarni olishning imkoni yo'q. Muammoni hal qilish atrofidagi, muayyan sharoitlarda o'zini namoyon qiladigan muhit "tabiat" deb ataladi va tegishli matematik modellar "tabiat bilan o'yinlar" yoki "statistik o'yinlar nazariyasi" deb ataladi. O'yin nazariyasining asosiy maqsadi nizoda o'yinchilarning qoniqarli xatti-harakatlari bo'yicha tavsiyalar ishlab chiqish, ya'ni ularning har biri uchun "optimal strategiya" ni aniqlashdir.

Xizmat maqsadi. Onlayn xizmatdan foydalanib, siz:

aniqlash Matritsa o'yin narxi(pastki va yuqori chegaralar), egar nuqtasi mavjudligini tekshiring, aralash strategiyaga yechim toping, o'yinchilarning minimaks strategiyasini toping;
Ikki chiziqli dasturlash masalalari juftligining matematik modelini yozing, matritsali o‘yinni quyidagi usullar yordamida yeching: minimax, simpleks usuli , grafik(geometrik) usul, Braun usuli.

Ko'rsatmalar. Matritsa o'lchamini tanlang, Keyingiga bosing. Yangi dialog oynasida matritsali o'yinni echish usulini tanlang. To'ldirish misoli. Hisoblash natijalari Word formatida hisobot shaklida taqdim etiladi.

O'yin haqiqiy konfliktli vaziyatning matematik modelidir. Ikki o'yinchi o'rtasidagi ziddiyatli vaziyat juftlik o'yini deb ataladi. Nol summali juftlik o'yinini o'rganish qulay, agar u matritsa shaklida tasvirlangan bo'lsa. Bu o'yin deyiladi matritsa; a ij sonlaridan tuzilgan matritsa deyiladi to'lov. Jadvalda to'lov matritsasi A tomonidan ko'rsatilgan o'yinni hal qilish variantlari keltirilgan.

Algoritm tavsifi:

To'lov matritsasini tahlil qilish asosida unda ustunlik qiladigan strategiyalar mavjudligini aniqlash va ularni yo'q qilish kerak.
O'yinning yuqori va pastki narxlarini toping va bu o'yinning egar nuqtasi bor yoki yo'qligini aniqlang (o'yinning pastki narxi o'yinning yuqori narxiga teng bo'lishi kerak).
Agar egar nuqtasi mavjud bo'lsa, o'yinning yechimi bo'lgan o'yinchilarning optimal strategiyalari egar nuqtasiga mos keladigan sof strategiyalari bo'ladi. O'yin narxi bir-biriga teng bo'lgan o'yinning yuqori va pastki narxlariga teng.
Agar o'yinda egar nuqtasi bo'lmasa, o'yinning echimini aralash strategiyalarda izlash kerak. M × n o'yinlarda optimal aralash strategiyalarni aniqlash uchun birinchi navbatda o'yin muammosini chiziqli dasturlash muammosiga aylantirib, simpleks usulidan foydalanish kerak.

Keling, matritsali o'yinni grafik tarzda yechish algoritmini taqdim qilaylik.

Rasm - Matritsali o'yinni yechish sxemasi.

Aralash strategiyalarda matritsali o'yinlarni yechish usullari

Shunday qilib, agar egar nuqtasi bo'lmasa, o'yin aralash strategiyalar yordamida hal qilinadi va quyidagi usullar yordamida hal qilinadi:

O'yinni tenglamalar tizimi orqali yechish.
Agar nxn (n=m) kvadrat matritsa berilgan bo‘lsa, ehtimollik vektorini tenglamalar tizimini yechish orqali topish mumkin. Ushbu usul har doim ham qo'llanilmaydi va faqat ma'lum holatlarda qo'llaniladi (agar matritsa 2x2 bo'lsa, o'yinning echimi deyarli har doim olinadi). Agar yechim manfiy ehtimollar hosil qilsa, u holda bu sistema simpleks usuli yordamida yechiladi.
O'yinni grafik tarzda hal qilish.
n=2 yoki m=2 bo'lgan hollarda, matritsali o'yinni grafik tarzda hal qilish mumkin.
Simpleks usuli yordamida matritsali o‘yinni yechish.
Bunday holda, matritsa o'yini ga kamayadi

Turi