iChomp

بازی‌های ترکیبیاتی : بازی‌های دو نفره که نتیجه برد یا باخت در آنها کاملا مشخص است و هیچ حرکت تصادفی و یا شانسی در آنها وجود ندارد.

بازی‌های بی‌طرفانه : بازی‌های ترکیبیاتی هستند که در آنها ، حرکت‌های مجاز فقط به وضعیت بستگی دارد و نه اینکه در حال حاضر نوبت حرکت کدامیک از این دو بازیکن است. همچنین شرایط آنها متقارن هستند. به عبارت دیگر، تنها تفاوت بازیکن ۱ با بازیکن ۲ این است که بازیکن ۱ اولین حرکت را انجام می‌دهد. مثال : بازی چامپ

بازی‌های پارتیزانی : بازی‌هایی که بی‌طرفانه نیستند. مثال: بازی شطرنج

بازی عادی : بازیکنی که آخرین حرکت را انجام دهد، برنده بازی خواهد بود. یعنی، بازیکنی که نمی‌تواند هیچ حرکتی انجام دهد ، مثلا هیچ شکلاتی باقی نمانده است که او بردارد، بازی را باخته است.

بازی بدبختی : هر بازی که در آن ، بازیکنی که آخرین حرکت را انجام می‌دهد بازنده می‌شود.

چامپ : بازی معرفی شده در سایت بازی ما که با استفاده از یک ناحیه انجام می‌شود و یک بازی بدبختی است.

آیا بازی نیم که در صفحه بازی‌های سایت کاریبو قرار دارد یک بازی عادی است یا یک بازی بدبختی؟
- بازی نیم ما یک بازی بدبختی است. زیرا بازیکنی که آخرین چوب کبریت را می‌گیرد بازی را می‌بازد.
آیا بازی چامپ که در صفحه بازی‌های سایت کاریبو قرار دارد یک بازی عادی است یا یک بازی بدبختی؟
- بازی چامپ ما یک بازی بدبختی است. زیرا بازیکنی که آخرین شکلات را برمی‌دارد بازی را می‌بازد.
چرا استفاده از بازی عادی برای چامپ منطقی نیست؟
- استفاده از بازی عادی به این معنی است که هر کس آخرین شکلات را بردارد برنده بازی است. بنابراین بازیکنی که ابتدا حرکت می‌کند می‌تواند فوراً و با گرفتن شکلات بالا- چپ برنده شود.
آیا بازی آي‌چامپ که در صفحه بازی‌های سایت کاریبو قرار دارد یک بازی عادی است یا یک بازی بدبختی؟
- در آي‌چامپ ، بازیکنی که آخرین شکلات را برمی‌دارد برنده می‌شود، بنابراین، این بازی یک بازی عادی است.
آیا شما پیشنهادی دارید که چگونه می‌توان صفحه بازی چامپ را تغییر داد بطوریکه از بازی عادی استفاده کند اما قوانین بازی تغییر نکند ؟
- شخص می‌تواند با وضعیتی که در آن شکلات گوشه بالا-چپ (مسموم) در شروع بازی وجود نداشته باشد بازی را شروع کند. برداشتن آخرین شکلات از چنین صفحه‌ای به این معنی است که او در بازی عادی برنده می‌شود. در بازی بدبختی و با وجود این شکلات، بازیکن دیگر باید آن را بردارد و بازی را خواهد باخت.
  
  بنابراین، داشتن یک شکلات در گوشه بالا-چپ و استفاده از بازی بدبختی و نداشتن این شکلات در شروع بازی و استفاده از بازی عادی ، هر دو دقیقا مشابه خواهند بود.

بازی آي‌چامپ به شکلی طراحی شده است که چهار بازی چامپ بطور هم‌زمان و به صورت یک بازی عادی انجام می‌شود. این کار باعث زیباتر شدن بازی از دو جنبه می‌شود که در زیر توضیح داده خواهد شد. همچنین، بازی آي‌چامپ از بازی چامپ خیلی سخت‌تر نیست به شرط آنکه بازیکن از مطالبی که در بخش

شرح داده شده است استفاده کند. این بازی در دسته بازی‌های بی‌طرفانه ترکیبیاتی. قرار می‌گیرد. این نظریه دو کار برای ما انجام می‌دهد :
1. الگوریتمی را به ما می‌دهد که برای هر بازی (یعنی هر وضعیت) یک عدد تعیین می‌کند (ما آن را SG-مقدار می‌نامیم) به گونه‌ای که SG-مقدار یک وضعیت برابر۰ است اگر و تنها اگر یک وضعیت بازنده باشد. (در نظریه بازی‌های ترکیبیاتی آن را یک P-وضعیت می‌نامند و نشان می‌دهد که بازیکن قبلی یک حرکت برنده را انجام داده است). یعنی اگر SG-مقدار یک وضعیت برابر 1، 2، 3 ، ... باشد، یک وضعیت برنده است (که آن را یک N-وضعیت می‌نامند.) در این صورت، اگر بازیکن بهترین حرکت‌های ممکن را انجام دهد می‌تواند بازی را ببرد.
2. هدف دوم نظریه اسپراگ-گروندی (SGT) توصیف چگونگی پیروزی در یک بازی است که از چندین وضعیت بازی تشکیل شده است و در یک زمان انجام می‌شود. یک حرکت در چنین بازی ترکیبی با انجام یک حرکت در یکی از وضعیت‌هایی که با هم ترکیب شده‌اند انجام می‌شود.
  
  چیزی که بازیکن باید بداند SG-مقدار هر یک از وضعیت‌های موجود در ترکیب است. برای پیدا کردن آنها لازم است که SG-مقدار پس از هر حرکت و در هر یک از این وضعیت‌های ترکیبی را بداند. دانستن این مقدارها برای انجام بهترین حرکت ضروری است.
  
  به عنوان مثال : در بازی نیم ، بازیکن یک یا دو یا چند دسته چوب کبریت‌ دارد. اگر SG-مقدار هر دسته را بطور جداگانه بدانیم آنگاه نظریه اسپراگ-گروندی (SGT) به ما می‌گوید که چگونه یک بازی بهینه انجام دهیم و تعداد مناسب چوب کبریت‌هایی که باید از هر یک از این دسته‌ها برداریم را مشخص می‌کند.
نکته شگفت‌انگیز در مورد نظریه اسپراگ-گروندی (SGT) این است که وضعیت‌هایی که می‌توانند به یک بازی ترکیبی تبدیل شوند نه تنها سطرهای بازی نیم هستند بلکه هر وضعیتی از هر بازی‌های بی‌طرفانه ترکیبیاتی. به عنوان مثال، می‌توان چندین وضعیت چامپ را به یک بازی "سوپر چامپ " ترکیب کرد، یا می‌توان یک بازی را به صورت بهینه انجام داد که با ۵ وضعیت مختلف چامپ و ۳ دسته چوب کبریت شروع می‌شود و در هر یک از ۸ وضعیت می‌توان در هر زمان حرکت انجام داد.

آي‌چامپ نسخه جدیدی از چامپ معرفی شده توسط مسابقات کاریبو است که در این صفحه وب بازی می‌شود. حرف انگلیسی 'i' در آي‌چامپ مخفف 'ایزوتروپیک' است، به این معنی تمام جهت‌‌ها بطور یکنواخت در نظر گرفته می‌شوند.

در چامپ معمولی ، حذف یک شکلات باعث حذف تمام شکلات‌های شرق و جنوب آن می‌شود. بنابراین، جهت‌های شرق و جنوب نقش ویژه‌ای دارند.

در آي‌چامپ ، با توجه به موقعیت شکلات انتخاب شده ، شکلات‌ها ممکن است در جهت‌های دیگر نیز حذف شوند. اگر این شکلات مثلاً در جهت شمال غربی مرکز باشد آنگاه تمام شکلات‌های شمال یا غرب نیز حذف می‌شوند.

از بین بردن قوانین مصنوعی، به عنوان مثال، قاعده‌ای که شرق و جنوب خاص هستند معمولاً برای زیباتر کردن یک بازی از نظر ریاضی در نظر گرفته می‌شود.

در مقایسه با چامپ ، زیباسازی دیگری نیز در آي‌چامپ وجود دارد.

در چامپ شکلات گوشه بالا-چپ نقش ویژه‌ای نسبت به شکلات‌های دیگر دارد. اگر این شکلات، تنها شکلات موجود در صفحه بازی باشد با برداشته شدن آن شکلات بازی به پایان می‌رسد اما اگر شکلات دیگری حذف شود بازی ادامه خواهد داشت. می‌توان بازی چامپ را بدون آن شکلات شروع کرد و با بقیه شکلات‌ها مانند قبل بازی کرد، اما این هم یک قانون مصنوعی خواهد بود که مثلا چرا بازی را بدون آن شکلات و نه بدون شکلات‌های دیگر شروع کنیم.

در آي‌چامپ تمام شکلات‌ها در شروع بازی وجود دارند و با همه بطور یکسان برخورد می‌شود و بدون اینکه بازی به طور خودکار پایان یابد ، هر شکلاتی را می‌توان حذف کرد.

برخی از سوال‌هایی که ممکن است به ذهن برسد :

آیا آي‌چامپ یک بازی بی اهمیت و ساده است که از ترکیب 4 بازی ساده چامپ و به عنوان یک 'بازی عادی' انجام می‌شود ؟
- پاسخ این سوال نه است. به عنوان مثال، بازی نیم با یک توده چوب کبریت‌ یک بازی ساده و بی اهمیت است. به عنوان یک 'بازی عادی', می‌توان تمام چوب کبریت‌ها را در یک حرکت حذف کرده و برنده شد. همچنین ، به عنوان یک 'بازی بدبختی', بازیکن می‌تواند با حذف همه چوب کبریت‌ها به جز یک چوب کبریت برنده شود. با این وجود، ترکیب چنین بازی‌های نیم شامل 1 دسته چوب کبریت ، به یک بازی نیم با چند دسته چوب کبریت در صفحه بازی‌های نیم ما ساده و بی اهمیت نیست.
  
  به طور مشابه ، در اینجا : یک بازی چامپ به عنوان یک 'بازی عادی' بی ارزش است چرا که بازیکن می‌تواند تمام شکلات‌ها را در یک حرکت حذف کرده و برنده شود. اما ترکیب ۴ بازی‌ چامپ بی اهمیت نیست.
خلاصه مقایسه
- آي‌چامپ از نظر ریاضی زیباتر از چامپ است زیرا به طور مصنوعی جهت‌های جنوب و شرق را استثنا نمی‌کند و به یک شکلات نقش ویژه‌ای نمی‌دهد. به نظر می‌رسد که آي‌چامپ بسیار دشوارتر از چامپ باشد اما نظریه اسپراگ-گروندی (SGT) به ما کمک می‌کند. برای این کار کافی است که SG-مقدار هر یک از بازی‌های چامپ چهارگانه را محاسبه کرده و در نتیجه بهترین حرکت ممکن را پیدا کنیم.

یای انحصاری (یای مانعه الجمع) یا بطور خلاصه XOR ، یک عمل دوتایی منطقی است. با استفاده از دستگاه دودویی می‌تواند یکی از دو مقدار درست (=۱) یا غلط (=۰) را داشته باشد. عمل XOR بر روی دو مقدار دودویی با جدول زیر تعریف می‌شود.

a b a XOR b
1 1 0
1 0 1
0 1 1
0 0 0

در حالیکه استفاده از این عمل بر روی مقدارهای 1 (درست) یا 0 (نادرست) آسان است، برای محاسبات ما باید قادر به انجام XOR بر روی دو عدد باشد. این کار هم امکان‌پذیر است اما برای اینکه عمل XOR قا استفاده باشد به یک گام دیگر نیاز داریم.

کاری که باید ابتدا انجام شود این است که عددها باید در دستگاه شمارش دودویی تبدیل شوند، یعنی از مبنای (پایه) ۱۰ به مبنای ۲ تبدیل شوند.

چگونه می‌توان یک عدد را از مبنای ۱۰ به مبنای ۲ تبدیل کرد ؟
- از الگوریتم زیر می‌توان برای تبدیل عدد طبیعی n در مبنای ۱۰ به مبنای ۲ استفاده کرد. (یادآوری می‌شود که 2⁰ = 1):
  1. بزرگترین توان p از 2 را پیدا کنید بطوری که 2^p ≤ n.
  2. رقم 1 را نوشته و عدد 2^p را از n کم کنید.
  3. اگر p = 0 آنگاه کار تمام شده است و در غیر این صورت 1 واحد از p کم کرده و ادامه دهید.
  4. اگر 2^p > n یک رقم 0 ثبت کنید و در غیر این صورت اگر 2^p را از n کم کرده و رقم 1 را ثبت کنید.
  5. به گام 3 برگردید.
  دنباله ۱ و ۰ که با این الگوریتم ثبت کرده‌اید، نمایش عدد n در دستگاه شمارش دودویی خواهد بود. مثال :
  
  اجازه دهید عدد 13 را به مبنای 2 تبدیل کنیم. ما با پیدا کردن بالاترین توان2 که کمتر یا برابر 13 باشد شروع می‌کنیم که 2³، یا 8 است. آنگاه یک رقم ۱ را نوشته و ۸ را از ۱۳ کم می‌کنیم که عدد ۵ را به ما می‌دهد. بعد بررسی می‌کنیم 2⁽³⁻¹⁾ = 2² = 4. به خاطر نامساوی 4 ≤ 5 یک رقم 1 ثبت کرده و 4 از 5 کم می‌کنیم که به ما عدد 1را می‌دهد. توان بعدی کوچکتر از 2 2¹ = 2 است. چون 2 > 1 ، بنابراین ما یک رقم 0 ثبت کرده و توان بعدی ۲ ۲^{۰ = ۱} است که برابر n یعنی ۱ است، بنابراین یک رقم ۱ را ثبت کرده عدد ۱ را از ۱ کم می‌کنیم و به ما ۰ می‌دهد. چون به توان p = 0 رسیده‌اسم الگوریتم را متوقف می‌کنیم. بنابراین 13 (مبنای 10) = 1101 (مبنای 2).
  
  پس از اینکه دو عدد را به نمایش دودویی تبدیل کردم ، می‌توانیم عمل XOR را بر روی ارقام متناظر دو عدد دودویی انجام دهیم. نتیجه این عمل یک عدد دودویی است که اگر لازم باشد و برای استفاده راحت‌تر در آینده می‌توان آن را به مبنای 10 تبدیل کرد. مثال:
  
  اجازه دهید XOR اعداد 6 و 13 را محاسبه کنیم. نمایش دودویی برای این دو عدد ۶ = ۱۱۰ و ۱۳ = ۱۱۰۱ است. در ابتدا ۰ را در سمت چپ عدد کوچکتر اضافه می‌کنیم به طوری که تعداد رقم‌های هر دو عدد یکسان باشد، بنابراین ۶ = ۰۱۱۰. سپس می‌توانیم XOR را با نوشتن آنها زیر هم و انجام عملیات بر روی رقم‌های متناظر انجام داد :
  
  0110
  XOR 1101
  ------
  1011
  
  بنابراین 6 XOR 13 = 1011 (مبنای 2) = 1×2³+0×2²+1×2¹+1×2⁰ = 8+2+1 = 11 (مبنای 10).
بیایید اطلاعات خود را در مورد XOR با مطرح کردن چند سوال بررسی کنیم.

برای یک عدد دلخواه m مقدار m XOR m چقدر است ؟
- برای یک عدد دلخواه m داریم m XOR m = 0 . زیرا 0 XOR 0 = 0 و همچنین 1 XOR 1 = 0.
آیا برای هر عدد n, m داریم n XOR m = m XOR n ؟
- بله، چون 1 XOR 0 = 0 XOR 1 (=1).
برای یک عدد دلخواه m مقدار 0 XOR m چقدر است ؟
- 0 XOR m = m چون 0 XOR 0 = 0 و 0 XOR 1 = 1.
اگر عمل XOR روی یک عدد m با عدد دیگر n به صورت m XOR n عمل کند آنگاه کدام رقم m تغییر می‌کند ؟
- اگر یک رقم m متناظر با رقم ۰ از n باشد آنگاه یک رقم بدون تغییر است (چون ۰ XOR ۰ = ۰ و ۱ XOR ۰ = ۱). اگر یک رقم m متناظر با یک رقم ۱از n باشد آنگاه آن رقم تغییر می‌کند (چون ۰ XOR ۱ = ۱ و ۱ XOR ۱ = ۰). به این ترتیب ، XOR n تمام رقم‌هایی را تغییر می‌دهد که رقم متناظر با آنها در n رقم ۱ است.

a	b	a XOR b
1	1	0
1	0	1
0	1	1
0	0	0

الگوریتم زیر SG-مقدار هر وضعیت P را در هر بازی ترکیبیاتی بی‌طرفانه محاسبه می‌کند. ما آن را با استفاده از بازی چامپ توضیح می‌دهیم.
- به هر وضعیت بازی که یک وضعیت بازنده است عدد 0 را به SG-مقدار نسبت می‌دهیم. در بازی چامپ ، یک وضعیت شامل فقط یک شکلات (در گوشه شمال غربی) تنها وضعیت بدون حرکت بعدی است و بنابراین یک وضعیت بازنده با SG-مقدار برابر 0 است.
- ما به مقدارهای SG تمام وضعیت‌هایی نیاز داریم با یک حرکت می‌توانند به یک وضعیت P (بازنده) تبدیل می‌شوند. بنابراین اگر وضعیت P دارای n شکلات است پس n-1 حرکت ممکن وجود دارد : به جز شکلات گوشه شمال غربی، هر شکلات‌ دیگر همراه با تمام شکلات‌های زیر یا سمت چپ آن شکلات را می‌توان حذف کرد.
- SG-مقدار یک وضعیت P کوچکترین عدد غیر منفی است که کمترین SG-مقدار است که در n-1 وضعیت جدید محاسبه می‌شود.
این یک الگوریتم بازگشتی است زیرا برای محاسبه SG-مقدار یک وضعیت P به مقدارهایSG تمام وضعیت‌های قابل رسیدن از P در یک حرکت نیاز داریم. این الگوریتم قابل استفاده است زیرا SG-مقدار که مورد نیاز است مربوط به وضعیت‌های کوچکتر و شامل شکلات‌های کمتر است و SG-مقدار کوچکترین وضعیت ممکن (یک شکلات در گوشه شمال غرب) شناخته شده است.

ویژگی 3 در بازی بالا، با انتخاب یک صفحه با عرض و ارتفاع بزرگتر و کلیک کردن بر روی 'صفحه تصادفی' بررسی کنید.
- هنگامی که شما ماوس را بر روی یک شکلات قرار می‌دهید , این شکلات و شکلات‌های دیگری که حذف خواهند شد مشخص می‌شوند. عددی که بر روی آن شکلات نمایش داده می‌شود SG-مقدار همان ناحیه به عنوان یک 'بازی عادی' (نه 'بازی بدبختی') است در صورتی که بر روی آن شکلات کلیک کنید. شما می‌توانید بررسی کنید که عدد نشان داده شده در متن 'SG-مقدار در مبنای 10:' در کنار ناحیه کوچکترین عدد نشان داده نشده در ناحیه است. شما همچنین می‌توانید بررسی کنید که اگر شما بر روی شکلات کنید آنگاه یک عدد را به عنوان ' SG-مقدار وضعیت جدید در مبنای 10 نشان می‌دهد.
نحوه محاسبه سریع مقدارهای SG :

از آنجا که یک وضعیت ممکن است از وضعیت‌های مختلف و با یک حرکت ایجاد شود و می‌تواند بارها و بارها در ظاهر شود، پس محاسبه مجدد آن به معنای هدر دادن زمان و تلاش بیهوده خواهد بود. بنابراین، هنگامی که SG-مقدار یک وضعیت P محاسبه شد، باید برای استفاده بعدی ذخیره شود.

اگر کسی بخواهد SG-مقدار همه وضعیت‌ها را ، تا اندازه‌ای که ممکن است مورد نیاز باشد ، محاسبه کند، آنگاه روش زیر مفید است. با وضعیت شامل یک شکلات (در گوشه شمال غرب) SG-مقدار آن برابر صفر شروع می‌شود. سپس از الگوریتم فوق برای محاسبه مقدارهای SG تمام وضعیت‌های شامل ۲ شکلات استفاده می‌کنیم، سپس تمام وضعیت‌های شامل ۳ شکلات و . . . .

وضعیت آي‌چامپ شامل 4 وضعیت چامپ ، یکی در هر چهارگوش از هیئت مدیره است.
- در ابتدا ما تعیین SG-مقدار هر یک از 4 وضعیت چامپ با استفاده از قانون چامپ 'بازی بدبختی' است. چهارگوش خالی یک وضعیت چامپ نیست، بنابراین ما به آن مقدار −1 می‌دهد.
- سپس به هر مقدار ۱ اضافه می‌کنیم.
- برای هر یک از ۴ عدد حاصل بازنمایی دودویی را محاسبه می‌کنیم.
- مقدار XOR عدد ۴ دودویی را محاسبه می‌کنیم و SG-مقدار آن وضعیت (به صورت دودویی) را بدست می‌آوریم. اگر این مقدار صفر باشد، یک وضعیت بازنده است، در غیر این صورت یک وضعیت برنده است.

چرا يه "1" اضافه کرديم؟

ما اضافه کردن 1 به منظور به دست آوردن SG-مقدار وضعیت چامپ تحت 'بازی عادی' از SG-مقدار تحت 'بازی بدبختی'. قضیه زیر، این مورد را توضیح می‌دهد.

قضیه :
--------
برای به دست آوردن SG-مقدار وضعیت چامپ تحت 'بازی عادی' (به عنوان یکی از گرفتن آخرین شکلات برنده بازی است که راه مشترک برای بازی چامپ نیست) یکی نیاز به اضافه کردن 1 به SG-مقدار همان وضعیت تحت 'بازی بدبختی' (به عنوان یکی از گرفتن آخرین شکلات از دست می‌دهد که راه مشترک برای بازی چامپ ).

آیا ممکن است که تلاش کنید و این نظریه را به کمک استقرا ، ثابت کنید ؟
- اثبات (با استقرا (و همراه با بیان جزئیات دقیق)) :
  
  حالت پایه (1 شکلات ) :
  -------------------
  تحت 'بازی عادی' هیئت مدیره خالی بدون شکلات یک وضعیت بازنده است و در نتیجه SG-مقدار صفر است. علاوه بر این ، تحت 'بازی عادی' برای هیئت مدیره با یک شکلات (در گوشه بالا-چپ) تنها حرکت ممکن است برای حذف این شکلات عملکرد وضعیت با SG-مقدار 0. بنابراین ، تحت 'بازی عادی' کوچکترین غیر منفی SG-مقدار است که نمی‌تواند توسط یک حرکت به دست آورد 1 است ، به طوری که SG-مقدار یک وضعیت با یک شکلات تحت 'بازی عادی'.
  
  تحت 'بازی بدبختی' داشتن یک شکلات یک وضعیت بازنده با SG-مقدار 0 است.
  
  بنابراین ، برای 1 شکلات 'بازی عادی' SG-مقدار است 1 بزرگتر از 'بازی بدبختی' ارزش.
  
  گام استقرا
  ---------------
  
  فرض استقرا (n شکلات ) :
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  ما فرض می‌کنیم که یک عدد n وجود دارد به طوری که برای تمام وضعیت‌های با ≥1 و ≤n شکلات SG-مقدار تحت 'بازی عادی' یکی بزرگتر از تحت 'بازی بدبختی'. حکم استقرا (n+1 شکلات ):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  ما نشان خواهیم داد که این است که پس از آن نیز مورد برای تمام وضعیت‌های با n +1 شکلات .
  
  مرحله استقرا (n شکلات → n+1 شکلات ):
  ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
  برای هر وضعیت 'بازی بدبختی' و 'بازی عادی' اجازه می‌دهد تا همان حرکت به جز که 'بازی عادی' نیز اجازه می‌دهد تا به تمام شکلات را از طریق شکلات گوشه بالا-چپ.
  
  اگر وضعیت دارای n+1 شکلات ، پس از آن ساخت یک حرکت تولید وضعیت با اکثر n شکلات‌ که ما می‌توانیم فرض استقرا اعمال:
  
  فهرست SG-مقدارهای به دست آمده تحت 'بازی عادی' بنابراین از لیست SG-مقدارهای قابل به دست آمده تحت 'بازی بدبختی' هر یک افزایش 1 و با اضافه کردن ارزش 0 از طریق گرفتن تمام شکلات به دست آمده است.
  
  بنابراین کوچکترین عدد غیر منفی NOT قابل به دست آوردن تحت 'بازی عادی' است 1 بالاتر از کوچکترین عدد غیر منفی قابل به دست آوردن تحت 'ببازی بدبختی'. به عبارت دیگر، برای وضعیت اصلی با n+1 شکلات SG-مقدار تحت 'بازی عادی' یکی بالاتر از SG-مقدار تحت 'بازی بدبختی' است. ∎ (این اثبات را کامل می‌کند.)

هدف این است که حرکتی به گونه‌ای انجام شود که SG-مقدار وضعیت حاصل صفر باشد. هر حرکتي که يکي انجام بده بايد توي يکي از 4 چهارگانه باشه این بدان معناست که SG-مقدار از وضعیت که در آن حرکت انجام شده است و SG-مقدارهای دیگر 3 چهارگانه بدون تغییر همه XOR'ed باید صفر بدهد. این مورد است اگر و تنها اگر دیگر 3 SG-مقدار XOR'ed را دقیقا SG-مقدار چهارگوش جدید پس از انجام حرکت (نگاه کنید به بیشتر زیر برای اثبات این بیانیه). بنابراین رویه به این قرار است:
- (ساده) مورد: دو تا از چهارگانه‌های ۴ دارای SG-مقدار یکسان هستند. سپس XOR از این دو مقدار برابر صفر خواهد داد بنابراین قرار است هر دو چهارگانه نادیده گرفته شوند.
- (عمومی) مورد:
چرا اين يه حرکت برنده است؟
- لطفا خودتان را در مورد خواص XOR به عنوان زودتر نشان داده شده برای پاسخ به سوالات زیر یادآوری.
  
  if you = w XOR xOR y XOR z, then what is y XOR u ?
  - با استفاده از قوانین XOR آموخته زودتر ما دریافت کنید
       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.
  اگر y با y XOR u جایگزین شده است پس XOR جدید از تمام 4 SG-مقدارهای چه است؟
  - XOR جدید خواهد بود
    (y XOR u) XOR w XOR x XOR z
    = (w XOR x XOR z) XOR (w XOR x XOR z)
    = 0
    به دلیل m XOR m = 0 برای هر عدد m.
    
    این بدان معناست که SG-مقدار جدید کل هیئت مدیره صفر خواهد بود، به طوری که یک وضعیت بازنده به عنوان در نظر گرفته شده خواهد بود.
  چرا باید یک حرکت وجود داشته باشد که یک SG-مقدار برابر y را به یک مقدار پایین تر تغییر دهد؟
  - با توجه به تعریف : یک وضعیت دارای SG-مقدار برابر y است اگر و تنها اگر حرکت‌هایی وجود داشته باشد که وضعیت‌هایی با SG-مقدار برابر 0,1,..,(y-1 تولید کند. بنابراین ، اگر y > (y XOR u) ، پس باید وجود داشته باشد حرکت تولید SG-مقدار (y XOR u) < y.
  چیزی که باقی می‌ماند تا پاسخ داده شود این است:
  
  چرا باید وجود داشته باشد چهارگوش با مقدار SG y است که راضی y > (y XOR u)؟
  - یک یادآوری:
    پیش از این، هنگامی که ما در مورد خواص XOR یاد گرفتیم، دیدیم: XOR u تمام ارقامی را تلنگر می‌کند که رقم مربوطه در u یک ۱ است.
    
    اگر شما ≠ 0 ، سپس تو شامل بالاترین قدرت از 2 ، می‌گویند 2^p. این قدرت از 2 باید در تعداد فرد از 4 SG - مقدارهای رخ می‌دهد ، بنابراین حداقل در یک ، می‌گویند y.
    
    این بدان معنی است که، هنگامی که محاسبات y XOR u، این 1 در y می‌شود به 0 توسط 1 مربوطه در u لغزش. ممکن است رقم‌های دودویی دیگری نیز وجود داشته باشد که در y واقع در سمت راست این ۱ قرار دارند. بزرگترین مقدار ممکن y − (y XOR u) در صورتی رخ می‌دهد که ارقام در y به سمت راست این ۱ صفر باشند و ارقام در شما به سمت راست آن ۱ یکی باشند. In that case u = 111..111 changes y = *100..00 (where * stands for any number of digits) to y XOR u = *011..11. تفاوت آنها در این است:
    
    y − (y XOR u)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)
    = 2^p − (2^p−1 + 2^p−2+ ... +2⁰)× (2-1)/(2-1)
    = 2^p − (2^p−1)/(2-1)
    = 1.
    این بدان معناست که y حداقل یک بزرگتر از (y XOR u) است. ∎
سعی کنید این الگوریتم را با بازی و برنده شدن در برابر 'دشواری: سخت'.
- برای شروع، "دشواری: سخت" را انتخاب کنید که بازی بهینه کامپیوتر را تضمین می‌کند. اگر شما هنوز هم برنده و سپس شما بازی هر حرکت بهینه.
  
  SG-مقدار هر چهارگوش در مبنای ۱۰ و مبنای ۲ نشان داده شده است. بررسی کنید که این عدد کوچکترین مقداری است که در چهارگوش نشان داده نشده است.
  
  در زیر XOR از هر ۴ SG-مقدارهای به نام u نشان داده شده است. بررسی ارزش شما به سادگی با تغییر هر جفت از دو 1 در 4 SG-مقدار به 0 اگر دو 1 در یک وضعیت هستند. سپس 1 باقی مانده را به یک عدد دودویی قرار داده و آن را به مبنای 10 تبدیل کنید.
  
  برای ادامه حرکت همانطور که در بالا شرح داده شد:
  - پیدا کردن یکی از 4 SG-مقدارهای ، می‌گویند y ، که دارای 1 در همان وضعیت سمت چپ ترین 1 در u.
  - محاسبه y XOR u به صورت دودویی و سپس تبدیل آن به مبنای 10.
  - در چهارگوش y کلیک کنید شکلات با محاسبات y XOR u.
  - بازی حرکت خود را در این راه تا زمانی که شما برنده شد.
  - دوباره بازی کنید اما این بار با یک حرکت تصادفی شروع می‌شود. مگر اینکه شما خوش شانس بودند و توسط تصادف یک حرکت برنده بازی، شما قادر به برنده شدن در این بازی حتی اگر شما پس از آن سعی کنید به بازی مطلوب.

برای محاسبه SG-مقدار یک وضعیت ، باید SG-مقدارهای تمام وضعیت‌هایی را که با انجام یک حرکت ساخته می‌شوند ، به دست آورد. این یک فرایند بازگشتی است. بنابراین ما باید کار را با وضعیت‌های شامل تعداد کمی شکلات شروع کرده و ادامه دهیم.

آیا می‌توانید SG-مقدار را برای وضعیت‌های شامل 1 ، 2 ، 3 و . . . شکات در یک سطر را به دست آورید ؟
- وضعیت شامل فقط 1 شکلات (در گوشه بالا-چپ) یک وضعیت بازنده است و بنابراین SG-مقدار آن برابر 0 است.
  
  در وضعیت شامل 2 شکلات (در سطر بالا و یا ستون سمت چپ) ، تنها حرکت ممکن برداشتن یک شکلات است و یک وضعیت بازنده با SG-مقدار برابر 0 ایجاد می‌شود. بنابراین کوچکترین SG-مقدارغیر منفی که با یک حرکت نمی‌توان به دست آورد ۱ است، بنابر این ، SG-مقدار یک وضعیت شامل ۲ شکلات برابر ۱ است.
  
  در وضعیت شامل 3 شکلات (همه در سطر بالا) ، دو انتخاب وجود دارد. برداشتن 1 شکلات یا برداشتن 2 شکلات. SG-مقدار این دو وضعیت ، به ترتیب، برابر 1 و 0 است. بنابراین مقدار SG این وضعیت برابر 2 است.
  
  به طور مشابه، SG-مقدار وضعیت شامل n شکلات (همه در سطر بالا) برابر n-1 است.
  
  اجازه دهید 3 شکلات ، 2 شکلات در سطر بالا و 2 شکلات در ستون سمت چپ در نظر بگیریم. ما می‌توانیم تنها ۱ شکلات را حذف کنیم و به مقدار SG ۱ اما نه ۰ برسند، بنابراین کوچکترین مقدارSG که نمی‌توان به دست داد ۰ است که بنابراین مقدار SG این وضعیت است. این یک وضعیت بازنده است.
آیا می‌توانید SG-مقدار از یک وضعیت با m+n−1 شکلات که n در سطر بالا هستند و m شکلات در ستون سمت چپ پیدا کنید؟
- تنها می‌توان شکلات‌ها را از سطر بالا یا از ستون سمت چپ حذف کرد. بنابراین SG-مقدار همان داشتن دو چهارگانه، یکی با n شکلات در سطر بالا و یکی با شکلات m در ستون سمت چپ است. بدین ترتیب SG-مقدار (m-1) XOR (n-1) است. این همان بازی نیم با دو دسته و 'بازی عادی' قانون که در آن چوب کبریت‌ها را می‌توان از تنها یک دسته در یک حرکت حذف شده است.
آیا می‌توانید SG-مقدار یک وضعیت با شکلات تنها در دو سطر بالا پیدا کنید؟
- فرمول‌های این وضعیت‌ها پیچیده تر هستند. تا آنجا که می‌دانیم پیش از این منتشر نشده بودند. شما می‌توانید سعی کنید آنها را برای تعداد کمی از شکلات تایید.
  
  تعداد شکلات‌ها در سطر اول و سطر دوم را ، به ترتیب ، برابر n و m در نظر می‌گیریم.
  
  اگر n حتی پس از آن
    k = (n-2)/2
    اگر m حتی پس از آن
      a = m/2
      SG-مقدار = 2*k+a+1
    else (m is odd)
      a = (m-1)/2
      اگر یک ≤ (k/2) سپس SG-مقدار = 2*k-a
      دیگری SG-مقدار = 3*(k-a)
  else (n is odd)
    k = (n-1)/2
    اگر m حتی پس از آن
      a = m/2
      اگر یک ≤ (k/2) سپس SG-مقدار = 2*k-a
      دیگری SG-مقدار = 3*(k-a)
    else (m is odd)
      a = (m-1)/2
      SG-مقدار = 2*k+a+1
  
  بررسی کنید که آیا فرمول‌ها با استفاده از تخته بازی بالا درست هستند یا خیر.
  - حداقل ارتفاع تخته را انتخاب کنید به طوری که چهارگوش با تنها دو سطر شکلات وجود دارد. پس از استفاده از فرمول‌های بالا شما باید یک SG-مقدار است که یکی پایین تر از ارزش نشان داده شده تحت ' SG-مقدار مبنای 10:' به دست آوردن چرا که فرمول‌ها برای 'بازی بدبختی' در حالی که آي‌چامپ با استفاده از 'بازی عادی'.

ما با یک مشاهده شروع می‌کنیم: قوانین چامپ هیچ تفاوتی بین جهت شرق و جنوب ایجاد نمی‌کند.

چه پیامد برای SG-مقدارهای دو وضعیت است که آینه متقارن به یکدیگر در زیر آینه بر روی مورب است که از گوشه بالا-چپ شروع می‌شود؟
- از آنجا که جهت شرق و جنوب به یکدیگر آینه این بدان معنی است که هر دو باید SG-مقدار یکسان داشته باشد.
چه معنی است که برای آي‌چامپ زمانی که 2 چهارگوش وضعیت است که متقارن تحت چرخش چهارگوش و / یا آینه مورب؟
- هر دو چهارگانه را می‌توان نادیده گرفت. چرا? هر دو چهارگانه دارای SG-مقدار یکسان تحت بازی بدبختی و پس از اضافه کردن ۱ نیز همان SG-مقدار تحت بازی عادی هستند. XOR از این دو مقدارهای برابر صفر می‌دهد. بنابراین، هر دو چهارگانه هیچ سهمی در SG-مقدار کل وضعیت هیئت مدیره ندارد.
بنابراین کدام استراتژی بازی باید کار کند؟
- باید یک حرکت انجام داد که دو جفت چهارگانه ایجاد می‌کند به طوری که چهارگانه‌ها در هر جفت دارای وضعیت‌های متقارن با SG-مقدارهای برابر، می‌گویند A و A، و B و B باشند. سپس، SG-مقدار از ترکیب هر 4 چهارگانه XOR A XOR B XOR B = 0 XOR 0 = 0 یا (A XOR B) XOR (A XOR B) = 0 تا همیشه 0 است. یکی وضعیت بازنده‌ای ایجاد کرد.
  
  به همان اندازه یکی نباید حرکت کند که دو چهارگانه متقارن باقی می‌ماند و دو تای دیگر آنها را می‌توان در یک حرکت توسط حریف به دیگری تغییر داد. این امر به حریف اجازه می‌دهد تا وضعیت بازنده‌ای ایجاد کند.

در اینجا تعدادی از سوال‌های آزمون که به کمک آنها شما می‌توانید درک خود را از بازی‌های چامپ و آي‌چامپ و همچنین نظریه اسپراگ-گروندی (SGT) بیازمایید.

آیا شناختن SG-مقدار برای انجام بازی چامپ کافی است ؟
- بله. اگر SG-مقدار یک وضعیت صفر باشد، آنگاه یک وضعیت بازنده است (چون هیچ حرکت وجود ندارد تا آن را صفر کند، بنابراین هیچ حرکت برنده‌ای وجود ندارد، بنابراین یک وضعیت بازنده است). اگر SG-مقدار بزرگتر از صفر باشد، آنگاه این بدان معنی است که یک حرکت وجود دارد تا SG-مقدار از وضعیت حاصل صفر شود، بنابراین یک حرکت برنده وجود دارد.
آیا یکی نیاز به دانستن SG-مقدار از وضعیت چامپ به بازی چامپ کاملا؟
- قهقهه برای بازی چامپ ما نیاز به پیدا کردن یک حرکت است که تولید یک وضعیت بازنده . اگر چنین حرکتی وجود نداشته باشد آنگاه وضعیت بازنده‌ای است و هر حرکتی را می‌توان انجام داد. اما اگر چنین حرکتی پیدا شود، می‌توان جستجو را متوقف کرد. SG-مقدار مورد نیاز نیست.
SG-مقدارهای برای آن زمان خوب هستند؟
- آنها تنها مورد نیاز برای انجام چند بازی چامپ به موازات به عنوان یک بازی جدید، مانند در آي‌چامپ.
چقدر سخت‌تر است در چامپ به محاسبه SG-مقدار یک وضعیت از یک حرکت برنده؟
- برای بازی چامپ ما نیاز به پیدا کردن یک حرکت است که تولید یک وضعیت بازنده . اگر چنین حرکتی وجود نداشته باشد آنگاه وضعیت بازنده‌ای است و هر حرکتی را می‌توان انجام داد. اما اگر چنین حرکتی پیدا شود، می‌توان جستجو را متوقف کرد.
  
  تلاش برای یافتن SG-مقدار یک وضعیت معمولاً بیشتر است. برای پیدا کردن SG-مقدار همیشه باید حرکت ALL را جستجو کند تا تمام SG-مقدارهای وضعیت‌های حاصل را پیدا کند و کوچکترین مقدار غیر منفی را پیدا کند که در یک حرکت نمی‌توان به آن رسید. این مقدار SG-مقدار وضعیت است.
  
  به عنوان مثال، در محاسبات ما (کاریبو) ما قادر به تعیین تمام وضعیت‌های بازنده (و در نتیجه برنده وضعیت ) با تا 93 شکلات . با تلاش محاسباتی قابل مقایسه ما قادر به محاسبه مقدار SG تمام وضعیت‌های چامپ با تا 82 شکلات .
  
  به این معنا تعیین SG-مقدارهای از نظر محاسباتی گران تر از تعیین یک حرکت برنده است.
اگر نیم با 4 دسته سخت‌تر است به بازی از نیم با 1 دسته ، پس از آن آي‌چامپ با 4 چهار برابر بسیار سخت‌تر به بازی از چامپ با 1 چهارگوش؟
- در نیم، SG-مقدار یک دسته به سادگی تعداد چوب کبریت‌ها در آن دسته است. (لطفا تایید این با استفاده از نظرات بالا چگونه به محاسبه SG-مقدارهای به یک پشته تنها در نیم.) تنها عارضه بازی چند دسته در نیم این است که XOR SG-مقدارهای های مختلف از این دسته برای به دست آوردن SG-مقدار تمام دسته ترکیب شده است.
  
  در چامپ از نظر محاسباتی گران است برای به دست آوردن SG-مقدار یک وضعیت (که در یک چهارگوش است). در آي‌چامپ ، هنگامی که SG-مقدارهای چهارگانه 4 شناخته شده است، این مقدارهای نیاز به XOR'ed نیز دارند، اما این بسیار آسان تر از پیدا کردن SG-مقدار یک چهارگوش است.
  
  برای بازی چامپ بهینه یکی نیاز به دانستن SG-مقدار وضعیت ، دانستن یک حرکت برنده به اندازه کافی خوب است، اما همانطور که بالاتر از تفاوت نشان داده شده است که بزرگ نیست.
  
  بنابراین پاسخ NO است، بازی آي‌چامپ به طور بهینه از چامپ خیلی سخت‌تر نیست.
در چامپ، آیا یک حرکت می‌تواند وضعیتی ایجاد کند که SG-مقدار بالاتری داشته باشد؟
- بله. SG-مقدار یک وضعیت کوچکترین مقداری است که نمی‌تواند توسط یک حرکت تولید شود.
در چامپ ، آیا می‌توان حرکت‌های متفاوتی وجود داشته باشد که وضعیتی با همان SG-مقدار ایجاد کند؟
- بله. شما می‌توانید مثال‌ها را با افزایش اندازه هیئت مدیره را ببینید و با کلیک بر روی دکمه 'نمایش SG-مقدارهای از حرکت'. به عنوان مثال وضعیت
  
  ###
  ##
  #
  
  دارای 3 حرکت برنده، همه ایجاد یک وضعیت با SG-مقدار. ما حتی یک وضعیت با 7 حرکت برنده پیدا کرد:
```
 + 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
```

iChomp^©

روش بازی :

روش برنده شدن :

نوبت بازیکن اول

	0110
XOR	1101
	------
	1011

iChomp©

روش بازی :

روش برنده شدن :

نوبت بازیکن اول

iChomp^©