نیم (بازی)
نظریه ریاضی

نیم به صورت ریاضی برای تعداد متناهی از کپه‌ها و سنگ‌ریزه‌ها حل شده‌است و می‌توان مشخص نمود که کدام بازیکن برنده خواهد شد.
با جمع دودویی (باینری) اندازه کپه‌ها می‌توان این مسئله را حل نمود. به این ترتیب که معادل دودویی اندازه کپه‌ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. این عمل همان یای انحصاری (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 تعداد زوجی
کپه با اندازه ۱ بر جای خواهد گذاشت و برنده خواهد شد. برای misere با
برداشتن تمام B تعداد فردی کپه با اندازه ۱ بر جای خواهد گذاشت.
۱ ۰ ۰ ۱ بازیکن۲ با برداشتن یکی از C بازنده می‌شود.
نیم برای هر تعداد دلخواهی از پشته‌ها و اشیا، ریاضی وار پاسخ داده شده‌است. یعنی روشی بسیار راحت وجود دارد که می‌توان فهمید کدام بازیکن خواهد برد و چه حرکاتی منجر به بردی برای برنده وجود دارد. در بازی که با پشته‌های ۳، ۴ و ۵ تایی آغاز می‌شود نفر اول با یک بازی بهینه (چه بازی معمولی باشد و چه میسر) خواهد برد.
کلید رسیدن به نظریه بازی، جمع دودویی ارقام اندازه پشته هاست. یعنی جمع دودویی بدون در نظر گرفتن رقم نقلی از یک رقم به رقم دیگر. این عمل با نام یای انحصاری معروف است که در نظریه بازی ترکیبی معمولاً جمع نیم (nim-sum) صدا زده می‌شود. جمع نیم x و y به صورت x ⊕ y نوشته می‌شود تا از جمع عادی x+y تشخیص داده شود. در زیر نمونه‌ای از محاسبات برای پشته‌های ۳، ۴ و ۵ تایی آورده شده‌است.
| 0 | 1 | 2 |
| --- | --- | --- |
| پشته | دودویی | دهدهی |
| پشتهA | 0112 | 310 |
| پشتهB | 1002 | 410 |
| پشتهC | 1012 | 510 |
| جمع نیم پشته‌ها ۲ است. | 0102 | 210 |
در روشی مشابه که ذهنی می‌توان آن را انجام داد اندازه پشته‌ها را به صورت جمع توان‌های دو می‌نویسیم جفتها با توان یکسان را حذف می‌کنیم و آنچه باقی می‌ماند را جمع می‌کنیم.
| ---- | ---- | ---- |
| --- | --- | --- |
| پشتهA | 3=0+2+1 | 0 2 1 |
| پشتهB | 4=4+0+0 | 4 ۰ ۰ |
| پشتهC | 5=4+0+1 | 4 0 1 |
در بازی عادی، سیاست برد اینست که در پایان هر حرکت جمع نیم برابر صفر باشد؛ که در صورتی که قبل از حرکت صفر نباشد همواره ممکن است. اگر جمع نیم صفر باشد بازیکن دیگر خواهد باخت. برای اینکه بفهمیم چه حرکتی کنیم x را برابر جمع نیم اندازه پشته‌ها قرار می‌دهیم و جمع نیم x را با اندازه یک یک پشته‌ها حساب می‌کنیم. حرکت ما در پشته‌ای است که اندازه آن کم می‌شود. در مثال قبل جمع نیم پشته‌ها X = ۳ ⊕ ۴ ⊕ ۵ = ۲ است. جمع نیم x با اندازه هر کدام از پشته‌ها برابرست با:
تنها پشته‌ای که کم شده A است. پس حرکت منجر به برد کاهش اندازه پشته A به یک است (برداشتن دو شیء).
در یک مثال ساده زمانی که تنها دو پشته باقی‌مانده سیاست برد کاهش دادن اندازه پشته بزرگتر برای هم اندازه کردن آن با پشته دیگر است. بعد از آن اصلاً مهم نیست که رقیب شما چه حرکتی انجام می‌دهد. شما هم می‌توانید همان حرکت را روی پشته دیگر انجام دهید با این ضمانت که شما حرکت آخر را انجام خواهید داد.
وقتی بازی به صورت میسر انجام می‌شود سیاست نیم فقط وقتی که حرکت بازی عادی، پشته‌هایی با اندازه ۲ یا بزرگتر ایجاد نمی‌کند فرق می‌کند. در این مورد حرکت صحیح حرکتی است که تعداد فردی پشته با اندازه باقی بگذارد. (در بازی عادی حرکت صحیح باقی گذاشتن تعداد زوجی از این پشته هاست)