300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийiChomp©
Umumiy o'yinlar soni: 873208
G'alabalarning umumiy soni: 500874
G'alabalarning umumiy soni: 500874
Qanday o'ynaladi:
- Har bir o'yinchi navbat bilan taxtadan shakar oladi.
- Olib tashlangan shakar shakar tanlangan kvadrantga bog'liq.
- Yuqori chap kvadrant tanlangan shakarning yuqoridan va chap qismidan barcha shakarlarni olib tashlaydi, yuqori o'ng yuqori va o'ng tomondan olib tashlanadi, pastki chap pastda va chapdan olib tashlanadi, pastki o'ng rangda tanlangan shakarning pastki va o'ng qismi olib tashlanadi.
Qanday qilib g'olib bo'ladi:
- Oxirgi kafelni olib tashlagan o'yinchi o'yinda g'alaba qozonadi.
1-o'yinchining navbati
Kengash kengligi:
Kengash balandligi:
iChomp o'yini uchun "Fikr uchun ba'zi oziq-ovqatlar" (SFFT) ga kirishni onlayn do'kon dan sotib olish mumkin.
Ushbu qo'llanmada o'rganadigan algoritm o'yinlarning katta sinfini maqbul tarzda o'ynashga qodir, shuning uchun uni o'rganishga vaqt sarflaydi. Kalit mashhur Sprague-Grundy nazariyasi bo'ladi. Agar siz Sprague-Grundy nazariyasini o'rganmasdan iChomp bo'yicha maslahatlarni bilmoqchi bo'lsangiz, tegishli bo'limga o'ting. Batafsil ma'lumotga ega bo'lishdan oldin biz bir nechta atamalarni aniqlashtirishimiz kerak.
Notatsiya
-
Kombinatorial o'yinlar: mukammal ma'lumotga ega bo'lgan ikki kishilik o'yinlar va natija g'alaba qozonish yoki yo'qotish va hech qanday imkoniyat harakatlari.
Xolis o'yinlar: ruxsat etilgan harakatlar ikki o'yinchidan qaysi biri harakatlanayotganiga emas, balki faqat pozitsiyaga bog'liq bo'lgan kombinatorial o'yinlar. Bundan tashqari, to'lovlar nosimmetrikdir. Boshqacha qilib aytganda, 1 va 2 o'yinchi o'rtasidagi yagona farq shundaki, 1 o'yinchi birinchi bo'ladi. Misol: Chomp.
Partizan o'yinlari: xolis bo'lmagan o'yinlar. Misol: shaxmat.
Oddiy o'yin: So'nggi harakatni qilgan o'yinchi g'alaba qozonadi, ya'ni harakat qila olmaydigan o'yinchi, ya'ni olib qo'yadigan hech narsasi yo'q bo'lgan o'yinchi yutqazadi.
Misère Play: So'nggi harakatni amalga oshiradigan o'yinchi YO'QOTADI.
Chomp: bizning o'yin saytimizda taqdim etilgan o'yin, bitta kvadrat va Misère Play-dan foydalanadi.
Bizning o'yin sahifamizda o'ynaladigan Nim o'yini normal yoki misère o'yin ishlatadimi?
- Bizning Nim o'yinimiz misère o'yinidan foydalanadi, chunki so'nggi o'yinni olgan o'yinchi o'yinni yo'qotadi.
Chomp o'yini bizning Chomp o'yin sahifamizda o'ynaydigan oddiy yoki misère o'yin ishlatadimi?
- Chomp o'yini bizning o'yin sahifamizda o'ynagan kabi misère o'yinidan foydalanadi, chunki oxirgi shakarni olgan o'yinchi yo'qotadi.
Nima uchun Chomp uchun oddiy o'yin ishlatish mantiqqa to'g'ri kelmaydi?
- Oddiy o'yin foydalanish so'nggi kafelni olgan kishi g'alaba qozonishini anglatadi. Shuning uchun, birinchi harakat o'yinchi yuqori chap burchagida kafel olib, darhol g'alaba qozonishi mumkin.
Ushbu veb-sahifada o'ynaladigan iChomp o'yini Normal yoki Misère Play-dan foydalanadimi?
- iChomp-da, so'nggi kafelni olgan o'yinchi g'alaba qozonadi, shuning uchun bu o'yin Normal O'yin foydalanadi.
Oddiy o'yinni ishlatish va hali ham bir xil o'yinni uchun Chomp taxtasini qanday o'zgartirish mumkinligi haqida taklifingiz bormi?
-
Yuqori chap burchakdagi (zaharlangan) shakar boshidan yo'qolgan holatdan boshlash mumkin. Bunday taxtadan so'nggi shakarni olish, oddiy o'yinda g'alaba qozonishini anglatadi. Misère Play va bu kafel bilan keyin boshqa o'yinchi uni olishi va yo'qotishi kerak edi, bu xuddi shu natija.
Shunday qilib, chap yuqori burchak kafeliga ega bo'lish va Misère Play foydalanish yoki o'yin boshidan bu kafelga ega bo'lmaslik va Normal O'yindan foydalanish ham aynan bir xil o'yin.
iChomp haqida
- iChomp o'yini to'rtta birlashma bo'lishi uchun mo'ljallangan Chomp o'yinlar bir vaqtning o'zida o'ynaydi, barchasi Normal o'yin qoidasi ostida. Bu o'yinni quyida tushuntiriladigan ikki jihatdan yanada chiroyli qiladi. Bundan tashqari, quyida tavsiflangan Sprague-Grundy nazariyasini qo'llasa, iChomp Chompdan ko'ra qiyin emas.
Sprague-Grundi nazariyasi haqida
-
U tegishli bo'lgan o'yinlar sinfi quyidagilardir xolis kombinatorial o'yinlar. Ushbu nazariya biz uchun ikkita narsani qiladi:
- Bu bizga har bir o'yin uchun (ya'ni har bir pozitsiya) raqamni (biz uni SG-qiymati deb ataymiz) aniqlaydigan algoritmni beradi, shunda raqam 0 bo'lsa va faqat yutqazilgan pozitsiya bo'lsa (kombinatorial o'yin nazariyasi bo'yicha adabiyotda 'P-pozitsiya' deb nomlanadi, 'P' esa 'p'revious o'yinchining g'alaba qozongan harakatni o'ynaganligini ko'rsatadi). Ya'ni, agar bu SG-qiymati 1, 2, 3, ... keyin bu g'alaba qozonadigan pozitsiyadir (adabiyotda "N" pozitsiyasi deb ataladi). Bunday holda, kim "n'ext" harakat qilsa, optimal o'ynasa, g'alabani kuchaytirishi mumkin.
- SG nazariyasining ikkinchi maqsadi bir vaqtning o'zida bir nechta pozitsiyalardan iborat o'yinni qanday g'alaba qozonishni tasvirlashdir. Bunday kombinatsiyalangan o'yinda harakat birlashtirilgan pozitsiyalardan har qanday birida bitta harakat qilish orqali amalga oshiriladi.
Bilish kerak bo'lgan narsa - bu birlashgan pozitsiyalarning har birining SG-qiymati. Ularni olish uchun ushbu birlashgan pozitsiyalarning har birida har bir harakatdan keyin SG-qiymatini bilish kerak. Bular optimal uchun ham kerak.
Masalan: Nim o'yinida bitta yoki ikki yoki undan ortiq o'yinlar qoziqi bor. Agar biz har bir qoziqni yolg'iz uchun SG-qiymatini bilsangiz, SG-nazariyasi bu qoziqlarning har qanday biridan tegishli miqdordagi o'yinlarni olib qo'yib, bu qoziqlarning barcha bilan qanday optimal kerakligini aytadi.
Nima uchun iChomp?
-
iChomp - bu ushbu veb-sahifada o'ynaladigan Caribou Contests tomonidan taqdim etilgan Chompning yangi versiyasi. iChompdagi "i" "izotropik" degan ma'noni anglatadi, ya'ni barcha yo'nalishlar teng muomala qilinadi.
Oddiy Chompda bitta kafelni olib tashlash, shuningdek, uning sharq va janubidagi barcha kafellarni olib tashlaydi. Shunday qilib, Sharq va Janubning yo'nalishlari alohida rol o'ynaydi.
iChomp-da, boshqa yo'nalishlardagi barcha kafellar, shuningdek, markazga eng yaqin bo'lgan olib tashlangan kafel qaerda bo'lishiga qarab, olib tashlanishi mumkin. Bu kafel, masalan, markazining shimoliy-g'arbiy yo'nalishida bo'lsa, keyin Shimol yoki G'arbdagi barcha kafellar ham olib tashlanadi.
Sun'iy qoidalarni olib tashlash, masalan, Sharq va Janubning maxsus ekanligi qoidasi odatda o'yinni matematik jihatdan yanada chiroyli qilish uchun hisoblanadi.
Chomp bilan taqqoslaganda iChompning yana bir go'zalligi bor.
Chompda chap yuqori burchakdagi kafel boshqa kafel bilan solishtirganda alohida ahamiyatga ega. Agar bu taxtada yagona kafel bo'lsa, o'yin tugadi. Agar boshqa kafel olib tashlangan bo'lsa, o'yin davom etadi. Bir burchak kafel holda Chomp boshlash mumkin, shuning uchun barcha kafellar bir xil muomala qilinadi, lekin bu o'zi keyin bu kafel holda o'yinni boshlash uchun nima uchun sun'iy qoida bo'ladi va boshqa kafellar holda emas.
iChomp yilda barcha kafel boshida mavjud va barcha bir xil muomala qilinadi. Har qanday kafel o'yinni avtomatik ravishda tugatmasdan olib tashlanishi mumkin.
Ba'zi savollar tug'iladi:
iChomp "Normal o'yin" dagi kombinatsiya yoki 4 trivial Chomp o'yinlari bo'lgani uchun arzimas o'yinmi?
-
Javobi esa yo'q. Masalan, bitta o'yinlar uyumi bilan Nim o'yini ahamiyatsiz. "Oddiy o'yin" ostida bitta harakatda butun qoziqni olib tashlash va g'alaba qozonish mumkin. Nim ostida "Misère Play", bitta o'yindan boshqa barchasini olib tashlash va g'alaba qozonish mumkin. Shunga qaramay, bunday 1-qoziq Nim o'yinlarining bizning Nim o'yinlar sahifamizdagi kabi ko'p qoziqli Nim o'yiniga kombinatsiyasi ahamiyatsiz emas.
Xuddi shunday bu erda: burchak kafel va "Normal o'yin" yordamida bitta chomp o'yin ahamiyatsiz, chunki bir harakatda barcha kafellarni olib tashlash va g'alaba qozonish mumkin. Ammo bunday 4 ta o'yinning kombinatsiyasi unchalik muhim emas.
Taqqoslash natijasi
- IChomp matematik jihatdan Chompdan ko'ra chiroyli, chunki u sun'iy ravishda janubi-sharqiy yo'nalishlarni ajratib qo'ymaydi va bitta kafelga alohida rol bermaydi. Narxi shundaki, iChompni Chompga qaraganda ancha qiyin, ammo SG-nazariyasi yordam beradi. iChomp pozitsiyalarining SG-qiymatini 4 baravar katta bo'lgan osongina hisoblash va shu bilan iChompni 4 barobar katta o'lchamga qadar optimal tarzda qanday o'ynashni bilish uchun Chomp pozitsiyalarining SG-qiymatini bilish kifoya.
-
Javobi esa yo'q. Masalan, bitta o'yinlar uyumi bilan Nim o'yini ahamiyatsiz. "Oddiy o'yin" ostida bitta harakatda butun qoziqni olib tashlash va g'alaba qozonish mumkin. Nim ostida "Misère Play", bitta o'yindan boshqa barchasini olib tashlash va g'alaba qozonish mumkin. Shunga qaramay, bunday 1-qoziq Nim o'yinlarining bizning Nim o'yinlar sahifamizdagi kabi ko'p qoziqli Nim o'yiniga kombinatsiyasi ahamiyatsiz emas.
SG-nazariyasida XOR deb nomlangan matematik operatsiya kerak. Agar siz u bilan tanish bo'lmasangiz, keyingi bo'lim foydali bo'ladi.
XOR nima?
-
Eksklyuziv yoki qisqacha XOR - bu ikkilik ma'lumotlar ustida amalga oshiriladigan mantiqiy operatsiya. Ikkilik ma'lumotlardan foydalanib, biz ikkita qiymatdan biriga ega bo'lishimiz mumkin, haqiqiy (=1) yoki yolg'on (=0). Ikkita ikkilik qiymatlar bo'yicha XOR operatsiyasi quyidagi jadval orqali aniqlanadi.
a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
Ushbu operatsiyani 1 (true) yoki 0 (yolg'on) qiymatlarida ishlatish oson bo'lsa-da, hisoblashlarimiz uchun biz ikkita sonda XOR ni bajara olishimiz kerak. Buni ham amalga oshirish mumkin, ammo xorni bajarishdan oldin yangi qadam talab etiladi.
Avval nima bo'lishi kerak bo'lsa, raqamlarni binar tizimga aylantirish kerak, ya'ni uni 10 bazasidan 2 bazasiga o'tkazish kerak.
Qanday qilib 10 bazasidan 2 bazasiga raqamni o'zgartirish mumkin?
-
Quyidagi algoritm 10 bazasidagi n sonini asosiy 2 formatiga aylantirish uchun ishlatilishi mumkin. (Eslatib o'tamiz, 20 = 1):
- 2 ning eng yuqori eksponentini toping, shunda 2p ≤ n.
- 1ni yozib oling va 2p dan n.
- Agar p = 0 bo'lsa, to'xtating, else 1ni p dan olib tashlang va davom eting.
- Agar 2p > n bo'lsa, 0 ni yozing, aks holda 2p ni n dan olib tashlang va 1 ni yozing.
- 3 bosqichiga qayting.
Ushbu algoritmga muvofiq yozilgan 1 va 0 ketma-ketligi n sonining ikkilik ifodasi bo'ladi. Misol:
Keling, 13 sonini asosiy 2 formatiga o'zgartiraylik. Biz 2ning eng yuqori kuchini topishdan boshlaymiz 13 dan kam yoki teng, bu 2,3, yoki 8. Keyin 1ni yozamiz va 8 dan 13 ni olib tashlaymiz, bu bizga 5 beradi. Keyin 2 (3−1) = 22 = 4 ni tekshiramiz. 4 ≤ 5 dan beri biz 1ni yozamiz va 4 dan 5 ni olib chiqamiz, bu bizga 1 beradi. 2 ning keyingi pastki kuchi 21 = 2. 2 > 1, shuning uchun biz 0 ni yozamiz. 2 ning keyingi kuchi 20 = 1 bo'lib, bu bizning n of 1 ga teng, shuning uchun biz 1 ni yozamiz va 1 dan 1 olib chiqamiz, bizga 0 beramiz. Chunki p = 0 biz algoritmni to'xtatamiz. Shuning uchun 13 (10 bazasi) = 1101 (2 bazasi).
Ikkita sonni ikkilik namoyishga aylantirganimizdan so'ng, endi ikkita ikkilik sonning tegishli raqamlari ustida XOR operatsiyasini amalga oshirishimiz mumkin. Natijada, XOR qiymatini kelajakda ishlatish uchun qulayroq bo'lsa, keyinchalik 10 bazasiga aylantirilishi mumkin bo'lgan ikkilik son. Misol:
Keling, 6 va 13 sonlarining XORini hisoblaylik. Ushbu ikki sonning ikkilik ifodasi 6 = 110 va 13 = 1101. Avvaliga biz kichik sonning chap tomoniga 0 ni qo'shamiz, shunda ikkalasi ham bir xil raqamlarga ega bo'ladi, shuning uchun 6 = 0110. Keyin biz ularni tartiblash va har bir raqamda operatsiyani bajarish orqali XORni amalga oshirishimiz mumkin:
0110 XOR 1101 ------ 1011
Shunday qilib, 6 XOR 13 = 1011 (2 bazasi) = 1×23+0×22+1×21+1×20 = 8+2+1 = 11 (10 bazasi).
Keling, XOR haqidagi tushunchamizni bir nechta savollar bilan tekshiraylik.
Har qanday m son uchun m XOR m nima?
- Har qanday m son uchun m XOR m = 0 bor, chunki 0 XOR 0 = 0 va shuningdek 1 XOR 1 = 0.
Har qanday n, m sonlari uchun n XOR m = m XOR n?
- Ha, chunki 1 XOR 0 = 0 XOR 1 (=1).
Har qanday m son uchun 0 XOR m nima?
- 0 XOR m = m chunki 0 XOR 0 = 0 va 0 XOR 1 = 1.
Agar m soni n dan m XOR n raqami bilan XOR n bo'lsa, unda m ning qaysi raqamlari aylantiriladi?
- Agar m dagi raqam 0 bilan XOR bo'lsa, raqam o'zgarmaydi (chunki 0 XOR 0 = 0 va 1 XOR 0 = 1). Agar m dagi raqam XOR 1 bilan XOR bo'lsa, raqam aylantiriladi (chunki 0 XOR 1 = 1 va 1 XOR 1 = 0). Shunday qilib, XOR n n bilan mos keladigan raqam 1 bo'lgan barcha raqamlarni aylantiradi.
-
Quyidagi algoritm 10 bazasidagi n sonini asosiy 2 formatiga aylantirish uchun ishlatilishi mumkin. (Eslatib o'tamiz, 20 = 1):
Chomp pozitsiyasining SG qiymatini hisoblash uchun algoritm.
-
Quyidagi algoritm har qanday xolis kombinatorial o'yinda har qanday pozitsiyaning SG-qiymatini hisoblaydi P Biz buni Chomp o'yinidan foydalanib tushuntiramiz.
- Mag'lub bo'lgan har bir o'yin pozitsiyasi SG-qiymati 0 ni oladi. Chompda bitta kafel (Shimoliy-G'arbiy burchagida) keyingi harakatsiz yagona pozitsiyadir va shuning uchun SG-qiymati 0 bilan yo'qotilgan pozitsiya.
- P pozitsiyasidan bir harakatda erishish mumkin bo'lgan barcha pozitsiyalarning SG-qiymatlari kerak. Shunday qilib, agar pozitsiya P n kafel bor bo'lsa, u erda n-1 mumkin harakatlar bor: Shimoliy-G'arbiy burchagida kafel tashqari, boshqa barcha kafellar o'sha kafel Janubiy / Sharqiy barcha kafel bilan birga olib tashlanishi mumkin.
- P pozitsiyasining SG-qiymati n-1 erishiladigan SG-qiymatlari ro'yxatida bo'lmagan eng kichik salbiy bo'lmagan sondir.
Ushbu algoritm rekursivdir, chunki P pozitsiyasining SG-qiymatini hisoblash uchun biz bir harakatda P dan erishiladigan barcha pozitsiyalarning SG-qiymatlariga muhtojmiz. Bu hali ham ishlaydi, chunki zarur SG-qiymatlar kam kafel kichik pozitsiyalar va eng kichik mumkin holat SG-qiymati (Shimoliy-G'arbiy burchagida bir kafel) ma'lum, chunki.
Yuqoridagi o'yindagi 3rd xususiyatini katta taxta kengligi va balandligini tanlab, "Randomize Board" ni bosish orqali tekshirishga harakat qiling.
- Agar sichqonchani kafel ustiga harakatlantirganingizda, keyin bu kafel va olib tashlanadigan boshqa kafellar ta'kidlanadi. Bu kafeldagi raqam "Normal o'yin" ostida kvadrantning SG-qiymati ("Misère Play" emas) bu kafel bosilgan taqdirda paydo bo'ladi. Kvadrat yonidagi 'SG qiymati Base Ten:' matnida ko'rsatilgan son kvadrant ichida ko'rsatiladigan eng kichik son ekanligini tekshirishingiz mumkin. Bundan tashqari, agar siz kafelni bossangiz, unda mavjud bo'lgan raqam yangi pozitsiyaning "SG qiymati Base Ten:" sifatida ko'rsatiladi.
SG-qiymatlarini aniqlashni qanday tezlashtirish mumkin:
Bir xil pozitsiyaga bir harakatda turli pozitsiyalardan erishish mumkin va katta pozitsiyaning SG-qiymatini hisoblashda qayta-qayta paydo bo'lishi mumkinligi sababli, uni qayta-qayta hisoblash uchun harakatlarni behuda sarflash bo'ladi. Shuning uchun, P pozitsiyasining SG-qiymati hisoblangandan so'ng, uni keyinchalik foydalanish uchun saqlash kerak.
Agar barcha pozitsiyalarning SG-qiymatini ba'zi bir hajmgacha hisoblashni istasangiz, quyidagi yondashuv foydalidir. Biz bitta kafel bilan (Shimoliy-G'arbiy burchagida) SG-qiymati nol bilan yagona pozitsiyani tayinlashdan boshlaymiz. Keyin, biz yuqoridagi algoritmdan foydalanib, barcha pozitsiyalarning SG qiymatlarini 2 kafel bilan, keyin 3 kafel va hokazo bilan hisoblash.
iChomp pozitsiyasining SG-qiymatini hisoblash uchun algoritm
-
iChomp pozitsiyasi 4 Chomp pozitsiyasidan iborat, kengashning har bir kvadrantida bittadan.
- Dastlab biz Chomp "Misère Play" qoidasidan foydalanib, 4 Chomp pozitsiyalarining har birining SG-qiymatini aniqlaymiz. Bo'sh kvadrant Chomp pozitsiyasi emas, shuning uchun biz unga −1 qiymatini beramiz.
- Keyin har bir qiymatga 1 qo'shamiz.
- Natijada paydo bo'lgan 4 sonlarning har biri uchun biz ikkilik namoyishni hisoblaymiz.
- Biz 4 ikkilik qiymatlarning XOR qiymatini hisoblaymiz va ushbu pozitsiyaning SG-qiymatini (ikkilik shaklda) olamiz. Agar qiymat nolga teng bo'lsa, u yutqazgan pozitsiyadir, aks holda u yutuqli pozitsiyadir.
-
Biz "Normal o'yin" ostidagi Chomp pozitsiyasining SG-qiymatini "Misère Play" ostidagi SG-qiymatidan olish uchun 1 qo'shamiz. Quyidagi teorem buni tushuntiradi.
Teoremas:
--------
"Normal o'yin" ostida Chomp pozitsiyasining SG-qiymatini olish uchun (ya'ni, oxirgi kafelni olib, Chomp o'ynashning umumiy usuli bo'lmagan o'yinni g'alaba qozonadi) "Misère Play" ostida xuddi shu pozitsiyaning SG-qiymatiga 1 qo'shish kerak (ya'ni, Chomp o'ynashning keng tarqalgan usuli bo'lgan oxirgi kafel yo'qotadi).
Teoremani induksiya bilan isbotlashga harakat qila olasizmi?
-
Isbot (induksiya orqali (va juda batafsil)):
Asosiy holat (1 kafel):
-------------------
"Normal o'yin" ostida kafelsiz bo'sh taxta yo'qotilgan pozitsiyadir va shuning uchun SG-qiymati nolga ega. Bundan tashqari, "Normal o'yin" ostida bitta kafel bilan taxta uchun (yuqori chap burchagida) yagona mumkin bo'lgan harakat SG-qiymati 0 bilan pozitsiyani beradi bu kafelni olib tashlashdir. Shunday qilib, "Normal o'yin" ostida harakat bilan erishib bo'lmaydigan eng kichik salbiy bo'lmagan SG-qiymati 1 bo'ladi, shuning uchun "Normal o'yin" ostida bitta kafel bo'lgan pozitsiyaning SG-qiymati.
"Misère Play" ostida bitta kafelga ega bo'lish SG-qiymati 0 bilan yo'qotilgan pozitsiya.
Shunday qilib, 1 kafel uchun 'Normal o'yin' SG-qiymati 'Misère Play' qiymatidan 1 kattaroqdir.
Induktiv qadam
---------------
Induksiya gipotezasi (n kafel):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Biz n raqami mavjud deb taxmin qilamiz, shuning uchun ≥1 va ≤n kafellari bo'lgan barcha pozitsiyalar uchun 'Normal o'yin' ostidagi SG-qiymati 'Misère Play' ostida bir kattaroqdir. Induksiya da'vosi (n + 1 kafel):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Biz bu keyin n + 1 kafel bilan barcha postlar uchun ham shunday ekanligini ko'rsatadi.
Indüksiyon qadam (n kafel → n + 1 kafel):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Har qanday pozitsiya uchun "Misère Play" va "Normal O'yin" Bundan tashqari "Normal O'yin" ham yuqori chap burchak kafel orqali barcha kafel olish imkonini beradi shu harakatlar ruxsat beradi.
Agar pozitsiyada n + 1 kafel bo'lsa, unda harakat qilish indüksiyon gipotezasini qo'llashimiz mumkin bo'lgan eng ko'p n kafel bilan pozitsiyani hosil qiladi:
Shuning uchun "Normal o'yin" ostida olinadigan SG-qiymatlari ro'yxati "Misère Play" ostida olingan SG-qiymatlari ro'yxatidan olinadi, ularning har biri 1 ga oshdi va barcha kafellarni olish orqali 0 qiymatini qo'shib olinadi.
Shuning uchun "Normal o'yin" ostida olinmaydigan eng kichik salbiy bo'lmagan son, "Misère Play" ostida olinmaydigan eng kichik salbiy bo'lmagan sondan 1 yuqori. Boshqacha qilib aytganda, n + 1 kafel bilan original pozitsiya uchun 'Normal o'yin' ostidagi SG-qiymati 'Misère Play' ostidagi SG-qiymatidan bir yuqori. ∎ (Bu isbotni yakunlaydi.)
-
Isbot (induksiya orqali (va juda batafsil)):
Nima uchun biz "1" ni qo'shdik?
iChomp qanday kerak
-
Maqsad natijada paydo bo'lgan pozitsiyaning SG-qiymati nolga teng bo'lgan harakatni amalga oshirishdir. Qanday harakat qilsa ham, u 4 kvadratlardan birida bo'lishi kerak. Bu shuni anglatadiki, harakat amalga oshirilgan pozitsiyaning SG-qiymati va boshqa 3 o'zgarmagan kvadrantlarning SG-qiymatlari barcha XOR'ed nolga teng bo'lishi kerak. Bu faqat boshqa 3 SG-qiymatlari XOR harakatni amalga oshirgandan keyin yangi kvadrantning SG-qiymatini aniq bersa va faqat shunday bo'ladi (ushbu bayonotning isboti uchun quyida ko'rib chiqing). Shuning uchun protsedura quyidagicha:
- (oddiy) Holat: 4 kvadrantdan ikkitasi bir xil SG qiymatiga ega. Keyin bu ikki teng qiymatning XOR nolni beradi, shuning uchun ikkala kvadrat ham e'tiborsiz qoldirilishi kerak.
- Agar boshqa ikkita kvadrant ham teng SG-qiymatlarga ega bo'lsa, unda butun pozitsiyaning SG-qiymati nolga teng va pozitsiya yo'qotilgan pozitsiyadir. Keyin mag'lubiyatni kechiktirish va raqibning optimal o'ynamasligi uchun ko'proq imkoniyatlarga ega bo'lish uchun har qanday kvadratdan faqat bitta kafelni olib tashlang.
- Agar boshqa ikkita kvadrant teng bo'lmagan SG-qiymatlariga ega bo'lsa, u holda katta SG-qiymatiga ega bo'lgan kvadrantni tanlang. Boshqa kvadratning SG-qiymatiga teng bo'lgan raqam yozilgan kafelni bosish orqali u erda harakat qiling. Natijada juft teng SG-qiymati va umumiy XOR qiymati nolga teng bo'lgan 2 juft kvadrant - yo'qotilgan pozitsiya.
- (umumiy) Holat:
- 4 iChomp-SG-qiymatlarini hisoblab chiqing, aytaylik w,x,y,z 4 kvadrantlarining (har biri ushbu kvadrantning Chomp-SG-qiymatlari plyus 1) va ularni Base Two-ga aylantiring.
- Keyin eng chap pozitsiyani toping, shunday qilib, ushbu 4 sonning toq soni bu holatda 1ga ega bo'ladi. Masalan, 4 raqamlari
w=11011
keyin 1 bilan eng chap pozitsiya 5-pozitsiyadir (pozitsiyalarni o'ngdan hisoblashni boshlaymiz). W va Y u erda 1 bor, ya'ni ikki son (w va y) u erda 1 bor. Ikki teng son, shuning uchun biz bu pozitsiyani e'tiborsiz qoldirishimiz kerak. Keyingi pozitsiya 4-pozitsiya, yana o'ngdan sanab chiqiladi. Bu erda ham teng ko'plab sonlar 1 bor (w va x). Biz ham bu pozitsiyani e'tiborsiz qoldirishimiz kerak. 3-pozitsiyada 3 ta raqam mavjud bo'lib, u erda 1 (x, y, z). 3 - toq son, shuning uchun biz ushbu 3 sondan istalgan birini tanlaymiz, masalan, Y=10100.
x= 1101
y=10100
z= 100- Agar barcha pozitsiyalarda 1 sonining teng bo'lsa, u holda barcha 4 sonning XOR qiymati nolga teng va bu yo'qotilgan pozitsiya. Misol uchun
w'=11011
har bir holatda 1 ning teng soniga ega bo'ling. Ushbu 4 sonning XOR qiymati nolga teng, bu yo'qotilgan pozitsiya. Bu holda, mag'lubiyatni kechiktirish va raqibning optimal uchun ko'proq imkoniyatga ega bo'lish uchun har qanday kvadratdan faqat bitta kafelni olib tashlaydi.
x'= 1011
y'=10110
z'= 110 - Agar kamida bitta pozitsiyada to'g'ri ko'p 1 bo'lsa, biz yuqoridagi y kabi bir sonni topdik (y 'emas).
- Biz boshqa 3 sonlarni XOR qilamiz, bizning holatimizda w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011. Bu qiymat har doim biz tanlagan sondan kamroq, bu erda y = 10100 (quyida keltirilgan dalillarga qarang).
- Tanlangan qiymat bilan kvadrantda, bu erda y, biz SG-qiymati bo'lgan pozitsiyaga ega bo'lgan pozitsiyani amalga oshiramiz, bizning misolimiz 10011 bo'yicha.
- Qaysi kafelni bosishni bilish uchun biz 10011 ni Base Ten ga aylantiramiz (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) va 19 raqami bilan kafelni bosing yoki 10100 − 10011 = 1 ikkilik shaklida hisoblaymiz va buni Base Ten (= 1) ga aylantiramiz va bosish uchun kafel 1 dan y (= 20) dan kam qiymatga ega bo'lishi kerakligini bilamiz, ya'ni 19 raqami yozilgan kafelni bosish.
Nima uchun bu g'alaba qozongan harakat?
-
Iltimos, quyidagi savollarga javob berish uchun yuqorida ko'rsatilgandek XOR xususiyatlari haqida o'zingizni eslating.
agar siz = w XOR x XOR y XOR z bo'lsa, unda y XOR u nima?
-
Avval o'rganilgan XOR qoidalaridan foydalanib,
y XOR u
= y XOR w XOR x XOR y XOR z
= y XOR y XOR w XOR x XOR z
= 0 XOR w XOR x XOR z
= w XOR x XOR z.
Agar y y bilan almashtirilsa, u holda barcha 4 SG-qiymatlarining yangi XOR nima?
-
Yangi XOR bo'ladi
(y XOR u) XOR w XOR x XOR z
= (w XOR x XOR z) XOR (w XOR x XOR z)
= 0
m tufayli XOR m = 0 har qanday m son uchun.
Bu shuni anglatadiki, butun kengashning yangi SG-qiymati nolga teng bo'ladi, shuning uchun bu mo'ljallangan yo'qotish pozitsiyasi bo'ladi.
Nima uchun SG-qiymati y ni past qiymatga o'zgartiradigan harakat mavjud bo'lishi kerak?
- Ta'rifga ko'ra: Pozitsiyaning SG-qiymati y ga teng, agar va faqat SG-qiymatlari 0,1,..,(y-1) bo'lgan pozitsiyalarni yaratadigan harakatlar mavjud bo'lsa. Shunday qilib, agar y > (y XOR u) bo'lsa, unda SG-qiymatini (y XOR u) yaratuvchi harakat bo'lishi kerak < y.
Javob berish kerak bo'lgan narsa:
Nima uchun y > (y XOR u) ni qondiradigan SG-qiymati y bo'lgan kvadrant bo'lishi kerak?
-
Eslatma:
Ilgari, xorning xususiyatlari haqida bilganimizda, biz ko'rdik: XOR u u ga tegishli raqam 1 bo'lgan barcha raqamlarni aylantiradi.
Agar siz 0 ≠ bo'lsangiz, u 2 ning eng yuqori kuchini o'z ichiga oladi, masalan, 2p. 2ning bu kuchi 4 SG-qiymatlarining toq sonida sodir bo'lishi kerak, shuning uchun kamida bittada, deylik y.
Bu shuni anglatadiki, y XOR u hisoblashda, bu 1 in y u ga mos keladigan 1 tomonidan 0 ga aylantiriladi. Ushbu 1ning o'ng tomonida joylashgan y ga aylantirilgan boshqa ikkilik raqamlar ham bo'lishi mumkin. Y − (y XOR u) ning eng katta qiymati agar bu 1ning o'ng tomonidagi y raqamlari nol bo'lsa va 1ning o'ng tomonidagi sizdagi raqamlar bir bo'lsa, paydo bo'ladi. Bunday holda u = 111..111 y = *100..00 (bu erda * har qanday raqam soni degan ma'noni anglatadi) y XOR u = *011..11 ga o'zgartiradi. Ularning farqi:
y − (y XOR u)
= 2p − (2p−1 + 2p−2+ ... +20)
= 2p − (2p−1 + 2p−2+ ... +20)× (2-1)/(2-1)
= 2p − (2p−1)/(2-1)
= 1.
Bu shuni anglatadiki, y kamida bitta kattaroq (y XOR u). ∎
-
Avval o'rganilgan XOR qoidalaridan foydalanib,
Ushbu algoritmni "Qiyinchilik: Qiyin" ga qarshi va g'alaba qozonish orqali sinab ko'ring.
-
Boshlash uchun "Qiyinlik" ni tanlang, bu esa kompyuterda maqbul o'ynashni kafolatlaydi. Agar siz hali ham g'alaba qozonsangiz, siz har bir harakatni optimal tarzda o'ynadingiz.
Har bir kvadratning SG-qiymati 10 va 2 bazasida ko'rsatiladi. Ushbu raqam kvadrantda koʻrsatilmagan eng kichik qiymat ekanligini tekshiring.
Quyida u deb ataladigan barcha 4 SG-qiymatlarining XOR ko'rsatiladi. Agar ikkita 1 bir xil holatda bo'lsa, 4 SG-qiymatlaridagi har qanday juftlikni 0 ga o'zgartirib, sizning qiymatingizni tekshiring. Keyin qolgan 1-larni bitta ikkilik songa joylashtiring va uni 10 bazasiga aylantiring.
Harakatni amalga oshirish uchun yuqorida aytib o'tilganidek:
- 4 SG-qiymatlaridan birini toping, masalan, y, u dagi eng chap 1 bilan bir xil holatda 1 bor.
- Hisoblash y XOR u ikkilik shaklda va keyin uni 10 bazasiga o'zgartiring.
- Y-kvadratda hisoblangan y XOR u bilan kafelni bosing.
- G'alaba qozonmaguningizcha harakatlaringizni shu tarzda o'ynang.
- Yana o'ynang, lekin bu safar tasodifiy harakat bilan boshlang. Agar siz omadli bo'lmasangiz va tasodifan g'alaba qozonish harakatini o'ynamasangiz, siz keyin optimal o'ynashga harakat qilsangiz ham, bu o'yinda g'alaba qozona olmaysiz.
Yuqoridagi barcha ko'rsatmalar 4 kvadrantning SG-qiymatini bilishini taxmin qiladi, ya'ni har bir mumkin bo'lgan harakatdan keyin har bir kvadrantning SG-qiymatini biladi.
Ba'zi Chomp pozitsiyalarining SG-qiymatlarini topa olasizmi ("Misère Play")?
-
Pozitsiyaning SG-qiymatini hisoblash uchun undan bir harakatda erishish mumkin bo'lgan barcha pozitsiyalarning SG-qiymatlarini bilish kerak. Bu rekursiv jarayon. Shuning uchun biz kafel kam soni bilan pozitsiyalar bilan boshlash va yuqoriga yo'l ishlash kerak.
SG-qiymatlarini 1,2,3 topa olasizmi,... Bir qatordagi kafellar?
-
Faqat 1 kafel (yuqori chap burchakda) bo'lishi SG-qiymati 0 bilan yo'qotilgan pozitsiyadir.
2 kafel mavjud (yuqori qatorda yoki chap ustunda), faqatgina mumkin bo'lgan harakat SG-qiymati 0 bilan ko'rsatilgan pozitsiyani qo'lga kiritadigan bitta kafel olishdir. Shunday qilib, harakat bilan erishib bo'lmaydigan eng kichik salbiy bo'lmagan SG-qiymati 1 bo'ladi, shuning uchun 2 kafelli pozitsiyaning SG-qiymati 1.
SG-qiymati shuning uchun 2 bo'ladi, yuqori qatorda barcha 3 kafel, bir 1 yoki 2 kafel olish va SG-qiymatlarni 1 va 0 olish mumkin, shuning uchun SG-qiymati 2.
Xuddi shunday, yuqori qatordagi n kafellarning SG-qiymati n-1.
Keling, 3 kafel, 2 yuqori qatorda va 2 chap ustunda ko'rib chiqaylik. Biz faqat 1 kafelni olib tashlashimiz va 1 SG-qiymatiga erishishimiz mumkin, lekin 0 emas, shuning uchun olinmaydigan eng kichik SG-qiymati 0 bo'lib, shuning uchun bu pozitsiyaning SG qiymati. Bu yo'qotilgan pozitsiya.
m + n-1 kafellari yuqori qatorda va m kafellari chap ustunda bo'lgan pozitsiyaning SG-qiymatini topa olasizmi?
- Bir faqat yuqori qatordagi yoki chap ustundan kafel olib tashlash mumkin. Shuning uchun SG-qiymati ikkita kvadrantga ega bo'lish bilan bir xil, biri yuqori qatorda n kafel va biri chap ustunda m kafel bilan. Shunday qilib, SG qiymati (m-1) XOR (n-1) ga teng. Bu NIM-ni ikkita qoziq va "Normal o'yin" qoidasi bilan bilan bir xil, bu erda o'yinlar bir harakatda faqat bitta qoziqdan olib tashlanishi mumkin.
Agar faqat yuqori ikki qatorda kafel bilan bir lavozimning SG-qiymatini topa olasizmi?
-
Ushbu pozitsiyalar uchun formulalar ancha murakkab. Bizga ma'lumki, ular ilgari nashr etilmagan. Siz kafel kichik bir qator uchun ularni tekshirish uchun harakat qilib ko'rish mumkin.
N va m yuqori va ikkinchi qatordagi kafellar soni bo'lsin.
Agar n ham boʻlsa
k = (n-2)/2
agar m hatto bo'lsa,
a = m/2
SG qiymati = 2*k+a+1
else (m - toq)
a = (m-1)/2
agar ≤ (k/2) bo'lsa, SG-qiymati = 2*k-a
boshqa SG-qiymat = 3*(k-a)
else (n - toq)
k = (n-1)/2
agar m hatto bo'lsa,
a = m/2
agar ≤ (k/2) bo'lsa, SG-qiymati = 2*k-a
boshqa SG-qiymat = 3*(k-a)
else (m - toq)
a = (m-1)/2
SG qiymati = 2*k+a+1
Yuqoridagi oʻyin taxtasi yordamida formulalar toʻgʻriligini tekshiring.
- kafel faqat ikki qatorli kvadrat bor, shunday qilib, minimal taxta balandligi tanlang. Yuqoridagi formulalarni qo'llagandan so'ng, "SG Value Base Ten:" ostida ko'rsatilgan qiymatdan bir past bo'lgan SG-qiymatini olishingiz kerak, chunki formulalar "Misère Play" uchun, iChomp esa "Normal o'yin" dan foydalanadi.
-
Faqat 1 kafel (yuqori chap burchakda) bo'lishi SG-qiymati 0 bilan yo'qotilgan pozitsiyadir.
SG-qiymatlarini bilmasdan qanday qilib iChompni mumkin?
-
Biz bir kuzatuvdan boshlaymiz: Chomp qoidalari Sharqiy va Janubiy yo'nalish o'rtasida farq qilmaydi.
Yuqori chap burchagidan boshlanadigan diagonalizda aks ettirish ostida bir-biriga ko'zgu simmetrik bo'lgan ikki pozitsiyaning SG-qiymatlari uchun qanday natija beradi?
- Sharqiy va Janubiy yo'nalishlar bir-biriga aks etganligi sababli, bu ikkalasi ham bir xil SG-qiymatiga ega bo'lishi kerakligini anglatadi.
2 kvadrantlari kvadrantlarning aylanishi va / yoki diagonal aks ettirish ostida nosimmetrik bo'lgan pozitsiyalarga ega bo'lsa, bu iChomp uchun nimani anglatadi?
- Ikkala kvadrat ham e'tiborsiz qoldirilishi mumkin. Nima uchun? Har ikkala kvadrat ham misère o'yin ostida bir xil SG-qiymatiga ega va 1 qo'shib keyin normal o'yin ostida bir xil SG-qiymati. Bu ikki teng qiymatning XOR qiymati nolni beradi. Shuning uchun, har ikkala kvadrat ham butun kengash pozitsiyasining SG-qiymatiga hissa qo'shmaydi.
Shuning uchun qaysi o'yin strategiyasi ishlashi kerak?
-
Har bir juftlikdagi kvadrantlar teng SG-qiymatlarga ega bo'lgan nosimmetrik pozitsiyalarga ega bo'lishi uchun ikki juft kvadrantni yaratadigan harakat qilish kerak, masalan, A va A, va B va B. Keyin, barcha 4 kvadrantlar kombinatsiyasining SG-qiymati A XOR A XOR B XOR B = 0 XOR 0 = 0 yoki (A XOR B) XOR (A XOR B) = 0 shuning uchun har doim 0. Biri yo'qotish pozitsiyasini yaratdi.
Xuddi shunday, ikkita nosimmetrik kvadrantni va yana ikkitasini raqib tomonidan bir harakatda ikkinchisiga o'zgartirishi mumkin bo'lgan harakatni amalga oshirmaslik kerak. Bu raqibga yo'qotilgan pozitsiyani yaratishga imkon beradi.
Ba'zi test savollari
-
Bu erda Chomp, iChomp va SG-nazariyasi haqidagi tushunchangizni sinab ko'rishingiz mumkin bo'lgan ba'zi savollar keladi.
SG-qiymatlarini bilish Chompni mukammal uchun etarlimi?
- Ha. Agar pozitsiyaning SG-qiymati nolga teng bo'lsa, u yo'qotilgan pozitsiyadir (chunki uni nolga aylantirish uchun hech qanday harakat yo'q, shuning uchun g'alaba qozongan harakat mavjud emas, shuning uchun u yo'qotilgan pozitsiya). Agar SG-qiymati noldan katta bo'lsa, bu natijada paydo bo'lgan pozitsiyaning SG-qiymatini nolga aylantirish uchun harakat borligini anglatadi, shuning uchun g'alaba qozonadigan harakat mavjud.
Chompni mukammal uchun Chomp pozitsiyalarining SG-qiymatlarini bilish kerakmi?
- Yo'q. Chompni uchun biz yo'qotish pozitsiyasini yaratadigan harakatni topishimiz kerak. Agar bunday harakat mavjud bo'lmasa, u yo'qotilgan pozitsiyadir va har qanday harakat mumkin. Ammo, agar bunday harakat topilsa, qidirishni to'xtatish mumkin. SG qiymati kerak emas.
SG-qiymatlari nima uchun yaxshi?
- Ular faqat iChompda bo'lgani kabi yangi o'yin sifatida parallel ravishda bir nechta Chomp o'yinlarini uchun kerak.
Chompda pozitsiyaning SG-qiymatini hisoblash g'alaba qozongan harakatdan ko'ra qanchalik qiyin?
-
Chompni uchun biz yo'qotish pozitsiyasini yaratadigan harakatni topishimiz kerak. Agar bunday harakat mavjud bo'lmasa, u yo'qotilgan pozitsiyadir va har qanday harakat mumkin. Ammo, agar bunday harakat topilsa, qidirishni to'xtatish mumkin.
Pozitsiyaning SG-qiymatini topishga harakat odatda yuqori. SG-qiymatini topish uchun har doim BARCHA harakatlarni qidirish kerak, natijada paydo bo'lgan pozitsiyalarning barcha SG-qiymatlarini topish va harakatda erishib bo'lmaydigan eng kichik salbiy bo'lmagan qiymatni topish kerak. Bu qiymat pozitsiyaning SG-qiymati.
Misol uchun, bizning (Karibu) hisob-kitoblarimizda biz 93 kafelgacha bo'lgan barcha yo'qotilgan pozitsiyalarni (va shuning uchun g'alaba qozongan pozitsiyalarni) aniqlashga muvaffaq bo'ldik. Taqqoslanadigan hisoblash harakatlari bilan biz 82 kafelgacha bo'lgan barcha Chomp pozitsiyalarining SG-qiymatini hisoblash imkoniga ega bo'ldik.
Shu ma'noda SG-qiymatlarini aniqlash g'alaba qozongan harakatni aniqlashdan ko'ra hisoblash jihatdan qimmatroq.
Agar 4 qoziqli Nim 1 qoziq bilan NIMga qaraganda qiyinroq bo'lsa, unda 4 kvadrantli iChomp 1 kvadrantli Chompga qaraganda ancha qiyinmi?
-
Nim'da bitta qoziqning SG-qiymati shunchaki bu qoziqdagi o'yinlar soni. (Iltimos, yuqoridagi izohlarni qo'llash orqali tasdiqlang SG-qiymatlarini Nimdagi bitta stackga qanday hisoblash mumkin.) Nim bir necha vayronaga faqat murakkabligi XOR uchun XOR bu qoziq turli SG-qiymatlari birlashgan barcha qoziq SG-qiymatini olish.
Chompda pozitsiyaning SG-qiymatini olish hisoblash jihatdan qimmatga tushadi (bu bir kvadrantda). iChomp-da, 4 kvadrantlarning SG-qiymatlari ma'lum bo'lgandan so'ng, bu qiymatlar ham XOR bo'lishi kerak, ammo bu bir kvadrantning SG-qiymatini topishdan ko'ra osonroq.
Chompni optimal uchun pozitsiyaning SG-qiymatini bilish shart emas, g'alaba harakatini bilish etarlicha yaxshi, lekin yuqorida ko'rsatilganidek, farq unchalik katta emas.
Shunday qilib, javob yo'q, iChompni Chompga qaraganda optimal tarzda qiyin emas.
Chompda harakat SG qiymati yuqori bo'lgan pozitsiyani yaratishi mumkinmi?
- Ha. Pozitsiyaning SG-qiymati harakat natijasida hosil bo'lmaydigan eng kichik qiymatdir.
Chompda bir xil SG-qiymati bilan pozitsiyani yaratadigan turli xil harakatlar bo'lishi mumkinmi?
-
Ha. Siz plata hajmini kattalashtirish va "SG qiymatlarini ko'rsatish" tugmasini bosish orqali misollarni ko'rishingiz mumkin. Masalan, pozitsiya
###
##
#
3 g'alaba harakatlariga ega bo'lib, ularning barchasi SG-qiymati 0 bo'lgan pozitsiyani yaratadi. Biz hatto 7 g'alaba harakatlari bilan pozitsiyani topdik:
+ 10 6 15 2 20 21 14 22 11 0 23 7 26 13 7 11 9 14 0 19 5 17 11 14 18 0 24 23 8 3 19 2 0 20 11 4 0 5 1 8 0 0 4 23 25 24
Follow or subscribe for updates: