بازی‌ها و گراف جهت‌دار¶

نتیجه¶

وضعیت راس ها، یعنی همان \(L\) یا \(W\) را، به ترتیب شماره راس ها مشخص می‌کنیم.

برای این کار، اگر راس \(u\) بین راس هایی که \(v\) به آن یال جهت دار دارد وجود داشت که وضعیتش برابر با \(L\) بود، آنگاه وضعیت راس \(v\) برابر با \(W\) می شود. و اگر همه راس هایی که \(v\) به آنها یال داشت، وضعیت شان \(W\) بود، آنگاه وضعیت راس \(v\) برابر با \(L\) می شود.

با این روش، می‌توان وضعیت همه راس ها را مشخص کرد. حال کافی است به حالت اولیه بازی نگاه کنیم و ببینیم \(L\) است یا \(W\). اگر \(L\) بود، یعنی نفر اول بازنده بازی است. و اگر وضعیت \(W\) بود، یعنی نفر اول برنده است. با این کار، می‌توان فهمید در بازی‌ای که بالا تر مشخص کردیم، علی برنده بازی است یا متین!

تعمیم¶

اگر به ماهیت اکثر بازی ها توجه کنید درون آن ها چنین گرافی خواهید دید! در واقع ذات بازی های ترکیبیاتی به این صورت است که دو نفر یا بیشتر روی منابعی مشترک تغییراتی اعمال می کنند (منابع مشترک می تواند صفحه شطرنج باشد که مهره ها را روی آن حرکت می دهیم یا می تواند یک کیسه باشد که از آن سنگ بر می داریم).

حالا فرض کنید به ازای هر وضعیت از منابع مشترک و اینکه نوبت چه کسی است یک راس بسازیم و راس \(A\) را به \(B\) یال جهت دار بزنیم اگر و تنها اگر فردی که در وضعیت \(A\) نوبتش است بتواند در نوبتش به \(B\) برود. حالا یک گراف داریم! ما توانستیم بازی خود را روی یک گراف تعریف کنیم.

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

حل بازی روی گراف¶

اگر بتوانیم بازی حرکت مهره روی گراف را حل کنیم گام بزرگی در فهم روش حل اکثر بازی ها برداشته ایم. برای حل این بازی به این صورت عمل می کنیم. به هر راس یک برچسب برد (W)، باخت(L) یا تساوی(D) نسبت می دهیم. به سه نکته زیر توجه کنید.

• راسی که یال خروجی نداشته باشد حتما L است.
• راسی که مجاور L داشته باشد حتما W است.
• اگر بازیکنی استراتژی نباختن داشته باشد امکان ندارد که مهره را به یک راس با برچسب W ببرد (زیرا در اینصورت حریفش می تواند ببرد).

پس این الگوریتم را روی گرافمان پیاده می کنیم. تا زمانی که راسی مثل \(u\) بود که یال خروجی نداشت روی آن برچسب \(L\) می زنیم سپس روی تمام راس هایی مثل \(v\) که \(v\) به \(u\) یال دارد برچسب W می زنیم. سپس تمام راس هایی که روی آنها برچسب زدیم را از گراف حذف می کنیم. چرا؟ چون مطمئنیم که اگر بازیکن بخواهد مهره را به \(v\) برساند باید قبل از آن به راسی که روی آن W نوشته شده برسد و هیچکدام از بازیکنان دوست ندارند که مهره را روی راس های W ببرند.

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

چند نتیجه گیری سودمند¶

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

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