جستجوی خصمانه

خطای اسکریپتی: پودمان «AfC submission catcheck» وجود ندارد.

جستجوی خصمانه (بازی‌ها)(Adversarial Search)^[۱]

هر بازی یک محیط چند عاملی است که در آن هر عامل برای تصمیم گیری باید سایر عامل ها و چگونگی تاثیر آنها را در نظر بگیرد . عدم امکان پیش بینی عامل‌ های دیگر باعث عدم قطعیت در فرآیند حل مسئله می شود. محیط های چند عاملی می تواند دو حالت داشته باشد:

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

محیط های همکار: در این محیط ها، عامل ها اهداف مشترک دارند و عمل هر عامل باعث افزایش کارایی همه عامل‌ها می شود.

*توجه* محیط بعضی عامل ها هم رقابتی و هم همکار هستند در این صورت بخشی از مسئله شامل جستجوی خصمانه می شود.

در انتهای بازی به هر یک از بازیکنان یک مقدار سودمندی یا امتیاز داده می‌شود مثلاً 1+ به برنده و 1- به بازنده و در حالت تساوی به هر دو 0 داده میشود.

مثلاً در بازی تخته نرد امتیاز ها می تواند 192+ تا 192- باشد.

به بازی که در پایان، مجموع امتیاز های دو بازیکن صفر شود بازی با مجموعه 0 یا بازی با اطلاعات کامل گفته می شود.

در اینجا فرض می‌کنیم محیط بازی قطعی و کاملا مشاهده پذیر است و بازیکن‌ها به نوبت عمل می کند و مجموع امتیازها نیز 0 میشود.

حرکت‌ها و توابع[ویرایش]

برای یک بازی دو نفره بین کامپیوتر و کاربر اسامی PC و ME را در نظر می گیریم . با توجه به شرایط مطرح شده قبلی تعاریف زیر را در نظر بگیرید.

نیم حرکت: به هر عمل یا حرکتی که یکی از دو بازیکن انجام دهد نیم حرکت گفته می شود.
حالت پایانه: حالتی است که در آن بازی تمام میشود. (terminal sate)
تابع آزمون پایه: تابعی است که تعیین میکند آیا حالت فعلی یک حالت پایان است یا نه; علت این است که برای بازی از آزمون هدف استفاده نمی کنیم این است که در یک بازی، عامل لزوماً به هدفش(برنده شدن) نمیرسد.

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

سودمندی[ویرایش]

در بازی با مجموع صفر کافی است میزان سودمندی یک عامل را مسابقه محاسبه کنیم به عنوان مثال اگر میزان سودمندی PC را محاسبه کنیم میزان سودمندی ME قابل محاسبه می باشد.

در اینجا میزان سودمندی PC را محاسبه می‌کنیم بنابراین هرچه میزان سودمندی بیشتر باشد به نفع عامل کامپیوتر و هر چه کمتر باشد به نفع عامل کاربر می باشد.

بدون کم شدن از کلیت مسئله فرض می‌کنیم الان نوبت PC است و باید تعیین کنیم عامل PC چه عملی را انجام می دهد تا بیشترین سودمندی را داشته باشد(تصمیم‌گیری بهینه).

برای مثال در برگ‌های این درخت جستجو در آنجایی که هیچ یک از دو کاربر برنده نشده‌اند امتیاز صفر در نظر می‌گیریم

الگوریتم های تصمیم گیری بهینه از یک درخت بازی برای بهترین عمل استفاده می کنند.

ریشه درخت بازی(سطح صفر): حالت یا وضعیت فعلی بازی(هیچ کدام از خانه های جدول دوز پر نشده است)
گره های سطح یک: وضعیت هایی که با انجام هر عمل ممکن توسط PC در وضعیت والد ممکن است تولید شود.
گره های سطح دو: وضعیت های که با انجام هر عمل توسط ME در وضعیت والد ممکن است تولید شود.
گره های سطح سه: مانند گره سطح یک
گره های سطح چهار: مانند گره های سطح دو
.
.
.

↑ خطای لوآ در پودمان:Citation/CS1/en/Identifiers در خط 47: attempt to index field 'wikibase' (a nil value).

This article "جستجوی خصمانه" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:جستجوی خصمانه. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.