O‘yin holatlarining asoslarini o‘rganing
ta cho‘pdan iborat uyumli o‘yinni ko‘rib chiqing. Alice va Bob navbatma-navbat o‘ynaydi, Alice birinchi yuradi. Har bir yurishda o‘yinchi uyumdan , yoki ta cho‘pni olib tashlashi shart. Oxirgi cho‘pni olgan o‘yinchi yutadi.
O‘yin holatini ko‘rinishida ifodalaymiz, bu yerda — qolgan cho‘plar soni.
Masala bayoniga ko‘ra:
Yutuvchi holat — bu joriy o‘yinchi, agar ikkala o‘yinchi ham optimal o‘ynasa, g‘alabani majburan ta’minlay oladigan holat.
Yutqazuvchi holat — bu joriy o‘yinchi, agar raqib ham optimal o‘ynasa, yutqazadigan holat.
Demak, o‘yinning har bir holatini yutuvchi yoki yutqazuvchi deb tasniflash mumkin.
Yuqoridagi o‘yinni ko‘rib chiqamiz:
Bu asosiy qoidani beradi:
Ushbu g‘oyadan foydalanib, yurishlar mumkin bo‘lmagan holatlardan boshlab, barcha holatlarni birma-bir tasniflashimiz mumkin.
Yuqoridagi o‘yin uchun dan gacha bo‘lgan holatlar quyidagicha tasniflanadi:
| Holatlar | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Natija | L | W | W | W | L | W | W | W | L | W | W | W | L |
Bu yerda W yutuvchi holatni va L yutqazuvchi holatni bildiradi.
Endi cho‘plar bilan yana bir o‘yinni ko‘rib chiqing.
holatda o‘yinchi quyidagi shartlarni qanoatlantiradigan istalgan ta cho‘pni olib tashlashi mumkin:
Masalan:
O‘yinni graf ko‘rinishida ifodalashimiz mumkin:
Bu o‘yinda jarayon doimo holatda tugaydi, chunki u yerda hech qanday yurish mumkin emas. Shuning uchun holat yutqazuvchi holatdir.
Barcha holatlarni tasniflagandan so‘ng, yutqazuvchi holatlar qizil rangda va yutuvchi holatlar yashil rangda belgilangan quyidagi rasmni olamiz:
N = 7 -> Boshlang‘ich holat (n = 7)
Alice 3 ta cho‘pni olib tashlaydi -> Yangi holat (n = 4)
Bob 2 ta cho‘pni olib tashlaydi -> Yangi holat (n = 2)
Alice 2 ta cho‘pni olib tashlaydi -> Yangi holat (n = 0)