نیم (بازی)

نیم (بازی)

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

نیم اغلب به این صورت بازی می‌شود که بازیکنی که آخرین سنگ‌ریزه را برمی‌دارد بازنده‌است (misere). اما می‌توان به‌طور معمولی نیز بازی کرد؛ بدین شکل که بازیکنی که آخرین انتخاب را دارد برنده است. این را به این دلیل معمولی گفتیم چون اکثر بازی‌ها چنین رویه‌ای را دنبال می‌کنند. در ادامه نیم معمولی در نظر گرفته می‌شود.

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

تاریخچه

نوع دیگری از نیم در زمان‌های دور بازی می‌شده‌است. گفته می‌شود که این بازی در چین ابداع شده‌است (نیم شباهت زیادی یه بازی چینی جی‌ان‌شی‌زی "Jianshizi" دارد) اما پیدایش آن نامشخص است؛ اروپاییان نیز در آغاز قرن شانزدهم با نیم آشنا شدند. نام رایج این بازی توسط سی. ال. بوتون (Charles L. Bouton) که تئوری کامل این بازی را در سال ۱۹۰۱ میلادی ایجاد کرد. ابداع شد. نیم احتمالاً از آلمانی بگیر! (nimm) یا فعل مهجور انگلیسی nim با همین معنا گرفته شده‌است.

اشکال گوناگون نیم از دوران باستان بازی می‌شده‌است. گفته می‌شود که چینیان این بازی را ابداع کرده‌اند (مانند بازی جیانشیزی به معنای برداشتن سنگ است). اما سرچشمه اصلی آن مشخص نیست. اولین ارجاعات اروپایی به این بازی به قرن شانزدهم بازمی‌گردد. اسم فعلی آن توسط چارلز ال بوتون ³ (دانشگاه هاروارد ⁴) که نظریه این بازی را در سال ۱۹۰۱ ارائه داد ساخته شده‌است. اما خاستگاه اصلی این اسم هیچگاه به‌طور کامل توضیح داده نشد. شاید از کلمه آلمانی nimm به معنای بَردار یا کلمه انگلیسی nim به همین معنا گرفته شده باشد. یا شاید از برگرداندن و وارون کردن کلمه WIN بدست آمده باشد.

نیم معمولاً به عنوان یک بازی میسِر ⁵ اجرا می‌شود که بازیکنی که آخرین حرکت را انجام می‌دهد بازی را می‌بازد. همچنین نیم می‌تواند به عنوان یک بازی عادی ⁶ اجرا شود که در آن کسی که آخرین حرکت را انجام می‌دهد می‌برد. به این نوع بازی بازی عادی می‌گویند چون بیشتر بازی‌ها از این سنت پیروی می‌کنند در حالی که نیم معمولاً این گونه نیست.

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

شکل خاصی از بازی نیم در فیلم سال گذشته در مارینباد ⁸ بازی شده.

1. object
2. heap
3. Charls L Bouton
4. Harvard University
5. misère
6. normal play
7. Sprague-Grundy
8. Last Year at Marienbad

مثال

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

A B C

۵ ۴ ۳ بازیکن۱ دو سنگ‌ریزه از A برمی‌دارد

۵ ۴ ۱ بازیکن۲ سه سنگ‌ریزه از C برمی‌دارد

۲ ۴ ۱ بازیکن۱ یکی از B برمی‌دارد

۲ ۳ ۱ بازیکن۲ یکی از B برمی‌دارد

۲ ۲ ۱ بازیکن۱ کپه A را برمی‌دارد

۲ ۲ ۰ بازیکن۲ یکی از B برمی‌دارد

۲ ۱ ۰ بازیکن۱ یکی از C برمی‌دارد (در misere تمام C را برمی‌داشت و پیروز می‌شد)

۱ ۱ ۰ بازیکن۲ یکی از B برمی‌دارد

۱ ۰ ۰ بازیکن۱ آخرین سنگ‌ریزه را برمی‌دارد و پیروز می‌شود.

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

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

در نیم یک کپه‌ای {n} , n> 0 یک N-وضعیت است {۰} یک P-وضعیت است.

در نیم دو کپه‌ای n≠ {m, n} , m یک N-وضعیت است {n, n} یک P-وضعیت است.

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

نظریه ریاضی

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

با جمع دودویی (باینری) اندازه کپه‌ها می‌توان این مسئله را حل نمود. به این ترتیب که معادل دودویی اندازه کپه‌ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. این عمل همان یای انحصاری (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 تشخیص داده شود. در زیر نمونه‌ای از محاسبات برای پشته‌های ۳، ۴ و ۵ تایی آورده شده‌است.

پشته	دودویی	دهدهی
پشته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 ⊕ X = 3 ⊕ 2 = 1

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

تنها پشته‌ای که کم شده A است. پس حرکت منجر به برد کاهش اندازه پشته A به یک است (برداشتن دو شیء).

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

وقتی بازی به صورت میسر انجام می‌شود سیاست نیم فقط وقتی که حرکت بازی عادی، پشته‌هایی با اندازه ۲ یا بزرگتر ایجاد نمی‌کند فرق می‌کند. در این مورد حرکت صحیح حرکتی است که تعداد فردی پشته با اندازه باقی بگذارد. (در بازی عادی حرکت صحیح باقی گذاشتن تعداد زوجی از این پشته هاست)

نمونه

بازی به شکل عادی ممکن است با پشته‌های سه، چهار و پنج تایی آغاز شود.

برای بردن کافیست تعداد زوجی از اعداد ۱، ۲ و ۴ باقی بگذارید.

A B C...........
۵ ۴ ۳	من دو تا از A برمی‌دارم.
۵ ۴ ۱	تو سه تا از C برمی‌داری.
۲ ۴ ۱	من یکی از B برمی‌دارم.
۲ ۳ ۱	تو یکی از B برمی‌داری.
۲ ۲ ۱	من کل پشته A را برمی‌دارم و دو پشته دوتایی می‌گذارم.
۲ ۲ ۰	تو یکی از B برمی‌داری.
۲ ۱ ۰	من یکی از C برمی‌دارم و دو پشته تکی می‌گذارم.
۱ ۱ ۰	تو یکی از B برمی‌داری.
۱ ۰ ۰	من کل C را برمی‌دارم و می‌برم.

اثبات فرمول برد

قضیه: در بازی عادی نیم برای نفر اول نقشه‌ای برای برد وجود دارد اگر و تنها اگر جمع اندازه پشته‌ها مخالف صفر باشد. در غیر این صورت نفر دوم نقشه‌ای برای برد دارد.

اثبات: توجه داشته باشید که جمع نیم از قوانین شرکت پذیری و جا به جایی شبیه جمع معمولی پیروی می‌کند و ویژگی دیگری به فرم x ⊕ x = ۰ دارد.

فرض کنید x₁، …، x_n اندازه پشته‌ها قبل از حرکت باشد و y₁، …، y_n اندازه متناظر بعد از حرکت باشد. قرار می‌دهیم s = x₁ ⊕ … ⊕ x_n وt = y₁ ⊕ … ⊕ y_n. اگر حرکت در پشته k باشد برای همه i≠k داریم x_i = y_i و x_k > y_k. با ویژگی که بالا گفته شد داریم:

 t = 0 ⊕ t
= s ⊕ s ⊕ t
= s ⊕ (x1 ⊕ … ⊕ xn) ⊕ (y1 ⊕ … ⊕ yn)
= s ⊕ (x1 ⊕ y1) ⊕ … ⊕ (xn ⊕ yn)
= s ⊕ 0 ⊕ … ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ … ⊕ 0
= s ⊕ xk ⊕ yk

(*) t = s ⊕ xk ⊕ yk.

لم ۱: اگر s=۰، آنگاه بدون در نظر گرفتن نوع حرکت t≠۰.

اگر هیچ حرکتی نتوان کرد، لم قطعاً صحیح است و نفر اول با توجه به تعریف بازی را می‌بازد؛ و اگر نه هر حرکتی در پشته kام از * نتیجه می‌دهد t = x_k ⊕ y_k که این عدد ناصفر است زیرا x_k ≠ y_k.

لم ۲: اگر s≠۰، می‌توان حرکتی انجام داد تا t=۰.

فرض کنید d مکان پرارزشترین بیت (MSB) غیر صفر در نمایش دودویی s باشد و k را طوری انتخاب کنید که dامین بیت x_k هم غیر صفر باشد. چنین kای وجود دارد زیرا در غیر این صورت dامین بیت s صفر خواهد بود. سپس با قرار دادن y_k = s ⊕ x_k می‌توان مطمئن شد که y_k < x_k': تمام بیتهای سمت چپ d در x_k و y_k مشابهند، بیت dام از یک به صفر کاهش می‌یابد و در نتیجه مقدار کل 2k کم می‌شود و هر تغییر دیگر در بیتهای مانده بیشینه تغییر 2k-۱ را ایجاد می‌کند. پس نفر اول می‌تواند حرکتی با برداشتن x_k − y_k شیء از پشته kام انجام دهد. سپس:

t = s ⊕ xk ⊕ yk (by (*))
= s ⊕ xk ⊕ (s ⊕ xk)
= 0.

تفاوت موجود در بازی میسر در مکانی است که فقط یک پشته با اندازه ۲ یا بیشتر وجود دارد. نقشه بازی عادی کاهش آن به اندازه ۰ و ۱ و باقی گذاشتن تعداد زوجی از پشته‌های با اندازه ۱ است در حالی که نقشه بازی میسر برای انجام خلاف این است. از آن به بعد حرکات به زور انجام می‌شوند یعنی حق انتخابی ندارند.

منابع

• W. W. Rouse Ball: Mathematical Recreations and Essays, The Macmillan Company، ۱۹۴۷.
• John D. Beasley: The Mathematics of Games, Oxford University Press، ۱۹۸۹.
• Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy: Winning Ways for Your Mathematical Plays, Academic Press, Inc. ، ۱۹۸۲.
• C. L. Bouton: Nim, a game with a complete mathematical theory, Annals of Mathematics 3 (1901-02)، ۳۵–۳۹.
• Manfred Eigen and Ruthild Winkler: Laws of the Game, Princeton University Press، ۱۹۸۱.
• Walter R. Fuchs: Computers: Information Theory and Cybernetics, Rupert Hart-Davis Educational Publications، ۱۹۷۱.
• G. H. Hardy and E. M. Wright: An Introduction to the Theory of Numbers, Oxford University Press، ۱۹۷۹.
• Edward Kasner and James Newman: Mathematics and the Imagination, Simon and Schuster، ۱۹۴۰.
• M. Kaitchik: Mathematical Recreations, W. W. Norton، ۱۹۴۲.
• Donal D. Spencer: Game Playing with Computers, Hayden Book Company, Inc.، ۱۹۶۸.