300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийiChomp©
Pyeslərin ümumi sayı: 859601
Qaliblərin ümumi sayı: 499579
Qaliblərin ümumi sayı: 499579
Necə oynamalı:
- Hər bir oyunçu növbə ilə lövhədən konfet seçir
- Çıxarılan konfet konfetin seçildiyi rübdən asılıdır.
- Ən sol üstdə seçilən konfetin aşağısındakı və sağındakı bütün konfetlər çıxarılır, ən sağ üstdən seçilən konfetin altında olan konfetlər çıxarılır. Digər seçilmiş konfetin altında və sağından olan bütün konfetlər çıxarılır.
Necə qazanmaq olar:
- son kafeli çıxaran oyunçu oyunu qazanır
1-ci oyunçunun növbəsi
Lövhənin eni:
Lövhənin uzunluğu:
Access to 'Some food for thought' (SFFT) for the iChomp game can be purchased in the online shop
Bu dərslikdə öyrənəcəyiniz alqoritm böyük bir oyun sinfini optimal şəkildə oynamağa qadirdir, ona görə də onu öyrənməyə bir qədər vaxt sərf etməyiniz öz bəhrəsini verəcəkdir. Açar məşhur Sprague-Grundy nəzəriyyəsi olacaq. Sprague-Grundy nəzəriyyəsini öyrənmədən iChomp oynamaq üçün göstərişləri bilmək istəyirsinizsə, müvafiq bölməyə sürüşdürün. Təfərrüatlara keçməzdən əvvəl bir neçə terminə aydınlıq gətirməliyik.
Qeydlər
-
Kombinator oyunlar: mükəmməl məlumat və nəticə qazanan və ya itirən və şanssız hərəkətlərlə iki nəfərlik oyunlar.
Qərəzsiz oyunlar: icazə verilən hərəkətlərin iki oyunçudan birinin hazırda hərəkət etməsindən deyil, yalnız mövqedən asılı olduğu kombinator oyunları. Həmçinin, ödənişlər simmetrikdir. Başqa sözlə, 1-ci oyunçu ilə 2-ci oyunçu arasında yeganə fərq, oyunçu 1-in birinci olmasıdır. Misal: Chomp.
Partizan Oyunları: qərəzsiz olmayan oyunlar. Məsələn: Şahmat.
Normal Oyun: Son hərəkət WINS etmək üçün oyunçu, yəni hərəkət edə bilməyən oyunçu, yəni əlindən alınmağa heç bir şey olmayan oyunçu itirir.
Misère Oyunçu: Son hərəkəti edən oyunçu İTİRİR.
Chomp: bir kvadrant və Misère Oyun istifadə edən oyun saytımızda təqdim edilmişdir.
Oyun səhifəmizdə oynanılan Nim oyunu normal və ya misère oyunundan istifadə edirmi?
- Nim oyunumuzda misère oyunundan istifadə olunur, çünki son yarışmanı aparan oyunçu oyunu uduzur.
Chomp oyun səhifəmizdə oynanılan Chomp oyunu normal və ya misère oyunundan istifadə edirmi?
- Oyun səhifəmizdə oynadığı kimi Chomp oyunu misère oyunundan istifadə edir, belə ki, son konfeti götürən oyunçu uduzur.
Chomp üçün normal oyun istifadə etmək niyə məntiqəuyğun deyil?
- Normal oynamaq o deməkdir ki, kim axırıncı xananı götürsə, qalib gəlir. Buna görə də, birinci hərəkət edən oyunçu sol yuxarı küncdəki xananı götürərək dərhal qalib gələ bilərdi.
Bu web səhifədə oynanmış kimi iChomp oyun Normal və ya Misère Oyun istifadə edir?
- iChomp-da son xananı götürən oyunçu qalib gəlir, buna görə də bu oyun Normal Oyun'dan istifadə edir.
Normal Oyun istifadə etmək və hələ də eyni oyun oynamaq üçün Chomp lövhəsinin necə dəyişə bilməsi üçün bir təklif var?
-
Biri sol yuxarı küncdəki (zəhərlənmiş) konfeti artıq əvvəldən itdiyi bir mövqedən başlaya bilər. Sonuncu konfeti belə lövhədən götürmək o deməkdir ki, Normal Oyun' da qalib gələcək. Misère Oyun' da və bu xana ilə o zaman digər oyunçu onu götürəcək və uduzacaq ki, bu da eyni nəticədir.
Beləliklə, yuxarı sol künc xanasına sahib olmaq və Misère Oyunundan istifadə etmək və ya oyunun əvvəlindən bu xanadan istifadə etməmək və Normal Oyundan istifadə etmək hər ikisi eyni oyundur.
iChomp haqqında
- iChomp oyunu dördlərin birliyi üçün nəzərdə tutulmuşdur Chomp eyni vaxtda oynanan oyunlar, hamısı Normal Play qaydası altında. Bu, oyunu aşağıda izah ediləcək iki aspektdə daha gözəl edir. Bundan əlavə, aşağıda təsvir olunan Sprague-Grundy nəzəriyyəsini tətbiq etsəniz, iChomp-u oynamaq Chomp-dan daha çətin deyil.
Sprague-Grundy nəzəriyyəsi haqqında
-
Aid olduğu oyunlar sinfi aşağıdakılardır: qərəzsiz combinatorial oyunlar. Bu nəzəriyyə bizim üçün iki şey edir:
- O, bizə hər bir oyun (yəni, hər mövqe) üçün bir nömrə (biz onu SG-dəyəri adlandıracağıq) müəyyən edən bir alqoritm verir ki, nömrə yalnız və yalnız itirilən mövqe olduqda ("P-mövqe" adlanır) 0 olsun. 'P' ilə kombinatoryal oyun nəzəriyyəsi ədəbiyyatı, 'əvvəlki oyunçunun qazanan bir hərəkət oynadığını göstərir). Bu o deməkdir ki, əgər bu SG-dəyəri 1, 2, 3, ... olarsa, bu, qalib mövqedir (ədəbiyyatda "N" mövqeyi adlanır). Bu halda, kim "n'ext"ə keçirsə, optimal şəkildə oynasa, qalibiyyəti təmin edə bilər.
- SQ-nəzəriyyənin ikinci məqsədi eyni anda oynanılan bir neçə mövqedən ibarət olan oyunda necə qalib gəlməyi təsvir etməkdir. Belə bir birləşmiş oyunda bir addım birləşən mövqelərdən hər hansı birində bir hərəkət etməklə edilir.
Bilmək lazımdır ki, ümumi mövqelərdən hər birinin SG-qiymətidir. Onları əldə etmək üçün bu birləşmiş mövqelərdən hər hansı birində hər bir hərəkətdən sonra SG-dəyəri ilə tanış olmaq lazımdır. Bunlar həm də optimal oynamaq üçün lazımdır.
Məsələn: Nim oyununda bir və ya iki və ya daha çox yarış var. Əgər biz hər bir svayın tək başına oynanması üçün SG-dəyərini biliriksə, onda SG-nəzəriyyəsi bizə bu yığınların hər hansı birindən uyğun sayda yarış götürməklə bütün bu yığınlarla optimal şəkildə necə oynamağı izah edir.
Nə üçün iChomp?
-
iChomp, Caribou Contests tərəfindən təqdim edilən və bu veb səhifədə oynanan Chomp'ın yeni versiyasıdır. IChomp-da 'i' 'i'dir. Bütün istiqamətlər bərabər rəftar edilir.
Normal Chomp'da bir xananın aradan qaldırılması da onun Şərq və Cənubuna olan bütün xanaları aradan qaldırır. Şərq və Cənub istiqamətləri xüsusi rol oynayır.
IChomp'da digər istiqamətlərdəki bütün xanalar, eləcə də mərkəzə ən yaxın olan götürülən xananın harada yerləşdiyindən asılı olaraq aradan qaldırıla bilər. Əgər bu xana, məsələn, mərkəzin Şimal-Qərb istiqamətindədirsə, onda Şimal və ya Qərbdəki bütün xanalar da götürülür.
Məsələn, süni qaydaların aradan qaldırılması, Şərq və Cənub xüsusi olan qayda adətən oyun riyazi baxımdan daha gözəl etmək hesab olunur.
IChomp'un Chomp ilə müqayisədə daha bir üstünlüyü var.
Chompda sol yuxarı küncdəki xana digər xanalarla müqayisədə xüsusi rol oynayır. Bu lövhədəki yeganə xanadırsa, oyun başa çatır. Başqa bir xana çıxarılarsa, oyun davam edir. Chomp'a o künc xana olmadan başlaya bilərsiniz, belə ki, bütün xanalara eyni yanaşılır, lakin bu, o zaman süni bir qayda olacaq ki, niyə oyuna o xana olmadan və digər xanalarsız da başlamaq lazımdır.
IChomp'da bütün xanalar başlanğıcda mövcuddur və hamısı eyni şəkildə düzəldilir. Hər hansı bir xananı avtomatik olaraq oyunu bitirmədən götürmək olar.
Bəzi suallar meydana çıxır:
'Normal Oyun'da birləşməsi və ya 4 əhəmiyyətsiz Chomp oyunları olduğu üçün iChomp bir əhəmiyyətsiz oyundur?
-
Cavab, xeyr. Məsələn, bir xallıq yarışa malik Nim oyunu əhəmiyyətsizdir. 'Normal Oyun' altında, bir hərəkət ilə bütün yığın aradan qaldırılması və qalib ola bilər. Nim altında 'Misère Oyunu', bir yarışdan başqa hamısını silib qalib gələ bilər. Buna baxmayaraq, Nim oyun səhifəmizdə olduğu kimi 1-xovlu Nim oyunlarının çoxşaxəli Nim oyununa birləşməsi əhəmiyyətsiz deyil.
Eynilə burada: Künc xanasından və "Normal Oyun"dan istifadə edən tək bir oyun oynamaq əhəmiyyətsizdir, çünki bir gedişlə bütün xanaları çıxarıb qalib gələ bilərsiniz. Ancaq 4 belə oyunun birləşməsi əhəmiyyətsiz deyil.
Müqayisənin xülasəsi
- IChomp riyazi baxımdan Chomp'dan daha gözəldir, çünki o, Cənub-Şərq istiqamətlərini süni şəkildə ayırmır və bir xanaya xüsusi rol vermir. Belə görünür ki, iChomp oynamaq Chomp'dan daha çətindir, lakin SG-nəzəriyyəsi kömək edir. Bir qədər ölçüyə qədər Chomp mövqelərinin SG-qiymətini bilmək kifayətdir ki, bu ölçüdən 4 dəfəyə qədər iChomp mövqelərinin SG-qiymətini asanlıqla hesablamaq və beləliklə, 4 dəfə böyük ölçüyə qədər iChomp optimal şəkildə oynamağı bilmək kifayətdir.
-
Cavab, xeyr. Məsələn, bir xallıq yarışa malik Nim oyunu əhəmiyyətsizdir. 'Normal Oyun' altında, bir hərəkət ilə bütün yığın aradan qaldırılması və qalib ola bilər. Nim altında 'Misère Oyunu', bir yarışdan başqa hamısını silib qalib gələ bilər. Buna baxmayaraq, Nim oyun səhifəmizdə olduğu kimi 1-xovlu Nim oyunlarının çoxşaxəli Nim oyununa birləşməsi əhəmiyyətsiz deyil.
SG-nəzəriyyədə XOR adlı riyazi əməliyyat lazımdır. Tanış olmadığınız halda aşağıdakı bölmə faydalı olacaq.
XOR nədir?
-
Eksklüziv, yaxud və ya qısaca XOR, ikili verilənlər üzərində yerinə yetirilən məntiqi əməliyyatdır. Binar verilənlərdən istifadə etməklə iki dəyərdən birinə sahib ola bilərik, doğru (=1) və ya yanlış (=0). İki ikili dəyər üzərində XOR əməliyyatı aşağıdakı cədvəl vasitəsilə müəyyən edilir.
a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
Bu əməliyyatı 1 (doğru) və ya 0 (səhv) dəyərləri üzərində istifadə etmək asan olsa da, hesablamalarımız üçün iki ədəd üzərində XOR-u yerinə yetirməyi bacarmalıyıq. Bunu da etmək olar, lakin xor ifa etməzdən əvvəl yeni bir addım atmaq lazımdır.
İlk növbədə, rəqəmləri ikiliyə çevirmək lazım gələcək, yəni 10 əsasdan 2-ci əsasa çevirmək üçün.
Bir ədəd baza 10 əsasdan 2-ci əsasa necə çevrirə bilərik?
-
Aşağıdakı alqoritm 10-cu əsasdan n nömrəli ədədi 2-ci əsas formatına çevirmək üçün istifadə oluna bilər. (Xatırlatmaq lazımdır ki, 20 = 1):
- 2-nin ən elə yüksək p qüvvəti-ni tapın ki, 2p ≤ n.
- 1-i qeyd edin və n-dən 2p çıxın.
- Əgər p = 0 olarsa, dayandırın, əks halda p-dən 1 çıxın və davam edin.
- Əgər 2p > n olarsa, 0-ı qeyd edin, əks halda n-dən 2p çıxın və 1-i qeyd edin.
- 3-cü addıma qayıdın.
Bu alqoritmin ardınca qeyd etdiyiniz 1'lərin və 0'ların ardıcıllığı n rəqəminin ikili təmsili olacaq. Nümunə:
Gəlin 13 rəqəmini əsası 2 olan formata çevirək. Biz 23, yəni 8 olan 13-dən az və ya bərabər 2-nin ən yüksək qüvvətini tapmaqla başlayırıq. Sonra 1-ni qeydə alıb 13-dən 8-ni çıxırıq . Bu da bizə 5 verir. Sonra 2(3−1) = 22 = 4-ü yoxlayırıq. 4 ≤ 5-dən etibarən 1, 5-dən isə 4-ü qeydə alarıq ki, bu da bizə 1 verir. 2-nin növbəti aşağı qüvvəti 21 = 2-dir. 2 > 1, ona görə də 0 qeyd edirik. 2-nin növbəti qüvvəti 20 = 1-dir, bu, bizim n-ə bərabərdir, ona görə də biz 1-i qeyd edirik və 1-dən 1-i çıxarırıq, bizə 0 veririk. p = 0 olduğundan alqoritmi dayandırırıq. Buna görə də 13 (əsas 10) = 1101 (əsas 2).
İki ədədi binar təsvirə çevirdikdən sonra indi iki ikili ədədin müvafiq rəqəmləri üzərində XOR əməliyyatını yerinə yetirə bilərik. Nəticə, XOR dəyərinin gələcəkdə istifadəsi üçün daha əlverişli olarsa, yenidən əsası 10-a çevrilə bilən binar ədəddir. Misal:
Gəlin 6 və 13-cü rəqəmlərin XOR-nu hesablayaq. Bu iki ədədin binar təmsili 6 = 110 və 13 = 1101-dir. Əvvəlcə daha kiçik ədədin solunda 0'ları əlavə edirik ki, hər ikisi eyni ədədə malik olsun. Beləliklə, 6 = 0110 ədəd. Sonra XOR-ları sıralayaraq və əməliyyatı ayrı-ayrı ədədlərin hər birinin üzərində yerinə yetirməklə yerinə yetirə bilərik:
0110 XOR 1101 ------ 1011
Beləliklə, 6 XOR 13 = 1011 (əsas 2) = 1×23+0×22+1×21+1×20 = 8+2+1 = 11 (əsas 10).
Xor haqqında anlayışımızı bir neçə sualla yoxlayaq.
Hər hansı m ədədi üçün m XOR m nədir?
- Hər hansı bir ədəd üçün m XOR m = 0 var, çünki 0 XOR 0 = 0 və həmçinin 1 XOR 1 = 0.
n XOR m = m XOR n hər hansı ədədlər üçün n, m?
- Bəli, çünki 1 XOR 0 = 0 XOR 1 (=1).
hər hansı bir ədəd m üçün 0 XOR m nədir?
- 0 XOR m = m çünki 0 XOR 0 = 0 və 0 XOR 1 = 1.
Əgər m ədədi n-dən m XOR n-ə qədər olan rəqəmlə XOR ilə yazılıbsa, m-in hansı rəqəmləri çevrilir?
- Əgər m-də bir ədəd 0 ilə XOR'ed olarsa, onda rəqəm dəyişməzdir (çünki 0 XOR 0 = 0 və 1 XOR 0 = 1). Əgər m-də bir ədəd 1 ilə XOR'ed olarsa, onda rəqəm çevirilmiş olur (çünki 0 XOR 1 = 1 və 1 XOR 1 = 0). Beləliklə, XOR n n-də müvafiq rəqəmin 1 olduğu bütün ədədləri çevirərək.
-
Aşağıdakı alqoritm 10-cu əsasdan n nömrəli ədədi 2-ci əsas formatına çevirmək üçün istifadə oluna bilər. (Xatırlatmaq lazımdır ki, 20 = 1):
Chomp mövqeyinin SG qiymətini hesablamaq alqoritmi.
-
Aşağıdakı alqoritm istənilən qərəzsiz kombinat oyununda hər hansı bir mövqe P-nin SG-qiymətini hesab edir. Biz bunu Chomp oyunundan istifadə edərək izah edirik.
- Bir itirmə mövqeyi olan hər oyun mövqeyi SG-dəyəri 0 alır. Chomp-da tək bir xana (Şimal-Qərb küncündə) izləmə hərəkəti olmadan yeganə mövqedir və buna görə də SG-dəyəri 0 ilə bir itirmə mövqeyidir.
- Bizə bir addımda P mövqeyindən çatmaq mümkün olan bütün mövqelərin SG-dəyərləri lazımdır. Belə ki, əgər P-nin n xanası varsa, onda n-1 mümkün gediş var: Şimal-Qərb küncündəki x ana stisna olmaqla, bütün digər xanaları həmin xananın Cənub/Şərqinə qədər olan bütün xanalarla birlikdə götürmək olar.
- Mövqe P-nin SG-qiyməti n-1 çata bilən SG-qiymətlər siyahısında olmayan ən kiçik mənfi olmayan ədəddir.
Bu alqoritm təkrarlanır, çünki mövqe P-nin SG-qiymətini hesablamaq üçün P-dən əldə edilə bilən bütün mövqelərin SG-qiymətlərinə ehtiyacımız var. Hələ də işə yarayır, çünki daha az xanaların kiçik mövqeləri və mümkün olan ən kiçik mövqeyin SG-dəyəri (Şimal-Qərb küncündə bir xana) ilə bağlı narahatlıq doğuran SG-dəyərlər məlumdur.
Daha böyük lövhənin en və hündürlüyünü seçərək və 'Randomize Board' düyməsinə basaraq yuxarıdakı oyunda 3-cü mülkü yoxlamağa çalışın.
- Siçanı bir xana zərində hərəkət etdirdikdə, bu xana və götürüləcək digər xanalar vurğulanır. Həmin xanadakı ədəd,'Normal Oyun' ('Misère Oyun'' deyil) altında olan dördbucaqın SG-dəyəridir. 'SGv dəyəri əsas On:' mətnində göstərilən rəqəmin kvadrantın yanında göstərildiyini yoxlaya bilərsiniz. Bu, kvadrantda göstərilməyən ən kiçik ədəddir. Həmçinin yoxlaya bilərsiniz ki, əgər bir xanaya basırsınızsa, onda onda indi onda olan nömrədə yeni vəzifənin 'SG qiyməti Əsas On:' kimi göstərilir.
SG-qiymətlərin təyinini necə sürətləndirmək lazımdır:
Çünki eyni mövqeyə bir hərəkətdə müxtəlif mövqelərdən çatmaq mümkündür və daha böyük bir mövqenin SG-qiymətini hesablayarkən dəfələrlə ortaya çıxa bilər. Bu, onu təkrar-təkrar hesablamaq cəhdinin itkisi olardı. Buna görə də, bir mövqe P-nin SG-qiyməti hesablandıqdan sonra, sonradan istifadə üçün saxlanılmalıdır.
Əgər biri bütün mövqelərin SG-qiymətini müəyyən ölçüyə qədər hesablamaq istəyirsə, o zaman aşağıdakı yanaşma faydalıdır. Biz yeganə mövqeyi bir xana(Şimal-Qərb küncündə) SG-qiymət sıfırı ilə təyin etməklə başlayırıq. Sonra yuxarıda göstərilən alqoritmdən istifadə edərək bütün mövqelərin SG qiymətlərini 2 x, sanaonra 3 xana və s. ilə hesablayırıq.
iChomp mövqeyinin SG-qiymətini hesablamaq alqoritmi
-
IChomp mövqeyi 4 Chomp mövqeyindən ibarətdir, lövhənin hər kvadrantında bir ədəddir.
- İlk öncə Chomp 'Misère Oyun' qaydasını istifadə edərək 4 Chomp mövqeyindən hər birinin SG-qiymətini müəyyən edirik. Boş kvadrant Chomp mövqeyi deyil, ona görə də biz ona qiyməti −1 veririk.
- Sonra hər bir dəyərə 1 əlavə edirik.
- 4 nəticəli ədədin hər biri üçün ikili təmsili hesablayırıq.
- Biz 4 ikili dəyərin XOR qiymətini hesablayırıq və həmin mövqenin SG-qiymətini əldə edirik (ikili formada). Əgər bu dəyər sıfırdırsa, o, uduzduğu mövqedir, əks halda qalib mövqedir.
-
"Normal Oyun" altında Chomp mövqeyinin SG-qiymətini 'Misère Oyun' altında SG-dəyərindən əldə etmək üçün 1 əlavə edirik. Aşağıdakı teorem bunu izah edir.
Teorem:
--------
"Normal Oyun" altında Chomp mövqeyinin SG-dəyəri əldə etmək üçün (yəni sonuncu tileni götürmək Chomp oynamaq üçün ümumi yol olmayan oyunda qalib gəlir) bir şəxs 'Misère Oyun' altında eyni mövqenin SG-dəyərinə 1 əlavə etmək lazımdır (yəni Chomp oynamağın ümumi üsulu olan sonuncu xanan;n alınması oyunu uduzdurur).
Teoremi induksiya ilə sübut etməyə çalışa bilərsinizmi?
-
Sübut (induksiya ilə)
Əsas Hal(1 xana):
-------------------
"Normal Oyun" altında xanasız boş lövhə itirilən mövqedir və buna görə də SG-dəyəri sıfırdır. Bundan əlavə, bir xana (yuxarı sol küncdə) olan lövhə üçün "Normal Oyun" altında yeganə mümkün hərəkət SG-dəyəri 0 olan bir mövqe verən bu xananı silməkdir. Beləliklə, "Normal Oyun" altında ən kiçik mənfi olmayan Hərəkətlə əldə edilə bilməyən SG-dəyəri 1-dir, beləliklə, "Normal Oyun" altında bir xana ilə mövqenin SG-dəyəridir.
'Misère Oyun' altında bir xananın olması SG-value 0 ilə bir itirmə mövqeyidir.
Beləliklə, 1 xana üçün "Normal Oyun" SG-dəyəri "Misère Oyun" dəyərindən 1 dəfə böyükdür.
İnduktiv Addım
---------------
İnduksiya Hipotezi (n xana):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Biz fərz edirik ki, n ədədi mövcuddur ki, ≥1 və ≤n xana ilə bütün mövqelər üçün 'Normal Oyun' altında SG-dəyəri 'Misère Oyun' altında bir daha böyükdür. İnduksiya İddia (n+1 xana):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Göstərəcəyik ki, bundan sonra n+1 xanalı bütün mövqelər üçün də belədir.
İnduksiya addımı ( n xana → n+1 xanaları):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
Hər hansı bir mövqe üçün 'Misère Oyun' və 'Normal Oyun' eyni hərəkətləri imkan verir, ancaq 'Normal Oyun' həmçinin bütün xanaları sol üst küncdən keçirmək üçün imkan verir.
Əgər mövqeyin n+1 xanasıvarsa, o zaman hərəkət etmək induksiya hipotezini tətbiq edə biləcəyimiz əksər n xanalı bir mövqe yaradır:
"Normal Oyun" altında əldə edilə bilən SG-qiymətlər siyahısı bu səbəbdən 'Misère Oyun' altında əldə edilə bilən SG-qiymətlərin siyahısından əldə edilir. Hər biri 1 ədəd artdı və bütün xanaları götürməklə 0 qiymətini əlavə etdi.
"Normal Oyun" altında əldə edilə bilməyən ən kiçik qeyri-mənfi rəqəm 'Misère Oyun' altında əldə edilə bilməyəcək ən kiçik mənfi olmayan rəqəmdən 1 vahid yüksəkdir. Başqa sözlə, n+1 xanalı orijinal mövqe üçün 'Normal Oyun' altında SG-dəyəri 'Misère Oyun' altında SG-qiymətdən bir vahid yüksəkdir. ∎ (Bu, isbatı tamamlayır)
-
Sübut (induksiya ilə)
Niyə '1' əlavə etdik?
Necə iChomp oynamaq
-
Məqsəd elə bir addım atmaqdır ki, nəticənin SG-qiyməti sıfırdır. Hər hansı bir hərəkət etsə də, 4 kvadrantdan birində olmalıdır. Bu o deməkdir ki, hərəkətin edildiyi mövqenin SG-dəyəri və digər 3 dəyişməz kvadrantın SG-qiymətləri bütün XOR'ed sıfır verməlidir. Bu, əgər və yalnız digər 3 SG-values XOR'ed hərəkət etdikdən sonra yeni kvadrantın SG-qiymətini dəqiq verirsə və yalnız bu halda belə olur (bu bəyanatın sübutu üçün daha aşağıda baxın). Buna görə də prosedur aşağıdakı kimidir:
- (sadə) Məsələ: 4 kvadrantdan ikisi eyni SQ-dəyərinə malikdirlər. Sonra bu iki bərabər dəyərdən XOR sıfır verəcək ki, hər iki kvadranta diqqət edilməsin.
- Əgər digər iki kvadrant da bərabər SG-dəyərlərə malikdirlərsə, onda bütün mövqenin SG-qiyməti sıfır, mövqe isə uduzan mövqedir. Sonra məğlubiyyəti gecikdirmək üçün hər hansı bir dördbucaqdan cəmi bir kisəni çıxarın və rəqibin optimal oynamaması üçün daha çox şans əldə edin.
- Əgər digər iki kvadrantın qeyri-bərabər SG-qiymətləri varsa, onda daha böyük SG-qiyməti olan kvadrantı seçin. Digər dördbucaqlının SG-dəyərinə bərabər olan bir ədəd yazılmış bir kirəyə basaraq oraya bir hərəkət edin. Nəticə cüt bərabər SG-dəyəri və ümumi XOR dəyəri sıfır olan 2 cüt kvadrantdır - uduzan mövqe.
- (ümumi) Məsələ:
- 4 iChomp-SG-dəyərlərini hesablayın, deyək ki, 4 kvadrantdan w,x,y,z (hər biri həmin kvadrantın Chomp-SG-dəyərləri üstəgəl 1dir) və onları İkinci Əsasa çevirin.
- Sonra ən sol mövqeyi tapın ki, bu 4 ədədin tək sayı bu mövqedə 1 olsun. Məsələn, əgər 4 ədəd
w=11011
onda 1 ilə ən sol mövqe 5-ci mövqedir (mövqeləri sağdan saymağa başlayırıq). w və y-nin orada 1-i var, yəni iki ədədin (w və y) orada 1-i var. İki cüt ədəddir, ona görə də bu mövqeyə məhəl qoymamalıyıq. Növbəti mövqe 4-cü mövqedir, yenidən sağdan sayılır. Burada da bərabər bir çox ədəddə 1 var (w və x). Biz də bu mövqeyə məhəl qoymamalıyıq. 3-cü mövqedə 1 olan 3 rəqəm var (x, y, z). 3 tək ədəddir, ona görə də bu 3 ədəddən hər hansı birini seçirik, məsələn, y=10100.
x= 1101
y=10100
z= 100- Əgər bütün mövqelərdə cüt sayda 1 varsa, onda bütün 4 rəqəmin XOR dəyəri sıfırdır və bu, itirən mövqedir. Misal üçün
w'=11011
hər mövqedə cüt sayı 1 olsun. Bu 4 rəqəmin XOR-u sıfırdır, bu itirən mövqedir. Bu halda, məğlubiyyəti gecikdirmək və rəqibin optimal şəkildə oynamaması üçün daha çox şans əldə etmək üçün istənilən kvadrantdan sadəcə bir kafel çıxarır.
x'= 1011
y'=10110
z'= 110 - Ən azı bir mövqedə tək çoxlu 1 varsa, biz yuxarıdakı y kimi bir ədəd tapdıq (y' deyil).
- Biz digər 3 rəqəmi XOR edirik, bizim vəziyyətimizdə w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011. Bu dəyər həmişə seçdiyimiz rəqəmdən azdır, burada y = 10100 (aşağıdakı sübutlara baxın).
- Seçilmiş dəyəri olan kvadrantda, burada y, nümunəmizdə 10011 olan digər 3 dəyərin XOR-a bərabər olan SG-dəyəri ilə bir mövqe ilə nəticələnən bir hərəkət edirik.
- Hansı xanaya basacağımızı bilmək üçün ya 10011-i Onluğa çevirəcəyik (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) və 19 ədədi olan xana üzzərinə klikləyin, ya da hesablayırıq. binar forması 10100 − 10011 = 1 və bunu Onluğa çevirin (= 1) və bilin ki, kliklənəcək xana y-dən (=20) 1 kiçik dəyərə malik olmalıdır, yəni 19 ədədi yazılmış xana üzərinə klikləmək üçün.
Bu, nəyə görə qələbədir?
-
Aşağıdakı suallara cavab vermək üçün daha əvvəl göstərildiyi kimi XOR-un xüsusiyyətlərini özünüzə xatırlatmayiniz xahiş olunur.
əgər siz = w XOR x XOR y XOR z, onda y XOR u nədir ?
-
Daha əvvəl öyrəndiyimiz XOR qaydalarından istifadə etməklə əldə etdiyimiz
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.
Əgər y y XOR u ilə əvəz olunursa, onda bütün 4 SG-lərin yeni XOR nədir?
-
Yeni XOR olacaqdı
(y XOR u) XOR w XOR x XOR z
= (w XOR x XOR z) XOR (w XOR x XOR z)
= 0
görə m XOR m = 0 hər hansı bir ədəd m üçün.
Bu o deməkdir ki, bütün lövhənin yeni SG-dəyəri sıfır olacaqdı, beləliklə də nəzərdə tutulduğu kimi bu, itiriləcək mövqe olardı.
SG-dəyəri y-i daha aşağı qiymətə dəyişən bir hərəkət niyə mövcud olmalıdır?
- Təsnifata görə: Bir mövqe SG-dəyərlər 0,1,..,(y-1) ilə mövqelər yaradan hərəkətlər varsa və yalnız mövcud olduqda y-nin SG-qiyməti var. Beləliklə, əgər y > (y XOR u), onda SG-value (y XOR u) < y-ni əmələ gətirən bir hərəkət mövcud olmalıdır.
Hələ ki, cavab vermək lazımdır:
y > (y XOR u) qane edən SG-value y ilə niyə kvadrant mövcud olmalıdır?
-
Xatırlatma:
Daha əvvəl XOR-un xüsusiyyətlərini öyrəndikdə gördük: XOR u bütün ədədləri çevirərək bu rəqəmə görə u-da müvafiq rəqəm 1-dir.
əgər 0 ≠, onda u ən yüksək gücü2,с с. 2-nin bu gücü 4 SG-nin qiymətinin bir ədədində baş verməlidir, buna görə də ən azı birində y de.
Bu o deməkdir ki, y XOR u hesablanarkən, bu 1-i y-də 0-a çevirərək müvafiq 1-i u. Bu 1-in sağında yerləşən y-də başqa ikilik ədədlər də ola bilər. y − (y XOR u) mümkün olan ən böyük qiymət, əgər bu 1-in sağında y-də olan ədədlər sıfır, sizdə isə həmin 1-in sağında olan ədədlər birdirsə baş verir. Belə halda u = 111..111 dəyişir y = *100..00 (burada * hər hansı bir ədədin sayı durur) y XOR u = *011..11-ə qədər dəyişir. Onların fərqi belədir:
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, o deməkdir ki, y ən azı bir böyük (y XOR u). ∎
-
Daha əvvəl öyrəndiyimiz XOR qaydalarından istifadə etməklə əldə etdiyimiz
Bu alqoritmi 'Çətinlik: Çətin'ə qarşı oynamaqla və qalib gəlməklə sınaqdan çıxarın.
-
Başlamaq üçün optimal kompüter oynanmağı zəmanət verən 'Çətinlik: Sərt' seçin. Əgər siz hələ də qalib gəlsəniz, onda hər bir hərəkəti optimal şəkildə oynayırdınız.
Hər bir kvadrantın SG-qiyməti baza 10 və baza 2-də göstərilir. Bu rəqəmin kvadrantda göstərilməyən ən kiçik dəyər olduğunu yoxlayın.
Altında u adlanan bütün 4 SG-lərin XOR-u göstərilir. Əgər iki 1'lər eyni mövqedədirsə, sadəcə olaraq 4 SG-də iki 1'lərdən hər hansı bir cüt 0-a dəyişməklə sizin dəyərinizi yoxlayın. Sonra qalan 1'ləri bir ikili ədədə qoyun və bunu 10-un bazasına çevirin.
Yuxarıda təsvir edildiyi kimi hərəkət etmək üçün:
- 4 SG-qiymətdən birini tapın, y deyin. Bu 1-i sol ən çox 1-i ilə eyni mövqedə u.
- İkili formada y XOR u hesablayıb sonra 10-cu əsasa çevirin.
- y kvadrantında hesablanmış y XOR u ilə xana üzərinə klikləyin.
- Qalib gələnə qədər hərəkətlərinizi bu şəkildə çalın.
- Yenidən oynayın, amma bu dəfə təsadüfi hərəkətlə başlayın. Əgər bəxtiniz gətirməsə və təsadüfən qələbə addımı ilə oynamasanız, o zaman optimal oynamağa çalışsanız belə, bu oyunda qalib gələ bilməyəcəksiniz.
Bütün yuxarıdakı təlimatlar fərz edir ki, biri 4 kvadrantın SG-qiymətini bilir ki, bu da o deməkdir ki, hər mümkün hərəkətdən sonra hər dördbucaqlının SG-qiymətini bir adam bilir.
Bəzi Chomp pozisiyalarının ('Misère Oyun''da) SG-qiymətlərini tapa bilərsinizmi?
-
Bir mövqenin SG-qiymətini hesablamaq üçün bir addımda ondan əldə edilə bilən bütün mövqelərin SG-qiymətlərini bilmək lazımdır. Bu rekursiv prosesdir. Buna görə də ən az sayda kirəmitlə mövqelərlə başlamalı və yolumuza qalxmalıyıq.
1,2,3-cü SG-ləri tapa bilərsinizmi,... Bir cərgədə kirəmitlər?
-
Cəmi 1 xananın olması (sol üst küncdə) bu səbəbdən SG-value 0 ilə itki mövqeyidir.
2 xanaya malik olmaq (üst sıra və ya sol sütunda), yeganə mümkün hərəkət SG-value 0 ilə qeyd olunan mövqeyi əldə edən bir tile götürməkdir. Beləliklə, bir hərəkətlə əldə edilə bilməyəcək ən kiçik mənfi olmayan SG-dəyəri 1-dir. Belə ki, 2 xanalı mövqenin SG-dəyəri 1-dir.
Üst sırada 3 xanann hamısına sahib olan biri ya 1, ya da 2 xana götürüb SG-lərin 1 və 0-larını əldə edə bilər. Buna görə də SG-dəyəri 2-dir.
Eyni şəkildə üst sırada n xana SG-qiyməti n-1-dir.
Gəlin 3 xana, 2-si üst sırada, 2-si isə sol sütuna nəzər salaq. Biz yalnız 1 xana aradan qaldırılması və 1, lakin 0 deyil SG-dəyərinə çata bilərik. Beləliklə, əldə edilə bilməz ən kiçik SG-dəyəri 0 bu səbəbdən bu mövqenin SG dəyəridir. Bu, uduzduğu mövqedir.
M+n−1 xana olan bir mövqenin SG-qiymətini tapa bilərsinizmi? Bunlardan n yuxarı sətirdə, m xanaları isə sol sütundadır?
- Biri yalnız yuxarı sətirdən və ya sol sütundan xanalar çıxara bilər. SG-qiyməti buna görə də iki kvadrantın olması ilə eynidir: biri üst sətirdə n xana, digəri isə sol sütunda m xana ilə. Beləliklə, SG-qiymət (m-1) XOR (n-1) olur. Bu, iki gediş ilə NIM oynamaqla eynidir və xanaların bir hərəkətdə yalnız bir gedişdən çıxarıla biləcəyi "Normal Oyun" qaydası.
Yalnız yuxarı iki sətirdə xanalar olan mövqeyin SG-qiymətini tapa bilərsinizmi?
-
Bu mövqelərin formulları daha mürəkkəbdir. Bildiyimiz kimi, onlar əvvəllər də nəşr olunmamışdı. Onları az sayda xana üçün yoxlamağa çalışa bilərsiniz.
n və m yuxarı və ikinci sətirdəki xanaların sayı olsun.
Əgər n cütdürsə
k = (n-2)/2
əgər m cütdürsə
a = m/2
SG-dəyəri = 2*k+a+1
əks halda (m təkdir)
a = (m-1)/2
≤ (k/2) olarsa, onda SQ-qiymət = 2*k-a
əks halda SG-qiyməti = 3*(k-a)
əks halda (n təkdir)
k = (n-1)/2
əgər m cütdürsə
a = m/2
≤ (k/2) olarsa, onda SQ-qiymət = 2*k-a
əks halda SG-qiyməti = 3*(k-a)
əks halda (m təkdir)
a = (m-1)/2
SG-dəyəri = 2*k+a+1
Yuxarıdakı oyun lövhəsinin köməyi ilə formulların düzgün olub-olmadığını yoxlayın.
- Minimal lövhə hündürlüyünü seçin ki, cəmi iki sıra xanas olan kvadrantlar olsun. Yuxarıdakı formulları tətbiq etdikdən sonra 'SG Dəyər Əsası On:' altında göstərilən qiymətdən bir aşağı olan bir SG dəyəri əldə etməlisiniz, çünki formullar 'Misère Oyun' üçün, iChomp isə 'Normal Oyun' istifadə edir.
-
Cəmi 1 xananın olması (sol üst küncdə) bu səbəbdən SG-value 0 ilə itki mövqeyidir.
SG-dəyərləri bilmədən iChomp'u necə yaxşı oynaya bilərsiniz?
-
Müşahidə ilə başlayırıq: Çompun qaydaları Şərq və Cənub istiqaməti arasında heç bir fərq yoxdur.
Yuxarı sol küncdən başlayan diaqonal üzərində güzgü altında bir-birinə güzgü simmetrik olan iki mövqenin SG-qiymətləri üçün nə ilə nəticələnə bilər?
- Şərq və Cənub istiqamətləri bir-birinə güzgü olduğu üçün bu o deməkdir ki, hər ikisi eyni SG-dəyərinə malik olmalıdır.
2 kvadrantın kvadrantların və/və ya diaqonal güzgülərin dönməsi altında simmetrik olan mövqeləri olduqda bu iChomp üçün nə deməkdir?
- Hər iki dördbucaqlıya diqqət etmək olar. Nəyə görə? Hər iki kvadrant misère oyun altında eyni SG-dəyərinə və 1 əlavə etdikdən sonra normal oyun altında eyni SG-dəyərinə sahib olur. Bu iki bərabər dəyərdən XOR sıfır verir. Buna görə də hər iki kvadrantın bütün lövhə mövqeyinin SG-dəyərinə heç bir töhfəsi yoxdur.
Buna görə də hansı oyun strategiyası işləməlidir?
-
İki cüt kvadrant yaradan bir addım atılmalıdır ki, hər cütdəki kvadrantlar bərabər SG-dəyərlərə malik simmetrik mövqelərə malik olsunlar, A və A, B və B və B. Sonra, bütün 4 kvadrantların birləşməsinin SG-qiyməti A XOR A XOR B XOR B = 0 XOR 0 = 0 və ya (A XOR B) XOR (A XOR B) XOR (A XOR B) = 0 belə həmişə 0 olur. Onlardan biri uduzduğu mövqeni yaratdı.
Eyni şəkildə, rəqib tərəfindən bir hərəkətdə biri digərinə dəyişdirilə bilən iki simmetrik kvadrant və digər ikisini tərk edən bir hərəkət etməməlidir. Bu, rəqibə məğlub mövqe yaratmağa imkan verəcəkdi.
Bəzi test sualları
-
Burada Chomp, iChomp və SG-nəzəriyyəsi haqqında anlayışınızı yoxlaya biləcəyiniz bəzi suallar yaranır.
SG-dəyərlər biliyi Chomp'un mükəmməl oynanması üçün kifayətdirmi?
- Bəli. Əgər bir mövqenin SG-dəyəri sıfırdırsa, deməli, bu, itiriləsi mövqedir (çünki onu sıfır etmək üçün heç bir hərəkət mövcud deyil, buna görə də heç bir uduşlu hərəkət mövcud deyil, buna görə də bu, uduzan mövqedir). Əgər SG-dəyəri sıfırdan böyükdürsə, onda bu o deməkdir ki, nəticənin SG-qiymətini sıfır etmək üçün bir hərəkət var, deməli, qalib bir hərəkət var.
Chomp'u mükəmməl oynamaq üçün Chomp mövqelərinin SG-qiymətlərini bilmək lazımdırmı?
- Xeyr. Chomp oynamaq üçün uduzan mövqe yaradan bir gediş tapmaq lazımdır. Əgər belə bir gediş yoxdursa, onda bu, uduzan mövqedir və hər hansı bir gedişi oynamaq olar. Lakin belə bir addım tapılsa, axtarışları dayandırmaq olar. SG-dəyərinə ehtiyac yoxdur.
O zaman SG-dəyərlər hansılardır?
- Onlar yalnız iChomp'da olduğu kimi yeni oyun kimi paralel olaraq bir neçə Chomp oyun oynamaq üçün lazımdır.
Çompda bir vəzifənin SG-qiymətini hesablamaq qalib addımından nə qədər çətindir?
-
Chomp oynamaq üçün biz məğlub mövqe yaradan bir hərəkət tapmalıyıq. Əgər belə bir hərəkət yoxdursa, bu, itirən mövqedir və istənilən hərəkət oynana bilər. Ancaq belə bir hərəkət tapılarsa, axtarış dayandırıla bilər.
Bir mövqenin SG-dəyərini tapmaq üçün səy adətən daha yüksəkdir. SG-dəyərini tapmaq üçün hər zaman BÜTÜN Hərəkətləri axtarmaq lazımdır ki, nəticədə yaranan mövqelərin bütün SG-dəyərlərini tapmaq və bir hərəkətdə əldə edilə bilməyən ən kiçik qeyri-mənfi dəyəri tapmaq lazımdır. Bu dəyər mövqenin SG-dəyəridir.
Məsələn, bizim (Caribou) hesablamalarımızda biz 93 xana qədər olan bütün uduzan mövqeləri (və bununla da qalib gələn vəzifələri) müəyyən edə bildik. 82 xanaya qədər olan bütün Chomp mövqelərinin SG-qiymətini müqayisəli hesablama səyləri ilə hesablaya bildik.
Bu mənada SG-qiymətlərin müəyyən edilməsi, qalib addımını müəyyən etməkdən daha çox hesablama baxımından daha sərfəlidir.
Əgər 4 yığma ilə Nim oynamaq 1 yığma ilə oynanan NİM-dən çətindirsə, onda 4 kvadrantla oynamaq 1 kvadrantlı Chomp'dan daha çətindirmi?
-
Nim'də bir yığının SG-dəyəri sadəcə olaraq həmin yığındakı xanaların sayıdır. (Zəhmət olmasa, yuxarıdakı şərhləri tətbiq etməklə bunu təsdiq edin ki, Nim'də bir yığın üçün SG-dəyərlərini hesablayın.) Nim'də bir neçə yığın oynamağın yeganə çətinliyi, SG-dəyərini əldə etmək üçün bu yığınların müxtəlif SG-dəyərlərini XOR etməkdir. bütün yığınlar birləşdirilmişdir.
Çompda bir mövqenin SG-qiymətini almaq hesablama baxımından bahadır (bir kvadrantda olan). iChomp-da, 4 kvadrantın SG-qiymətləri məlum olduqdan sonra bu dəyərlər xor'ed də olmalıdır, lakin bu, bir dördbucaqlının SG-qiymətini tapmaqdan çox daha asandır.
Chomp optimal oynamaq üçün mövqeyin SG-qiymətini bilmək lazım deyil, bilmək ki, qalib hərəkət kifayət qədər yaxşıdır, lakin fərq yuxarıda göstərildiyi kimi, o qədər də böyük deyil.
Beləliklə, cavab YOX, iChomp'u optimal şəkildə oynamaq Chomp'dan daha çətin deyil.
Chomp'da bir hərəkət daha yüksək SG-dəyəri olan mövqe yarada bilərmi?
- Bəli. Mövqenin SG-qiyməti bir hərəkətlə əmələ gələ bilməyən ən kiçik dəyərdir.
Chomp'da eyni SG-dəyəri ilə mövqe yaradan fərqli gedişlər ola bilərmi?
-
Bəli. Nümunələri lövhənin ölçüsünü artıraraq və 'Hərəkətlərin SG qiymətlərini göstər' düyməsinə basmaqla görə bilərsiniz. Məsələn, mövqe
###
##
#
3 qalib gediş var, hamısı SG-dəyəri 0 olan mövqe yaradır. Hətta 7 qalib gedişlə də bir mövqe tapdıq:
+ 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
Yeniliklər üçün izləyin və ya abunə olun: