المپدیا

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

ابزار کاربر

ابزار سایت


آموزش:ترکیبیات:مدل کردن بازی‌ با گراف٬ حالات برد و باخت

مدل کردن بازی با گراف

برای حل مسائل مربوط به نظریه بازی‌ها ابتدا آن را با گراف مدل می‌کنند. پس از اینکار بررسی استراتژی‌های برد و باخت راحت‌تر قابل بررسی هستند.

گراف حالت

هر گراف با مجموعه‌ی راس‌ها و یال‌هایش مشخص می‌شود. گراف حالت برای بررسی نحوه جابجایی بین حالات مختلف یک بازی ساخته می‌شود. هر وضعیتی از بازی را با یک راس نمایش می‌دهیم. در نتیجه تعداد رئوس گراف حالت، برابر تعداد وضعیت‌های بازی است. یال‌های گراف حالت، جهت‌دار هستند. از حالت $َA$ به حالت $B$ یال جهت‌دار می‌کشیم اگر و تنها اگر بتوان از حالت $A$ با یک حرکت (طبق قوانین بازی) به حالت $B$ رسید.

مثال: 100 سکه در کیسه‌ای قرار دارند. دو نفر به نوبت در هر مرحله یک یا دو سکه از کیسه برمی‌دارند. کسی که آخرین سکه را بردارد برنده‌ی بازی است. چه کسی می‌تواند برنده‌ی بازی باشد؟ (نفر اول یا نفر دوم؟)

هر حالت در این بازی با توجه به تعداد سکه‌های درون کیسه تعیین می‌شود. به طور مثال اگر بدانیم هم‌اکنون 2 سکه در کیسه است می‌توان فهمید که هر کسی که نوبتش باشد برنده‌ی بازی است (2 سکه را برمی‌دارد و پیروز می‌شود). پس گراف حالت 101 راس دارد (از 0 تا 100 سکه). فرض کنید راس $A_i$ مربوط به حالتی است که $i$ سکه در کیسه باشد. در این صورت از راس $A_i$ تنها به راس‌های $A_{i-1}$ و $A_{i-2}$ (در صورت وجود) یال جهت‌دار وجود دارد، چون با برداشتن یک و دو سکه می‌توان به آن حالات رسید. با مشخص کردن رئوس و یال‌ها توانستیم گراف حالت این مثال را بسازیم.

حالت برد $(W)$ و حالت باخت $(L)$

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

اگر بتوانیم بفهمیم هر حالت، حالت برد است یا باخت، مسئله حل شده است. مثلا در مسئله‌ی سکه‌ها، حالت اولیه $A_{100}$ است و باید استراتژی برد برای این حالت را بدست آوریم.

تعیین حالات برد و باخت

فرض کنید در حالت $A$ هستیم. چگونه بفهمیم حالت $A$ برد است یا باخت؟

برای هر حالت (همانند $A$) دو امکان وجود دارد:

  1. بتواند با حرکتی به یک حالت باخت (مثلا $B$) برسد. در این صورت حالت $A$ برد است. چون با شروع از آن می‌تواند به حالت $B$ برود و برنده‌ی بازی شود.
  2. با هر حرکت، به یک حالت برد برسد. در این صورت حالت $A$ باخت است. چون با شروع از آن هر کاری کنیم به حالتی می‌رسیم که حالت برد رقیب (و باخت ما) است.

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

در نتیجه $A_1$ و $A_2$ حالت برد $(W)$ هستند. چون با یک حرکت می‌توانند به حالت باخت $A_0$ برسند. ولی $A_3$ حالت باخت است، چون $A_1$ و $A_2$ هر دو حالت برد هستند و هر حرکتی انجام دهیم می‌بازیم. با همین روش می‌توان استراتژی برد$A_{100}$ را بدست آورد. البته این روش زمان‌بر خواهد بود و اگر عدد 100 با $n$ عوض شود غیرقابل حل است.

حدس و اثبات ادعا

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

در این مثال، ادعا می‌کنیم اگر $i \equiv 0 \pmod 3$، $A_i$ حالت باخت است و بقیه‌ی حالات برد هستند. پس باید دو حکم را ثابت کنیم:

  • هر حالت برد می‌تواند به یک حالت باخت برسد. اگر در حالت $A_i$ باشیم و باقیمانده‌ی $i$ بر 3 برابر یک یا دو باشد می‌توان به ترتیب با برداشتن یک یا دو سکه به حالتی رسید که باقیمانده‌ی سکه‌ها بر 3 برابر صفر شود. پس این بخش اثبات شد.
  • هر حالت باخت تنها می‌تواند به حالت برد برسد. اگر در حالت $A_i$ باشیم و $i$ بر 3 بخش‌پذیر باشد با برداشتن یک یا دو سکه دیگر تعداد سکه‌ها بر 3 بخش‌پذیر نیست، پس در هر صورت به یک حالت برد می‌رسد و این بخش هم ثابت می‌شود.

بدین ترتیب ادعای ارائه شده اثبات شد. با این توضیحات می‌توان فهمید در حالت اولیه (100 سکه) نفر اول برنده‌ی بازی است (چون 100 بر 3 بخش‌پذیر نیست).

مسائل نمونه

  • سوال 10 مرحله اول دوره‌ی 22
  • سوال 3 مرحله اول دوره‌ی 19
  • سوال 18 مرحله اول دوره‌ی 16
  • سوال 20 مرحله اول دوره‌ی 16
  • سوال 2 مرحله اول دوره‌ی 14
  • سوال 8 مرحله اول دوره‌ی 14
  • سوال 11 مرحله اول دوره‌ی 14
  • سوال 29 مرحله اول دوره‌ی 14
  • سوال 33 مرحله اول دوره‌ی 14
  • سوال 15 مرحله اول دوره‌ی 11
  • سوال 20 مرحله اول دوره‌ی 11
  • سوال 29 مرحله اول دوره‌ی 11

ابزار صفحه