Uzluksiz strategiyalar bilan antagonistik o'yinlar. Matritsali antagonistik o'yinlarni hal qilish Antagonistik o'yinlarni onlayn hal qilish

Ikki kishilik nol summali o'yin deyiladi, unda ularning har biri cheklangan strategiyalar to'plamiga ega. Matritsa o'yinining qoidalari to'lov matritsasi bilan belgilanadi, uning elementlari birinchi o'yinchining to'lovlari 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-harakatiga bog'liq emas) to'lovni oladi, xuddi shunday, ikkinchi o'yinchi minimal kafolatlangan yo'qotishga erishadi.

ostida strategiya o'yinchining har bir shaxsiy harakati uchun mavjud vaziyatdan kelib chiqqan holda harakatlar variantini tanlashni belgilovchi qoidalar (tamoyillar) to'plami sifatida tushuniladi.

Endi hamma narsa tartibda va batafsil.

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

DA 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'yinchiga ruxsat bering m sof strategiyalar va ikkinchi o'yinchining ixtiyorida - n toza strategiyalar. O'yin ko'rib chiqilayotgani uchun bu o'yinda g'alaba va mag'lubiyat bo'lishi tabiiy.

DA to'lov matritsasi elementlar o'yinchilarning daromadlari va yo'qotishlarini ifodalovchi raqamlardir. Yutuqlar va yo'qotishlar ball, pul yoki boshqa birliklarda ifodalanishi mumkin.

Keling, to'lov matritsasi yarataylik:

Agar birinchi o'yinchi tanlasa i-th sof strategiya, va ikkinchi o'yinchi j-th sof strategiya, keyin birinchi o'yinchi to'lov hisoblanadi 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 aylantirilsa, birinchi o'yinchi bitta birlik yutadi, boshqa hollarda esa u bitta birlikni yo'qotadi (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 daromadni kafolatlaydigan strategiyasini, shuningdek, unga maksimal o'rtacha yo'qotishni kafolatlaydigan ikkinchi o'yinchining strategiyasini tanlashni aniqlashdir.

Matritsali o'yinda strategiya qanday tanlanadi?

Keling, to'lov matritsasiga yana qaraylik:

Birinchidan, agar u foydalansa, birinchi o'yinchining to'lovini aniqlaymiz i sof strategiya. Agar birinchi o'yinchi foydalansa i- 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 foydasi minimal bo'ladi. O'z navbatida, birinchi o'yinchi unga maksimal foyda keltiradigan shunday sof strategiyadan foydalanadi. Ushbu shartlarga asoslanib, biz belgilagan birinchi o'yinchining to'lovi v1 , deyiladi maksimal g'alaba yoki past o'yin 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 to'lovi minimaldan maksimal bo'ladi. Shuning uchun nom - maximin win. Ushbu elementning qator raqami birinchi o'yinchi tomonidan tanlangan sof strategiyaning raqami bo'ladi.

Endi ikkinchi o'yinchining yo'qotishini aniqlaymiz, agar u foydalansa j- strategiya. Bunday holda, birinchi o'yinchi o'zining sof strategiyasidan foydalanadi, bunda ikkinchi o'yinchining yo'qolishi maksimal bo'ladi. Ikkinchi o'yinchi shunday sof strategiyani tanlashi kerak, unda uning yo'qotilishi minimal bo'ladi. Ikkinchi o'yinchining yo'qolishi, biz buni deb belgilaymiz v2 , deyiladi minimal yo'qotish yoki yuqori o'yin 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 - minimal daromad. Ushbu elementning ustun raqami ikkinchi o'yinchi tomonidan tanlangan sof strategiyaning raqami bo'ladi. Agar ikkinchi o'yinchi "minimaks" dan foydalansa, birinchi o'yinchi qanday strategiya tanlashidan qat'i nazar, u ko'pi bilan yutqazadi. 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 qanday topishni o'rganganimizdan so'ng, ushbu tushunchalarni rasmiy ravishda qanday belgilashni o'rganish vaqti keldi.

Shunday qilib, birinchi o'yinchining kafolatlangan to'lovi:

Birinchi o'yinchi unga minimal to'lovlarning maksimal miqdorini 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 aniqlanadi:

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

.

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 qatorlaridagi eng kichik elementlarni yozamiz va ularning maksimalini, matritsaning pastki qismidan esa - ustunlardagi eng katta elementlarni belgilaymiz va ulardan minimalini tanlaymiz:

Qatorlarning eng kichik elementlaridan eng kattasi 3 ta, bu o'yinning past narxi, ikkinchi qator unga mos keladi, shuning uchun birinchi o'yinchining maksimal strategiyasi ikkinchi. 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 narxi 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, o'yinning teng past va yuqori narxlariga bir xil strategiyalar juftligida erishiladi.

Ushbu holatda matritsali o'yin sof strategiyalarda yechimga ega .

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

.

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

O'yinning past narxi o'yinning yuqori narxi bilan bir xil. 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 minimal strategiyasi esa uchinchi sof strategiyadir. Ushbu matritsali o'yinda sof strategiyalarda yechim bor.

Matritsa o'yini muammosini o'zingiz hal qiling va keyin yechimni ko'ring

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, matritsa o'yinida egar nuqtasi yo'q, shuning uchun mos keladigan matritsa o'yinida sof strategiya echimlari yo'q.

Lekin u optimal aralash strategiyalarda yechimga ega. Ularni topish uchun o'yin etarlicha marta takrorlangan deb taxmin qilish kerak, tajribaga asoslanib, qaysi strategiya afzalroq ekanligini taxmin qilish mumkin. Shuning uchun qaror ehtimollik va o'rtacha (kutish) tushunchalari 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 daromad olishi 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 birinchi o'yinchining aralash strategiyasi deyiladi. Boshqacha qilib aytganda, bu sof strategiyalarning "aralashmasi". Ushbu ehtimolliklarning yig'indisi bittaga teng:

.

Agar ikkinchi o'yinchi ehtimollik bilan sof strategiyalardan foydalansa , keyin vektor ikkinchi o'yinchining aralash strategiyasi deb ataladi. Ushbu ehtimolliklarning 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'yinchi g'alaba qozonadi (ikkinchi o'yinchi yutqazadi). 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

.

Birinchi o'yinchining yutug'ining (ikkinchi o'yinchining yo'qotilishi) matematik taxminini aniqlang, agar birinchi o'yinchining aralash strategiyasi , ikkinchi o'yinchining aralash strategiyasi bo'lsa.

Yechim. Birinchi o'yinchining daromadini (ikkinchi o'yinchini yo'qotish) matematik kutish formulasiga ko'ra, u birinchi o'yinchining aralash strategiya vektori, to'lov matritsasi va ikkinchi o'yinchining aralash strategiya vektorining 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 holatlarida maksimal va minimaks belgilariga o'xshab, optimal aralash strategiyalar quyidagicha belgilanadi (va matematik kutish, ya'ni birinchi o'yinchining daromadi va ikkinchi o'yinchining yo'qotishining o'rtacha qiymati bilan bog'liq):

,

.

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

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

Matritsali o'yinni chiziqli dasturlash muammosiga qisqartirish

Aralash strategiyalarda matritsali o'yinni hal qilish uchun siz to'g'ri chiziq yaratishingiz kerak chiziqli dasturlash muammosi va uning ikki tomonlama vazifasi. Dual masalada cheklashlar tizimidagi o'zgaruvchilar koeffitsientlarini, doimiy hadlarni va maqsad funksiyadagi o'zgaruvchilar koeffitsientlarini saqlaydigan kengaytirilgan matritsa transpozitsiya qilinadi. Bunda asl masalaning maqsad funksiyasining minimali dual masaladagi maksimal bilan bog’lanadi.

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

.

Chiziqli dasturlashning bevosita muammosidagi cheklovlar tizimi:

Ikkilamchi muammoda maqsad funksiyasi:

.

Dual masalada cheklovlar tizimi:

To'g'ridan-to'g'ri chiziqli dasturlash masalasining optimal rejasini belgilang

,

dual masalaning optimal rejasi esa bilan belgilanadi

Tegishli optimal dizaynlar uchun chiziqli shakllar va bilan belgilanadi,

va ularni optimal rejalarning tegishli koordinatalari yig'indisi sifatida topishingiz kerak.

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

.

Matematiklar buni isbotladilar o'yin narxi optimal rejalarning chiziqli shakllarida quyidagicha 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 ham vektorlardir, chunki biz avvalgi xatboshida aniqlagan edik. Shuning uchun raqamni (o'yin narxini) vektorga (optimal rejalar koordinatalari bilan) ko'paytirsak, 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 masalasini tuzamiz:

Biz to'g'ridan-to'g'ri muammoning echimini olamiz:

.

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

Yaxshi ishingizni bilimlar bazasiga yuborish oddiy. Quyidagi shakldan foydalaning

Talabalar, aspirantlar, bilimlar bazasidan o‘z o‘qishlarida va ishlarida foydalanayotgan yosh olimlar sizdan juda minnatdor bo‘lishadi.

Kirish

1. Nazariy qism

1.3 O'yin tartibi 2v2

1.4 Algebraik usul

1.5 Grafik usul

1.6 O'yinlar 2xn yoki mx2

1.7 O'yinlarni matritsa usulida yechish

2. Amaliy qism

2.2 2xn va mx2 o'yinlar

2.3 Matritsa usuli

2.4 Jigarrang usul

Natijalarni tahlil qilish

Kirish

Antagonistik o'yin nol summali o'yindir. Antagonistik o'yin - bu kooperativ bo'lmagan o'yin bo'lib, unda ikki o'yinchi ishtirok etadi, ularning daromadlari qarama-qarshidir.

Rasmiy ravishda, antagonistik o'yin uchlik bilan ifodalanishi mumkin , bu erda X va Y mos ravishda birinchi va ikkinchi o'yinchilarning strategiyalari to'plamidir, F - har bir juft strategiyani (x, y) bog'laydigan birinchi o'yinchining to'lov funktsiyasi, bu erda foydali dasturga mos keladigan haqiqiy son. bu vaziyatni anglagan birinchi o'yinchi.

O'yinchilarning manfaatlari qarama-qarshi bo'lganligi sababli, F funktsiyasi bir vaqtning o'zida ikkinchi o'yinchining yo'qolishini anglatadi.

Tarixiy jihatdan, antagonistik o'yinlar o'yin nazariyasining matematik modellarining birinchi sinfi bo'lib, ular tasvirlash uchun ishlatilgan. qimor. Ushbu tadqiqot mavzusi tufayli o'yin nazariyasi o'z nomini oldi deb ishoniladi. Hozirgi vaqtda antagonistik o'yinlar kooperativ bo'lmagan o'yinlarning kengroq sinfining bir qismi sifatida qaraladi.

1. Nazariy qism

1.1 O'yinning asosiy ta'riflari va qoidalari

O'yin o'yin ishtirokchilari sonini, ularning sonini belgilaydigan qoidalar tizimi bilan tavsiflanadi mumkin bo'lgan harakatlar va yutuqlarni ularning xatti-harakati va natijalariga qarab taqsimlash. O'yinchi o'yinning bir ishtirokchisi yoki ular uchun boshqa guruhlarning manfaatlariga to'g'ri kelmaydigan umumiy manfaatlarga ega bo'lgan ishtirokchilar guruhi hisoblanadi. Shuning uchun har bir ishtirokchi o'yinchi hisoblanmaydi.

O'yin qoidalari yoki shartlari o'yin rivojlanishining istalgan bosqichida o'yinchilarning mumkin bo'lgan xatti-harakatlari, tanlovlari va harakatlarini belgilaydi. O'yinchi uchun tanlov qilish uning xulq-atvor imkoniyatlaridan birida to'xtashni anglatadi. Keyin o'yinchi bu tanlovni harakatlar bilan amalga oshiradi. Harakat qilish o'yinning ma'lum bir bosqichida o'yin qoidalarida ko'zda tutilgan imkoniyatlarga qarab bir vaqtning o'zida to'liq yoki bir qismini tanlashni anglatadi. Har bir o'yinchi o'yinning ma'lum bir bosqichida qilgan tanloviga ko'ra harakat qiladi. Boshqa o'yinchi birinchi o'yinchining tanlovini bilib yoki bilmagan holda ham harakat qiladi. O'yinchilarning har biri, agar o'yin qoidalarida bunday imkoniyatga ruxsat berilsa, o'yinning o'tmishdagi rivojlanishi haqidagi ma'lumotlarni hisobga olishga harakat qiladi.

O'yin natijasida yuzaga kelgan vaziyatga qarab, o'yinchiga har bir harakatda qanday tanlov qilish kerakligini aniq aytib beradigan qoidalar to'plami o'yinchi strategiyasi deb ataladi. O'yin nazariyasidagi strategiya o'yinchi uchun o'yin rivojlanishining barcha mumkin bo'lgan holatlarida qanday harakat qilish kerakligini ko'rsatadigan ma'lum bir to'liq harakat rejasini anglatadi. Strategiya - bu o'yin rivojlanishining istalgan bosqichida o'yinchi uchun mavjud bo'lgan har qanday ma'lumot holati uchun barcha ko'rsatkichlar yig'indisi. Bu allaqachon strategiyalar yaxshi va yomon, muvaffaqiyatli va muvaffaqiyatsiz bo'lishi mumkinligini ko'rsatadi.

Agar uning har bir o'yinida barcha o'yinchilarning to'lovlari yig'indisi nolga teng bo'lsa, nol summali o'yin bo'ladi, ya'ni nol summali o'yinda barcha o'yinchilarning umumiy kapitali o'zgarmaydi, lekin o'yinchilar o'rtasida qayta taqsimlanadi. olingan natijalarga qarab. Shunday qilib, ko'plab iqtisodiy va harbiy vaziyatlarni nol summali o'yinlar sifatida ko'rish mumkin.

Xususan, ikkita o'yinchining nol summali o'yini antagonistik deb ataladi, chunki undagi o'yinchilarning maqsadlari to'g'ridan-to'g'ri qarama-qarshidir: bir o'yinchining daromadi faqat ikkinchisining yo'qotishi hisobiga sodir bo'ladi.

1.1.1 Sof strategiyalarda matritsali o'yinlarning ta'rifi, misollari va echimlari

Ikki o'yinchi nol yig'indili matritsa o'yinini quyidagi mavhum ikki o'yinchi o'yini sifatida ko'rish mumkin.

Birinchi o'yinchi m strategiyaga ega: i =1, 2,…, m, ikkinchisida n ta strategiya mavjud j = 1, 2,…, n Har bir juft strategiyaga (i, j) a ij raqami beriladi, bu raqam Agar birinchi o'yinchi uni ishlatsa, ikkinchi o'yinchi uchun birinchi o'yinchining to'lovi i-strategiya, ikkinchisi esa - uning j-chi strategiyasi.

O'yinchilarning har biri bitta harakatni amalga oshiradi: birinchi o'yinchi o'zining i-strategiyasini tanlaydi (i = 1, 2, ..., m), ikkinchisi --sizning j-th strategiya (j = 1, 2,…, n), shundan so'ng birinchi o'yinchi ikkinchi o'yinchi hisobidan ij to'lovini oladi (agar a ij bo'lsa).< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

O'yinchining har bir strategiyasi i = 1, 2,…, t; j = 1, 2,…, n odatda sof strategiya deb ataladi.

Ikki o'yinchining nol yig'indili matritsali o'yini oddiygina matritsali o'yin deb ataladi. Shubhasiz, matritsa o'yini antagonistik o'yinlarga tegishli. Uning ta'rifidan kelib chiqadiki, matritsali o'yinni aniqlash uchun birinchi o'yinchining to'lovlarining m tartibidagi A = (a ij) matritsasini ko'rsatish kifoya.

To'lov matritsasini hisobga olgan holda

keyin A matritsasi bilan matritsa o'yinining har bir o'yinining bajarilishi birinchi o'yinchining tanloviga qisqartiriladi. i-chi qator, va j-ustundagi ikkinchi o'yinchi va birinchi o'yinchi (ikkinchi o'yinchi hisobiga) i-qator va j-ustunning kesishmasida A matritsasida joylashgan to'lovni oladi.

Haqiqiy ziddiyatli vaziyatni matritsali o'yin shaklida rasmiylashtirish uchun har bir o'yinchining sof strategiyalarini aniqlash va qayta raqamlash va to'lov matritsasini tuzish kerak.

Keyingi qadam o'yinchilarning optimal strategiyalari va to'lovlarini aniqlashdir.

O'yinlarni o'rganishda asosiy narsa o'yinchilar uchun optimal strategiyalar kontseptsiyasidir. Ushbu kontseptsiya intuitiv ravishda quyidagi ma'noga ega: agar o'yinchining strategiyasi, agar ushbu strategiyani qo'llash unga boshqa o'yinchining barcha mumkin bo'lgan strategiyalari uchun eng katta kafolatlangan to'lovni ta'minlasa, optimal hisoblanadi. Ushbu pozitsiyalarga asoslanib, birinchi o'yinchi (1.1) formula bo'yicha o'z to'lovlarining A matritsasini quyidagicha tekshiradi: har bir qiymat uchun i (i = 1, 2, ..., m) ga qarab minimal to'lov qiymati aniqlanadi. ikkinchi o'yinchi tomonidan qo'llaniladigan strategiyalar bo'yicha

(i = 1, 2,..., m) (1.2)

ya'ni birinchi o'yinchi uchun minimal to'lov aniqlanadi, agar u o'zining i - sof strategiyasini qo'llasa, keyin bu minimal to'lovlardan shunday strategiya topiladiki i=i 0 bu minimal foyda maksimal bo'ladi, ya'ni topiladi.

Ta'rif. Formula (1.3) bo'yicha aniqlangan b raqami o'yinning eng kam sof qiymati deb ataladi va birinchi o'yinchi ikkinchi o'yinchining barcha mumkin bo'lgan harakatlari uchun o'zining sof strategiyalarini qo'llash orqali o'ziga qanday minimal daromad keltirishi mumkinligini ko'rsatadi.

Ikkinchi o'yinchi o'zining optimal xulq-atvori bilan, agar iloji bo'lsa, birinchi o'yinchining foydasini uning strategiyalari hisobiga kamaytirishga harakat qilishi kerak. Shuning uchun, ikkinchi o'yinchi uchun biz topamiz

ya'ni, ikkinchi o'yinchi o'zini qo'llash sharti bilan birinchi o'yinchining maksimal to'lovi aniqlanadi j-chi toza strategiya, keyin ikkinchi o'yinchi o'zining j = j 1 strategiyasini topadi, buning uchun birinchi o'yinchi minimal to'lovni oladi, ya'ni topadi.

Ta'rif. Formula (1.5) bo'yicha aniqlangan b soni o'yinning sof yuqori narxi deb ataladi va birinchi o'yinchi o'z strategiyalari tufayli o'ziga qanday maksimal daromadni kafolatlashi mumkinligini ko'rsatadi. Boshqacha qilib aytadigan bo'lsak, o'zining sof strategiyalarini qo'llash orqali birinchi o'yinchi kamida b daromad olishi mumkin, ikkinchi o'yinchi esa o'zining sof strategiyalarini qo'llash orqali birinchi o'yinchining c dan ko'proq yutishini oldini oladi.

Ta'rif. Agar A matritsasi bo'lgan o'yinda o'yinning pastki va yuqori sof narxlari mos tushsa, ya'ni b = c, bu o'yin sof strategiyalarda egar nuqtasi va sof o'yin narxiga ega deb aytiladi:

n = b = c (1,6)

Egar nuqtasi mos ravishda birinchi va ikkinchi o'yinchilarning bir juft sof strategiyasi () bo'lib, ular ostida tenglikka erishiladi.

Egar nuqtasi tushunchasi quyidagi ma'noga ega: agar o'yinchilardan biri egar nuqtasiga mos keladigan strategiyaga rioya qilsa, ikkinchi o'yinchi egar nuqtasiga mos keladigan strategiyaga rioya qilishdan yaxshiroq ish qila olmaydi. O'yinchining eng yaxshi xulq-atvori uning daromadining kamayishiga olib kelmasligi va eng yomon xatti-harakati uning daromadining pasayishiga olib kelishi mumkinligini hisobga olib, ushbu shartlarni matematik tarzda quyidagi munosabatlar shaklida yozish mumkin:

bu erda i, j mos ravishda birinchi va ikkinchi o'yinchilarning har qanday sof strategiyalari; (i 0 , j 0) -- egar nuqtasini tashkil etuvchi strategiyalar. Quyida biz egar nuqtasining ta'rifi shartlarga (1.8) ekvivalent ekanligini ko'rsatamiz.

Shunday qilib, (1.8) ga asoslanib, egar elementi A matritsadagi i 0 - qatorda minimal va j 0 - ustunida maksimal bo'ladi. A matritsaning egar nuqtasini topish oson: matritsada. A, har bir satrda ketma-ket minimal elementni toping va bu element uning ustunida maksimal ekanligini tekshiring. Agar shunday bo'lsa, u egar elementidir va unga mos keladigan strategiyalar juftligi egar nuqtasini tashkil qiladi. Egar nuqtasi va egar elementini tashkil etuvchi birinchi va ikkinchi o'yinchilarning bir juft sof strategiyasi (i 0, j 0) o'yinning yechimi deb ataladi.

Egar nuqtasini tashkil etuvchi i 0 va j 0 sof strategiyalar mos ravishda birinchi va ikkinchi o'yinchilarning optimal sof strategiyalari deb ataladi.

Teorema 1. f (x, y) ikkita x A va y B o‘zgaruvchilarning real funksiyasi bo‘lsin va mavjud bo‘lsin.

keyin b = c.

Isbot. Minimal va maksimal ta'rifdan kelib chiqadiki

(1.11) ning chap tomonida x ixtiyoriy bo'lgani uchun, u holda

Tengsizlikning (1.12) o'ng tomonida y ixtiyoriy, shuning uchun

Q.E.D.

Xususan, () matritsa f (x, y) funksiyaning maxsus holatidir, ya'ni x = i, y = j, = f (x, y) ni qo'ysak, u holda 1-teoremadan biz eng past ekanligini olamiz. sof narx matritsali o'yindagi o'yinning yuqori sof qiymatidan oshmaydi.

Ta'rif. f (x, y) ikkita x A va y B o‘zgaruvchilarning haqiqiy funksiyasi bo‘lsin. Agar quyidagi tengsizliklar bajarilsa, nuqta (x 0, y 0) f (x, y) funksiya uchun egar nuqtasi deyiladi:

f (x, y 0) f (x 0, y 0) f (x 0, y) (1.14)

har qanday x A va y B uchun.

1.2 Optimal aralash strategiyalar va ularning xususiyatlari

Matritsali o'yinni o'rganish sof strategiyalarda uning egar nuqtasini topishdan boshlanadi. Agar matritsali o'yin sof strategiyalarda egar nuqtasiga ega bo'lsa, bu nuqtani topish o'yinni o'rganishni tugatadi. Agar matritsali o'yinda sof strategiyalarda egar nuqtasi bo'lmasa, biz ushbu o'yinning pastki va yuqori sof narxlarini topishimiz mumkin, bu birinchi o'yinchi o'yinning yuqori narxidan kattaroq daromadga umid qilmasligi kerakligini ko'rsatadi va o'yinning past narxidan kam bo'lmagan to'lovni olishiga ishonch hosil qilishi mumkin. Sof strategiyalarda egar nuqtasi bo'lmagan matritsali o'yinda o'yinchilarning xatti-harakatlariga oid bunday tavsiyalar tadqiqotchilar va amaliyotchilarni qoniqtirmaydi. Matritsali o'yinlarni hal qilishda takomillashtirishni sof strategiyalarni qo'llash sirini va partiyalar shaklida o'yinlarni takroriy takrorlash imkoniyatidan foydalanishda izlash kerak. Masalan, bir qator shaxmat, shashka, futbol o'yinlari o'ynaladi va har safar o'yinchilar o'z strategiyalarini shunday qo'llaydilarki, raqiblari ularning mazmunidan bexabar bo'lib, yo'lda o'rtacha hisobda ma'lum daromadlarga erishadilar. o'yinlarning butun seriyasini o'ynash. Bu to'lovlar, o'rtacha, o'yinning past narxidan kattaroq va o'yinning yuqori narxidan kamroq. Bu o'rtacha qiymat qanchalik katta bo'lsa yaxshiroq strategiya o'yinchi tomonidan qo'llaniladi. Shu sababli, sof strategiyalarni tasodifiy, ma'lum bir ehtimollik bilan qo'llash g'oyasi paydo bo'ldi. Bu ulardan foydalanish sirini to'liq ta'minlaydi. Har bir o'yinchi o'zining o'rtacha daromadini maksimal darajada oshirish va yo'lda optimal strategiyalarni olish uchun o'zining sof strategiyalarini qo'llash ehtimolini o'zgartirishi mumkin. Bu g'oya aralash strategiya kontseptsiyasiga olib keldi.

Ta'rif. O'yinchining aralash strategiyasi uning sof strategiyalarini qo'llash ehtimolining to'liq to'plamidir.

Shunday qilib, agar birinchi o'yinchi 1, 2, … i, … m sof strategiyalarga ega bo'lsa, uning x aralash strategiyasi x = (x 1 , x 2 , ..., x i ,…, x t ) qanoatlantiruvchi raqamlar to'plamidir. munosabatlar

x i 0 (i = 1, 2, ... , m), = 1. (1.15)

Xuddi shunday, n ta sof strategiyaga ega bo‘lgan ikkinchi o‘yinchi uchun aralash strategiya y munosabatlarni qanoatlantiradigan y = (y 1 ,…, y j, … y n) raqamlar to‘plamidir.

y j 0 (j = 1, 2, ... , n), = 1. (1.16)

O'yinchi har safar bitta sof strategiyadan foydalangani boshqasidan foydalanishga to'sqinlik qilganligi sababli, sof strategiyalar mos kelmaydigan hodisalardir. Bundan tashqari, ular yagona mumkin bo'lgan hodisalardir.

Shubhasiz, sof strategiya aralash strategiyaning alohida holatidir. Haqiqatan ham, agar aralash strategiyada bo'lsa i-to'r strategiya bitta ehtimol bilan qo'llaniladi, keyin boshqa barcha sof strategiyalar qo'llanilmaydi. Va bu i-sof strategiya aralash strategiyaning alohida holatidir. Maxfiylikni saqlash uchun har bir o'yinchi boshqa o'yinchining tanlovidan qat'i nazar, o'z strategiyasini qo'llaydi.

Ta'rif. Matritsa A bilan birinchi o'yinchining o'rtacha to'lovi uning to'lovlarining matematik kutilishi sifatida ifodalanadi.

E (A, x, y) = (1,20)

Shubhasiz, birinchi o'yinchining o'rtacha daromadi x va y o'zgaruvchilarning ikkita to'plamining funktsiyasidir. Birinchi o'yinchi o'zining aralash strategiyasini x o'zgartirish orqali o'zining o'rtacha daromadini E (A, x, y) maksimal darajaga ko'tarishni maqsad qiladi, ikkinchi o'yinchi esa aralash strategiyalari orqali E (A, x, y) ni minimal qilishga intiladi, ya'ni. o'yinni hal qilish uchun o'yinning yuqori narxiga erishilgan x, y ni topish kerak.

1.3 Buyurtma 22 o'yin

22-tartibdagi matritsali o'yin birinchi o'yinchi uchun quyidagi to'lov matritsasi bilan beriladi:

Ushbu o'yinning yechimi sof strategiyalarda egar nuqtasini topishdan boshlanishi kerak. Buning uchun birinchi qatordagi minimal elementni toping va uning ustunida maksimal ekanligini tekshiring. Agar bunday element topilmasa, ikkinchi qator xuddi shu tarzda tekshiriladi. Agar bunday element ikkinchi qatorda topilsa, u holda egar elementidir.

Egar elementini topish bilan, agar mavjud bo'lsa, uning yechimini topish jarayoni tugaydi, chunki bu holda o'yinning narxi topiladi - egar elementi va egar nuqtasi, ya'ni birinchi va ikkinchi uchun sof strategiyalar juftligi. optimal sof strategiyalarni tashkil etuvchi o'yinchilar. Agar sof strategiyalarda egar nuqtasi bo'lmasa, aralash strategiyalarda matritsali o'yinlarning asosiy teoremasi bo'yicha majburiy ravishda mavjud bo'lgan egar nuqtasini topish kerak.

Birinchi va ikkinchi o'yinchilarning mos ravishda x=(x 1 ,x 2), y=(y 1 ,y 2) aralash strategiyalarini belgilang. Eslatib o'tamiz, x 1 birinchi o'yinchining birinchi strategiyasidan foydalanish ehtimolini anglatadi va x 2 \u003d 1 - x 1 - uning ikkinchi strategiyasidan foydalanish ehtimoli. Xuddi shunday ikkinchi o'yinchi uchun: 1 - birinchi strategiyadan foydalanish ehtimoli, y 2 = 1 - 1 - ikkinchi strategiyadan foydalanish ehtimoli.

Teoremaning xulosasiga ko'ra, x va y aralash strategiyalarining optimalligi uchun nomanfiy x 1 , x 2 , y 1 , y 2 uchun quyidagi munosabatlar o'rinli bo'lishi zarur va etarli:

Endi biz shuni ko'rsatamizki, agar matritsa o'yinining sof strategiyalarda egar nuqtasi bo'lmasa, unda bu tengsizliklar tenglikka aylanishi kerak:

Haqiqatdan ham. O'yinda sof strategiyalarda hech qanday nuqta bo'lmasin, keyin aralash strategiyalarning optimal qiymatlari tengsizliklarni qondiradi.

0<<1, 0<< 1,

0< <1, 01. (1.25)

Faraz qilaylik (1.22) dan ikkala tengsizlik ham qat'iy

u holda teoremaga ko'ra y 1 = y 2 = 0 bo'lib, bu (1.25) shartlarga ziddir.

Xuddi shunday isbotlash mumkinki, (1.23) dagi ikkala tengsizlik ham qat'iy tengsizlik bo'la olmaydi.

Aytaylik, tengsizliklardan biri (1.22) qat'iy bo'lishi mumkin, masalan, birinchi

Demak, teoremaga ko'ra y 1 = 0, y 2 =1. Shuning uchun (1.23) dan biz olamiz

Agar ikkala tengsizlik (1.24) qatʼiy boʻlsa, teorema boʻyicha x1 = x2 = 0, bu (1.25) ga ziddir. Ammo a 12 a 22 bo'lsa, (1.27) tengsizliklardan biri qat'iy, ikkinchisi esa tenglikdir. Bundan tashqari, tenglik 12 va 22 dan kattaroq element uchun amal qiladi, ya'ni (1.27) dan bitta tengsizlik qat'iy bo'lishi kerak. Masalan, 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Shunday qilib, agar matritsali o'yinning sof strategiyalarda egar nuqtasi bo'lmasa, u holda tengsizliklar (1.22) birinchi o'yinchining optimal strategiyalari uchun tenglikka aylanadi. Tengsizliklar haqidagi shunga o'xshash dalillar (1.23) bu holda tengsizliklar (1.23) tenglik bo'lishi kerakligiga olib keladi.

Shunday qilib, agar 22-tartibdagi matritsali o'yinda egar nuqtasi bo'lmasa, o'yinchilarning optimal aralash strategiyalari va o'yin narxini tenglamalar tizimini echish orqali aniqlash mumkin (1.24). Shuningdek, agar 2x2 matritsali o'yinda o'yinchilardan biri optimal sof strategiyaga ega bo'lsa, boshqa o'yinchi ham optimal sof strategiyaga ega ekanligi aniqlandi.

Shuning uchun, agar matritsali o'yinda sof strategiyalarda egar nuqtasi bo'lmasa, u holda (1.24) tenglamalardan aniqlangan aralash strategiyalarda yechimga ega bo'lishi kerak. Tizim yechimi (1.25)

1.4 Algebraik usul

Masalalarni algebraik usulda yechishning ikkita holati mavjud:

1. matritsaning egar nuqtasi bor;

2. matritsaning egar nuqtasi yo‘q.

Birinchi holda, yechim o'yinning egar nuqtasini tashkil etuvchi strategiyalar juftligidir. Keling, ikkinchi ishni ko'rib chiqaylik. Bu erda yechimlarni aralash strategiyalarda izlash kerak:

Strategiyalarni toping va Birinchi o'yinchi o'zining optimal strategiyasidan foydalanganda, ikkinchi o'yinchi, masalan, ikkita sof strategiyani qo'llashi mumkin.

Shu bilan birga, mulkka ko'ra, agar o'yinchilardan biri optimal aralash strategiyadan foydalansa, ikkinchisi esa - nolga teng bo'lmagan ehtimollik bilan uning optimal aralash strategiyasiga kiritilgan har qanday sof bo'lsa, unda har doim to'lovni matematik kutish mumkin. o'zgarishsiz qoladi va o'yin narxiga teng, ya'ni.

Ushbu holatlarning har birida to'lov V o'yinining qiymatiga teng bo'lishi kerak. Bu holda quyidagi munosabatlar amal qiladi:

Ikkinchi o'yinchining optimal strategiyasi uchun (2.5), (2.6) ga o'xshash tenglamalar tizimi ham tuzilishi mumkin:

Normalizatsiya shartini hisobga olgan holda:

(1.37) - (1.41) tenglamani nomaʼlumlarga nisbatan birgalikda yechamiz va hammasi birdan emas, bir vaqtning oʻzida uchta: alohida (1.36), (1.38), (1.40) va (1.37), (1.39). , (1.41). Yechim natijasida biz quyidagilarni olamiz:

1.5 Grafik usul

22-o'yinning taxminiy yechimini grafik usul yordamida juda oson olish mumkin. Uning mohiyati quyidagicha:

1.1-rasm - uzunlik birligi kesimini topish

Abscissa o'qida birlik uzunlikdagi qismni tanlang. Uning chap tomonida birinchi o'yinchining birinchi strategiyasi, ikkinchisining o'ng uchi tasvirlangan. Barcha oraliq nuqtalar birinchi o'yinchining aralash strategiyalariga to'g'ri keladi va nuqtaning o'ng tomonidagi segmentning uzunligi birinchi strategiyadan foydalanish ehtimoliga teng, chapdagi segmentning uzunligi esa foydalanish ehtimoliga teng. birinchi o'yinchi tomonidan ikkinchi strategiya.

I-I va II-II ikkita eksa amalga oshiriladi. I-I-da, birinchi o'yinchi birinchi strategiyani qo'llaganida, to'lovni keyinga qoldiramiz, II-IIda esa ikkinchi strategiyani qo'llaganida. Masalan, ikkinchi o'yinchi o'zining birinchi strategiyasini qo'llasin, keyin qiymat I-I o'qda, qiymat esa II-II o'qda chizilishi kerak.

Birinchi o'yinchining har qanday aralash strategiyasi uchun uning to'lovi segment hajmiga qarab belgilanadi. I-I qatori ikkinchi o'yinchi tomonidan birinchi strategiyani qo'llashiga mos keladi, biz uni ikkinchi o'yinchining birinchi strategiyasi deb ataymiz. Ikkinchi o'yinchining ikkinchi strategiyasi ham xuddi shunday tuzilishi mumkin. Keyin, umuman olganda, o'yin matritsasining grafik ko'rinishi quyidagi shaklni oladi:

1.2-rasm - o'yin narxini topish

Ammo shuni ta'kidlash kerakki, bu qurilish birinchi o'yinchi uchun amalga oshirilgan. Bu erda segmentning uzunligi V o'yinining qiymatiga teng.

1N2 chizig'i pastki to'lov chizig'i deb ataladi. Bu erda N nuqtasi birinchi o'yinchining kafolatlangan to'lovining maksimal qiymatiga mos kelishi aniq ko'rinib turibdi.

Umuman olganda, ikkinchi o'yinchining strategiyasini ham ushbu raqamdan aniqlash mumkin, masalan, shunday yo'llar bilan. I-I o'qi bo'yicha:

yoki II-II o'qda

Biroq, ikkinchi o'yinchining strategiyasi ham birinchi o'yinchi uchun qilinganidek aniqlanishi mumkin, ya'ni. shunday diagramma tuzing.

1.3-rasm - ikkinchi o'yinchi strategiyasining ta'rifi

Bu erda 1N2 chizig'i yo'qotishning yuqori chegarasi. N nuqtasi ikkinchi o'yinchining minimal yo'qotishiga to'g'ri keladi va u strategiyani belgilaydi.

Koeffitsientlarning o'ziga xos qiymatlariga qarab, grafik matritsalar boshqa shaklga ega bo'lishi mumkin, masalan, quyidagicha:

1.4-rasm - birinchi o'yinchining optimal strategiyasini belgilaydi

Bunday vaziyatda birinchi o'yinchining optimal strategiyasi sof:

1.6 O'yinlar 2n yoki m2

2n tartibli o'yinlarda birinchi o'yinchi 2 ta sof strategiyaga ega, ikkinchi o'yinchi esa n ta sof strategiyaga ega, ya'ni. Birinchi o'yinchi uchun to'lov matritsasi:

Agar bunday o'yinda egar nuqtasi bo'lsa, uni topish va yechim topish oson.

O'yinda egar nuqtalari bor deylik. Keyin munosabatlarni qondiradigan bunday aralash strategiyalarni va mos ravishda birinchi va ikkinchi o'yinchilarni va v o'yinining narxini topish kerak:

O'yinning egar nuqtasi yo'qligi sababli, tengsizlik (1,54) tengsizliklar bilan almashtiriladi.

(1.56), (1.55), (1.53) tizimlarini yechish uchun grafik usuldan foydalanish maqsadga muvofiqdir. Buning uchun biz tengsizlikning chap tomoni uchun belgini kiritamiz (1.53)

Matritsali o'yin matematik modeli

yoki (1.55) dan o'rnatib, oddiy o'zgartirishlarni amalga oshirib, biz olamiz

Birinchi o'yinchining o'rtacha daromadi qaerda, agar u aralash strategiyasidan foydalansa, ikkinchisi esa - uning j-chi sof strategiyasi.

Ifodaga ko'ra, j=1, 2, …, n har bir qiymat to'rtburchaklar koordinatalar sistemasidagi to'g'ri chiziqqa mos keladi.

Ikkinchi o'yinchining maqsadi birinchi o'yinchining strategiyasini tanlash orqali uning daromadini minimallashtirishdir. Shuning uchun biz hisoblaymiz

cheklash to'plamining pastki chegarasi qayerda. 1.6-rasmda funksiya grafigi qalin chiziq bilan ko'rsatilgan.

http://www.allbest.ru/ saytida joylashgan

1.6-rasm - funksiya grafigi

Birinchi o'yinchining maqsadi tanlov orqali o'z to'lovini maksimal darajada oshirishdir, ya'ni. hisoblash

1.6-rasmda nuqta olingan maksimal qiymatni bildiradi. O'yinning narxi, chunki:

Shunday qilib, birinchi o'yinchining optimal aralash strategiyasi va ikkinchi o'yinchining bir juft sof strategiyasi grafik tarzda aniqlanadi, ular kesishishda nuqta hosil qiladi.1.6-rasmda ikkinchi o'yinchining 2 va 3-strategiyalari ko'rsatilgan. Bunday strategiyalar uchun tengsizliklar (1.53) tenglikka aylanadi. 1.6-rasmda bular j=2, j=3 strategiyalardir.

Endi biz tenglamalar tizimini echishimiz mumkin

va qiymatlarini aniq aniqlang (grafik ravishda ular taxminan aniqlanadi). Keyin barcha qiymatlarni nuqta hosil qilmaydigan j ga qo'yib, tenglamalar tizimini yechish (1.56) 1.6-rasmda ko'rsatilgan misol uchun bu quyidagi tizimdir:

qolganlari esa bu tizimni qiyalik yo‘li bilan yechish mumkin. Agar ba’zi j=j 0 bo‘lsa, ikkinchi o‘yinchining strategiyalari M 0 nuqtani tashkil etsa va u holda cheklashlar to‘plamining pastki chegarasining maksimal qiymati unga parallel bo‘lgan segment bilan ifodalansa. eksa Bunday holda, birinchi o'yinchi cheksiz ko'p optimal qiymatlarga va o'yin narxiga ega. Bu holat 1.7-rasmda ko'rsatilgan, bu erda va MN segmenti yuqori chegarani ifodalaydi, optimal qiymatlar chegaralar ichida. ikkinchi o'yinchi j=j 0 sof optimal strategiyaga ega.

m2 tartibli matritsali o'yinlar ham grafik usul yordamida echiladi. Bu holda birinchi o'yinchining to'lov matritsasi shaklga ega

Birinchi va ikkinchi o'yinchilarning aralash strategiyalari, mos ravishda, 2n tartibli o'yinlardagi kabi aniqlanadi. Birinchi o'yinchi o'zining sof i-strategiyasini (i=1, 2, ..., m), ikkinchisi - uning aralash strategiyasi (y 1 , 1- y 1) =y. Masalan, m=4 grafik bo’lganda) 1.7-rasmda ko’rsatilgandek ifodalanishi mumkin.

1.7-rasm - funksiya grafigi)

Birinchi o'yinchi o'zining o'rtacha daromadini maksimal darajada oshirishga harakat qiladi, shuning uchun u topishga harakat qiladi

Funktsiya qalin chiziq sifatida ko'rsatilgan va cheklovlar to'plamining yuqori chegarasini ifodalaydi. Ikkinchi o'yinchi o'z strategiyasini tanlab, minimallashtirishga harakat qiladi, ya'ni. qiymati mos keladi

Rasmda qiymat nuqta bilan ko'rsatilgan. Boshqacha qilib aytadigan bo'lsak, birinchi o'yinchining bunday ikkita strategiyasi va ikkinchi o'yinchi uchun ehtimollik aniqlanadi, ular uchun tenglikka erishiladi.

Rasmdan ko'ramizki, o'yinning narxi nuqtaning ordinatasi, ehtimollik nuqtaning abscissasidir. Optimal aralash strategiyada birinchi o'yinchining qolgan sof strategiyalari uchun ().

Shunday qilib, tizimni (1.69) hal qilish orqali biz ikkinchi o'yinchining optimal strategiyasini va o'yinning qiymatini olamiz. Birinchi o'yinchi uchun optimal aralash strategiyani quyidagi tenglamalar tizimini yechish orqali topamiz:

1.7 O'yinlarni echish uchun matritsa usuli

Belgilar:

Tartib matritsasining istalgan kvadrat submatritsasi

Matritsa (1);

Matritsa ko'chiriladi;

B ga biriktirilgan matritsa;

- (1) X dan olingan matritsa, qabul qilinganda o'chirilgan qatorlarga mos keladigan elementlarni o'chirish orqali;

- (1) qabul qilingan paytdan o'chirilgan qatorlarga mos keladigan elementlarni o'chirish natijasida olingan matritsa.

Algoritm:

1. Tartib matritsasining () kvadrat submatritsasini tanlang va hisoblang

2. Agar ba'zi yoki bo'lsa, topilgan matritsani tashlang va boshqa matritsani sinab ko'ring.

3. Agar (), (), X va dan va tegishli joylarga nollarni qo'shib hisoblaymiz va quramiz.

Tengsizliklar qondirilganligini tekshirish

har biri uchun (1,75)

va tengsizliklar

har biri uchun (1,76)

Agar nisbatlardan biri qoniqmasa, biz boshqasini sinab ko'ramiz. Agar barcha munosabatlar to'g'ri bo'lsa, u holda X va kerakli echimlar.

1.8 O'yin narxini ketma-ket yaqinlashtirish usuli

O'yin holatlarini o'rganishda ko'pincha o'yinning aniq echimini olishning hojati yo'qligi yoki ba'zi sabablarga ko'ra o'yin narxining aniq qiymatini va optimal aralash strategiyalarni topish imkonsiz yoki juda qiyin bo'lishi mumkin. Keyin matritsali o'yinni echish uchun taxminiy usullardan foydalanishingiz mumkin.

Keling, ushbu usullardan birini tasvirlab beraylik - o'yin narxini ketma-ket yaqinlashish usuli. Usul yordamida hisoblangan to'lovlar soni to'lov matritsasi satrlari va ustunlari soniga mutanosib ravishda ortadi.

Usulning mohiyati quyidagicha: aqliy jihatdan o'yin ko'p marta o'ynaydi, ya'ni. ketma-ket, har bir o'yin o'yinida, o'yinchi unga eng katta umumiy (jami) foyda keltiradigan strategiyani tanlaydi.

Ba'zi o'yinlarning bunday amalga oshirilishidan so'ng, birinchi o'yinchining g'alabasi va ikkinchi o'yinchining yo'qotishining o'rtacha qiymatini hisoblab chiqadi va ularning arifmetik o'rtacha qiymati o'yin narxining taxminiy qiymati sifatida qabul qilinadi. Usul ikkala o'yinchining optimal aralash strategiyalarining taxminiy qiymatini topishga imkon beradi: har bir sof strategiyani qo'llash chastotasini hisoblash va uni mos keladigan o'yinchining optimal aralash strategiyasida taxminiy qiymat sifatida qabul qilish kerak.

Dastur o'yinlari sonining cheksiz ko'payishi bilan birinchi o'yinchining o'rtacha daromadi va ikkinchi o'yinchining o'rtacha yo'qotishi o'yin narxiga va aralash strategiyalarning taxminiy qiymatlariga cheksiz yaqinlashishini isbotlash mumkin. Agar o'yinning echimi noyob bo'lsa, har bir o'yinchining optimal aralash strategiyalariga moyil bo'ladi. Umuman olganda, belgilangan qiymatlardan yuqori qiymatlarni haqiqiy qiymatlarga yaqinlashtirish sekin. Biroq, bu jarayonni osongina mexanizatsiyalash mumkin va shuning uchun nisbatan katta tartibdagi to'lov matritsalarida ham kerakli darajadagi aniqlik bilan o'yinni hal qilishga yordam beradi.

2. Amaliy qism

Er-xotin qaerga sayr qilish va ikkining manfaati uchun vaqt o'tkazishni hal qiladi.

Qiz toza havo olish uchun parkda sayr qilishga, kechqurun eng yaqin kinoteatrga kino ko'rishga borishga qaror qiladi.

Yigit markaziy stadionda mahalliy klub futbolchilarining o‘yinini tomosha qilib, texnoparkga borishni taklif qiladi.

Shunga ko'ra, siz o'yinchilardan birining maqsadi qancha vaqt davomida amalga oshishini topishingiz kerak. To'lov matritsasi quyidagicha ko'rinadi:

Jadval 1. To'lov matritsasi

1 2 dan boshlab, bu o'yinda sof strategiyalarda hech qanday egar nuqtasi yo'qligi aniq. Shuning uchun biz quyidagi formulalardan foydalanamiz va biz quyidagilarni olamiz:

http://www.allbest.ru/ saytida joylashgan

2.2 2xn va mx2 o'ynash

1-muammo(2xn)

Quruq va nam iqlim uchun ikkita ekin yetishtiriladi.

Va tabiatning holatini: quruq, nam, o'rtacha deb hisoblash mumkin.

http://www.allbest.ru/ saytida joylashgan

M() ning maksimal qiymati j=1, j"=2 ga to'g'ri keladigan chiziqlar kesishmasidan hosil bo'lgan M nuqtada erishiladi. Shuning uchun biz: , deb faraz qilamiz.

Muammo 2(mx2)

Yigit va qiz dam olish kunlari uchun qaerga borish variantlarini ko'rib chiqmoqda.

Dam olish joyini tanlash quyidagicha ifodalanishi mumkin: park, kinoteatr, restoran.

http://www.allbest.ru/ saytida joylashgan

M() ning maksimal qiymatiga j=1, j"=2 ga to'g'ri keladigan chiziqlar kesishmasidan hosil bo'lgan E nuqtada erishiladi. Demak, shunday deb faraz qilamiz: ,

v qiymatini aniqlash uchun quyidagi tenglamalarni yechish kerak:

2.5 Matritsa usuli

Ikki raqobatchi restoran (ovqatlanish korxonalari) quyidagi xizmatlar to'plamini taqdim etadi. Birinchi restoran markazda, ikkinchisi esa shaharning chekkasida joylashgan.

Markaziy restoran quyidagi xizmatlarni o'z ichiga oladi:

1) qimmatroq va yaxshi mijozlarga xizmat ko'rsatish;

2) taomlar frantsuz oshxonasiga qaratilgan;

Ikkinchi restoran quyidagilarni ta'minlaydi:

1) qimmat emas va sifatli xizmat;

2) menyu dunyoning turli mashhur oshxonalarini birlashtiradi;

3) shuningdek muntazam aksiyalar va chegirmalar;

4) yetkazib berishni amalga oshiradi va uyga yetkazib berish uchun buyurtmalarni qabul qiladi.

Vazifaga muvofiq, ikki restoran o'rtasida bir kunlik foyda quyidagicha taqsimlanadi:

Jadval 2. To'lov matritsasi

Matritsali shakldagi o'yinni yechish:

Oltita submatritsa mavjud va:

Matritsani ko'rib chiqing:

x 1 =? 0,x2=? 0

Chunki x 2 =< 0, то мы отбрасываем.

Endi matritsani ko'rib chiqing:

x 1 =? 0,x2=? 0

O'yin narxi.

Bu nisbat talabga zid, shuning uchun mos emas.

Endi matritsani ko'rib chiqing:

x 1 =, x 2 =? 0,

y 1 =< 0, y 2 = ? 0.

y 1 = bo'lgani uchun< 0, то мы отбрасываем и.

Endi matritsani ko'rib chiqing:

x 1 \u003d, x 2 \u003d 0, chunki x 2 \u003d 0, keyin biz tashlaymiz va.

Endi matritsani ko'rib chiqing:

x 1 =, x 2 =? 0. x 1 \u003d 0 dan beri, keyin biz tashlaymiz va.

Endi matritsani ko'rib chiqing:

x 1 =, x 2 =, y 1 =, y 2 =, keyin davom etamiz:

x 1 =, x 2 =, y 1 =, y 2 = yoki

O'yin narxi.

Endi asosiy munosabatlar tekshiriladi:

http://www.allbest.ru/ saytida joylashgan

Javob: x 1 =, x 2 =, y 1 =, y 2 =, y 3 =0, y 4 =0,.

Jigarrang usul

Muayyan korxona ishchilarining iltimosiga binoan kasaba uyushmasi o'z rahbariyati bilan korxona hisobidan issiq ovqat tashkil etish to'g'risida kelishib oladi. Ishchilarning manfaatlarini ifodalovchi kasaba uyushmasi ovqatning eng yuqori sifatli va shuning uchun qimmatroq bo'lishini ta'minlaydi. Kompaniya rahbariyati bir-biriga qarama-qarshi manfaatlarga ega. Yakunda tomonlar quyidagilarga kelishib oldilar. Kasaba uyushmasi (1-o'yinchi) issiq ovqat bilan ta'minlaydigan uchta firmadan (A 1, A 2, A 3) birini tanlaydi va kompaniya rahbariyati (2-o'yinchi) uchta mumkin bo'lgan variantdan (B 1, B 2) idishlar to'plamini tanlaydi. B 3) . Shartnoma imzolangandan so'ng kasaba uyushmasi quyidagi to'lov matritsasini tuzadi, uning elementlari idishlar to'plamining narxini ifodalaydi:

O'yin quyidagi to'lov matritsasi bilan berilsin:

Aytaylik, ikkinchi o'yinchi o'zining ikkinchi strategiyasini tanladi, birinchisi:

2 agar u birinchi strategiyasidan foydalansa,

3, agar u uchinchi strategiyasidan foydalansa.

Olingan qiymatlar 1-jadvalda jamlangan.

Jadval 3. Ikkinchi o'yinchining strategiyasi

3-jadvalda ko'rsatilgandek, ikkinchi o'yinchining 2-strategiyasi bilan birinchi o'yinchi o'zining 2 yoki 3-strategiyasidan foydalangan holda eng katta foyda 3 ni oladi. Birinchi o'yinchi maksimal foyda olishni xohlayotgani uchun u ikkinchi o'yinchining 2-strategiyasiga o'zining 2-strategiyasi bilan javob beradi. Birinchi o'yinchining 2-strategiyasi bilan ikkinchisi yo'qotadi:

1 agar u birinchi strategiyasini qo'llasa,

3 agar u ikkinchi strategiyasidan foydalansa,

4, agar u uchinchi strategiyasidan foydalansa.

Jadval 4. Birinchi o'yinchining strategiyasi

2-jadvaldan ko'rinib turibdiki, birinchi o'yinchining 2-strategiyasi bilan ikkinchi o'yinchi o'zining birinchi strategiyasini qo'llasa, eng kam yo'qotish 1 bo'ladi. Ikkinchi o'yinchi kamroq yo'qotishni xohlasa, birinchi o'yinchining 2-strategiyasiga javoban u o'zining 1-strategiyasini qo'llaydi. Olingan natijalar 5-jadvalda jamlangan.

Jadval 5. Mos ravishda birinchi va ikkinchi o'yinchilarning strategiyalari

Jadvalda. 5 ikkinchi qatordagi ikkinchi o'yinchining strategiyasi ustunida 1 raqami ko'rsatilgan, bu ikkinchi o'yinda ikkinchi o'yinchi uchun o'zining 1-strategiyasini qo'llash foydali ekanligini ko'rsatadi; ustunda va birinchi o'yinda u tomonidan qabul qilingan birinchi o'yinchining eng katta o'rtacha to'lovi 3; w ustunida birinchi o'yinda ikkinchi o'yinchi olgan eng kichik o'rtacha yo'qotish 1; v ustunida o'rtacha arifmetik v = (u + w) -- ya'ni o'yinning bir o'yinini o'ynash natijasida olingan o'yin narxining taxminiy qiymati mavjud. Agar ikkinchi o'yinchi o'zining birinchi strategiyasidan foydalansa, birinchi o'yinchi o'zining 1, 2, 3 strategiyalari bilan mos ravishda 3, 1, 2 oladi va birinchi o'yinchining har ikkala o'yin uchun umumiy to'lovi quyidagicha bo'ladi:

2 + 3 = 5 birinchi strategiyasi bilan,

3 + 1 = 4 ikkinchi strategiyasi bilan,

Uning 3-strategiyasi bilan 3 + 2 = 5.

Ushbu jami yutuqlar jadvalning ikkinchi qatorida qayd etilgan. 3 va birinchi o'yinchining strategiyalariga mos keladigan ustunlarda: 1, 2, 3.

Barcha umumiy to'lovlardan eng kattasi 5. Birinchi o'yinchining 1 va 3 strategiyalari bilan olinadi, keyin u ulardan istalganini tanlashi mumkin; aytaylik, ikkita (yoki bir nechta) bir xil umumiy to'lovlar mavjud bo'lganda, eng kichik raqamga ega strategiya tanlanadi (bizning holatimizda biz 1-strategiyani olishimiz kerak).

Birinchi o'yinchining 1-strategiyasi bilan ikkinchi o'yinchi o'zining 1, 2, 3 strategiyalariga mos ravishda 3, 2, 3 yo'qotadi va ikkinchi o'yinchining ikkala o'yin uchun umumiy yo'qotishi quyidagicha bo'ladi:

1 + 3 = 4 birinchi strategiyasi bilan,

3 + 2 = 5 ikkinchi strategiyasi bilan,

Uning 3-strategiyasi bilan 4 + 3 = 7.

Ushbu jami yo'qotishlar jadvalning ikkinchi qatorida qayd etilgan. 5 va ikkinchi o'yinchining 1, 2, 3-strategiyalariga mos keladigan ustunlarda.

Ikkinchi o'yinchining jami yo'qotishlaridan eng kichigi 4. Bu uning 1-strategiyasi bilan olinadi, shuning uchun uchinchi o'yinda ikkinchi o'yinchi o'zining 1-strategiyasini qo'llashi kerak. Ustunga va ikkita o'yinda birinchi o'yinchining eng katta umumiy to'lovini qo'ying, o'yinlar soniga bo'linadi, ya'ni; w ustuni ikkita o'yinda ikkinchi o'yinchining eng kichik umumiy yo'qotishlarini o'z ichiga oladi, o'yinlar soniga bo'linadi, ya'ni; ushbu qiymatlarning o'rtacha arifmetik qiymati v ustuniga qo'yiladi, ya'ni = Bu raqam ikkita "o'ynagan" o'yin bilan o'yin narxining taxminiy qiymati sifatida olinadi.

Shunday qilib, ikkita o'yin to'plami uchun quyidagi 4-jadval olinadi.

Jadval 6. Ikki o'yinda o'yinchilarning umumiy daromadlari va yo'qotishlari

6-jadvalning uchinchi qatorida, ikkinchi o'yinchining strategiya ustunida 1 raqami mavjud, bu uchinchi o'yinda ikkinchi o'yinchi o'zining 1-strategiyasini qo'llashi kerakligini ko'rsatadi. Bunday holda, birinchi o'yinchi mos ravishda 1, 2, 3 strategiyalaridan foydalangan holda 3, 1, 2 g'alaba qozonadi va uning uchta o'yin uchun umumiy to'lovi quyidagicha bo'ladi:

Uning birinchi strategiyasida 3 + 5 = 8,

1 +4 = 5 ikkinchi strategiyasi bilan,

Uchinchi strategiyasi uchun 2 + 5 = 7.

Birinchi o'yinchining ushbu umumiy to'lovlari 6-jadvalning uchinchi qatorida va uning 1, 2, 3 strategiyalariga mos keladigan ustunlarda qayd etilgan. Birinchi o'yinchining eng katta umumiy to'lovi 8 1-strategiya bilan olinganligi sababli, u mos ravishda birinchi o'yinchini tanlaydi. .

Birinchi o'yinchining 1-strategiyasi bilan ikkinchi o'yinchi 1, 2, 3-strategiyalarga mos ravishda 3, 1, 2 yo'qotadi va ikkinchi o'yinchining ikkala o'yin uchun umumiy yo'qotishi quyidagicha bo'ladi:

3 + 4 = 7 birinchi strategiyasi bilan,

2 + 5 = 7 ikkinchi strategiyasi bilan,

Uning 3-strategiyasi bilan 3 + 7 = 10.

Ushbu jami yo'qotishlar jadvalning uchinchi qatorida qayd etilgan. 6 va ikkinchi o'yinchining 1, 2, 3-strategiyalariga mos keladigan ustunlarda. Uning jami yo'qotishlaridan 7 tasi eng kichiki bo'lib, uning 1 va 2 strategiyalari bilan olinadi, keyin ikkinchi o'yinchi o'zining birinchi strategiyasini qo'llashi kerak.

Jadvalda. Ustunning uchinchi qatorida 6 va uchta o'yinda birinchi o'yinchining eng katta umumiy yutug'i, o'yinning soniga bo'lingan, ya'ni; ustun w uchta o'yinda ikkinchi o'yinchining eng kichik umumiy yo'qotishlarini o'z ichiga oladi, o'yinlar soniga bo'linadi, ya'ni; v ustuniga ularning arifmetik o'rtasini qo'ying

Shunday qilib, biz stolni olamiz. Uch partiya uchun 7.

Jadval 7. O'ynagan uchta o'yinda o'yinchilarning umumiy daromadlari va yo'qotishlari

Jadval 8. Yigirmata o'yindan iborat yakuniy jadval

Jadvaldan. 7 va 8-dan ko'rinib turibdiki, 20 ta yo'qotilgan o'yinda birinchi o'yinchi uchun 1, 2, 3-strategiyalar mos ravishda 12, 3, 5 marta sodir bo'ladi, shuning uchun ularning nisbiy chastotalari mos ravishda teng; ikkinchi o'yinchi uchun 1, 2, 3 strategiyalari mos ravishda 7, 11,2 marta sodir bo'ladi, shuning uchun ularning nisbiy chastotalari mos ravishda teng; o'yin narxining taxminiy qiymati. Bu yaqinlik etarli darajada yaxshi.

Xulosa qilib shuni ta'kidlaymizki, agar o'yinda bir nechta echim bo'lsa, o'yin narxining taxminiy qiymatlari hali ham o'yinning haqiqiy narxiga cheksiz yaqinlashadi va o'yin strategiyalari paydo bo'lishining nisbiy chastotalari. o'yinchilar endi o'yinchilarning haqiqiy optimal aralash strategiyalariga yaqinlashishlari shart emas.

Natijalarni tahlil qilish

Ushbu kurs ishida antagonistik o'yinlar yechimini topish uchun material grafik, matritsali usul, o'yin narxini ketma-ket yaqinlashtirish usuli bilan o'rganiladi. Birinchi va ikkinchi o'yinchilarning optimal strategiyalari, shuningdek, 2x2, 2xn va mx2 o'yinlarida, shuningdek, matritsa usuli va Braun usulidan foydalangan holda o'yinlarda o'yin narxi topiladi.

Juftlik misolida 2x2 o'yin modellashtirildi, u algebraik va grafik usulda echildi. O'yinni algebraik usulda yechish, yechim ularning optimal aralash strategiyalarini qo'llash orqali birinchi va ikkinchi o'yinchilar birgalikda 4,6 soat vaqt sarflashlarini ko'rsatadi. Muammoning grafik yechimi kichik xato bilan chiqdi va 4,5 soatni tashkil etdi.

Shuningdek, ikkita vazifa 2xn va mx2 modellashtirildi. 2xn muammosida qishloq xo'jaligi madaniyati ko'rib chiqildi va strategiya dalani 50 dan 50 gacha ekish yaxshiroq ekanligini ko'rsatadi va o'yinning narxi 3,75 million rublni tashkil etdi. Va mx2 muammosida bir juftlik ko'rib chiqildi, uning strategiyasi park va kinoga borish arzonroq ekanligini ko'rsatdi va narx va narx 4,3 rublni tashkil qiladi.

Matritsa usuli uchun vazifa modellashtirilgan bo'lib, unda ikkita restoran ko'rib chiqildi, muammoning echimi shuni ko'rsatdiki, uning optimal aralash strategiyasini qo'llashda birinchi restoranning foydasi 15,6 million rublni tashkil qiladi va uning optimal aralash strategiyasidan foydalanganda: ikkinchi restoran, u birinchisiga 15,6 million rubldan ko'proq daromad olishga imkon bermaydi. Grafik usul bilan yechim xatoga yo'l qo'ydi va o'yinning narxi 14,9 million rublni tashkil etdi.

Braun usuli uchun kasaba uyushmasi va kompaniya rahbariyati hisobga olinadigan vazifa tuzildi, ularning vazifasi ishchilarni oziq-ovqat bilan ta'minlashdir. Ikkala o'yinchi ham o'zlarining optimal strategiyalaridan foydalanganda, bir kishi uchun oziq-ovqat 2,45 ming rublni tashkil qiladi.

Foydalanilgan manbalar ro'yxati

1) Vilisov V.Ya. Ma'ruza matnlari "O'yin nazariyasi va statistik echimlar", - Filial - "Vosxod" MAI. 1979. 146 b.

2) Krushevskiy A.V. O'yin nazariyasi, - Kiev: Vishcha maktabi, 1977. - 216 p.

3) Cherchmen U., Akof R., Arnof L., Operatsion tadqiqotlarga kirish. - M.: Fan. 1967. - 488 b.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0%B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Allbest.ru saytida joylashgan

Shunga o'xshash hujjatlar

Qaror qabul qilish inson faoliyatining alohida turi sifatida. O'yin matritsasining ratsional tasviri. Sof va aralash strategiyalardagi matritsali o'yinlarga misollar. Operatsion tadqiqotlar: chiziqli dasturlash muammolarining o'yin nazariyasi modeli bilan aloqasi.

muddatli ish, 05/05/2010 qo'shilgan


Ko'p marta takrorlangan o'yinlar, ularning o'ziga xos xususiyatlari va bosqichlari. Aralash strategiyalar, ulardan amaliyotda foydalanish shartlari va imkoniyatlari. 2 x 2 o'yinni echishning analitik usuli.To'rtburchaklar o'yinlari uchun asosiy teoremalar. Algebraik yechimlar.

taqdimot, 23/10/2013 qo'shilgan


Bimatritsali o'yinlar nazariyasining asosiy ta'riflari. "Talaba-o'qituvchi" bimatritsali o'yiniga misol. Bimatrix o'yinlarida aralash strategiyalar. "Muvozanat holati" ni qidiring. 2x2 bimatritsali o'yinlar va har bir o'yinchi ikkita strategiyaga ega bo'lgan holatlar uchun formulalar.

referat, 2011-yil 13-02-da qo‘shilgan


Matritsa va antagonistik o'yinlar haqida umumiy ma'lumotni o'rganish. Pozitsion o'yin, daraxt, axborot to'plami tushunchasi. Maksimin printsipi va muvozanat tamoyilini ko'rib chiqish. Pareto optimalligi. Pozitsion antagonistik bo'lmagan o'yin, uning xususiyatlari.

muddatli ish, 10/17/2014 qo'shilgan


O'yin nazariyasi - bu matematikaning bir bo'limi bo'lib, uning predmeti konfliktda optimal qarorlar qabul qilish uchun matematik modellarni o'rganishdir. Iterativ Braun-Robinson usuli. Matritsali o'yinlarni yechish uchun monotonli iterativ algoritm.

dissertatsiya, 08/08/2007 qo'shilgan


To'lov matritsasini tuzish, o'yinning pastki va yuqori sof narxlarini, o'yinchilarning maksimal va minimal strategiyalarini qidirish. To'lov matritsasini soddalashtirish. Chiziqli dasturlash muammosiga qisqartirish va "Yechim izlash" qo'shimchasidan foydalangan holda matritsali o'yinni yechish.

test, 11/10/2014 qo'shilgan


O'yin nazariyasi - ziddiyatli vaziyatlarning matematik nazariyasi. Ikki kishilik nol yig‘indili o‘yinning matematik modelini ishlab chiqish, uni dastur kodlari ko‘rinishida amalga oshirish. Muammoni hal qilish usuli. Ma'lumotlarni kiritish va chiqarish. Dastur, foydalanuvchi qo'llanma.

kurs qog'ozi, 2013 yil 17 iyulda qo'shilgan


Simpleks usuli haqida asosiy ma'lumotlar, uning chiziqli dasturlashdagi o'rni va ahamiyatini baholash. Geometrik talqin va algebraik ma'no. Chiziqli funksiyaning maksimal va minimumini topish, maxsus holatlar. Masalani matritsali simpleks usulida yechish.

dissertatsiya, 06/01/2015 qo'shilgan


Hisoblash tizimlarining tuzilishi va ishlash jarayonlarini aks ettiruvchi matematik modellarini qurish texnikasi. O'rtacha vazifa davomida faylga kirishlar soni. Fayllarni tashqi xotira disklariga joylashtirish imkoniyatini aniqlash.

laboratoriya ishi, 21/06/2013 qo'shilgan


Matematik modelni loyihalash. Tik-tak-toe o'yinining tavsifi. Mantiqiy o'yin modeli mantiqiy algebraga asoslangan. Raqamli elektron qurilmalar va ularning matematik modelini ishlab chiqish. O'yin konsoli, o'yin boshqaruvchisi, o'yin taxtasi ipi.

O'yin nazariyasi - bu ziddiyat yoki noaniqlik sharoitida qaror qabul qilishning matematik modellari nazariyasi. O'yinda tomonlarning harakatlari ma'lum strategiyalar - harakat qoidalari to'plami bilan tavsiflanadi deb taxmin qilinadi. Agar bir tomonning daromadi muqarrar ravishda ikkinchi tomonning yo'qolishiga olib kelsa, ular antagonistik o'yinlar haqida gapirishadi. Agar strategiyalar to'plami cheklangan bo'lsa, u holda o'yin matritsali o'yin deb ataladi va yechimni juda oddiy olish mumkin. O'yin nazariyasi yordamida olingan echimlar raqobatchilarning mumkin bo'lgan qarshiliklari yoki tashqi muhitdagi noaniqlik sharoitida rejalar tuzishda foydalidir.

Agar bimatritsa o'yini antagonistik bo'lsa, u holda 2-o'yinchining to'lov matritsasi 1-o'yinchining to'lov matritsasi bilan to'liq aniqlanadi (bu ikki matritsaning mos keladigan elementlari faqat belgilar bilan farqlanadi). Shuning uchun bimatritsali antagonistik o'yin to'liq bitta matritsa (1-o'yinchining to'lov matritsasi) bilan tavsiflanadi va shunga mos ravishda matritsali o'yin deb ataladi.

Bu o'yin antagonistik. Unda j \u003d x2 - O, P va R (O, O] \u003d H (P, P) \u003d -I va R (O, P) \u003d R (P, O) \u003d 1 yoki matritsa shaklida o p

O'yinlarning ba'zi G sinflari "oyna-yopiq" bo'lsin, ya'ni. uning har bir o'yinlari bilan birgalikda oyna izomorfik o'yinni o'z ichiga oladi (ma'lum biriga ko'zgu izomorf bo'lgan barcha o'yinlar bir-biriga izomorf bo'lganligi sababli, biz yuqorida aytib o'tilganlarga muvofiq, bitta oyna izomorf o'yin haqida gapirishimiz mumkin). Bunday sinf, masalan, barcha antagonistik o'yinlar sinfi yoki barcha matritsali o'yinlar sinfidir.

Antagonistik o'yinda maqbul vaziyatlarning ta'rifini eslab, biz matritsali o'yinning aralash kengaytmasidagi vaziyat (X, Y) 1-o'yinchi uchun har qanday x G x tengsizlik bo'lgan taqdirdagina maqbul ekanligini bilib olamiz.

O'yinlarni simmetrik o'yinlarga aylantirish jarayoni simmetriya deb ataladi. Biz bu erda simmetriyalashning bir usulini tasvirlaymiz. Simmetriyaning boshqa, tubdan farqli versiyasi 26.7-bo'limda keltirilgan. Simmetriyaning ikkala varianti ham ixtiyoriy antagonistik o'yinlar uchun amal qiladi, lekin faqat matritsali o'yinlar uchun shakllantiriladi va isbotlanadi.

Shunday qilib, umumiy antagonistik o'yinlar nazariyasining dastlabki atamalari va belgilari matritsali o'yinlar nazariyasining tegishli atamalari va belgilariga to'g'ri keladi.

Cheklangan antagonistik (matritsa) o'yinlar uchun bu ekstremallarning mavjudligi biz tomonidan 10-bobda isbotlangan. 1, va hamma narsa ularning tengligini o'rnatish yoki hech bo'lmaganda ularning tengsizligini bartaraf etish yo'llarini topish edi.

Matritsali o'yinlarni ko'rib chiqish allaqachon o'yinchilarning dastlab berilgan strategiyalarida muvozanatli vaziyatlarsiz (va hatto etarlicha kichik e > 0 uchun elektron muvozanatli vaziyatlarsiz) antagonistik o'yinlar mavjudligini ko'rsatadi.

Biroq, har bir chekli (matritsa) o'yinni cheksiz o'yinga kengaytirish mumkin, masalan, har bir o'yinchiga har qanday sonli ustunlik strategiyalarini taqdim etish orqali (22-bo'lim 1-ga qarang). Shubhasiz, o'yinchining strategiyalar to'plamining bunday kengayishi uning imkoniyatlarini kengaytirishni anglatmaydi va kengaytirilgan o'yindagi uning haqiqiy xatti-harakati asl o'yindagi xatti-harakatlaridan farq qilmasligi kerak. Shunday qilib, biz darhol egar nuqtalari bo'lmagan cheksiz antagonistik o'yinlarning etarli miqdordagi misollarini oldik. Bunday misollar ham mavjud.

Shunday qilib, cheksiz antagonistik o'yinda maksimal printsipni amalga oshirish uchun, xuddi cheklangan (matritsali) o'yinda bo'lgani kabi, o'yinchilarning strategik imkoniyatlarini biroz kengaytirish kerak. 96 uchun

Matritsali o'yinlarda bo'lgani kabi (1, 17-boblarga qarang), umumiy antagonistik o'yinlar uchun aralash strategiya spektri kontseptsiyasi muhim rol o'ynaydi, ammo bu erda umumiy ta'rif berilishi kerak.

Va nihoyat, ixtiyoriy antagonistik o'yindagi 1-o'yinchining barcha aralash strategiyalari to'plami matritsadagi kabi ekanligini unutmang.

Hatto antagonistik o'yinlarni ko'rib chiqish shuni ko'rsatadiki, bunday o'yinlarning ko'pligi, shu jumladan chekli o'yinlar, matritsali o'yinlar asl, sof strategiyalarda emas, balki faqat umumlashtirilgan, aralash strategiyalarda muvozanatli vaziyatlarga ega. Shuning uchun umumiy, antagonistik bo'lmagan, hamkorlikda bo'lmagan o'yinlar uchun muvozanatli vaziyatlarni aniq aralash strategiyalardan izlash tabiiydir.

Shunday qilib, masalan, (3.1-rasmga qarang), biz allaqachon "Pudratchi" deyarli hech qachon xulq-atvor noaniqligi bilan shug'ullanmasligini ta'kidladik. Ammo agar biz "Administrator" turining kontseptual darajasini oladigan bo'lsak, unda hamma narsa aksincha bo'ladi. Qoidaga ko'ra, bunday "bizning qaror qabul qiluvchimiz" duch keladigan noaniqlikning asosiy turi "mojaro" dir. Endi aniqlik kiritishimiz mumkinki, bu odatda qattiq bo'lmagan raqobatdir. Bir oz kamroq tez-tez "Administrator" "tabiiy noaniqlik" sharoitida qaror qabul qiladi va kamdan-kam hollarda u qattiq, antagonistik mojaroga duch keladi. Bundan tashqari, "Administrator" tomonidan qaror qabul qilishda manfaatlar to'qnashuvi sodir bo'ladi, aytganda, "bir marta", ya'ni bizning tasnifimizda u ko'pincha o'yinning faqat bitta (ba'zan juda oz sonli) o'yinlarini o'ynaydi. Natijalarni baholash uchun o'lchovlar miqdoriy emas, balki sifat jihatidan ko'proq bo'ladi. “Administrator”ning strategik mustaqilligi ancha cheklangan. Yuqoridagilarni hisobga olgan holda, bunday kattalikdagi muammoli vaziyatlarni ko'pincha hamkorlikda bo'lmagan antagonistik bo'lmagan bi-matritsali o'yinlar yordamida, shuningdek, sof strategiyalarda tahlil qilish kerakligi haqida bahslashish mumkin.

Matritsa antagonistik o'yinlarini yechish tamoyillari

Natijada, yuqorida tavsiflangan o'yinda raqiblar o'zlari tanlagan strategiyalarga amal qilishlarini kutish o'rinli. Maks min besh = min max Aiy> bo'lgan matritsa antagonistik o'yini

Biroq, barcha matritsa antagonistik o'yinlari juda aniq emas va umumiy holatda

Shunday qilib, umumiy holatda, o'lchovli matritsaning antagonistik o'yinini hal qilish uchun /uxl, bir juft chiziqli dasturlash muammolarini hal qilish kerak, natijada optimal strategiyalar to'plami , / va o'yinning narxi v.

Ikki kishining matritsa antagonistik o'yini qanday aniqlanadi?

Matritsa antagonistik o'yinlarini soddalashtirish va yechish usullari qanday

Ikki kishining o'yini bo'lsa, ularning manfaatlarini to'g'ridan-to'g'ri qarama-qarshi deb hisoblash tabiiydir - o'yin antagonistikdir. Shunday qilib, bir o'yinchining to'lovi ikkinchisini yo'qotishiga teng (har ikkala o'yinchining to'lovlari yig'indisi nolga teng, shuning uchun nom, nol yig'indisi o'yin). Biz har bir o'yinchining cheklangan soniga ega bo'lgan o'yinlarni ko'rib chiqamiz. Bunday nol summali ikki kishilik o'yin uchun to'lov funktsiyasi matritsa shaklida (to'lov matritsasi shaklida) berilishi mumkin.

Yuqorida aytib o'tilganidek, yakuniy antagonistik o'yin matritsa deb ataladi.

MATRIX O'YINLARI - ikkita o'yinchi ishtirok etadigan va har bir o'yinchi cheklangan miqdordagi strategiyalarga ega bo'lgan antagonistik o'yinlar sinfi. Agar bir o'yinchi m ta strategiyaga, ikkinchi o'yinchi esa n ta strategiyaga ega bo'lsa, biz txn o'lchamli o'yin matritsasini qurishimiz mumkin. M.i. egar nuqtasi bo'lishi mumkin yoki bo'lmasligi mumkin. Oxirgi holatda

Cheklangan nol yig'indili juftlik o'yinini ko'rib chiqing. tomonidan belgilang a o'yinchining to'lovi A, va orqali b- o'yinchi g'alaba qozondi B. Chunki a = –b, keyin bunday o'yinni tahlil qilishda bu raqamlarning ikkalasini ham hisobga olishning hojati yo'q - o'yinchilardan birining to'lovini hisobga olish kifoya. Bo'lsin, masalan, A. Taqdimotning qulayligi uchun keyingi qismda A shartli ravishda nom beramiz" biz"va tomoni B – "dushman".

Kelinglar m mumkin bo'lgan strategiyalar A 1 , A 2 , …, A m, va dushman n mumkin bo'lgan strategiyalar B 1 , B 2 , …, B n(bunday o'yin o'yin deb ataladi m×n). Har bir tomon ma'lum strategiyani tanlagan deb faraz qiling: biz tanladik Ai, raqib Bj. Agar o'yin faqat shaxsiy harakatlardan iborat bo'lsa, unda strategiyalarni tanlash Ai va Bj o'yin natijasini noyob tarzda belgilaydi - bizning to'lovimiz (ijobiy yoki salbiy). Bu daromadni quyidagicha belgilaymiz aij(strategiyani tanlaganimizda g'alaba qozonamiz Ai, va dushman - strategiyalar Bj).

Agar o'yin shaxsiy tasodifiy harakatlardan tashqari, bir juft strategiya uchun to'lovni o'z ichiga olsa Ai, Bj barcha tasodifiy harakatlarning natijalariga bog'liq bo'lgan tasodifiy o'zgaruvchidir. Bunday holda, kutilayotgan to'lovning tabiiy bahosi tasodifiy g'alabaning matematik kutish. Qulaylik uchun biz bilan belgilaymiz aij ham to'lovning o'zi (tasodifiy harakatlarsiz o'yinda) va uning matematik kutilishi (tasodifiy harakatlar bilan o'yinda).

Aytaylik, biz qadriyatlarni bilamiz aij Har bir strategiya juftligi uchun. Ushbu qiymatlarni satrlari bizning strategiyalarimizga mos keladigan matritsa sifatida yozish mumkin ( Ai) va ustunlar raqibning strategiyalarini ko'rsatadi ( Bj):

Bunday matritsa deyiladi O'yinning to'lov matritsasi yoki oddiygina o'yin matritsasi.

E'tibor bering, ko'p sonli strategiyalarga ega o'yinlar uchun to'lov matritsasini qurish qiyin vazifa bo'lishi mumkin. Masalan, shaxmat o'yini uchun mumkin bo'lgan strategiyalar soni shunchalik kattaki, to'lov matritsasini qurish deyarli mumkin emas. Biroq, printsipial jihatdan har qanday cheklangan o'yinni matritsa shakliga keltirish mumkin.

O'ylab ko'ring misol 1 4×5 antagonistik o'yin. Bizning ixtiyorimizda to'rtta strategiya bor, dushmanning beshta strategiyasi bor. O'yin matritsasi quyidagicha:

Biz qanday strategiyani qo'llashimiz kerak (ya'ni, o'yinchi A) foydalanish uchun? Qaysi strategiyani tanlamasligimizdan qat'iy nazar, oqilona raqib unga bizning foydamiz minimal bo'lgan strategiya bilan javob beradi. Misol uchun, agar strategiyani tanlasak A 3 (10 g'alaba bilan vasvasaga solingan), raqib javob strategiyasini tanlaydi B 1 , va bizning to'lovimiz faqat 1 bo'ladi. Shubhasiz, ehtiyotkorlik tamoyiliga asoslanib (va bu o'yin nazariyasining asosiy printsipi), biz qaysi strategiyani tanlashimiz kerak. bizning minimal daromadimiz maksimaldir.

tomonidan belgilang a i strategiya uchun minimal to'lov qiymati Ai:

va o'yin matritsasiga ushbu qiymatlarni o'z ichiga olgan ustun qo'shing:

Strategiyani tanlashda biz qiymatga ega bo'lgan strategiyani tanlashimiz kerak a i maksimal. Bu maksimal qiymatni bilan belgilaymiz α :

Qiymat α chaqirdi past o'yin narxi yoki maksimal(maksimal minimal g'alaba). O'yinchi strategiyasi A maksimalga mos keladi α , deyiladi maksimal strategiya.

Ushbu misolda maksimal α 3 ga teng (jadvaldagi tegishli katak kulrang rang bilan ajratilgan) va maksimal strategiya A to'rtta. Ushbu strategiyani tanlaganimizdan so'ng, biz dushmanning har qanday xatti-harakati uchun biz kamida 3 ta g'alaba qozonishimizga amin bo'lishimiz mumkin (va ehtimol, dushmanning "asossiz" xatti-harakati bilan). o'zimizni, eng ehtiyotkor ("qayta sug'urta") strategiyasiga rioya qilgan holda.

Endi biz dushman uchun xuddi shunday fikr yuritamiz B B A B 2 - biz unga javob beramiz A .

tomonidan belgilang bj A B) strategiya uchun Ai:

bj β :

7. YUQORI QIMMATLI O'YIN NIMA Endi biz raqib uchun ham xuddi shunday mulohaza yuritamiz. B. U bizning daromadimizni minimallashtirishdan, ya'ni bizga kamroq berishdan manfaatdor, lekin u bizning xatti-harakatlarimizga ishonishi kerak, bu uning uchun eng yomoni. Misol uchun, agar u strategiyani tanlasa B 1 , keyin unga strategiya bilan javob beramiz A 3 , va u bizga 10 beradi. Agar xohlasa B 2 - biz unga javob beramiz A 2 , va u 8 beradi va hokazo.. Shubhasiz, ehtiyotkor raqib qaysi strategiyani tanlashi kerak. bizning maksimal daromadimiz minimal bo'ladi.

tomonidan belgilang bj to'lov matritsasi ustunlaridagi maksimal qiymatlar (o'yinchining maksimal to'lovi). A, yoki, qaysi bir xil, futbolchining maksimal yo'qotish B) strategiya uchun Ai:

va o'yin matritsasiga ushbu qiymatlarni o'z ichiga olgan qatorni qo'shing:

Strategiyani tanlab, dushman o'zi uchun qadrli bo'lgan strategiyani afzal ko'radi bj eng kam. bilan belgilaymiz β :

Qiymat β chaqirdi yuqori o'yin narxi yoki minimaks(minimal maksimal g'alaba). Minimaksga mos keladigan raqib (o'yinchi) strategiyasi B), deyiladi Minimax strategiyasi.

Minimaks - bu daromadning qiymati bo'lib, undan ko'proq oqilona raqib bizga bermaydi (boshqacha qilib aytganda, oqilona raqib undan ko'p yo'qotmaydi. β ). Ushbu misolda, minimax β 5 ga teng (jadvaldagi tegishli katak kulrang rangda ta'kidlangan) va unga raqib strategiyasi bilan erishiladi B 3 .

Shunday qilib, ehtiyotkorlik tamoyiliga asoslanib ("har doim eng yomonini kuting!"), biz strategiyani tanlashimiz kerak A 4 , va dushman - strategiya B 3 . Ehtiyotkorlik printsipi o'yin nazariyasida asosiy hisoblanadi va deyiladi Minimax printsipi.

O'ylab ko'ring misol 2. O'yinchilarga ruxsat bering A va DA uchta raqamdan biri bir vaqtning o'zida va bir-biridan mustaqil ravishda yoziladi: "1", yoki "2" yoki "3". Agar yozilgan raqamlarning yig'indisi juft bo'lsa, o'yinchi B o'yinchiga pul to'laydi A bu miqdor. Agar miqdor g'alati bo'lsa, o'yinchi bu miqdorni to'laydi A futbolchi DA.

Keling, o'yinning to'lov matritsasini yozamiz va o'yinning pastki va yuqori narxlarini topamiz (strategiya raqami yozma raqamga mos keladi):

O'yinchi A maksimal strategiyaga rioya qilish kerak A 1 kamida -3 g'alaba qozonish (ya'ni, eng ko'p 3 yutqazish). Minimax o'yinchi strategiyasi B har qanday strategiya B 1 va B 2 , bu esa u 4 dan ortiq bo'lmasligini kafolatlaydi.

Agar biz o'yinchi nuqtai nazaridan to'lov matritsasini yozsak, xuddi shunday natijaga erishamiz DA. Aslida, bu matritsa o'yinchi nuqtai nazaridan qurilgan matritsani ko'chirish orqali olinadi. A, va elementlarning belgilarini teskarisiga o'zgartirish (o'yinchining to'lovidan beri A o'yinchining yo'qolishi DA):

Ushbu matritsaga asoslanib, o'yinchi quyidagicha B har qanday strategiyaga amal qilish kerak B 1 va B 2 (va keyin u 4 dan ortiq yo'qotadi) va o'yinchi A- strategiyalar A 1 (va keyin u 3 dan ortiq yo'qotmaydi). Ko'rib turganingizdek, natija yuqorida olingan natija bilan bir xil, shuning uchun tahlilni qaysi o'yinchi tomonidan o'tkazishimiz muhim emas.

8 QIMMATLI O'YIN NIMA.

9. MINIMAKS PRINSIBI NIMALARDAN MUMKIN. 2. O'yinning pastki va yuqori narxi. Minimax printsipi

To'lov matritsasi bilan turdagi matritsali o'yinni ko'rib chiqing

Agar o'yinchi LEKIN strategiyasini tanlaydi A i, keyin uning barcha mumkin bo'lgan to'lovlari elementlar bo'ladi i-matritsaning qatori FROM. Futbolchi uchun eng yomoni LEKIN futbolchi qachon DA tegishli strategiyani qo'llaydi eng kam bu chiziq elementi, futbolchining to'lovi LEKIN soniga teng bo'ladi.

Shuning uchun, maksimal to'lov olish uchun, futbolchi LEKIN raqam bo'lgan strategiyalardan birini tanlashingiz kerak maksimal.

O'yin nazariyasida batafsil ishlab chiqilgan eng oddiy holat - bu nol yig'indili chekli juftlik o'yini (ikki kishi yoki ikkita koalitsiyaning antagonistik o'yini). Qarama-qarshi manfaatlarga ega bo'lgan ikkita 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 biriga (bu A bo'lsin) aqlan tanishtiramiz va uni "biz", B o'yinchisini 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, raqib esa strategiyadan foydalansa, foydamizni belgilaylik

26.1-jadval

Faraz qilaylik, har bir juft strategiya uchun foyda (yoki o'rtacha daromad) a bizga ma'lum. Keyin, printsipial jihatdan, o'yinchilarning strategiyalari va tegishli to'lovlar ro'yxati keltirilgan to'rtburchaklar jadvalini (matritsani) tuzish mumkin (26.1-jadvalga qarang).

Agar shunday jadval tuzilgan bo'lsa, u holda G o'yini matritsali shaklga qisqartirilgan deb aytiladi (o'z-o'zidan, o'yinni bunday shaklga keltirish juda ko'p strategiyalar tufayli allaqachon qiyin, ba'zan esa deyarli imkonsiz bo'lishi mumkin. ). E'tibor bering, agar o'yin matritsa shakliga tushirilsa, u holda ko'p harakatli o'yin aslida bir harakatli o'yinga qisqartiriladi - o'yinchi faqat bitta harakatni amalga oshirishi kerak: strategiyani tanlang. Biz o'yin matritsasini qisqacha belgilaymiz

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

Keling, o'ylab ko'raylik, biz (A o'yinchisi) qanday strategiyadan foydalanamiz? Matritsa 26.2 "10" jozibador daromadga ega; Biz ushbu "tidbit" ni oladigan strategiyani tanlashga majburmiz.

Lekin kuting, dushman ham ahmoq emas! Agar biz strategiyani tanlasak, u bizga qaramay, strategiyani tanlaydi va biz "1" achinarli foyda olamiz. Yo'q, siz strategiya tanlay olmaysiz! Qanday bo'lish kerak? Shubhasiz, ehtiyotkorlik printsipidan kelib chiqqan holda (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 eng yomon xatti-harakati bilan siz maksimal foyda olasiz.

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

26.3-jadval

Barcha qiymatlardan (o'ng ustun) eng kattasi (3) tanlanadi. Bu strategiyaga mos keladi. Ushbu strategiyani tanlab, biz har qanday holatda ham (dushmanning har qanday xatti-harakati uchun) biz 3 dan kam bo'lmagan foyda olishimizga amin bo'lishimiz mumkin. Bu qiymat bizning kafolatlangan daromadimizdir; o'zimizni ehtiyotkorlik bilan tutsak, bundan kam ololmaymiz, ko'proq olamiz).

Ushbu to'lov o'yinning past narxi (yoki "maksimin" - minimal to'lovlarning maksimali) deb ataladi. Biz uni a sifatida belgilaymiz. Bizning holatda

Keling, dushmanning nuqtai nazarini olib, uning uchun bahslashamiz. U qandaydir garov emas, balki oqilona! Strategiyani tanlab, u kamroq berishni xohlaydi, lekin u bizning xatti-harakatlarimizga ishonishi kerak, bu uning uchun eng yomoni. Agar u strategiya tanlasa, biz unga javob beramiz va u 10 beradi; agar u tanlasa, biz unga javob beramiz va u qaytarib beradi va hokazo.26.3-jadvalga qo'shimcha pastki qator qo'shamiz va undagi ustunlarning maksimal miqdorini 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 (yoki "mi-nimax" - maksimal yutuqning minimali) deb ataladi. Bizning misolimizda va raqibning 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 "minimaks" deb ataladi (minimax printsipidan kelib chiqqan holda). Bizning misolimizdagi ikkala tomon ham o'zlarining minimaks strategiyalariga sodiq qolar ekan, foyda bo'ladi

Endi bir lahza tasavvur qiling-a, biz dushman strategiyaga amal qilayotganini bilib oldik. Keling, biz uni buning uchun jazolaymiz va strategiyani tanlaymiz, biz 5 ball olamiz va bu unchalik yomon emas. Lekin oxir-oqibat, dushman ham sog'inmaydi; let him that our strategiyamiz , u ham tanlashga shoshiladi, bizning to‘lovimizni 2 ga kamaytiradi va hokazo (sheriklar “strategiyalar atrofida 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 yuqoriga teng: . Bundan nima kelib chiqadi? A va B o'yinchilarining minimaks strategiyalari barqaror bo'ladi. Ikkala o'yinchi ham ularga yopishgan ekan, to'lov 6 ga teng. Keling, agar (A) raqib (B) B strategiyasiga yopishganini bilsak nima bo'lishini ko'raylik?

26.4-jadval

Va aniq hech narsa o'zgarmaydi, chunki strategiyadan har qanday og'ish bizning vaziyatimizni faqat yomonlashtirishi mumkin. Xuddi shunday, raqib tomonidan olingan ma'lumotlar uni o'z strategiyasidan chekinishga majbur qilmaydi. 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 kombinatsiyasi o'yinning yechimidir. Bunday holda, o'yinning o'zi sof strategiyalarda hal qilinishi aytiladi. Ikkala A va B partiyalariga ularning pozitsiyalari eng yaxshi bo'lgan optimal strategiyalari berilishi mumkin. Va o'sha o'yinchi A 6 g'alaba qozonadi va o'yinchi B yutqazadi, yaxshi, bu o'yin shartlari: ular A uchun foydali va B uchun zarar.

O'quvchida savol tug'ilishi mumkin: nima uchun optimal strategiyalar "sof" deb ataladi? Biroz oldinga qarab, bu savolga javob beraylik: "aralash" strategiyalar mavjud, ular o'yinchi bitta strategiyani emas, balki bir nechtasini tasodifiy ravishda almashtirib ishlatishidan iborat. Shunday qilib, agar biz sof strategiyalardan tashqari aralash strategiyalarni ham tan olsak, har qanday cheklangan o'yinning yechimi - muvozanat nuqtasi bor. Ammo bu haqda ko'proq narsa hali oldinda.

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 turli xil o'yinlar 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 harakatda uning rivojlanishining butun tarixini, ya'ni shaxsiy va tasodifiy barcha oldingi harakatlar natijalarini biladigan o'yin. To'liq ma'lumotga ega bo'lgan o'yinlarga shashka, shaxmat, tic-tac-toe va boshqalar misol bo'ladi.

O'yin nazariyasida to'liq ma'lumotga ega bo'lgan har bir o'yinning egar nuqtasi borligi isbotlangan va shuning uchun uni sof strategiyalarda hal qilish mumkin. Mukammal 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 strategiyasini qo'llaganida, u juda aniq tarzda - o'yin narxiga teng bo'lgan to'lov bilan yakunlanishi kerak. Demak, agar o'yinning yechimi 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: ikki o'yinchi navbatma-navbat nikellarni dumaloq stol ustiga qo'yib, tanga markazining o'rnini o'zboshimchalik bilan tanlaydi (tangalarning o'zaro bir-biriga yopishishiga yo'l qo'yilmaydi). Oxirgi tiyinni qo'ygan kishi g'olib bo'ladi (boshqalar uchun joy yo'q bo'lganda). Bu o'yin natijasi mohiyatan oldindan aytib bo'lgan xulosa ekanligini ko'rish oson. Tangani birinchi qo'ygan o'yinchi g'alaba qozonishini ta'minlaydigan ma'lum bir strategiya mavjud.

Ya'ni, u birinchi marta stol markaziga nikel qo'yishi kerak, keyin esa raqibning har bir harakatiga simmetrik harakat bilan javob berishi kerak. Ochig'i, raqib o'zini qanday tutmasin, mag'lubiyatdan qochib qutula olmaydi. Vaziyat shaxmat va umuman to'liq ma'lumotga ega o'yinlar bilan bir xil: matritsa ko'rinishida yozilgan ularning har biri egar nuqtasiga ega va shuning uchun yechim sof strategiyalarda va shuning uchun bu yechim mavjud bo'lgandagina mantiqiy bo'ladi. topilmadi. Aytaylik shaxmat o'yini yo har doim Oqning g'alabasi bilan tugaydi, yoki u har doim qoraning g'alabasi bilan tugaydi, yoki har doim durang bilan tugaydi, lekin aniq nima - biz hali bilmaymiz (baxtimizga shaxmat ixlosmandlari uchun). Yana bir narsani qo'shamiz: biz yaqin kelajakda bilib bo'lmaydi, chunki strategiyalar soni shunchalik kattaki, o'yinni matritsa shakliga keltirish va unda egar nuqtasini topish juda qiyin (agar imkonsiz bo'lsa).

Va 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. Yana bir narsa shundaki, agar siz o'zingizning strategiyalaringizni "aralashtira" olsangiz, ularni tasodifiy ba'zi ehtimolliklar bilan almashtiring. Aralash strategiyalardan foydalanish shu tarzda o'ylab topilgan: o'yin ko'p marta takrorlanadi; o'yinning har bir o'yinidan oldin, o'yinchiga shaxsiy harakat berilganda, u o'z tanlovini tasodifga "ishonib beradi", "qur'a tashlaydi" va yiqilgan 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 raqibning berilgan o'yinda o'zini qanday tutishini bilmasa. Ushbu taktika (odatda hech qanday matematik asossiz bo'lsa ham) ko'pincha ishlatiladi karta o'yinlari. 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.

Shunday qilib, keling, aralash strategiyalar haqida gapiraylik. Biz mos ravishda A va B o'yinchilarining aralash strategiyalarini belgilaymiz

Muayyan 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 ikki o'yinchidan iborat cheklangan nol yig'indili o'yin kamida bitta yechimga ega - odatda aralashgan optimal strategiyalar juftligi va mos keladigan narx.

O'yin yechimini tashkil etuvchi optimal strategiyalar juftligi quyidagi xususiyatga ega: agar o'yinchilardan biri o'zining optimal strategiyasiga rioya qilsa, ikkinchisi uchun undan chetga chiqish foydali bo'lmaydi. Ushbu juftlik strategiyasi o'yinda o'ziga xos muvozanatni shakllantiradi: bir o'yinchi foydani maksimal darajaga, ikkinchisi - minimal darajaga o'tkazishni xohlaydi, har biri o'z yo'nalishi bo'yicha tortadi va ikkalasining ham oqilona harakati bilan muvozanat va barqaror foyda v o'rnatildi. Agar u holda o'yin biz uchun foydali bo'lsa, agar - dushman uchun; o'yin "adolatli" bo'lsa, ikkala ishtirokchi uchun ham bir xil foydali.

Egar nuqtasi bo'lmagan o'yin misolini ko'rib chiqing va uning yechimini (isbotsiz) keltiring. 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. G'olib barmoqlarning umumiy soniga qarab belgilanadi: agar u juft bo'lsa, A yutadi va B dan shu raqamga teng miqdorni oladi; agar g'alati bo'lsa, unda, aksincha, A B ga bu raqamga teng miqdorda to'laydi. O'yinchilar 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, ​​ehtiyotkor xatti-harakatlar bilan biz 3 dan ortiq yo'qotmasligimizga kafolat beramiz. Kichik tasalli, lekin baribir, aytaylik, g'alaba qozongandan ko'ra yaxshiroq - 5, ba'zilarida topilgan. matritsa hujayralari. Bu biz uchun yomon, futbolchi L... Lekin o'zimizga taskin beraylik: raqibning ahvoli bundan ham yomonroq ko'rinadi: o'yin narxi pastroq. oqilona xulq-atvor, u bizga kamida 4 beradi.