تسریع در تعیین نقاط تعادل نش بازی های چند بازیگره فرم استراتژیک با استفاده از پردازنده های گرافیکی چند هسته ای

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

Keywords:

نظریه بازی , بازی های فرم استراتژیک , تعادل نش , الگوریتم های موازی , پردازنده گرافیکی چند هسته ای