بازی‌های منصفانه

بازی کاشی‌کاری-۲

برد تقارنی بازی

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

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

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

کاشی‌کاری منصفانه و پارتیزانی

در صورتی که برای دو بازیکن استفاده از دومینو به یک صورت ممکن باشد، مثلاً هر دو بازیکن بتوانند از یک دومینوی افقی استفاده کنند یا استفاده از دومینوی افقی یا عمودی برای هر دو بازیکن ممکن باشد، بازی کاشی‌کاری منصفانه است.

در صورتی که یکی از دو بازیکن از دومینوهای افقی و دیگری از دومینوهای عمودی استفاده کند، بازی Domineering را داریم که یک بازی پارتیزانی است.

در این مطلب بازی منصفانه را بررسی می‌کنیم که در آن هر دو بازیکن می‌توانند از دومینوها عمودی یا افقی استفاده کنند.

الگوریتم حل در حالت‌های خاص

در صورتی که صفحه‌ی بازی یک مستطیل با ابعاد طول و عرض زوج باشد، مثلاً ۴ در ۶ دارای یک مرکز تقارن خواهد بود. شکل زیر را ببینید.

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

بازی زیر را به عنوان نمونه ببینید.

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

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

بازی زیر را در نظر بگیرید.

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

در صورت تمایل با دیگر علاقه‌مندان به این بازی در وب‌سایت شهر ریاضی، گروه بازی‌های ترکیبیاتی دیدار کنید

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

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

بازی کاشی‌کاری-۲

برد تقارنی بازی

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

بازی کاشی‌کاری-۱

شرح بازی

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

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

الگوریتم برد

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

بازی نیم، مقدمه

شرح بازی

بازی نیم معروف‌ترین بازی منصفانه است که توسط چالرز ال. بوتون این نام به آن داده شده است. بوتون در سال ۱۹۰۱ الگوریتم این بازی را ارائه داد که منجر به شکل‌گیری نظریه‌ی بازی‌های ترکیبیاتی شد

این بازی یک بازی منصفانه است. بنابراین طبق قوانین بازی‌های منصفانه، دونفره خواهد بود و به نوبت بازی خواهد شد.

بازی کاهشی

شرح بازی

شکل کلی بازی کاهشی به این صورت است:

فرض کنید دسته‌هایی با تعداد دلخواه مهره داریم. یک مجموعه‌ی انتخاب وجود دارد که مشخص می‌کند در هر حرکت چند مهره می‌توان از یک و فقط یکی از دسته‌ها برداشت. این مجموعه را با S={s_1, ..., s_n} نشان می‌دهیم.