موضوع مقاله: نیم (بازی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نیم (بازی) | مقدمه: در هر نوبت هر بازیکن از یک کپه حداقل یک سنگ‌ریزه برمی‌دارد (بازیکن حتی می‌تواند تمام کپه را نیز بردارد). | ## بخش 1: نیم (بازی) | نیم اغلب به این صورت بازی می‌شود که بازیکنی که آخرین سنگ‌ریزه را برمی‌دارد بازنده‌است (misere). اما می‌توان به‌طور معمولی نیز بازی کرد؛ بدین شکل که بازیکنی که آخرین انتخاب را دارد برنده است. نیم یک بازی دو نفره ریاضی است که طبق یک نقشه پیش می‌رود و در آن بازی کنان در نوبت‌های خود اشیا1 را از پشته 2های مجزا برمی‌دارند. در هر نوبت بازیکن حداقل یک شیء را برمی‌دارد و ممکن است هر تعدادی را به شرط اینکه از یک پشته باشد بردارد. گفته می‌شود که این بازی در چین ابداع شده‌است (نیم شباهت زیادی یه بازی چینی جی‌ان‌شی‌زی "Jianshizi" دارد) اما پیدایش آن نامشخص است؛ اروپاییان نیز در آغاز قرن شانزدهم با نیم آشنا شدند. گفته می‌شود که چینیان این بازی را ابداع کرده‌اند (مانند بازی جیانشیزی به معنای برداشتن سنگ است). اسم فعلی آن توسط چارلز ال بوتون 3 (دانشگاه هاروارد 4) که نظریه این بازی را در سال ۱۹۰۱ ارائه داد ساخته شده‌است. شاید از کلمه آلمانی nimm به معنای بَردار یا کلمه انگلیسی nim به همین معنا گرفته شده باشد. نیم معمولاً به عنوان یک بازی میسِر 5 اجرا می‌شود که بازیکنی که آخرین حرکت را انجام می‌دهد بازی را می‌بازد. همچنین نیم می‌تواند به عنوان یک بازی عادی 6 اجرا شود که در آن کسی که آخرین حرکت را انجام می‌دهد می‌برد. به این نوع بازی بازی عادی می‌گویند چون بیشتر بازی‌ها از این سنت پیروی می‌کنند در حالی که نیم معمولاً این گونه نیست. بازی عادی نیم بر پایه قضیه اسپراگ-گراندی 7 است که می‌گوید در بازی عادی، هر بازی منصفانه معادل یک پشته نیم است که زمانی که موازی با بازی‌های عادی منصفانه دیگر بازی شود، خروجی یکسان می‌دهد. A B C ۵ ۴ ۳ بازیکن۱ دو سنگ‌ریزه از A برمی‌دارد ۵ ۴ ۱ بازیکن۲ سه سنگ‌ریزه از C برمی‌دارد ۲ ۴ ۱ بازیکن۱ یکی از B برمی‌دارد ۲ ۳ ۱ بازیکن۲ یکی از B برمی‌دارد ۲ ۲ ۱ بازیکن۱ کپه A را برمی‌دارد ۲ ۲ ۰ بازیکن۲ یکی از B برمی‌دارد ۲ ۱ ۰ بازیکن۱ یکی از C برمی‌دارد (در misere تمام C را برمی‌داشت و پیروز می‌شد) ۱ ۱ ۰ بازیکن۲ یکی از B برمی‌دارد ۱ ۰ ۰ بازیکن۱ آخرین سنگ‌ریزه را برمی‌دارد و پیروز می‌شود. به‌طورکلی در یک N-وضعیت بازیکن اول می‌تواند با حرکات مناسب حتماً به پیروزی برسد و در یک P-وضعیت بازیکن دوم می‌تواند با حرکات مناسب حتماً به پیروزی برسد. برای یک کپه‌ای که علت آن پر واضح است اما برای دو کپه‌ای اگر اندازه دو کپه برابر باشد نفر دوم با تقلید حرکات نفر اول می‌تواند مطمئن باشد که برنده خواهد شد و اگر اندازه دو کپه برابر نباشد نفر اول با برداشتن مقدار اضافی از کپه اول می‌تواند اندازه دو کپه را برابر کند و این بار او با ترفند تقلید به پیروزی برسد. با افزایش تعداد کپه‌ها بررسی این موضوع پیچیده‌تر می‌شود که به صورت یک مسئله ریاضی آن را حل می‌کنیم. | ## بخش 2: نیم (بازی) | نظریه ریاضی نیم به صورت ریاضی برای تعداد متناهی از کپه‌ها و سنگ‌ریزه‌ها حل شده‌است و می‌توان مشخص نمود که کدام بازیکن برنده خواهد شد. به این ترتیب که معادل دودویی اندازه کپه‌ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. این عمل همان یای انحصاری (XOR) در مدارهای منطقی است که در تئوری بازی‌های ترکیبی آن را جمع نیمی (nim-sum) می‌نامند. ما برای نشان دادن جمع نیمی از همان نمایش آن در مدارهای منطقی که + است؛ استفاده می‌کنیم. جمع نیمی را می‌توان به صورت ذهنی که انگشتان دست را به ترتیب توان‌های ۲ در نظر می‌گیرند و اگر عددی دارای آن توان ۲ بود آن را بالا می‌برند و اگر دارای آن توان نبود آن را پایین می‌آورند و در جمع با سایر اعداد اگر آن عدد دارای توانی از ۲ بود وضعیت مربوط به آن انگشت را برعکس می‌کنند؛ یعنی اگر بالا بود آن را پایین می‌آورند و اگر پایین بود آن را بالا می‌برند. در بازی معمولی استراتژی برد صفر کردن جمع نیمی اندازه کپه‌هاست که این امر تا زمانی‌که جمع نیمی آن‌ها ۰ نشده‌است ممکن است. برای آن‌که بدانیم در هر مرحله چه حرکتی باید انجام دهیم؛ جمع نیمی کپه‌ها را X در نظر می‌گیریم. با جمع نیمی اندازه هر کپه با X کپه‌ای را که اندازه آن کم شده‌است را پیدا می‌کنیم. برای مثال بالا داریم: X = 3 + 4 + 5 = 2 A + X = 3 + 2 = 1 B + X = 4 + 2 = 6 C + X = 5 + 2 = 7 تنها کپه‌ای که اندازه آن کاهش یافته A است؛ بنابراین برای برنده شدن در حرکت خود اندازه A را به ۱ کاهش می‌دهیم. وقتی که به صورت misere بازی می‌کنیم؛ استراتژی بازی فقط در مقایسه با بازی معمولی این تغییر را می‌کند تلاش می‌کنیم که در هر حرکت هیچ کپه‌ای با اندازه بیشتر از ۱ بر جای نگذاریم. در بازی معمولی استراتژی برد در باقی گذاشتن تعداد زوجی از کپه‌ها با اندازه ۱ است. در بازی نیم به صورت misere با کپه‌های ۳، ۴ و ۵ استراتژی به صورت زیر است: C B A Nim-sum ۵ ۴ ۳ ۲ بازیکن۱ دو تا از A برمی‌دارد و جمع نیمی ۰ می‌شود و این بازیکن حتماً می‌برد ۵ ۴ ۱ ۰ بازیکن۲ دو تا از C برمی‌دارد ۳ ۴ ۱ ۶ بازیکن۱ دو تا از B برمی‌دارد ۳ ۲ ۱ ۰ بازیکن۲ یکی از C برمی‌دارد ۲ ۲ ۱ ۱ بازیکن۱ یکی از A برمی‌دارد ۲ ۲ ۰ ۰ بازیکن۲ یکی از C برمی‌دارد ۱ ۲ ۰ ۳ بازیکن۱ در بازی معمولی مطابق استراتژی با برداشتن یکی از B تعداد زوجی کپه با اندازه ۱ بر جای خواهد گذاشت و برنده خواهد شد. یعنی روشی بسیار راحت وجود دارد که می‌توان فهمید کدام بازیکن خواهد برد و چه حرکاتی منجر به بردی برای برنده وجود دارد. در بازی که با پشته‌های ۳، ۴ و ۵ تایی آغاز می‌شود نفر اول با یک بازی بهینه (چه بازی معمولی باشد و چه میسر) خواهد برد. این عمل با نام یای انحصاری معروف است که در نظریه بازی ترکیبی معمولاً جمع نیم (nim-sum) صدا زده می‌شود. 0102 210 در روشی مشابه که ذهنی می‌توان آن را انجام داد اندازه پشته‌ها را به صورت جمع توان‌های دو می‌نویسیم جفتها با توان یکسان را حذف می‌کنیم و آنچه باقی می‌ماند را جمع می‌کنیم. | ## بخش 3: نیم (بازی) | پشتهA3=0+2+10 2 1پشتهB4=4+0+04 ۰ ۰پشتهC5=4+0+14 0 1 در بازی عادی، سیاست برد اینست که در پایان هر حرکت جمع نیم برابر صفر باشد؛ که در صورتی که قبل از حرکت صفر نباشد همواره ممکن است. برای اینکه بفهمیم چه حرکتی کنیم x را برابر جمع نیم اندازه پشته‌ها قرار می‌دهیم و جمع نیم x را با اندازه یک یک پشته‌ها حساب می‌کنیم. در یک مثال ساده زمانی که تنها دو پشته باقی‌مانده سیاست برد کاهش دادن اندازه پشته بزرگتر برای هم اندازه کردن آن با پشته دیگر است. شما هم می‌توانید همان حرکت را روی پشته دیگر انجام دهید با این ضمانت که شما حرکت آخر را انجام خواهید داد. وقتی بازی به صورت میسر انجام می‌شود سیاست نیم فقط وقتی که حرکت بازی عادی، پشته‌هایی با اندازه ۲ یا بزرگتر ایجاد نمی‌کند فرق می‌کند. (در بازی عادی حرکت صحیح باقی گذاشتن تعداد زوجی از این پشته هاست) نمونه بازی به شکل عادی ممکن است با پشته‌های سه، چهار و پنج تایی آغاز شود. A B C...۵ ۴ ۳ من دو تا از A برمی‌دارم.۵ ۴ ۱ تو سه تا از C برمی‌داری.۲ ۴ ۱ من یکی از B برمی‌دارم.۲ ۳ ۱ تو یکی از B برمی‌داری.۲ ۲ ۱ من کل پشته A را برمی‌دارم و دو پشته دوتایی می‌گذارم.۲ ۲ ۰ تو یکی از B برمی‌داری.۲ ۱ ۰ من یکی از C برمی‌دارم و دو پشته تکی می‌گذارم.۱ ۱ ۰ تو یکی از B برمی‌داری.۱ ۰ ۰ من کل C را برمی‌دارم و می‌برم. اثبات فرمول برد قضیه: در بازی عادی نیم برای نفر اول نقشه‌ای برای برد وجود دارد اگر و تنها اگر جمع اندازه پشته‌ها مخالف صفر باشد. اثبات: توجه داشته باشید که جمع نیم از قوانین شرکت پذیری و جا به جایی شبیه جمع معمولی پیروی می‌کند و ویژگی دیگری به فرم x ⊕ x = ۰ دارد. فرض کنید x1، …، xn اندازه پشته‌ها قبل از حرکت باشد و y1، …، yn اندازه متناظر بعد از حرکت باشد. اگر هیچ حرکتی نتوان کرد، لم قطعاً صحیح است و نفر اول با توجه به تعریف بازی را می‌بازد؛ و اگر نه هر حرکتی در پشته kام از * نتیجه می‌دهد t = xk ⊕ yk که این عدد ناصفر است زیرا xk ≠ yk. فرض کنید d مکان پرارزشترین بیت (MSB) غیر صفر در نمایش دودویی s باشد و k را طوری انتخاب کنید که dامین بیت xk هم غیر صفر باشد. سپس با قرار دادن yk = s ⊕ xk می‌توان مطمئن شد که yk < xk': تمام بیتهای سمت چپ d در xk و yk مشابهند، بیت dام از یک به صفر کاهش می‌یابد و در نتیجه مقدار کل 2k کم می‌شود و هر تغییر دیگر در بیتهای مانده بیشینه تغییر 2k-۱ را ایجاد می‌کند. تفاوت موجود در بازی میسر در مکانی است که فقط یک پشته با اندازه ۲ یا بیشتر وجود دارد. | ## جمع‌بندی | نقشه بازی عادی کاهش آن به اندازه ۰ و ۱ و باقی گذاشتن تعداد زوجی از پشته‌های با اندازه ۱ است در حالی که نقشه بازی میسر برای انجام خلاف این است.