بازی‌ها و گراف جهت‌دار ======================= مقدمه --------------------------- در این قسمت، به بررسی ارتباط بازی ها و گراف های جهت دار می‌پردازیم. کار را با یک مثال ساده شروع می‌کنیم: علی و متین مشغول بازی هستند. یک کیسه سنگریزه شامل 10 سنگریزه جلوی آن‌ها قرار دارد. در هر مرحله، کسی که نوبش است، 1 یا 2 سنگریزه از کیسه بر می‌دارد. بازنده بازی کسی است که با کیسه خالی مواجه شود و نتواند سنگریزه بردارد. فرض کنید متین بازی را شروع می‌کند. اگر هر دو نفر به بهترین نحو بازی کنند، برنده بازی چه کسی خواهد بود؟ بررسی یک مثال --------------------------- در این بخش، مثالی که در بخش مقدمه مطرح کردیم را توضیح می‌دهیم. یک گراف 11 راسی می‌سازیم که شماره راس های آن، از 0 تا 10 هستند. از راس :math:`i` به راس :math:`j` یک یال جهت‌دار رسم می‌کنیم، اگر بتوان با برداشتن 1 یا 2 سنگریزه از :math:`i` به :math:`j` رسید. کنار هر راس یک حرف :math:`L(Lose)` یا :math:`W(Win)` می‌نویسیم(یا اینکه هیچی نمی‌نویسیم،‌ که یعنی وضعیت این راس، هنوز مشخص نشده). فرض کنید کنار راس با شماره :math:`i` حرف :math:`L` را نوشته‌ایم. معنای آن این است که اگر کیسه اولیه که دو نفر روی آن بازی می‌کنند، :math:`i` سنگریزه داشته باشد،‌ اگر هر دو نفر به بهترین شکل بازی کنند،‌ نفر اول بازنده آن بازی است. و برعکس،‌ فرض کنید کنار راس با شماره :math:`i` حرف :math:`W` را نوشته‌ایم. معنای آن این است که اگر کیسه اولیه که دو نفر روی آن بازی می‌کنند، :math:`i` سنگریزه داشته باشد،‌ اگر هر دو نفر به بهترین شکل بازی کنند،‌ نفر اول برنده آن بازی است. حال در ابتدای بازی، به کدام راس می‌توان :math:`L` یا :math:`W` را نسبت داد؟! با کمی فکر، متوجه می‌شیم راس با شماره 0. به این معنا که اگر کیسه اولیه، شامل 0 سنگریزه باشد، طبق قوانین بازی، نفر اول، بازنده است. چون نمی‌تواند سنگریزه ای بردارد. پس به راس 0، :math:`L` را نسبت می‌دهیم. حال راس بعدی که تکلیف آن مشخص می‌شود کدام است؟ راس 1 را در نظر بگیرید. اگر کیسه فقط 1 سنگریزه داشته باشد، نفر اول می‌تواند فقط یک سنگریزه بردارد. حال اگر دقت کنیم، میبینیم کیسه ای که بعد از حرکت نفر اول مانده است، شامل 0 سنگریزه است که قبلا تکلیف آن را مشخص کردیم. قبلا گفتیم که وضعیت راس 0، :math:`L` می‌باشد. پس وضعیت راس 1، برابر با :math:`W` می‌شود. چون اگر دقت کرده باشید، وقتی نفر اول، یک سنگریزه برداشت،‌ جای نفر اول و دوم بازی عوض شده(چون نوبت عوض شد). بنابراین راس 0، نشان دهنده باخت نفر دوم بازی(علی) است. **نتیجه** ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ وضعیت راس ها، یعنی همان :math:`L` یا :math:`W` را، به ترتیب شماره راس ها مشخص می‌کنیم. برای این کار، اگر راس :math:`u` بین راس هایی که :math:`v` به آن یال جهت دار دارد وجود داشت که وضعیتش برابر با :math:`L` بود، آنگاه وضعیت راس :math:`v` برابر با :math:`W` می شود. و اگر همه راس هایی که :math:`v` به آنها یال داشت، وضعیت شان :math:`W` بود، آنگاه وضعیت راس :math:`v` برابر با :math:`L` می شود. با این روش، می‌توان وضعیت همه راس ها را مشخص کرد. حال کافی است به حالت اولیه بازی نگاه کنیم و ببینیم :math:`L` است یا :math:`W`. اگر :math:`L` بود، یعنی نفر اول بازنده بازی است. و اگر وضعیت :math:`W` بود، یعنی نفر اول برنده است. با این کار، می‌توان فهمید در بازی‌ای که بالا تر مشخص کردیم، علی برنده بازی است یا متین! بازی حرکت مهره روی گراف --------------------------- بازی ما به این صورت است که یک گراف داریم و در ابتدا یک مهره روی راس شروع است. بازیکنان به نوبت حرکت می کنند و هر بازیکن در نوبتش مهره را روی یک راس مجاور می برد. کسی که نتواند حرکتی کند بازنده بازی است. تعمیم ~~~~~~~~~~~~~~~~ اگر به ماهیت اکثر بازی ها توجه کنید درون آن ها چنین گرافی خواهید دید! در واقع ذات بازی های ترکیبیاتی به این صورت است که دو نفر یا بیشتر روی منابعی مشترک تغییراتی اعمال می کنند (منابع مشترک می تواند صفحه شطرنج باشد که مهره ها را روی آن حرکت می دهیم یا می تواند یک کیسه باشد که از آن سنگ بر می داریم). حالا فرض کنید به ازای هر وضعیت از منابع مشترک و اینکه نوبت چه کسی است یک راس بسازیم و راس :math:`A` را به :math:`B` یال جهت دار بزنیم اگر و تنها اگر فردی که در وضعیت :math:`A` نوبتش است بتواند در نوبتش به :math:`B` برود. حالا یک گراف داریم! ما توانستیم بازی خود را روی یک گراف تعریف کنیم. پس به صورت شهودی قبول می کنیم که اکثر بازی ها می توانند به بازی حرکت مهره روی گراف (که در بالا گفتیم) تبدیل شود. برای مثال، بازی شطرنج را در نظر بگیرید. هر وضعیت از این بازی، یک صفحه شطرنج با چینش مختلف مهره‌ها است. حل بازی روی گراف ~~~~~~~~~~~~~~~~~~~~~ اگر بتوانیم بازی حرکت مهره روی گراف را حل کنیم گام بزرگی در فهم روش حل اکثر بازی ها برداشته ایم. برای حل این بازی به این صورت عمل می کنیم. به هر راس یک برچسب برد (W)، باخت(L) یا تساوی(D) نسبت می دهیم. به سه نکته زیر توجه کنید. - راسی که یال خروجی نداشته باشد حتما L است. - راسی که مجاور L داشته باشد حتما W است. - اگر بازیکنی استراتژی نباختن داشته باشد امکان ندارد که مهره را به یک راس با برچسب W ببرد (زیرا در اینصورت حریفش می تواند ببرد). پس این الگوریتم را روی گرافمان پیاده می کنیم. تا زمانی که راسی مثل :math:`u` بود که یال خروجی نداشت روی آن برچسب :math:`L` می زنیم سپس روی تمام راس هایی مثل :math:`v` که :math:`v` به :math:`u` یال دارد برچسب W می زنیم. سپس تمام راس هایی که روی آنها برچسب زدیم را از گراف حذف می کنیم. چرا؟ چون مطمئنیم که اگر بازیکن بخواهد مهره را به :math:`v` برساند باید قبل از آن به راسی که روی آن W نوشته شده برسد و هیچکدام از بازیکنان دوست ندارند که مهره را روی راس های W ببرند. در نهایت زمانی می رسد که هر راس از گراف باقی مانده حداقل یک خروجی دارد. از هر کدام از راس های گراف که شروع کنیم بازی هیچگاه تمام نخواهد شد و هر دو بازیکن می توانند بازی را تا ابد ادامه دهند! پس توانستیم راس ها را به سه دسته افراز کنیم و به ازای هر دسته می دانیم که اگر از راسی روی آنها شروع کنیم نتیجه بازی چه خواهد بود (برد، باخت یا تساوی). پس ما بازی حرکت مهره روی گراف را به صورت الگوریتمی حل کردیم. چند نتیجه گیری سودمند ~~~~~~~~~~~~~~~~~~~~~~~~~~ اگر راسی به خودش یال داشته باشد آنگاه قطعا این راس L نخواهد بود. زیرا طبق الگوریتم تنها زمانی به یک راس برچسب L می زنیم که یال خروجی نداشته باشد. به صورت دقیق تر کسی که در حال حاضر مهره اش روی این راس است می تواند به راحتی استراتژی نفر مقابل را بدزدد. یعنی اگر تشخیص دهد نفر دیگر می تواند ببرد به راحتی از یال طوقه استفاده می کند و این حرکت مثل این است که نوبت خودش و نفر بعد را عوض کرده است، بعد از این می تواند از استراتژی نفر دیگر استفاده کند. در مسائل این بخش مثال هایی از دزدیدن استراتژی آورده شده است. الگوریتمی که مطرح کردیم به شیوه دیگری برای گراف های بدون دور قابل بررسی است. این موضوع به خاطر ویژگی DAG ها یعنی داشتن ترتیب توپولوژیکی است. راس های گراف را به ترتیب توپولوژیکی می چینیم. حالا از آخر شروع می کنیم و یکی یکی راس ها را حذف می کنیم. اگر راسی که حذف می کنیم به یک L که جلو تر است یال داشته باشد روی آن W می نویسیم در غیر اینصورت L می نویسیم و در نهایت به تمام راس ها برد یا باخت نسبت داده می شود زیرا چنین بازی هایی همیشه پایان پذیر هستند. حرف آخر ------------ به نظر می آید تبدیل کردن بازی ها به گراف راه موثری برای حل کردن آن ها می باشد اما در حقیقت اینطور نیست. زیرا که در عمل خیلی از بازی ها بعد از تبدیل شدن به گراف تعداد راس های بسیار زیادی (یا حتی نامتناهی) خواهند داشت و از آنجایی که ما برای حل کردن بازی ها به اندازه تعداد راس ها و یال ها حافظه و زمان اجرا نیاز خواهیم داشت، حل کردن بسیاری از بازی ها به این شیوه امکان پذیر نیست.‌ (می توانید تخمین بزنید که بازی شطرنج بعد از تبدیل به گراف چند راس متفاوت خواهد داشت؟!). از طرف دیگر در خیلی از بازی ها تبدیل کردن به گراف می تواند شهود بهتری برای حل مسئله به ما بدهد و یا اینکه گراف ما بسیار خاص خواهد شد. پس نتیجه گیری این است که تبدیل کردن به گراف ابزار نسبتا قدرتمندی در حل و شهود پیدا کردن روی بازی ها می باشد اما همیشه پاسخگوی نیاز ما نخواهد بود.