بازی شاهزاده و هیولا

در نظریهٔ بازی‌ها، بازی شاهزاده و هیولا یک بازی تعقیب و گریز است که با دو بازیکن در یک ناحیه انجام می‌شود. این بازی توسط روفوس ایزاکس ابداع و در کتابش، "بازی‌های دیفرانسیل" (۱۹۶۵)، به صورتی که در ادامه می‌آید منتشر شد. "هیولا به دنبال شاهزاده می‌گردد، در اینجا زمانی که برای این کار لازم است را به عنوان نتیجه و سود در نظر می‌گیریم. هر دوی آن‌ها در یک اتاق کاملاً تاریک (و به هر شکل ممکنی) هستند، ولی هر دوی آن‌ها از محدودهٔ خود آگاه هستند. "گرفتن" به این معنی است که فاصلهٔ بین شاهزاده و هیولا در شعاع "گرفتن" قرار دارد، که در مقایسه با ابعاد اتاق، کوچک در نظر گرفته می‌شود. هیولا، که بسیار باهوش فرض شده‌است، با یک سرعت مشخص حرکت می‌کند. ما به شاهزاده آزادی کامل برای حرکت را می‌دهیم. این بازی، یک مسئلهٔ باز شناخته شده باقی ماند تا زمانی که توسط Shmuel Gal در اواخر دههٔ ۱۹۷۰ حل شد. استراتژی بهینهٔ او برای شاهزاده در نوع خود جالب است. او باید به یک مکان تصادفی در اتاق برود. در همانجا برای یک مدت زمان که نه زیاد کوتاه باشد و نه زیاد طولانی باقی بماند، سپس به یک مکان تصادفی (مستقل) دیگر برود و این روند را تکرار کند. استراتژی جستجوی بهینهٔ ارائه شدهٔ او بر اساس تقسیم اتاق به تعداد زیادی مستطیل‌های باریک، انتخاب تصادفی یک مستطیل و جستجوی آن با یک روش خاص است. پس از یک مدت زمان، یک مستطیل دیگر را باید به صورت تصادفی و مستقل انتخاب کند و کار این روال را ادامه دهد. جزئیات دقیق استراتژی‌های جستجو و گریز در منابع آورده شده‌اند. بازی شاهزاده و هیولا می‌تواند روی یک گراف از قبل انتخاب شده انجام شود (یک گراف سادهٔ ممکن، دایره‌است، که توسط ایزاکس به عنوان یک جاپا برای بازی در آن ناحیه پیشنهاد شد). می‌توان نشان داد که برای هر گراف متناهی، یک استراتژی جستجوی مختلط وجود دارد که به یک امتیاز و نتیجه و سود متناهی منجر می‌شود. این بازی تنها برای گرافی بسیار ساده که شامل یک دور (یک حلقه) حل شده‌است. ارزش بازی روی یک بازهٔ واحد زمانی (یک گراف با دو گره با یک پیوند بین آن‌ها) به صورت تقریبی تخمین زده شده‌است. این بازی ساده به نظر می‌رسد ولی کاملاً پیچیده‌است. به طور عجیبی، استراتژی جستجوی "بدیهی" که از یک انتها شروع می‌شود (به صورت تصادفی) و با حداکثر سرعت ممکن کل بازه را جاروب کند، بهینه نیست. این استراتژی، زمان مورد انتظار گرفتن را به اندازهٔ ۰٫۷۵ تضمین می‌کند. با این حال، با به کار بردن یک جستجوگر و پنهان کننده مختلط خبره تر، می‌توان زمان مورد انتظار گرفتن را به اندازهٔ ۸٫۶ درصد کاهش داد. در واقع، این عدد می‌تواند کاملاً به ارزش بازی نزدیک باشد اگر بتوان بهینگی استراتژی مرتبط شاهزاده را ثابت کرد.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Princess and Monster Game». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲ ژوئیهٔ ۲۰۱۲.