المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:بازی‌های منصفانه و غیرمنصفانه

نظریه‌ی بازی‌ها

نظریه‌ی بازی‌ها به دسته‌ای از مسائل ترکیبیاتی اشاره می‌کند که در آنها شاهد رقابت بین تعدادی بازیکن (دو و یا بیشتر) برای برتری در آن رقابت هستیم.

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

وجه اشتراک بازی‌ها

تمامی بازی‌ها در چند مورد با یکدیگر مشترک هستند:

  • قوانین بازی: هر بازی قوانینی دارد که مجموعه‌ی حرکات مورد قبول در هر مرحله را مشخص می‌کند (همانند قوانین حرکت در بازی شطرنج).
  • حالت برد و باخت: در هر بازی حالت برد (و یا باخت) مشخص است. در صورتی که یک بازیکن به حالت برد (باخت) برسد، برنده (بازنده) بازی است (مثلا در شطرنج اگر بازیکنی در وضعیت مات قرار بگیرد بازنده بازی است).
  • حالت اولیه: وضعیتی که ابتدای بازی را مشخص می‌کند و ترتیب نوبت بازیکنان را مشخص می‌کند را حالت اولیه می‌گویند (همانند ترتیب چینش اولیه مهره‌ها در بازی شطرنج).

استراتژی برد

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

انواع بازی‌ها

بازی‌ها را به دو دسته تقسیم‌بندی می‌کنند:

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

بازی‌های منصفانه به بازی‌هایی گفته می‌شود که حرکت‌های قابل قبول در آن وضعیت تنها وابسته به وضعیت کنونی بستگی داشته باشد و نه براساس نوبت بازیکنان. به عنوان مثال «نیم» یک بازی منصفانه است. در بازی‌های منصفانه مستقل از نوبت بازیکنان و تنها براساس وضعیت موجود می‌توان استراتژی برد را تعیین کرد. به بیانی دیگر، اگر وضعیت بازی را ثابت نگه‌داریم و نوبت بازیکنان را عوض کنیم تحلیل بازی تغییری نمی‌کند.

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

بازی‌هایی را که منصفانه نباشند، اصطلاحا بازی‌های غیرمنصفانه و یا بازی‌های پارتیزانی می‌گویند. طبق تعریف، در این بازی‌ها استراتژی برد براساس وضعیت موجود و همچنین نوبت بازیکنان تعیین می‌شود. به عنوان مثال شطرنج و یا اتللو بازی‌هایی پارتیزانی هستند. بررسی بازیهای پارتیزانی نیز تا حدودی مشابه بازی‌های منصفانه است ولی با توجه به اینکه پارامترهای بیشتری در وضعیت بازی تاثیرگذارند، پیچیدگی بیشتری خواهند داشت.

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


ابزار صفحه