Mavzu: ko’p qadamli o’yinlar reja

O'yin daraxtida orqaga induksiya
Xulq-atvor strategiyalarining modulli tuzilishi (ya'ni, ular yaratilganligi
Har bir ma'lumot to'plamida mustaqil tasodifiy qarorlar) hisoblash imkonini beradi Nash muvozanatli xulq-atvor strategiyalarini induktiv tarzda, dan barglaridan o'yin daraxtining ildizi. Quyidagi misolda qanday qilib bitta daraja ko'rsatilgan daraxtni hal qilish mumkin va orqaga qaytish uchun qurilish blokini ta'minlaydi ko'p bosqichli o'yinning yechimi. misol. Bir bosqichli fikr-mulohaza o'yinlari Nol yig'indili o'yinni ko'rib chiqing rasmda ko'rsatilgan keng ko'lamli shakl. Xulq-atvorli egar-nuqta strategiyasi mumkin u yerdagi amallarni bajarish orqali topiladi.
1. Har bir tayoq uchun , h = 1, 2, mos keladigan matritsa o'yinini tuzing, bu erda pahga kiradigan qirralar 1-o'yinchi uchun harakatlar, chetlari esa hawaga kiruvchi harakatlardir. O'yinchi 2 uchun harakatlar.

2. Har bir matritsa o‘yini uchun aralash Nash muvozanatini hisoblang. Olingan
2-o'yinchi uchun Nash muvozanati aralash strategiyasi ularning Nash muvozanatidir xulq-atvor strategiyasi.

3. Har bir ma'lumot to'plamiga mos keladigan matritsa o'yinining qiymatini belgilang J_k,
V₁=0, V₂=+1
4. 1-o'yinchi uchun xulq-atvor Nesh muvozanati aralash strategiya bilan berilgan eng qulay to'plamga mos keladi J_k

Bunday yondashuv bilan bir bosqichli o'yinlarni keng shaklda hal qilishimiz mumkin ko'p bosqichli o'yinga rekursiv ravishda, barglardan ildizgacha hujum qiling daraxt. Olingan orqaga induksiya jarayoni quyidagi bosqichlarni bajaradi:

4-rasm: Keng ko'rinishdagi bir bosqichli qayta aloqa o'yinlari.


FOYDALANILGAN ADABIYOTLAR RO’YXATI:
[1] Piter Abbeel va Endryu Y. Ng. “Teskari mustahkamlash orqali shogirdlikni o'rganish”. In: Mashina o'rganish bo'yicha yigirma birinchi xalqaro konferentsiya - ICML '04. 346. Nyu-York, Nyu-York,
[2] Tamer Başar va Geert Yan Olsder. Dinamik hamkorliksiz o'yin nazariyasi, 2-nashr. Ed. SIAM tomonidan. jild. 85. 3. Sanoat va amaliy matematika jamiyati,
[3] Andreas Britzelmeier va Axel Dreves. "Kesishuvlarni boshqarishda Nash muvozanati uchun parchalanish algoritmi". In: Optimallashtirish iyun (2020).
[4] Andrea Censi va boshqalar. "Mas'uliyat, axloq va madaniyatni hisobga olgan holda xulq-atvor qoidalarini qo'llash bo'yicha spetsifikatsiyalar". In:
2019 Robototexnika va avtomatlashtirish bo'yicha xalqaro konferentsiya (ICRA).
[5] Saymon Le Klik, Mak Shvager va Zakari Manchester. «LUCIDGames: Onlayn hidsiz teskari Moslashuvchan traektoriyani bashorat qilish va rejalashtirish uchun dinamik o'yinlar.
[6] Anne Kollin va boshqalar. "Qoidalar kitobidan foydalangan holda mo'ljallangan haydash xulq-atvorining xavfsizligi".