Algorithms for computing strategies in two-player simultaneous move games

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