پیچیدگی بازی

نظریه بازی‌های ترکیبیاتی راه‌های بسیاری برای اندازه‌گیری پیچیدگی بازی دارد، که بعضی از آن‌ها به شرح زیر هستند:

پیچیدگی فضای حالت

پیچیدگی فضای حالت یک بازی تعداد وضعیت‌های مجاز قابل دسترسی از وضعیت اولیهٔ بازی است.

هنگامی که محاسبهٔ این حالات دشوار باشد، اغلب با به حساب آوردن وضعیت‌های قانونی یا وضعیت‌هایی که هرگز در طی بازی ایجاد نمی‌شوند کران بالایی برای این مقدار قابل محاسبه است.

اندازهٔ درخت بازی

هر بازی از یک فضای مسئله، یک حالت اولیه و یک یا چند وضعیت هدف تشکیل می‌شود. فضای مسئله یک واسط ریاضی به شکل درخت است: ریشه وضعیت فعلی را نشان می‌دهد، رئوس وضعیت‌های بازی را نشان می‌دهند، یال‌ها نشانگر حرکات هستندو برگ‌ها حالات نهایی (برد یا باخت یا مساوی). اندازهٔ درخت بازی تعداد کل حالاتی که در یک بازی ممکن است به دست آیند: تعداد برگ‌های درخت بازی که ریشهٔ آن وضعیت اولیهٔ بازی است.

برای بعضی مسائل انتخاب فضای مسئله بدیهی نیست. طبق یک قانون کلی نمایش کوچک‌تر، که به معنای تعداد وضعیت‌های کمتری برای جستجو می‌باشد، اغلب بهتر از یک نمایش بزرگ‌تر است.

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

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

درخت تصمیم

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

پیچیدگی تصمیم

پیچیدگی تصمیم یک بازی تعداد برگ‌های کوچک‌ترین درخت تصمیم آن است که ارزش وضعیت اولیه را تثبیت می‌کند.

پیچیدگی درخت بازی

پیچیدگی درخت بازی یک بازی تعداد برگ‌های کوچک‌ترین درخت تصمیم تمام عرض است که ارزش وضعیت اولیه را تثبیت می‌کند. درخت تمام عرض درختیست که همهٔ گره‌ها در هر سطح را شامل می‌شود.

این برآوردیست از تعداد وضعیت‌هایی که برای ارزیابی در یک جستجوی مینی‌ماکس به منظور تعیین ارزش وضعیت اولیه نیاز است.

حتی تخمین پیچیدگی درخت بازی نیز سخت است، ولی برای بعضی بازی‌ها یک کران پایین منطقی با بالا بردن ضریب انشعاب میانگین بازی تا توانی از لایه‌ها در یک بازی متوسط می‌تواند به دست آید.

پیچیدگی محاسباتی

پیچیدگی محاسباتی یک بازی سختی مجانبی یک بازی را هنگامی که به‌طور دلخواه بزرگ می‌شود توضیح می‌دهد، که در نماد O بزرگ یا به عنوان عضویت در کلاس پیچیدگی بیان می‌شود. این مفهوم در بازی‌های به خصوصی اعمال نمی‌شود، بلکه در بازی‌هایی که عمومی شده‌اند اعمال می‌شوند بنابراین آن‌ها می‌توانند به‌طور دلخواه بزرگ شوند، که معمولاًً از طریق اجرای آن‌ها بر یک صفحهٔ n به n بزرگ می‌شوند. (از دیدگاه پیچیدگی محاسباتی یک بازی بر یک صفحه با اندازهٔ معین یک مسئلهٔ متناهی است که می‌تواند در ${\displaystyle O(1)}$

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

• راهبرد مینی‌ماکس عمق اول متناسب با پیچیدگی درخت بازی از زمان محاسبه استفاده می‌کند، زیرا باید تمام درخت و تعدادی چند جمله‌ای حافظه را در الگوریتم پیچیدگی درخت جستجو کند، چراکه الگوریتم باید همواره یک گره از درخت را در هر عمق حرکت ممکن ذخیره کند، و تعداد گره‌ها در بالاترین عمق حرکت دقیقاً پیچیدگی درخت است.
• القای عقب حافظه و زمان را متناسب با پیچیدگی فضای حالت استفاده می‌کند زیرا باید حرکت درست برای هر وضعیت ممکن را محاسبه و ذخیره کند.

به عنوان مثال، برای ایکس او، یک کران بالای ساده برای فضای حالت ۳ به توان ۹ یا ۱۹۶۸۳ است. (۹ خانه وجود دارد که برای هریک سه حالت داریم) این شمارش بسیاری وضعیت‌های غیرقانونی را شامل می‌شود، مانند وضعیتی با ۵ ایکس و بدون او، یا وضعیتی که هر یک از دو بازیکن یک ردیف سه تایی را پرکرده‌اند. یک شمارش دقیق تر، با حذف این وضعیت‌های غیرمجاز، عدد ۵۴۷۸ را به دست می‌دهد؛ و هرگاه دورانها و بازتابهای وضعیت‌ها یکسان در نظر گرفته شوند، تنها ۷۶۵ وضعیت اساساً متفاوت وجود دارد.

یک کران بالای ساده برای درخت بازی !۹ یا ۳۶۲۸۸۰ است. (۹ وضعیت برای اولین حرکت وجود دارد ۸ وضعیت برای دومین حرکت و به همین ترتیب…)این شامل بازی‌های غیرمجازی می‌شود که پس از برد یکی از طرفین ادامه می‌یابد. یک شمارش دقیق تر ۲۵۵۱۶۸ بازی را به دست می‌آورد. اگر دوران‌ها و بزتاب‌های وضعیت‌ها یکسان در نظر گرفته شوند، تنها ۲۶۸۳۰ بازی ممکن وجود دارد.

پیچیدگی محاسباتی ایکس او به چگونگی تعمیم آن بستگی دارد. یک تعمیم طبیعی تعمیم به m,n,k-game است: بازی در یک صفحهٔ m در n که برندهٔ بازی اولین کسی است که k خانه در یک ردیف بگیرد. بلافاصله روشن می‌شود که این بازی می‌تواند در (DSPACE(mn(پیچیدگی فضا) با جستجوی تمام درخت بازی حل شود. پس این بازی در کلاس پیچیدگی مهم PSPACE قرار می‌گیرد. با کمی کار بیشتر می‌توان نشان داد که PSPACE-complete است.

ویکی‌پدیای انگلیسی