بازی‌های منصفانه
در نظریه بازی‌های ترکیبیاتی، بازی منصفانه به بازی گفته می‌شود که حرکت‌های قابل قبول تنها به وضعیت بستگی دارد نه به اینکه آخرین بار چه کسی حرکت کرده‌است و درحالی که حاصل متقارن می‌باشد.
در یک بازی منصفانه مستقل از این‌که نوبت کدام بازیکن است، امکانات یکسانی وجود دارد.
بازی‌های منصفانه می‌توانند توسط نظریه سپرگو-گراندی تحلیل شوند.
از جمله این بازی‌ها می‌توان نیم ، نیمبل ، نیم پکر و دلار نقره‌ای ان.جی.دی براین را نام برد.
بازی که منصفانه نباشند را بازی پارتیزانی می‌نامیم. مانند بازی‌های گو ، بازی درافت ، شطرنج، تیک-تاک-تو ، تخته نرد یا نقطه بازی .
گفته می‌شود که این بازی در چین ابداع شده‌است و در زمان‌های دور بازی می‌شده‌است. ( نیم شباهت زیادی یه بازی چینی جی‌ان‌شی‌زی Jianshizi دارد) اما چگونگی پیدایش آن نامشخص است؛ اروپاییان نیز در آغاز قرن شانزدهم با نیم آشنا شدند. نام رایج این بازی توسط سی. ال. بوتون (Charles L. Bouton) که تئوری کامل این بازی را در سال 1901 میلادی ایجاد کرد.؛ ابداع شد.
نیم احتمالاً از آلمانی بگیر! (nimm) یا فعل مهجور انگلیسی nim با همین معنا گرفته شده‌است. نیم یک بازی راهبردی (استراتژیک) ریاضی است که با کپه‌هایی از سنگ‌ریزه (یا لوبیا، چوب‌کبریت، چیپس) انجام می‌شود. در هر نوبت هر بازیکن از یک کپه حداقل یک سنگ‌ریزه بر می‌دارد (بازیکن حتی می‌تواند تمام کپه را نیز بردارد). نیم اغلب به این صورت بازی می‌شود که بازیکنی که آخرین سنگ‌ریزه را برمی‌دارد بازنده است. (misere). اما می‌توان به‌طور معمولی نیز بازی کرد به این معنا که بازیکنی که نتواند چیزی را بردارد بازنده است (کسی که آخرین سنگ‌ریزه را برمی‌دارد). این را به این دلیل معمولی گفتیم چون اکثر بازی‌ها چنین رویه‌ای را دنبال می‌کنند.
ما در ادامه نیم معمولی را در نظر می‌گیریم. یک بازی نیم را با کپه‌های {۳، ۴ و ۵} تایی در نظر بگیرید بنابراین وضعیت {۳، ۴، ۵} را یک N-وضعیت می‌گوییم. به‌طورکلی در یک N-وضعیت بازیکن اول می‌تواند با حرکات مناسب حتماً به پیروزی برسد و در یک P-وضعیت بازیکن دوم می‌تواند با حرکات مناسب حتماً به پیروزی برسد.
در بازی با تعداد کپه کم می‌توان به راحتی N-وضعیت‌ها و P-وضعیت‌ها را یافت. برای مثال: برای یک کپه‌ای که علت آن پر واضح است اما برای دو کپه‌ای اگر اندازه دو کپه برابر باشد نفر دوم با تقلید حرکات نفر اول می‌تواند مطمئن باشد که برنده خواهد شد و اگر اندازه دو کپه برابر نباشد نفر اول با برداشتن مقدار اضافی از کپه اول می‌تواند اندازه دو کپه را برابر کند و این بار او با ترفند تقلید به پیروزی برسد.
با افزایش تعداد کپه‌ها بررسی این موضوع پیچیده‌تر می‌شود که به صورت یک مسئله ریاضی آن را حل می‌کنیم
نیم به صورت ریاضی برای تعداد متناهی از کپه‌ها و سنگ‌ریزه‌ها حل شده‌است و می‌توان مشخص نمود که کدام بازیکن برنده خواهد شد.
با جمع دودویی (باینری) اندازه کپه‌ها می‌توان این مسئله را حل نمود. به این ترتیب که معادل دودویی اندازه کپه‌ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. این عمل همان یاءانحصاری (XOR) در مدارهای منطقی است که در تئوری بازی‌های ترکیبیاتی (Combinatorial Games) آن را جمع نیمی (nim-sum) می‌نامند. ما برای نشان دادن جمع نیمی از همان نمایش آن در مدارهای منطقی که formula_1 است؛ استفاده می‌کنیم. جمع نیمی را می‌توان به صورت ذهنی انگشان دست هم حساب نمود. به این ترتیب که انگشتان دست را به ترتیب توان‌های 2 در نظر می‌گیرند و اگر عددی دارای آن توان 2 بود آن را بالا می‌برند و اگر دارای آن توان نبود آن را پایین می‌آورند و در جمع با سایر اعداد اگر آن عدد دارای توانی از 2 بود وضعیت مربوط به آن انگشت را برعکس می‌کنند؛ یعنی اگر بالا بود آن را پایین می‌آورند و اگر پایین بود آن را بالا می‌برند.
در بازی معمولی استراتژی برد صفر کردن جمع نیمی اندازه کپه‌هاست که این امر تا زمانی‌که جمع نیمی آن‌ها 0 نشده‌است ممکن است. اگر جمع نیمی صفر شود بازیکنی که نوبت آن است خواهد باخت. (در صورتی که بازیکن دیگر اشتباه نکند). ما فرض می‌کنیم که در هر نوبت هر بازیکن بهترین حرکت ممکن را انجام می‌دهد. برای آن‌که بدانیم در هر مرحله چه حرکتی باید انجام دهیم؛ جمع نیمی کپه‌ها را X در نظر می‌گیریم. با جمع نیمی اندازه هر کپه با X، کپه‌ای را که اندازه آن کم شده‌است را پیدا می‌کنیم. استراتژی برد در بازی با چنین کپه‌ای است. برای مثال بالا داریم: formula_2
formula_3
formula_4
formula_5 تنها کپه‌ای که اندازه آن کاهش یافته A است؛ بنابراین برای برنده شدن در حرکت خود اندازه A را به 1 کاهش می‌دهیم.
وقتی که به صورت misere بازی می‌کنیم؛ استراتژی بازی فقط در مقایسه با بازی معمولی این تغییر را می‌کند تلاش می‌کنیم که در هر حرکت هیچ کپه‌ای با اندازه بیشتر از 1 بر جای نگذاریم. در این مورد حرکتی درست است که تعداد فردی از کپه‌ها با اندازه 1 بر جای گذارد. در بازی معمولی استراتژی برد در باقی گذاشتن تعداد زوجی از کپه‌ها با انداره 1 است.
در بازی نیم به صورت misere با کپه‌های 3، 4 و 5 استراتژی به صورت زیر است:
درستی الگوریتم بالا توسط بوتون اثبات شد..
قضیه : در بازی نیم معمولی نفر اول برنده می‌شود (یک N-وضعیت است) اگر و تنها اگر جمع نیمی اندازه کپه‌ها غیر صفر باشد. در غیر این صورت نفر دوم برنده می‌شود (یک P-وضعیت است).
اثبات : می‌دانیم که جمع نیمی (XOR) از قوانین جابه‌جایی و شرکت‌پذیری پیروی می‌کند. هم‌چنین داریم: formula_6
formula_7 را برابر با اندازه کپه‌ها قبل از حرکت و formula_8 را برابر با اندازه کپه‌ها بعد از حرکت قرار می‌دهیم:
formula_9
formula_10
اگر سنگ‌ریزه از کپه k-ام برداشته شود خواهیم داشت:
formula_11
پس داریم:
formula_12
formula_13
formula_14
formula_15
formula_16
formula_17 formula_18
لم1: اگر formula_19 باشد آن‌گاه formula_20 است و مهم نیست که چه حرکتی انجام شود.
اثبات: اگر انجام هیچ حرکتی ممکن نباشد یعنی کپه‌ها تهی هستند و بازیکن اول بازنده است. در غیراین‌صورت با حرکت در کپه formula_21 خواهیم داشت formula_22 و این حاصل حتماً غیر صفر است زیرا formula_23 است.
لم2: اگر formula_24 باشد آن‌گاه می‌توان حرکتی انجام داد که formula_25 شود.
اثبات: formula_26 را برابر با سمت چپ‌ترین بیت غیر صفر formula_27 در نمایش دودویی قرار می‌دهیم و formula_21 را نیز formula_26-امین بیت formula_30 که آن‌هم غیر صفر است؛ انتخاب می‌کنیم (formula_21 حتماً وجود دارد زیرا در غیراین‌صورت formula_26-امین بیت formula_27 صفر می‌شد). پس formula_34 و ما ادعا می‌کنیم کهformula_35 . زیرا همه بیت‌های سمت چپ formula_26 مشابه هستند و در formula_30 و formula_38 بیت formula_26 از 1 به 0 کاهش می‌یابد.(ارزش آن formula_40 تا کاهش می‌یابد)، و هر تغییری در بیت‌های باقی‌مانده حداکثر formula_41 تاست. بنابراین بازیکن اول می‌تواند formula_42 تا سنگ‌ریزه از کپه formula_21-ام بردارد. در این صورت خواهیم داشت:
formula_44
formula_45
formula_46 نیم پکر نیز مانند نیم با کپه‌هایی از سنگ‌ریزه (یا لوبیا، چوب‌کبریت، چیپس) انجام می‌شود. و همانند بازی نیم هر بازیکن می‌توانند اندازه کپه‌ها را با برداشتن تعدادی از سنگ‌ریزه‌ها کاهش دهد؛ اما بازیکنان در این بازی می‌توانند اندازه کپه‌ها را با افزودن سنگ‌ریزه‌هایی که در نوبت‌های قبل بدست آورده‌اند افزایش دهند. این دو حرکت، تنها حرکت‌های مجاز این بازی‌اند. در یک بازی نیم پکر سه کپه با اندازه‌های {3, 4, 5} وجود دارد و بازی مدتی است که شروع شده‌است و هر بازیکن مقدار قابل توحه‌ای سنگ‌ریزه ذخیره کرده‌است؛ اکنون نوبت بازیکن1 است و او بازی را به {1, 4, 5} که وضعیت خوبی در بازی نیم است می‌برد. اما بازیکن2، 50 تا سنگ‌ریزه به کپه با اندازه 4 اضافه می‌کند و وضعیت {1, 54, 5} را ایجاد می‌کند. به نظر می‌رسد که بازی پیچیده شده‌است.
بازیکن1 باید چه بکند؟ بعد از مدتی فکر کردن او فقط 50 تا سنگ‌ریزه‌ای را که ابازیکن2 اضافه کرده بود؛ برمی‌دارد و بازی را به وضعیت قبل در می‌آورد. مهم نیست که بازیکن2 در این بین چقدر سنگ‌ریزه ذخیره کرده‌است یا چند تا سنگ ریزه اضافه می‌کند؛ زیرا هم تعداد سنگ‌ریزه‌هایی که ذخیره کرده‌است متناهی است وهم ما همواره می‌توانیم آن مقداری را که بازیکن2 اضافه کرده‌است برداریم و بازی را مثل بازی نیم معمولی دنبال کنیم.
با توجه به مطالب قسمت قبل هر بازیکنی که بتواند در یک وضعیت نیم معمولی برنده شود در نیم پکر با همان وضعیت نیز می‌تواند برنده شود. زیرا اگر بازیکن مقابل اندازه کپه‌ای را کاهش دهد او مطابق با استراتژی بازی نیم پیش می‌رود. و اگر بازیکن مقابل اندازه کپه‌ای را افزایش دهد؛ او حرکت بازیکن مقابل را با برداشتن مقداری که ابه کپه اضافه کرده‌است خنثی می‌کند و بازی را به وضعیت قبل برمی‌گرداند. در این حالت فقط پایان بازی به تأخیر می‌افتد.
Hexapawn یک بازی دونفره است که توسط مارتین گاردنر (Martin Gardner) ابداع شد. این بازی روی یک مستطیل n×m انجام می‌شود و هر بازیکن m مهره در اختیار دارد که در ردیف اول و آخر در مقابل هم قرار می‌گیرند. برای مثال روی یک صفحه 3×3 .
این بازی برای 3×3 آن حل شده است و اگر هر دو بازیکن خوب بازی کنند حتماً نفر دوم خواهد برد. در این بازی به نظر می‌رسد که هیچ بازیکنی نمی‌تواند تمام مهره‌های حریفش را بزند.
در این بازی مانند شطرنج هر مهره مانند مهره سرباز شطرنج می‌تواند دو نوع حرکت انجام دهد. یک خانه رو به جلو در صورت خالی بودن آن خانه یا زدن مهره حریف به صورت حرکت قطری با اندازه یک. اما در این بازی برخلاف شطرنج در حرکت ابتدایی مهره‌ها نمی‌توانند دو خانه به جلو حرکت کنند.
توماس رینر داوسون (Thomas Rayner Dawson) سلطان شطرنج منصفانه، یک بازی با دو ردیف سرباز روی یک صفحه شطرنجی n×3 اختراع کرد. قوانین این بازی مانند بازی Hexapawn است با این قانون اضافی که زدن مهره حریف در صورت فراهم شدن موقعیت، اجباری است. فارغ از محتوای شطرنجی آن، این بازی معادل با بازی است که با یک ردیف مهره انجام می‌شود و در آن یک حرکت عبارت است از برداشتن یک مهره همراه با (یک یا دو) مهره مجاورش، در صورت وجود. اگر این بازی را با کپه‌های سنگ‌ریزه به جای ردیف‌هایی از مهره انجام از مهره‌ها انجام دهید؛ قاعده بیان شده را می‌توان به این صورت بیان کرد:
0 کپه، اگر دقیقاً یک سنگ‌ریزه برداشته شود (هیچ مهره مجاوری برداشته نشود)
0 یا 1 کپه، اگر دقیقاً دو سنگ‌ریزه برداشته شود (یک مهره مجاور برداشته شود)
0 یا 1 یا 2 کپه، اگر دقیقاً سه لوبیا برداشته شود (دو مهره مجاورش برداشته شود)
به عنوان مثال، از یک ردیف‌هشتایی، می‌توانید به یک ردیف شش‌تایی، یا به یک ردیف پنج‌تایی، یا به دو ردیف 1 و 4تایی یا 2 و 3تایی برسید. یک مهره یا سنگ‌ریزه خود به تنهایی یک ردیف یا کپه باشد؛ می‌توان برداشت. ریچارد کنت گای (Richard Kenneth Guy) و سدریک اوستون باردل اسمیت این شرایط را به وسیله کد رقمی، برای هر تعداد سنگ‌ریزه 0، 1، 2، ... که ممکن است برداشته شود؛ به صورت رمزی در آوردند. برای شطرنج داوسون رقم‌های رمزی به صورت زیر هستند.
برای برداشتن یک سنگ‌ریزه formula_47
برای برداشتن دو سنگ‌ریزهformula_48
برای برداشتن سه سنگ‌ریزهformula_49
و بازی شطرنج داوسون برچسب 137• را می‌گیرد؛ که اولین رقم رمز بعد از نقطه، شرایطی است که تحت آن می‌توانید یک سنگ‌ریزه را بردارید؛ رقم دوم شرایطی است برای برداشتن دو سنگ‌ریزه و سومین رقم سرایط برای برداشتن رقم سوم را نشان می‌دهد.
به‌طور کلی، اگر در یک بازی بتوانیم k سنگ‌ریزه از یک کوپه برداریم؛ با این فرض که باقی‌مانده کپه دقیقاً به a کپه ناتهی، یا b کپه، یا c کپه، یا ... (a، b، c و ... متمایزاند) تقسیم شود، به این بازی رمز formula_50 را برای برداشتن k سنگ‌ریزه می‌دهیم.