بازی‌های منصفانه

گفته می‌شود که این بازی در چین ابداع شده‌است و در زمان‌های دور بازی می‌شده‌است. ( نیم شباهت زیادی یه بازی چینی جی‌ان‌شی‌زی Jianshizi دارد) اما چگونگی پیدایش آن نامشخص است؛ اروپاییان نیز در آغاز قرن شانزدهم با نیم آشنا شدند. نام رایج این بازی توسط سی. ال. بوتون (Charles L. Bouton) که تئوری کامل این بازی را در سال 1901 میلادی ایجاد کرد.؛ ابداع شد.

نیم احتمالاً از آلمانی بگیر! (nimm) یا فعل مهجور انگلیسی nim با همین معنا گرفته شده‌است.

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

ما در ادامه نیم معمولی را در نظر می‌گیریم.

یک بازی نیم را با کپه‌های {۳، ۴ و ۵} تایی در نظر بگیرید

بنابراین وضعیت {۳، ۴، ۵} را یک N-وضعیت می‌گوییم. به‌طورکلی در یک N-وضعیت بازیکن اول می‌تواند با حرکات مناسب حتماً به پیروزی برسد و در یک P-وضعیت بازیکن دوم می‌تواند با حرکات مناسب حتماً به پیروزی برسد.

در بازی با تعداد کپه کم می‌توان به راحتی N-وضعیت‌ها و P-وضعیت‌ها را یافت. برای مثال:

در نیم یک کپه‌ای

n} , n> ۰} یک N-وضعیت است

{۰} یک P-وضعیت است.

در نیم دو کپه‌ای

m, n} , n ≠ m} یک N-وضعیت است

{n, n} یک P-وضعیت است.

برای یک کپه‌ای که علت آن پر واضح است اما برای دو کپه‌ای اگر اندازه دو کپه برابر باشد نفر دوم با تقلید حرکات نفر اول می‌تواند مطمئن باشد که برنده خواهد شد و اگر اندازه دو کپه برابر نباشد نفر اول با برداشتن مقدار اضافی از کپه اول می‌تواند اندازه دو کپه را برابر کند و این بار او با ترفند تقلید به پیروزی برسد.

با افزایش تعداد کپه‌ها بررسی این موضوع پیچیده‌تر می‌شود که به صورت یک مسئله ریاضی آن را حل می‌کنیم

نیم به صورت ریاضی برای تعداد متناهی از کپه‌ها و سنگ‌ریزه‌ها حل شده‌است و می‌توان مشخص نمود که کدام بازیکن برنده خواهد شد.

با جمع دودویی (باینری) اندازه کپه‌ها می‌توان این مسئله را حل نمود. به این ترتیب که معادل دودویی اندازه کپه‌ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. این عمل همان یاءانحصاری (XOR) در مدارهای منطقی است که در تئوری بازی‌های ترکیبیاتی (Combinatorial Games) آن را جمع نیمی (nim-sum) می‌نامند. ما برای نشان دادن جمع نیمی از همان نمایش آن در مدارهای منطقی که ${\displaystyle \oplus }$ است؛ استفاده می‌کنیم. جمع نیمی را می‌توان به صورت ذهنی انگشان دست هم حساب نمود. به این ترتیب که انگشتان دست را به ترتیب توان‌های 2 در نظر می‌گیرند و اگر عددی دارای آن توان 2 بود آن را بالا می‌برند و اگر دارای آن توان نبود آن را پایین می‌آورند و در جمع با سایر اعداد اگر آن عدد دارای توانی از 2 بود وضعیت مربوط به آن انگشت را برعکس می‌کنند؛ یعنی اگر بالا بود آن را پایین می‌آورند و اگر پایین بود آن را بالا می‌برند.

در بازی معمولی استراتژی برد صفر کردن جمع نیمی اندازه کپه‌هاست که این امر تا زمانی‌که جمع نیمی آن‌ها 0 نشده‌است ممکن است. اگر جمع نیمی صفر شود بازیکنی که نوبت آن است خواهد باخت. (در صورتی که بازیکن دیگر اشتباه نکند). ما فرض می‌کنیم که در هر نوبت هر بازیکن بهترین حرکت ممکن را انجام می‌دهد. برای آن‌که بدانیم در هر مرحله چه حرکتی باید انجام دهیم؛ جمع نیمی کپه‌ها را X در نظر می‌گیریم. با جمع نیمی اندازه هر کپه با X، کپه‌ای را که اندازه آن کم شده‌است را پیدا می‌کنیم. استراتژی برد در بازی با چنین کپه‌ای است. برای مثال بالا داریم:

تنها کپه‌ای که اندازه آن کاهش یافته A است؛ بنابراین برای برنده شدن در حرکت خود اندازه A را به 1 کاهش می‌دهیم.

وقتی که به صورت misere بازی می‌کنیم؛ استراتژی بازی فقط در مقایسه با بازی معمولی این تغییر را می‌کند تلاش می‌کنیم که در هر حرکت هیچ کپه‌ای با اندازه بیشتر از 1 بر جای نگذاریم. در این مورد حرکتی درست است که تعداد فردی از کپه‌ها با اندازه 1 بر جای گذارد. در بازی معمولی استراتژی برد در باقی گذاشتن تعداد زوجی از کپه‌ها با انداره 1 است.

در بازی نیم به صورت misere با کپه‌های 3، 4 و 5 استراتژی به صورت زیر است:

درستی الگوریتم بالا توسط بوتون اثبات شد..

قضیه : در بازی نیم معمولی نفر اول برنده می‌شود (یک N-وضعیت است) اگر و تنها اگر جمع نیمی اندازه کپه‌ها غیر صفر باشد. در غیر این صورت نفر دوم برنده می‌شود (یک P-وضعیت است).

اثبات : می‌دانیم که جمع نیمی (XOR) از قوانین جابه‌جایی و شرکت‌پذیری پیروی می‌کند. هم‌چنین داریم:

${\displaystyle x_{1},x_{2},...,x_{n}\,\!}$ را برابر با اندازه کپه‌ها قبل از حرکت و ${\displaystyle y_{1},y_{2},...,y_{n}\,\!}$ را برابر با اندازه کپه‌ها بعد از حرکت قرار می‌دهیم:

اگر سنگ‌ریزه از کپه k-ام برداشته شود خواهیم داشت:

پس داریم:

لم1: اگر ${\displaystyle s=0\,\!}$ باشد آن‌گاه ${\displaystyle t\neq \;0\,\!}$ است و مهم نیست که چه حرکتی انجام شود.

اثبات: اگر انجام هیچ حرکتی ممکن نباشد یعنی کپه‌ها تهی هستند و بازیکن اول بازنده است. در غیراین‌صورت با حرکت در کپه ${\displaystyle k\,\!}$ خواهیم داشت ${\displaystyle t=x_{k}\oplus y_{k}\,\!}$ و این حاصل حتماً غیر صفر است زیرا ${\displaystyle x_{k}\neq \;y_{k}\,\!}$ است.

لم2: اگر ${\displaystyle s\neq \;0\,\!}$ باشد آن‌گاه می‌توان حرکتی انجام داد که ${\displaystyle t=0\,\!}$ شود.

اثبات: ${\displaystyle d\,\!}$ را برابر با سمت چپ‌ترین بیت غیر صفر ${\displaystyle s\,\!}$ در نمایش دودویی قرار می‌دهیم و ${\displaystyle k\,\!}$ را نیز ${\displaystyle d\,\!}$-امین بیت ${\displaystyle x_{k}\,\!}$ که آن‌هم غیر صفر است؛ انتخاب می‌کنیم (${\displaystyle k\,\!}$ حتماً وجود دارد زیرا در غیراین‌صورت ${\displaystyle d\,\!}$-امین بیت ${\displaystyle s\,\!}$ صفر می‌شد). پس ${\displaystyle y_{k}=s\oplus x_{k}\,\!}$ و ما ادعا می‌کنیم که${\displaystyle y_{k}<\;x_{k}\,\!}$ . زیرا همه بیت‌های سمت چپ ${\displaystyle d\,\!}$ مشابه هستند و در ${\displaystyle x_{k}\,\!}$ و ${\displaystyle y_{k}\,\!}$ بیت ${\displaystyle d\,\!}$ از 1 به 0 کاهش می‌یابد.(ارزش آن ${\displaystyle 2^{k}\,\!}$ تا کاهش می‌یابد)، و هر تغییری در بیت‌های باقی‌مانده حداکثر ${\displaystyle 2^{k-1}\,\!}$ تاست. بنابراین بازیکن اول می‌تواند ${\displaystyle x_{k}-y_{k}\,\!}$ تا سنگ‌ریزه از کپه ${\displaystyle k\,\!}$-ام بردارد. در این صورت خواهیم داشت:

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

در یک بازی نیم پکر سه کپه با اندازه‌های {3, 4, 5} وجود دارد و بازی مدتی است که شروع شده‌است و هر بازیکن مقدار قابل توحه‌ای سنگ‌ریزه ذخیره کرده‌است؛ اکنون نوبت بازیکن1 است و او بازی را به {1, 4, 5} که وضعیت خوبی در بازی نیم است می‌برد. اما بازیکن2، 50 تا سنگ‌ریزه به کپه با اندازه 4 اضافه می‌کند و وضعیت {1, 54, 5} را ایجاد می‌کند. به نظر می‌رسد که بازی پیچیده شده‌است.

بازیکن1 باید چه بکند؟ بعد از مدتی فکر کردن او فقط 50 تا سنگ‌ریزه‌ای را که ابازیکن2 اضافه کرده بود؛ برمی‌دارد و بازی را به وضعیت قبل در می‌آورد. مهم نیست که بازیکن2 در این بین چقدر سنگ‌ریزه ذخیره کرده‌است یا چند تا سنگ ریزه اضافه می‌کند؛ زیرا هم تعداد سنگ‌ریزه‌هایی که ذخیره کرده‌است متناهی است وهم ما همواره می‌توانیم آن مقداری را که بازیکن2 اضافه کرده‌است برداریم و بازی را مثل بازی نیم معمولی دنبال کنیم.

با توجه به مطالب قسمت قبل هر بازیکنی که بتواند در یک وضعیت نیم معمولی برنده شود در نیم پکر با همان وضعیت نیز می‌تواند برنده شود. زیرا اگر بازیکن مقابل اندازه کپه‌ای را کاهش دهد او مطابق با استراتژی بازی نیم پیش می‌رود. و اگر بازیکن مقابل اندازه کپه‌ای را افزایش دهد؛ او حرکت بازیکن مقابل را با برداشتن مقداری که ابه کپه اضافه کرده‌است خنثی می‌کند و بازی را به وضعیت قبل برمی‌گرداند. در این حالت فقط پایان بازی به تأخیر می‌افتد.