نظریهی بازیها به دستهای از مسائل ترکیبیاتی اشاره میکند که در آنها شاهد رقابت بین تعدادی بازیکن (دو و یا بیشتر) برای برتری در آن رقابت هستیم.
برعکس دیگر مسائل ترکیبیاتی، در یک بازی شاهد مفهومی به نام رقابت هستیم. در واقع هر بازیکن تلاش میکند با رعایت قوانین بازی به حالتی برسد که پیروز بازی باشد. معمولا بازیهای مورد بررسی بصورت نوبتی اجرا میشوند، یعنی در هر مرحله یک بازیکن اجازه حرکت دارد و پس از آن نوبت به بازیکن بعدی میرسد (همانند بازی شطرنج).
تمامی بازیها در چند مورد با یکدیگر مشترک هستند:
هدف از بررسی بازیها یافتن برندهی بازی از یک حالت اولیه مشخص و همچنین نحوهی پیروزی برنده است (یعنی برنده با چه حرکاتی میتواند پیروز شود) که اصطلاحا به آن استراتژی برد میگویند.
بازیها را به دو دسته تقسیمبندی میکنند:
بازیهای منصفانه به بازیهایی گفته میشود که حرکتهای قابل قبول در آن وضعیت تنها وابسته به وضعیت کنونی بستگی داشته باشد و نه براساس نوبت بازیکنان. به عنوان مثال «نیم» یک بازی منصفانه است. در بازیهای منصفانه مستقل از نوبت بازیکنان و تنها براساس وضعیت موجود میتوان استراتژی برد را تعیین کرد. به بیانی دیگر، اگر وضعیت بازی را ثابت نگهداریم و نوبت بازیکنان را عوض کنیم تحلیل بازی تغییری نمیکند.
بازیهایی را که منصفانه نباشند، اصطلاحا بازیهای غیرمنصفانه و یا بازیهای پارتیزانی میگویند. طبق تعریف، در این بازیها استراتژی برد براساس وضعیت موجود و همچنین نوبت بازیکنان تعیین میشود. به عنوان مثال شطرنج و یا اتللو بازیهایی پارتیزانی هستند. بررسی بازیهای پارتیزانی نیز تا حدودی مشابه بازیهای منصفانه است ولی با توجه به اینکه پارامترهای بیشتری در وضعیت بازی تاثیرگذارند، پیچیدگی بیشتری خواهند داشت.
قبل از حل چند مساله لازم است با مدل کردن بازی با گراف و حالات برد و باخت آشنا شوید.