×

Warning

JLIB_APPLICATION_ERROR_COMPONENT_NOT_LOADING

Error loading component: com_menus, Component not found

Articles

الگوریتم بازی نیم

الگوریتم برد

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

مثال ۱

بازی نیم‌ای با دو دسته مهره‌ی ۱۰ تایی در نظر می‌گیریم. بازی زیر یک بازی نمونه است که در آن بازیکن دوم حرکت بازیکن اول را تقلید می‌کند.

{10, 10} → {10, 7} → {7, 7} → {3, 7} → {3, 3} → {0, 3} → {0, 0}

مثال ۲

حال فرض کنید به جای ۲ دسته، ۶ دسته مهره داریم که دوبه‌دو مقادیر مساوی دارند. مثلاً {10, 3, 4, 3, 10, 4}. بدیهی است که در روش بازی برای بردن تفاوتی ایجاد نمی‌شود. یعنی بازیکن دوم حرکات بازیکن اول را تقلید می‌کند.

مثال ۳

حال بازی نیم با مهره‌های {10, 2, 3, 2, 2, 3, 2, 10} را در نظر بگیرید. با اینکه در این‌جا ۴ دسته‌ی با تعداد مهره‌ی ۲ داریم ولی باز هم می‌توان روش بالا را به کار برد. در حقیقت تعداد زوج بودن دسته‌ها مهم است.

مثال ۴

بازی نیمی با دسته های {10, 2, 3, 2, 10} را در نظر بگیرید. بازیکن اول که از روش تقارنی باخبر است در حرکت اول دسته‌ی با ۳ مهره را برداشته و بازی را طوری تغییر می‌دهد که به نفع او باشد. با برداشتن این ۳ مهره بازی به شکل {10, 2, 10, 2} خواهد بود. حال می‌تواند با بازی تقارنی برنده باشد. پس در این بازی بازیکن اول برنده است.

به طور کلی زوج کردن دسته‌ها برد بازی خواهد بود. اما این روش همیشه کاربرد ندارد. به مثال زیر دقت کنید.

مثال ۵

بازی نیم با دسته‌های {1, 2, 3, 4, 5} را در نظر بگیرید. در این بازی کدام بازیکن برنده است؟

می‌بینید که روش تقارنی قبلی نه برای بازیکن اول و نه برای بازیکن دوم راه‌حل مناسبی نیست.

روش حل کلی

بوتون در سال ۱۹۰۱ روش بازی تقارنی ارائه شده را به گونه‌ای تغییر داد که در همه‌ی حالات قابل استفاده باشد. ابتدا فرض کنید همه‌ی اعداد داده شده را در مبنای ۲ بنویسیم. یعنی به صورت مجموع توان‌های ۲

با فرض این که دسته‌ها به صورت {3, 6, 2, 11} باشند. مبنای ۲ را برای همه‌ی آن‌ها می‌نویسیم
2 = 2
3 = 2 + 1
6 = 4 + 2
11 = 8 + 2 + 1

حال همه‌ی این اعداد به دست آمده را در نظر می‌گیریم و قاعده‌ی تقارن را برای آن‌ها به کار می‌بریم.
{2, 2, 1, 4, 2, 8, 2, 1}

تعداد ۱ ها و ۲ ها زوج است. یک ۸ و یک ۴ داریم. برای زوج کردن تعداد این دو، بازیکن اول در حرکت اول از دسته‌ی ۸ تایی ۴ مهره برمی‌دارد. یعنی معادل اینکه بگوییم از دسته‌ی ۱۱ تایی ۴ مهره بر‌می‌دارد. بنابراین بازی به شکل زیر خواهد بود:
{2, 3, 6, 11} → {2, 3, 6, 4}
معادل این که
{2, 2, 1, 4, 2, 8, 2, 1} → {2, 2, 1, 4, 4, 2, 1}

بنابراین باز هم روش تقارنی گفته شده صحیح است. البته زوج کردن دسته‌ها در این حالت نیاز به کمی مهارت دارد و به سادگی حالت قبلی نیست. این کار به کمی تمرین نیاز خواهد داشت.

می‌توانید بازی نیم را از این‌جا دانلود کنید

لطفاً استفاده از مطالب وب‌سایت را با نام وب‌سایت همراه کنید تا ما هم برای ادامه‌ی این مسیر دلگرم شویم.