300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutschروش بازی:
- هر بازیکن، به نوبت از روی صفحه یک آب نبات را بر میدارد.
- آب نبات حذف شده، به ربعی که آب نبات از آن انتخاب شده است بستگ ی دارد.
- The top left quadrant removes all candy from above and the left of the selected candy, the top right removes above and right, the bottom left removes below and left, and the bottom right removes below and right of the selected candy.
روش برنده شدن:
- بازیکنی که آخرین کاشی را حذف کند برنده بازی خواهد بود.
نوبت بازیکن اول
تعداد کل بازی ها: 268206
تعداد بردهای بازیکن: 35795
تعداد بردهای کامپیوتر: 232431
Access to 'Some food for thought' (SFFT) for the iChomp game can be purchased in the online shop
تعداد بردهای بازیکن: 35795
تعداد بردهای کامپیوتر: 232431
Access to 'Some food for thought' (SFFT) for the iChomp game can be purchased in the online shop
الگوریتمی که شما در این آموزش یاد خواهید گرفت برای دسته بزرگی از بازی‌ها و در بهترین حالت ممکن قابل استفاده است، بنابراین لازم است که زمانی را برای یادگیری آن صرف کنید. نکته کلیدی آن نظریه معروف اسپراگ-گروندی (SGT) خواهد بود. اگر شما می‌خواهید بدون یادگیری SGT فقط نکته‌های مهم در مورد بازی iChomp را بدانید، به بخش مربوطه در ادامه متن بروید. قبل از بیان جزئیات لازم است که به چند نکته اشاره کنیم.
نمادگذاری
-
بازیهای ترکیبیاتی: بازی های دو نفره با اطلاعات کامل و برنده شدن یا از دست دادن نتیجه و هیچ شانسی حرکت می کند.
بازی های بی طرفانه: بازی های ترکیب کننده ای که در آن حرکت های مجاز تنها به موقعیت بستگی دارد و نه اینکه یکی از این دو بازیکن در حال حاضر در حال حرکت است. همچنین پرداخت ها متقارن هستند. به عبارت دیگر تنها تفاوت بازیکن ۱ با بازیکن ۲ این است که بازیکن ۱ اول می شود. مثال: Chomp.
پارتیزان بازی : بازی است که بی طرف نیست. مثال: شطرنج.
بازی عادی: بازیکنی که آخرین حرکت را WINS انجام دهد، به این صورت است که بازیکنی که نمی تواند یک حرکت انجام دهد، به این صورت که چیزی برای گرفتن ندارد، باخت.
Misère بازی : بازیکن را به آخرین حرکت از دست می دهد.
Chomp : بازی معرفی شده در سایت بازی ما که با استفاده از یک چهارگوش و Misère بازی.
آیا بازی Nim آن را به عنوان آن را در صفحه بازی ما بازی استفاده از بازی عادی و یا misère؟
- بازی نیم ما از بازی misère استفاده می کند، زیرا بازیکنی که آخرین مسابقه را می گیرد بازی را از دست می دهد.
آیا بازی Chomp به عنوان آن است که در صفحه بازی Chomp ما بازی استفاده عادی و یا misère بازی؟
- بازی Chomp آن را به عنوان در صفحه بازی ما بازی با استفاده از بازی misère، از بازیکن که طول می کشد آخرین آب نبات از دست می دهد.
چرا استفاده از بازی عادی برای چامپ منطقی نیست؟
- استفاده از بازی عادی به این معنی است که هر طول می کشد آخرین کاشی برنده. بنابراین بازیکنی که ابتدا حرکت می کند می توانست فوراً با گرفتن کاشی در گوشه بالا سمت چپ برنده شود.
آیا بازی iChomp به عنوان آن است که در این صفحه وب بازی استفاده از عادی و یا Misère بازی؟
- در iChomp، بازیکنی که آخرین کاشی را می گیرد برنده می شود، بنابراین این بازی از Normal Play استفاده می کند.
آیا شما یک پیشنهاد برای چگونه می توان هیئت مدیره Chomp را تغییر دهید به استفاده از بازی عادی و هنوز هم بازی همان بازی؟
-
یکی می تواند با یک موقعیت که در آن (مسموم) آب نبات در گوشه بالا سمت چپ در حال حاضر از شروع گم شده شروع می شود. گرفتن آخرین آب نبات از چنین هیئت مدیره به این معنی است که یکی در بازی عادی برنده شوید. در Misère بازی و با این کاشی و سپس بازیکن دیگر باید آن را و از دست دادن است که همان نتیجه است.
بنابراین، داشتن یک کاشی گوشه بالا سمت چپ و با استفاده از Misère بازی و یا نداشتن این کاشی حق از شروع بازی و با استفاده از بازی عادی هر دو دقیقا همان بازی.
درباره iChomp
- بازی iChomp طراحی شده است به اتحادیه چهار چامپ بازی های انجام شده در همان زمان، همه تحت قانون بازی عادی. این کار باعث زیباتر شدن بازی از دو جنبه می شود که در زیر توضیح داده خواهد شد. همچنین، iChomp است که سخت تر از Chomp اگر یکی از اعمال نظریه Sprague- Grundy، که در زیر نیز شرح داده شده است.
درباره نظریه اسپراگ-گروندی
-
کلاس بازی هایی که در آن صدق می کند این است که بازی های بی طرفانه ترکیب. این نظریه دو کار برای ما انجام می دهد:
- الگوریتمی را به ما می دهد که برای هر بازی (به معنی هر موقعیت) یک عدد تعیین می کند (ما آن را SG-value می نامیم) به گونه ای که عدد ۰ باشد اگر و تنها اگر یک موقعیت بازنده باشد (به نام 'P-position' در ادبیات بر روی نظریه بازی های ترکیب کننده با 'P' نشان می دهد که 'p'revious player یک حرکت برنده را انجام داده است). یعنی اگر این SG-value 1، 2، 3 باشد، ... سپس این یک موقعیت برنده است (به نام 'N'-position در ادبیات). در آن صورت، هر 'n'ext حرکت می کند می تواند یک برد را در صورت بازی بهینه اجرا کند.
- هدف دوم نظریه SG توصیف چگونگی پیروزی در یک بازی است که متشکل از چندین موقعیت بازی شده در یک زمان است. یک حرکت در چنین بازی ترکیبی با انجام یک حرکت در هر یک از موقعیت هایی که با هم ترکیب می شوند انجام می شود.
چیزی که فرد باید بداند ارزش SG هر یک از موقعیت های ترکیبی است. برای دریافت آنها یکی نیاز به دانستن SG ارزش پس از هر حرکت در هر یک از این موقعیت های ترکیبی. این مورد نیاز است و همچنین به بازی بهینه.
به عنوان مثال: در بازی نیم یک یا دو یا چند شمع از مسابقات دارد. اگر ما می دانیم SG ارزش برای بازی هر شمع فردی به تنهایی، سپس SG نظریه به ما می گوید که چگونه به بازی بهینه با تمام این شمع با گرفتن تعداد مناسب از مسابقات از هر یک از این شمع.
چرا آي کومپ؟
-
iChomp نسخه جدیدی از Chomp معرفی شده توسط Caribou Contests است که در این صفحه وب پخش می شود. 'i' در iChomp مخفف 'ایزوتروپیک' است، به عبارتی تمام جهات به طور مساوی درمان می شوند.
در Chomp طبیعی حذف یک کاشی نیز حذف تمام کاشی به شرق و جنوب آن. بنابراین، جهت های شرق و جنوب نقش ویژه ای دارند.
در iChomp تمام کاشی در جهات دیگر ممکن است حذف و همچنین بسته به جایی که کاشی حذف شده است که نزدیک ترین به مرکز است. اگر این کاشی مثلاً در جهت شمال غربی مرکز باشد آنگاه تمام کاشی های شمال یا غرب نیز حذف می شوند.
از بین بردن قوانین مصنوعی، به عنوان مثال، قاعده ای که شرق و جنوب خاص هستند معمولاً برای زیباتر کردن یک بازی از نظر ریاضی در نظر گرفته می شود.
زیباسازی دیگری نیز وجود دارد که iChomp در مقایسه با چامپ دارد.
در Chomp کاشی در گوشه فوقانی سمت چپ نقش ویژه ای نسبت به کاشی های دیگر دارد. اگر این تنها کاشی در هیئت مدیره بازی به پایان رسید. اگر کاشی دیگری حذف شود بازی ادامه دارد. یکی می تواند Chomp بدون آن کاشی گوشه شروع بنابراین تمام کاشی ها همان درمان می شود، اما این خود را پس از آن یک قانون مصنوعی خواهد بود که چرا برای شروع بازی بدون آن کاشی و نه بدون کاشی های دیگر نیز هست.
در iChomp تمام کاشی در شروع وجود دارد و همه یکسان درمان می شود. هر کاشی را می توان بدون پایان دادن به بازی به طور خودکار حذف شده است.
برخی سوالات به وجود می آیند:
آیا iChomp یک بازی بی اهمیت است چرا که آن را ترکیب و یا 4 بازی Chomp بی اهمیت در 'بازی عادی'?
-
پاسخ نه است. به عنوان مثال بازی نیم با یک توده مسابقات بی اهمیت است. تحت 'بازی عادی', می توان تمام شمع در یک حرکت حذف و برنده. در نیم زیر 'Misère Play', یکی می تواند حذف همه به جز یک مسابقه و برنده شوید. با این وجود، ترکیب چنین بازی های نیم 1 شمع به یک بازی نیم چند شمع به عنوان در صفحه بازی های نیم ما بی اهمیت نیست.
به طور مشابه در اینجا: یک بازی chomp تنها با استفاده از کاشی گوشه و 'بازی عادی' بی اهمیت است چرا که یکی می تواند تمام کاشی در یک حرکت حذف و برنده شوید. اما ترکیب ۴ چنین بازی هایی بی اهمیت نیست.
خلاصه مقایسه
- IChomp از نظر ریاضی زیباتر از چامپ است زیرا به طور مصنوعی جهت های جنوب شرقی را تک نمی کند و به یک کاشی نقش ویژه ای نمی دهد. قیمت به نظر می رسد که iChomp بسیار دشوارتر از Chomp بازی اما SG نظریه کمک می کند تا. کافی است به دانستن SG ارزش موقعیت Chomp تا برخی از اندازه به راحتی محاسبه SG ارزش از موقعیت iChomp تا 4 برابر که اندازه و در نتیجه بدانید که چگونه به بازی iChomp بهینه تا آن اندازه 4 برابر بزرگتر.
-
پاسخ نه است. به عنوان مثال بازی نیم با یک توده مسابقات بی اهمیت است. تحت 'بازی عادی', می توان تمام شمع در یک حرکت حذف و برنده. در نیم زیر 'Misère Play', یکی می تواند حذف همه به جز یک مسابقه و برنده شوید. با این وجود، ترکیب چنین بازی های نیم 1 شمع به یک بازی نیم چند شمع به عنوان در صفحه بازی های نیم ما بی اهمیت نیست.
در SGT به یک عملگر ریاضی به نام XOR نیاز داریم. در صورت عدم آشنایی با آن، بخش زیر مفید خواهد بود.
XOR چیه؟
-
اختصاصی یا یا XOR برای کوتاه مدت، یک عملیات منطقی است که بر روی داده های دودویی انجام می شود. با استفاده از داده های دودویی می توانستیم یکی از دو مقادیر درست (=۱) یا غلط (=۰) را داشته باشد. عملیات XOR بر روی دو مقادیر دودویی از طریق جدول زیر تعریف می شود.
a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
در حالی که استفاده از این عملیات بر روی مقادیر 1 (درست) یا 0 (نادرست) آسان است، برای محاسبات ما باید قادر به انجام XOR بر روی دو عدد باشد. این نیز می تواند انجام شود، با این حال یک گام جدید مورد نیاز است قبل از ما می توانیم XOR انجام دهد.
آنچه برای اولین بار باید اتفاق بیفتد این است که اعداد باید به دودویی تبدیل شوند، به این منظور که آن را از پایه ۱۰ به پایه ۲ تبدیل کنند.
چگونه می توان یک عدد را از پایه ۱۰ به پایه ۲ تبدیل کرد؟
-
از الگوریتم زیر می توان برای تبدیل عدد n در پایه ۱۰ به فرمت پایه ۲ استفاده کرد. (یادآوری شود که 20 = 1):
- پیدا کردن بالاترین p نمایی از 2، به طوری که 2p ≤ n.
- ضبط 1 و تفریق 2p از n.
- اگر p = 0 سپس توقف دیگر تفریق 1 از p و ادامه.
- اگر 2p > n پس از آن ثبت 0 دیگر تفریق 2p از n و ثبت 1.
- برگرد به مرحله 3 .
دنباله ۱ و ۰ که در پی این الگوریتم ثبت کرده ای، بازنمایی دودویی عدد n خواهد بود. مثال:
اجازه دهید شماره 13 را به فرمت پایه 2 تبدیل کنیم. ما با پیدا کردن بالاترین قدرت 2 کمتر یا برابر 13 شروع می کنیم که 23، یا 8 است. سپس یک ۱ و تفریق ۸ را از ۱۳ ثبت می کنیم که به ما ۵ می دهد. بعد بررسی می کنیم 2(3−1) = 22 = 4. از 4 ≤ 5 ، ما ثبت 1 ، و تفریق 4 از 5 ، که به ما می دهد 1. قدرت بعدی پایین تر از 2 21 = 2 است. 2 > 1 ، بنابراین ما ضبط 0. قدرت بعدی ۲ ۲۰ = ۱ است که برابر n ۱ ما است، بنابراین یک ۱ و تفریق ۱ را از ۱ ثبت می کنیم و به ما ۰ می دهد. از آنجا که p = 0 الگوریتم را متوقف می کنیم. بنابراین 13 (پایه 10) = 1101 (پایه 2).
پس از اینکه دو عدد را به نمایش دودویی تبدیل می کنیم، اکنون می توانیم عملیات XOR را بر روی ارقام متناظر دو عدد دودویی انجام دهیم. نتیجه یک عدد دودویی است که پس از آن می تواند به پایه تبدیل 10 اگر که راحت تر برای استفاده در آینده از آن مقدار XOR است. مثال:
اجازه دهید XOR اعداد 6 و 13 را محاسبه کنیم. نمایش دودویی برای این دو عدد ۶ = ۱۱۰، و ۱۳ = ۱۱۰۱ است. در ابتدا ۰ را در سمت چپ عدد کوچکتر اضافه می کنیم به طوری که هر دو عدد یکسانی داشته باشد، بنابراین ۶ = ۰۱۱۰. سپس می توانیم XOR را با پوشش دادن آن ها و انجام عملیات بر روی هر یک از ارقام فردی انجام دهد:
0110 XOR 1101 ------ 1011
بنابراین 6 XOR 13 = 1011 (پایه 2) = 1×23+0×22+1×21+1×20 = 8+2+1 = 11 (پایه 10).
اجازه دهید درک ما از XOR با چند سوال بررسی کنید.
M XOR m برای هر عدد m?
- برای هر عدد m m XOR m = 0 داریم زیرا 0 XOR 0 = 0 و همچنین 1 XOR 1 = 0.
آیا n XOR m = m XOR n برای هر عدد n, m?
- بله، چون 1 XOR 0 = 0 XOR 1 (=1).
0 XOR m برای هر عدد m?
- 0 XOR m = m چون 0 XOR 0 = 0 و 0 XOR 1 = 1.
اگر یک عدد m XOR'ed با یک عدد n از طریق m XOR n باشد آنگاه کدام رقم از m تلنگر می خورد؟
- اگر یک رقم در m XOR'ed با ۰ باشد آنگاه رقم بدون تغییر است (چون ۰ XOR ۰ = ۰ و ۱ XOR ۰ = ۱). اگر یک رقم در m XOR'ed با ۱ باشد آنگاه رقم تلنگر می خورد (چون ۰ XOR ۱ = ۱ و ۱ XOR ۱ = ۰). به این ترتیب XOR n تمام ارقامی را تلنگر می کند که رقم مربوطه در n برای آن ها یک ۱ است.
-
از الگوریتم زیر می توان برای تبدیل عدد n در پایه ۱۰ به فرمت پایه ۲ استفاده کرد. (یادآوری شود که 20 = 1):
الگوریتم برای محاسبه مقدار SG یک موقعیت Chomp.
-
الگوریتم زیر مقدار SG هر موقعیت P را در هر بازی ترکیب کننده بی طرف محاسبه می کند. ما آن را با استفاده از بازی Chomp توضیح می دهیم.
- هر موقعیت بازی است که موقعیت از دست دادن می شود SG ارزش 0. در Chomp، یک کاشی واحد (در گوشه شمال غرب) تنها موقعیت بدون حرکت پیگیری است و بنابراین یک موقعیت از دست دادن با SG-value 0 است.
- ما نیاز به SG-مقادیر از تمام موقعیت است که می تواند از موقعیت P در یک حرکت رسیده است. بنابراین اگر موقعیت P دارای n کاشی و سپس n-1 حرکت ممکن وجود دارد: به جز کاشی در گوشه شمال غرب، تمام کاشی های دیگر را می توان همراه با تمام کاشی به جنوب / شرق آن کاشی حذف شده است.
- مقدار SG یک موقعیت P کوچکترین عدد غیر منفی است که در این لیست از n-1 مقادیر SG قابل رسیدن نیست.
این الگوریتم بازگشتی است زیرا برای محاسبات SG-value از موقعیت P به SG-مقادیر تمام موقعیت های قابل رسیدن از P در یک حرکت نیاز داریم. هنوز هم کار می کند چرا که SG ارزش است که مورد نیاز نگرانی موقعیت های کوچکتر از کاشی های کمتر و SG ارزش کوچکترین موقعیت ممکن (یک کاشی در گوشه شمال غرب) شناخته شده است.
سعی کنید برای بررسی اموال 3 در بازی بالا با انتخاب عرض تخته بزرگتر و ارتفاع و کلیک کردن بر روی 'تصادفی هیئت مدیره'.
- هنگامی که شما حرکت ماوس بیش از یک کاشی, سپس این کاشی و کاشی های دیگر که حذف می شود برجسته. تعداد در آن کاشی SG ارزش چهارگوش تحت 'بازی عادی' (نه 'Misère بازی') است که نتیجه اگر این کاشی کلیک شده است. شما می توانید بررسی کنید که عدد نشان داده شده در متن 'SG مقدار پایه ده:' در کنار چهارگوش کوچکترین عدد نشان داده نشده در چهارگوش است. شما همچنین می توانید بررسی کنید که اگر شما با کلیک بر روی کاشی و سپس شماره ای که در آن بود در حال حاضر به عنوان 'SG ارزش پایه ده نشان می دهد:' از موقعیت جدید.
نحوه سرعت بخشیدن به تعیین مقادیر SG:
از آنجا که همان موقعیت را می توان از موقعیت های مختلف در یک حرکت رسید، و می تواند بارها و بارها در هنگام محاسبات SG-value از یک موقعیت بزرگتر، آن را هدر دادن تلاش برای محاسبه آن دوباره و دوباره خواهد بود. بنابراین، هنگامی که SG-مقدار یک موقعیت P محاسبه شد، باید برای استفاده بعدی ذخیره شود.
اگر کسی بخواهد SG-value از همه موقعیت ها را تا اندازه ای محاسبه کند، آنگاه رویکرد زیر مفید است. ما با اختصاص تنها موقعیت با یک کاشی (در گوشه شمال غرب) SG ارزش صفر شروع می شود. سپس از الگوریتم فوق برای محاسبه مقادیر SG تمام موقعیت ها با ۲ کاشی استفاده می کنیم، سپس با ۳ کاشی و مانند آن.
الگوریتم محاسبه SG-مقدار یک موقعیت iChomp
-
موقعیت iChomp شامل 4 موقعیت Chomp، یکی در هر چهارگوش از هیئت مدیره است.
- در ابتدا ما تعیین SG ارزش هر یک از 4 موقعیت Chomp با استفاده از قانون Chomp 'Misère بازی' است. چهارگوش خالی یک موقعیت Chomp نیست، بنابراین ما به آن مقدار −1 می دهد.
- سپس به هر مقدار ۱ اضافه می کنیم.
- برای هر یک از ۴ عدد حاصل بازنمایی دودویی را محاسبه می کنیم.
- مقدار XOR مقادیر ۴ دودویی را محاسبه می کنیم و مقدار SG آن موقعیت (به صورت دودویی) را بدست می آوریم. اگر این مقدار صفر باشد، یک موقعیت بازنده است، در غیر این صورت یک موقعیت برنده است.
-
ما اضافه کردن 1 به منظور به دست آوردن SG ارزش موقعیت Chomp تحت 'بازی عادی' از SG ارزش تحت 'Misère بازی'. در ادامه این مورد به توضیح آن می رسد.
قضیه:
--------
برای به دست آوردن SG ارزش موقعیت Chomp تحت 'بازی عادی' (به عنوان یکی از گرفتن آخرین کاشی برنده بازی است که راه مشترک برای بازی Chomp نیست) یکی نیاز به اضافه کردن 1 به SG ارزش همان موقعیت تحت 'Misère بازی' (به عنوان یکی از گرفتن آخرین کاشی از دست می دهد که راه مشترک برای بازی Chomp).
آیا می توانید سعی کنید با القای این تئوری را اثبات کنید؟
-
اثبات (با القای (و در جزئیات بسیار)):
مورد پایه (1 کاشی):
-------------------
تحت 'بازی عادی' هیئت مدیره خالی بدون کاشی یک موقعیت از دست دادن است و در نتیجه SG ارزش صفر است. علاوه بر این ، تحت 'بازی عادی' برای هیئت مدیره با یک کاشی (در گوشه بالا سمت چپ) تنها حرکت ممکن است برای حذف این کاشی عملکرد موقعیت با SG ارزش 0. بنابراین ، تحت 'بازی عادی' کوچکترین غیر منفی SG ارزش است که نمی تواند توسط یک حرکت به دست آورد 1 است ، به طوری که SG ارزش یک موقعیت با یک کاشی تحت 'بازی عادی'.
تحت 'Misère بازی' داشتن یک کاشی یک موقعیت از دست دادن با SG ارزش 0 است.
بنابراین ، برای 1 کاشی 'بازی عادی' SG ارزش است 1 بزرگتر از 'Misère بازی' ارزش.
گام استنشایی
---------------
فرضیه القایی (n کاشی):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
ما فرض می کنیم که یک عدد n وجود دارد به طوری که برای تمام موقعیت های با ≥1 و ≤n کاشی SG ارزش تحت 'بازی عادی' یکی بزرگتر از تحت 'Misère بازی'. ادعای القایی (n+1 کاشی):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
ما نشان خواهیم داد که این است که پس از آن نیز مورد برای تمام موقعیت های با n +1 کاشی.
مرحله القایی (n کاشی → n+1 کاشی):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
برای هر موقعیت 'Misère بازی' و 'بازی عادی' اجازه می دهد تا همان حرکت به جز که 'بازی عادی' نیز اجازه می دهد تا به تمام کاشی را از طریق کاشی گوشه بالا سمت چپ.
اگر موقعیت دارای n+1 کاشی، پس از آن ساخت یک حرکت تولید موقعیت با اکثر n کاشی که ما می توانیم فرضیه القای اعمال:
فهرست مقادیر SG به دست آمده تحت 'بازی عادی' بنابراین از لیست SG-مقادیر قابل به دست آمده تحت 'Misère بازی' هر یک افزایش 1 و با اضافه کردن ارزش 0 از طریق گرفتن تمام کاشی به دست آمده است.
بنابراین کوچکترین عدد غیر منفی NOT قابل به دست آوردن تحت 'بازی عادی' است 1 بالاتر از کوچکترین عدد غیر منفی قابل به دست آوردن تحت 'Misère بازی'. به عبارت دیگر، برای موقعیت اصلی با n+1 کاشی SG-value تحت 'بازی عادی' یکی بالاتر از SG-value تحت 'Misère Play' است. ∎ (این اثبات را کامل می کند.)
-
اثبات (با القای (و در جزئیات بسیار)):
چرا يه "1" اضافه کرديم؟
چگونه به بازی iChomp
-
هدف این است که حرکتی به گونه ای انجام شود که SG-مقدار موقعیت حاصل صفر باشد. هر حرکتي که يکي انجام بده بايد توي يکي از 4 چهارگانه باشه این بدان معناست که SG-value از موقعیت که در آن حرکت انجام شده است و SG-مقادیر دیگر 3 چهارگانه بدون تغییر همه XOR'ed باید صفر بدهد. این مورد است اگر و تنها اگر دیگر 3 SG ارزش XOR'ed را دقیقا SG ارزش چهارگوش جدید پس از انجام حرکت (نگاه کنید به بیشتر زیر برای اثبات این بیانیه). بنابراین رویه به این قرار است:
- (ساده) مورد: دو تا از چهارگانه های ۴ دارای مقدار SG یکسان هستند. سپس XOR از این دو مقادیر برابر صفر خواهد داد بنابراین قرار است هر دو چهارگانه نادیده گرفته شوند.
- اگر دو چهارگانه دیگر نیز برابر SG-مقادیر داشته باشند آنگاه SG-مقدار کل موقعیت صفر و موقعیت یک موقعیت از دست دادن است. سپس حذف تنها یک کاشی از هر چهارگوش به تاخیر انداختن شکست و شانس بیشتری برای حریف به بازی بهینه نیست.
- اگر دو چهارگوش دیگر دارای مقادیر SG نابرابر هستند سپس چهارگوش را با مقدار SG بزرگتر انتخاب کنید. یک حرکت در وجود دارد با کلیک کردن بر روی یک کاشی با یک عدد نوشته شده است که برابر است با SG ارزش چهارگوش دیگر. نتیجه 2 جفت چهار برابر با جفت برابر SG ارزش و مقدار XOR کل صفر - یک موقعیت از دست دادن است.
- (عمومی) مورد:
- محاسبه 4 iChomp - SG - مقادیر ، می گویند w ، x ، y ، z از چهارگانه 4 (هر یک از Chomp - SG - مقادیر از آن چهارگوش به علاوه 1) و تبدیل آنها را به پایه دو.
- سپس چپ ترین موقعیت را پیدا کنید به گونه ای که تعداد فرد از این ۴ عدد ۱ در این موقعیت داشته باشد. به عنوان مثال اگر ۴ عدد باشد
w=11011
سپس چپ ترین موقعیت با 1 موقعیت 5 (ما شروع به شمارش موقعیت از سمت راست). w و y وجود دارد 1، به عنوان یکی دو عدد (w و y) 1 وجود دارد. دو یک عدد حتی است، بنابراین باید این موقعیت را نادیده بگیریم. موقعیت بعدی جایگاه ۴ است که دوباره از سمت راست شمارش می شود. در اینجا نیز، به طور مساوی بسیاری از اعداد 1 وجود دارد (w و x). ما باید این موقعیت را نیز نادیده بگیریم. جایگاه سوم دارای ۳ عدد با ۱ وجود دارد (x, y, z). 3 یک عدد عجیب است، بنابراین ما هر یک از این 3 عدد را انتخاب می کنیم، به عنوان مثال، y=10100.
x= 1101
y=10100
z= 100- اگر در تمام موقعیت ها یک عدد حتی از 1s وجود دارد و سپس مقدار XOR از هر 4 عدد صفر است و این یک موقعیت از دست دادن است. به عنوان مثال
w'=11011
حتی تعداد 1 در هر موقعیت. XOR از این 4 عدد صفر است، این یک موقعیت از دست دادن است. در این حالت یکی حذف تنها یک کاشی از هر چهارگوش به تاخیر انداختن شکست و شانس بیشتری برای حریف به بازی بهینه نیست.
x'= 1011
y'=10110
z'= 110 - اگر حداقل یک موقعیت عجیب و غریب بسیاری از 1 و سپس ما در بر داشت یک عدد، مانند y بالا (نه y').
- ما XOR 3 عدد دیگر، در مورد ما w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011. این مقدار همیشه کمتر از عدد ما برداشت، در اینجا y = 10100 (نگاه کنید به اثبات بیشتر در زیر).
- در چهارگوش با مقدار برداشت شده، در اینجا y، ما یک حرکت است که منجر به یک موقعیت با SG-مقدار برابر XOR از 3 مقدار دیگر، در مثال ما 10011.
- برای دانستن که کاشی را کلیک کنید ما یا تبدیل 10011 به پایه ده (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) و کلیک بر روی کاشی با شماره 19، یا به صورت دودویی محاسبه می کنیم 10100 − 10011 = 1 و این را به پایه ده (= 1) تبدیل می کنیم و می دانیم که کاشی برای کلیک کردن باید ارزش 1 کمتر از y (=20) را داشته باشد، به عبارتی برای کلیک بر روی کاشی با شماره 19 نوشته شده است.
چرا اين يه حرکت برنده است؟
-
لطفا خودتان را در مورد خواص 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-value y را به یک مقدار پایین تر تغییر دهد؟
- با توجه به تعریف: یک موقعیت دارای SG-value of y است اگر و تنها اگر حرکت هایی وجود داشته باشد که موقعیت هایی با SG-values 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 ، می گویند 2p. این قدرت از 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)
= 2p − (2p−1 + 2p−2+ ... +20)
= 2p − (2p−1 + 2p−2+ ... +20)× (2-1)/(2-1)
= 2p − (2p−1)/(2-1)
= 1.
این بدان معناست که y حداقل یک بزرگتر از (y XOR u) است. ∎
-
با استفاده از قوانین XOR آموخته زودتر ما دریافت کنید
سعی کنید این الگوریتم را با بازی و برنده شدن در برابر 'دشواری: سخت'.
-
برای شروع، "دشواری: سخت" را انتخاب کنید که بازی بهینه کامپیوتر را تضمین می کند. اگر شما هنوز هم برنده و سپس شما بازی هر حرکت بهینه.
مقدار SG هر چهارگوش در پایه ۱۰ و پایه ۲ نشان داده شده است. بررسی کنید که این عدد کوچکترین مقداری است که در چهارگوش نشان داده نشده است.
در زیر XOR از هر ۴ SG-values به نام u نشان داده شده است. بررسی ارزش شما به سادگی با تغییر هر جفت از دو 1 در 4 SG ارزش به 0 اگر دو 1 در یک موقعیت هستند. سپس 1 باقی مانده را به یک عدد دودویی قرار داده و آن را به پایه 10 تبدیل کنید.
برای ادامه حرکت همانطور که در بالا شرح داده شد:
- پیدا کردن یکی از 4 SG - مقادیر ، می گویند y ، که دارای 1 در همان موقعیت سمت چپ ترین 1 در u.
- محاسبه y XOR u به صورت دودویی و سپس تبدیل آن به پایه 10.
- در چهارگوش y کلیک کنید کاشی با محاسبات y XOR u.
- بازی حرکت خود را در این راه تا زمانی که شما برنده شد.
- دوباره بازی کنید اما این بار با یک حرکت تصادفی شروع می شود. مگر اینکه شما خوش شانس بودند و توسط تصادف یک حرکت برنده بازی، شما قادر به برنده شدن در این بازی حتی اگر شما پس از آن سعی کنید به بازی مطلوب.
تمام دستورالعمل های بالا فرض می کنند که یکی می داند SG ارزش از چهارگانه 4 که به این معنی است که یکی می داند SG ارزش هر چهارگوش پس از هر حرکت ممکن است.
آیا می توانید SG-values برخی از موقعیت های Chomp (در 'Misère Play') را پیدا کنید؟
-
برای محاسبه SG-مقدار یک موقعیت، باید SG-مقادیر تمام موقعیت هایی را که می توان در یک حرکت از آن به دست آمد، دانست. این یک فرایند بازگشتی است. بنابراین ما نیاز به شروع با موقعیت با تعداد کمی از کاشی و کار راه ما تا.
آیا می توانید SG ارزش های 1،2،3 پیدا کنید,... کاشی در یک ردیف؟
-
داشتن تنها 1 کاشی (در گوشه بالا سمت چپ) یک موقعیت از دست دادن با بنابراین SG ارزش 0 است.
داشتن 2 کاشی (در ردیف بالا و یا ستون سمت چپ) ، تنها حرکت ممکن است به یک کاشی به دست آوردن موقعیت ذکر شده با SG - مقدار 0. بنابراین کوچکترین SG-value غیر منفی که با یک حرکت نمی توان به دست آورد ۱ است، به طوری که SG-value یک موقعیت با ۲ کاشی ۱ است.
با داشتن 3 کاشی همه در ردیف بالا، یکی می تواند یا 1 یا 2 کاشی و به دست آوردن SG ارزش 1 و 0، بنابراین SG ارزش است بنابراین 2.
به طور مشابه، مقدار SG از n کاشی در ردیف بالا n-1 است.
اجازه دهید ما در نظر 3 کاشی، 2 در ردیف بالا و 2 در ستون سمت چپ. ما می توانیم تنها ۱ کاشی را حذف کنیم و به مقدار SG ۱ اما نه ۰ برسند، بنابراین کوچکترین SG-مقداری که نمی توان به دست داد ۰ است که بنابراین مقدار SG این موقعیت است. این یک موقعیت بازنده است.
آیا می توانید SG-value از یک موقعیت با m+n−1 کاشی که n در ردیف بالا هستند و m کاشی در ستون سمت چپ پیدا کنید؟
- تنها می توان کاشی ها را از ردیف بالا یا از ستون سمت چپ حذف کرد. بنابراین مقدار SG همان داشتن دو چهارگانه، یکی با n کاشی در ردیف بالا و یکی با کاشی m در ستون سمت چپ است. بدین ترتیب مقدار SG (m-1) XOR (n-1) است. این همان بازی NIM با دو شمع و 'بازی عادی' قانون که در آن مسابقات را می توان از تنها یک شمع در یک حرکت حذف شده است.
آیا می توانید SG ارزش یک موقعیت با کاشی تنها در دو ردیف بالا پیدا کنید؟
-
فرمول های این موقعیت ها پیچیده تر هستند. تا آنجا که می دانیم پیش از این منتشر نشده بودند. شما می توانید سعی کنید آنها را برای تعداد کمی از کاشی تایید.
اجازه دهید n و m تعداد کاشی در ردیف بالا و دوم باشد.
اگر n حتی پس از آن
k = (n-2)/2
اگر m حتی پس از آن
a = m/2
SG-value = 2*k+a+1
else (m is odd)
a = (m-1)/2
اگر یک ≤ (k/2) سپس SG-value = 2*k-a
دیگری SG-value = 3*(k-a)
else (n is odd)
k = (n-1)/2
اگر m حتی پس از آن
a = m/2
اگر یک ≤ (k/2) سپس SG-value = 2*k-a
دیگری SG-value = 3*(k-a)
else (m is odd)
a = (m-1)/2
SG-value = 2*k+a+1
بررسی کنید که آیا فرمول ها با استفاده از تخته بازی بالا درست هستند یا خیر.
- حداقل ارتفاع تخته را انتخاب کنید به طوری که چهارگوش با تنها دو ردیف کاشی وجود دارد. پس از استفاده از فرمول های بالا شما باید یک SG ارزش است که یکی پایین تر از ارزش نشان داده شده تحت 'SG ارزش پایه ده:' به دست آوردن چرا که فرمول ها برای 'Misère بازی' در حالی که iChomp با استفاده از 'بازی عادی'.
-
داشتن تنها 1 کاشی (در گوشه بالا سمت چپ) یک موقعیت از دست دادن با بنابراین SG ارزش 0 است.
چگونه می توان یک بازی iChomp منطقی به خوبی بدون دانستن SG ارزش؟
-
ما با یک مشاهده شروع می کنیم: قوانین چامپ هیچ تفاوتی بین جهت شرق و جنوب ایجاد نمی کند.
چه پیامد برای SG-مقادیر دو موقعیت است که آینه متقارن به یکدیگر در زیر آینه بر روی مورب است که از گوشه بالا سمت چپ شروع می شود؟
- از آنجا که جهت شرق و جنوب به یکدیگر آینه این بدان معنی است که هر دو باید ارزش SG یکسان داشته باشد.
چه معنی است که برای iChomp زمانی که 2 چهارگوش موقعیت است که متقارن تحت چرخش چهارگوش و / یا آینه مورب؟
- هر دو چهارگانه را می توان نادیده گرفت. چرا? هر دو چهارگانه دارای ارزش SG یکسان تحت بازی misère و پس از اضافه کردن ۱ نیز همان SG-value تحت بازی عادی هستند. XOR از این دو مقادیر برابر صفر می دهد. بنابراین، هر دو چهارگانه هیچ سهمی در SG-value کل موقعیت هیئت مدیره ندارد.
بنابراین کدام استراتژی بازی باید کار کند؟
-
باید یک حرکت انجام داد که دو جفت چهارگانه ایجاد می کند به طوری که چهارگانه ها در هر جفت دارای موقعیت های متقارن با مقادیر 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 است. یکی موقعیت بازنده ای ایجاد کرد.
به همان اندازه یکی نباید حرکت کند که دو چهارگانه متقارن باقی می ماند و دو تای دیگر آن ها را می توان در یک حرکت توسط حریف به دیگری تغییر داد. این امر به حریف اجازه می دهد تا موقعیت بازنده ای ایجاد کند.
برخی از سوالات آزمون
-
در اینجا آمده است برخی از سوالات که در آن شما می توانید درک خود را از Chomp تست, iChomp و SG نظریه.
آیا دانش SG ارزش به اندازه کافی برای بازی Chomp کاملا؟
- بله. اگر SG-مقدار یک موقعیت صفر باشد، آنگاه یک موقعیت بازنده است (چون هیچ حرکت وجود ندارد تا آن را صفر کند، بنابراین هیچ حرکت برنده ای وجود ندارد، بنابراین یک موقعیت بازنده است). اگر SG-مقدار بزرگتر از صفر باشد، آنگاه این بدان معنی است که یک حرکت وجود دارد تا SG-value از موقعیت حاصل صفر شود، بنابراین یک حرکت برنده وجود دارد.
آیا یکی نیاز به دانستن SG ارزش از موقعیت Chomp به بازی Chomp کاملا؟
- قهقهه برای بازی Chomp ما نیاز به پیدا کردن یک حرکت است که تولید یک موقعیت از دست دادن. اگر چنین حرکتی وجود نداشته باشد آنگاه موقعیت بازنده ای است و هر حرکتی را می توان انجام داد. اما اگر چنین حرکتی پیدا شود، می توان جستجو را متوقف کرد. ارزش SG مورد نیاز نیست.
ارزش های SG برای آن زمان خوب هستند؟
- آنها تنها مورد نیاز برای انجام چند بازی Chomp به موازات به عنوان یک بازی جدید، مانند در iChomp.
چقدر سخت تر است در Chomp به محاسبه SG ارزش یک موقعیت از یک حرکت برنده؟
-
برای بازی Chomp ما نیاز به پیدا کردن یک حرکت است که تولید یک موقعیت از دست دادن. اگر چنین حرکتی وجود نداشته باشد آنگاه موقعیت بازنده ای است و هر حرکتی را می توان انجام داد. اما اگر چنین حرکتی پیدا شود، می توان جستجو را متوقف کرد.
تلاش برای یافتن SG-value یک موقعیت معمولاً بیشتر است. برای پیدا کردن SG-value همیشه باید حرکت ALL را جستجو کند تا تمام SG-مقادیر موقعیت های حاصل را پیدا کند و کوچکترین مقدار غیر منفی را پیدا کند که در یک حرکت نمی توان به آن رسید. این مقدار SG-مقدار موقعیت است.
به عنوان مثال، در محاسبات ما (Caribou) ما قادر به تعیین تمام موقعیت های از دست دادن (و در نتیجه برنده موقعیت) با تا 93 کاشی. با تلاش محاسباتی قابل مقایسه ما قادر به محاسبه SG ارزش تمام موقعیت های Chomp با تا 82 کاشی.
به این معنا تعیین مقادیر SG از نظر محاسباتی گران تر از تعیین یک حرکت برنده است.
اگر نیم با 4 شمع سخت تر است به بازی از NIM با 1 شمع، پس از آن iChomp با 4 چهار برابر بسیار سخت تر به بازی از Chomp با 1 چهارگوش؟
-
در نیم، SG-value یک شمع به سادگی تعداد مسابقات در آن شمع است. (لطفا تایید این با استفاده از نظرات بالا چگونه به محاسبه SG - مقادیر به یک پشته تنها در نیم.) تنها عارضه بازی چند شمع در نیم این است که XOR SG ارزش های مختلف از این شمع برای به دست آوردن SG ارزش تمام شمع ترکیب شده است.
در Chomp از نظر محاسباتی گران است برای به دست آوردن SG-مقدار یک موقعیت (که در یک چهارگوش است). در iChomp، هنگامی که SG-مقادیر چهارگانه 4 شناخته شده است، این مقادیر نیاز به XOR'ed نیز دارند، اما این بسیار آسان تر از پیدا کردن SG-value یک چهارگوش است.
برای بازی Chomp بهینه یکی نیاز به دانستن SG ارزش موقعیت، دانستن یک حرکت برنده به اندازه کافی خوب است، اما همانطور که بالاتر از تفاوت نشان داده شده است که بزرگ نیست.
بنابراین پاسخ NO است، بازی iChomp به طور بهینه از Chomp خیلی سخت تر نیست.
در چامپ، آیا یک حرکت می تواند موقعیتی ایجاد کند که ارزش SG بالاتری داشته باشد؟
- بله. SG-مقدار یک موقعیت کوچکترین مقداری است که نمی تواند توسط یک حرکت تولید شود.
در Chomp، آیا می توان حرکت های متفاوتی وجود داشته باشد که موقعیتی با همان SG-value ایجاد کند؟
-
بله. شما می توانید مثال ها را با افزایش اندازه هیئت مدیره را ببینید و با کلیک بر روی دکمه 'نمایش مقادیر SG از حرکت'. به عنوان مثال موقعیت
###
##
#
دارای 3 حرکت برنده، همه ایجاد یک موقعیت با SG ارزش 0. ما حتی یک موقعیت با 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
.برای به روز رسانی عضو شوید و یا ما را دنبال کنید