موضوع مقاله: بازی‌های منصفانه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بازی‌های منصفانه | مقدمه: در نظریه بازی‌های ترکیبیاتی، بازی منصفانه به بازی گفته می‌شود که حرکت‌های قابل قبول تنها به وضعیت بستگی دارد نه به اینکه آخرین بار چه کسی حرکت کرده‌است و درحالی که حاصل متقارن می‌باشد. | ## بخش 1: بازی‌های منصفانه | در یک بازی منصفانه مستقل از این‌که نوبت کدام بازیکن است، امکانات یکسانی وجود دارد. ( نیم شباهت زیادی یه بازی چینی جی‌ان‌شی‌زی Jianshizi دارد) اما چگونگی پیدایش آن نامشخص است؛ اروپاییان نیز در آغاز قرن شانزدهم با نیم آشنا شدند. قوانین بازی نیم یک بازی راهبردی (استراتژیک) ریاضی است که با کپه‌هایی از سنگ‌ریزه (یا لوبیا، چوب‌کبریت، چیپس) انجام می‌شود. در هر نوبت هر بازیکن از یک کپه حداقل یک سنگ‌ریزه بر می‌دارد (بازیکن حتی می‌تواند تمام کپه را نیز بردارد). نیم اغلب به این صورت بازی می‌شود که بازیکنی که آخرین سنگ‌ریزه را برمی‌دارد بازنده است. اما می‌توان به‌طور معمولی نیز بازی کرد به این معنا که بازیکنی که نتواند چیزی را بردارد بازنده است (کسی که آخرین سنگ‌ریزه را برمی‌دارد). ۲ ۱ ۰ بازیکن یک ۱ سنگ ریز از C بر می‌دارد.(در misere تمام C را بر می‌داشت وپیروز می‌شد) ۱ ۱ ۰ بازیکن دو ۱ سنگ ریز از A بر می‌دارد و پیروز می‌شود. به‌طورکلی در یک N-وضعیت بازیکن اول می‌تواند با حرکات مناسب حتماً به پیروزی برسد و در یک P-وضعیت بازیکن دوم می‌تواند با حرکات مناسب حتماً به پیروزی برسد. برای یک کپه‌ای که علت آن پر واضح است اما برای دو کپه‌ای اگر اندازه دو کپه برابر باشد نفر دوم با تقلید حرکات نفر اول می‌تواند مطمئن باشد که برنده خواهد شد و اگر اندازه دو کپه برابر نباشد نفر اول با برداشتن مقدار اضافی از کپه اول می‌تواند اندازه دو کپه را برابر کند و این بار او با ترفند تقلید به پیروزی برسد. با افزایش تعداد کپه‌ها بررسی این موضوع پیچیده‌تر می‌شود که به صورت یک مسئله ریاضی آن را حل می‌کنیم الگوریتم ریاضی نیم به صورت ریاضی برای تعداد متناهی از کپه‌ها و سنگ‌ریزه‌ها حل شده‌است و می‌توان مشخص نمود که کدام بازیکن برنده خواهد شد. به این ترتیب که معادل دودویی اندازه کپه‌ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. ما برای نشان دادن جمع نیمی از همان نمایش آن در مدارهای منطقی که است؛ استفاده می‌کنیم. به این ترتیب که انگشتان دست را به ترتیب توان‌های 2 در نظر می‌گیرند و اگر عددی دارای آن توان 2 بود آن را بالا می‌برند و اگر دارای آن توان نبود آن را پایین می‌آورند و در جمع با سایر اعداد اگر آن عدد دارای توانی از 2 بود وضعیت مربوط به آن انگشت را برعکس می‌کنند؛ یعنی اگر بالا بود آن را پایین می‌آورند و اگر پایین بود آن را بالا می‌برند. در بازی معمولی استراتژی برد صفر کردن جمع نیمی اندازه کپه‌هاست که این امر تا زمانی‌که جمع نیمی آن‌ها 0 نشده‌است ممکن است. برای آن‌که بدانیم در هر مرحله چه حرکتی باید انجام دهیم؛ جمع نیمی کپه‌ها را X در نظر می‌گیریم. | ## بخش 2: بازی‌های منصفانه | با جمع نیمی اندازه هر کپه با X، کپه‌ای را که اندازه آن کم شده‌است را پیدا می‌کنیم. برای مثال بالا داریم: تنها کپه‌ای که اندازه آن کاهش یافته A است؛ بنابراین برای برنده شدن در حرکت خود اندازه A را به 1 کاهش می‌دهیم. وقتی که به صورت misere بازی می‌کنیم؛ استراتژی بازی فقط در مقایسه با بازی معمولی این تغییر را می‌کند تلاش می‌کنیم که در هر حرکت هیچ کپه‌ای با اندازه بیشتر از 1 بر جای نگذاریم. در بازی معمولی استراتژی برد در باقی گذاشتن تعداد زوجی از کپه‌ها با انداره 1 است. قضیه : در بازی نیم معمولی نفر اول برنده می‌شود (یک N-وضعیت است) اگر و تنها اگر جمع نیمی اندازه کپه‌ها غیر صفر باشد. اثبات : می‌دانیم که جمع نیمی (XOR) از قوانین جابه‌جایی و شرکت‌پذیری پیروی می‌کند. هم‌چنین داریم: را برابر با اندازه کپه‌ها قبل از حرکت و را برابر با اندازه کپه‌ها بعد از حرکت قرار می‌دهیم: اگر سنگ‌ریزه از کپه k-ام برداشته شود خواهیم داشت: پس داریم: لم1: اگر باشد آن‌گاه است و مهم نیست که چه حرکتی انجام شود. اثبات: اگر انجام هیچ حرکتی ممکن نباشد یعنی کپه‌ها تهی هستند و بازیکن اول بازنده است. در غیراین‌صورت با حرکت در کپه خواهیم داشت و این حاصل حتماً غیر صفر است زیرا است. اثبات: را برابر با سمت چپ‌ترین بیت غیر صفر در نمایش دودویی قرار می‌دهیم و را نیز -امین بیت که آن‌هم غیر صفر است؛ انتخاب می‌کنیم ( حتماً وجود دارد زیرا در غیراین‌صورت -امین بیت صفر می‌شد). زیرا همه بیت‌های سمت چپ مشابه هستند و در و بیت از 1 به 0 کاهش می‌یابد.(ارزش آن تا کاهش می‌یابد)، و هر تغییری در بیت‌های باقی‌مانده حداکثر تاست. در این صورت خواهیم داشت: نیم پکر قوانین بازی نیم پکر نیز مانند نیم با کپه‌هایی از سنگ‌ریزه (یا لوبیا، چوب‌کبریت، چیپس) انجام می‌شود. و همانند بازی نیم هر بازیکن می‌توانند اندازه کپه‌ها را با برداشتن تعدادی از سنگ‌ریزه‌ها کاهش دهد؛ اما بازیکنان در این بازی می‌توانند اندازه کپه‌ها را با افزودن سنگ‌ریزه‌هایی که در نوبت‌های قبل بدست آورده‌اند افزایش دهند. مثالی از یک بازی نیم پکر در یک بازی نیم پکر سه کپه با اندازه‌های {3, 4, 5} وجود دارد و بازی مدتی است که شروع شده‌است و هر بازیکن مقدار قابل توحه‌ای سنگ‌ریزه ذخیره کرده‌است؛ اکنون نوبت بازیکن1 است و او بازی را به {1, 4, 5} که وضعیت خوبی در بازی نیم است می‌برد. اما بازیکن2، 50 تا سنگ‌ریزه به کپه با اندازه 4 اضافه می‌کند و وضعیت {1, 54, 5} را ایجاد می‌کند. | ## بخش 3: بازی‌های منصفانه | بعد از مدتی فکر کردن او فقط 50 تا سنگ‌ریزه‌ای را که ابازیکن2 اضافه کرده بود؛ برمی‌دارد و بازی را به وضعیت قبل در می‌آورد. مهم نیست که بازیکن2 در این بین چقدر سنگ‌ریزه ذخیره کرده‌است یا چند تا سنگ ریزه اضافه می‌کند؛ زیرا هم تعداد سنگ‌ریزه‌هایی که ذخیره کرده‌است متناهی است وهم ما همواره می‌توانیم آن مقداری را که بازیکن2 اضافه کرده‌است برداریم و بازی را مثل بازی نیم معمولی دنبال کنیم. استراتژی برد با توجه به مطالب قسمت قبل هر بازیکنی که بتواند در یک وضعیت نیم معمولی برنده شود در نیم پکر با همان وضعیت نیز می‌تواند برنده شود. زیرا اگر بازیکن مقابل اندازه کپه‌ای را کاهش دهد او مطابق با استراتژی بازی نیم پیش می‌رود. و اگر بازیکن مقابل اندازه کپه‌ای را افزایش دهد؛ او حرکت بازیکن مقابل را با برداشتن مقداری که ابه کپه اضافه کرده‌است خنثی می‌کند و بازی را به وضعیت قبل برمی‌گرداند. این بازی روی یک مستطیل n×m انجام می‌شود و هر بازیکن m مهره در اختیار دارد که در ردیف اول و آخر در مقابل هم قرار می‌گیرند. این بازی برای 3×3 آن حل شده است و اگر هر دو بازیکن خوب بازی کنند حتماً نفر دوم خواهد برد. در این بازی مانند شطرنج هر مهره مانند مهره سرباز شطرنج می‌تواند دو نوع حرکت انجام دهد. یک خانه رو به جلو در صورت خالی بودن آن خانه یا زدن مهره حریف به صورت حرکت قطری با اندازه یک. اما در این بازی برخلاف شطرنج در حرکت ابتدایی مهره‌ها نمی‌توانند دو خانه به جلو حرکت کنند. قوانین این بازی مانند بازی Hexapawn است با این قانون اضافی که زدن مهره حریف در صورت فراهم شدن موقعیت، اجباری است. فارغ از محتوای شطرنجی آن، این بازی معادل با بازی است که با یک ردیف مهره انجام می‌شود و در آن یک حرکت عبارت است از برداشتن یک مهره همراه با (یک یا دو) مهره مجاورش، در صورت وجود. اگر این بازی را با کپه‌های سنگ‌ریزه به جای ردیف‌هایی از مهره انجام از مهره‌ها انجام دهید؛ قاعده بیان شده را می‌توان به این صورت بیان کرد: 0 کپه، اگر دقیقاً یک سنگ‌ریزه برداشته شود (هیچ مهره مجاوری برداشته نشود) 0 یا 1 کپه، اگر دقیقاً دو سنگ‌ریزه برداشته شود (یک مهره مجاور برداشته شود) 0 یا 1 یا 2 کپه، اگر دقیقاً سه لوبیا برداشته شود (دو مهره مجاورش برداشته شود) به عنوان مثال، از یک ردیف‌هشتایی، می‌توانید به یک ردیف شش‌تایی، یا به یک ردیف پنج‌تایی، یا به دو ردیف 1 و 4تایی یا 2 و 3تایی برسید. برای برداشتن یک سنگ‌ریزه برای برداشتن دو سنگ‌ریزه برای برداشتن سه سنگ‌ریزه و بازی شطرنج داوسون برچسب 137• را می‌گیرد؛ که اولین رقم رمز بعد از نقطه، شرایطی است که تحت آن می‌توانید یک سنگ‌ریزه را بردارید؛ رقم دوم شرایطی است برای برداشتن دو سنگ‌ریزه و سومین رقم سرایط برای برداشتن رقم سوم را نشان می‌دهد. | ## جمع‌بندی | به‌طور کلی، اگر در یک بازی بتوانیم k سنگ‌ریزه از یک کوپه برداریم؛ با این فرض که باقی‌مانده کپه دقیقاً به a کپه ناتهی، یا b کپه، یا c کپه، یا ...