جستجوی خصمانه و بازیهای رایانهای
جستجوی خصمانه مطالعه تصمیمگیری در محیطهای رقابتی است، جایی که یک عامل باید در یک درخت بازی در برابر حریفی که سعی در دستیابی به نتیجهای متضاد دارد، حرکتهایی را انتخاب کند.
Definition
جستجوی خصمانه با کاوش در یک درخت بازی که در آن بازیکنان به نوبت حرکت میکنند، با استفاده از اصل مینیمکس (هر بازیکن با فرض اینکه حریف بهینه بازی میکند، بهینهسازی میکند) همراه با هرس و ارزیابی اکتشافی برای مقابله با درختان بزرگ، حرکتی را برای یک بازیکن محاسبه میکند.
Scope
این موضوع جستجو در بازیهای دو نفره، با مجموع صفر و اطلاعات کامل را پوشش میدهد: قاعده تصمیمگیری مینیمکس، هرس آلفا-بتا که به مینیمکس اجازه میدهد شاخههایی را که به طور اثباتشده بیربط هستند نادیده بگیرد، توابع ارزیابی و جستجوی با عمق محدود برای بازیهایی که برای حل دقیق بسیار بزرگ هستند، و جستجوی درختی مونت کارلو برای بازیهایی با فاکتورهای انشعاب بسیار بزرگ. این موضوع به چگونگی مدلسازی درختان بازی و چگونگی اجبار محدودیتهای محاسباتی به برشهای اکتشافی میپردازد. این موضوع تحلیل تعادل نظریه بازیها در مورد انگیزههای چندعاملی را پوشش نمیدهد که در سیستمهای چندعاملی مورد بررسی قرار میگیرد.
Core questions
- چگونه قاعده مینیمکس یک حرکت بهینه را در برابر یک حریف بهینه تعیین میکند؟
- چگونه هرس آلفا-بتا شاخهها را بدون تأثیر بر مقدار مینیمکس حذف میکند؟
- چگونه از توابع ارزیابی برای قطع جستجو در عمق ثابت در بازیهای بزرگ استفاده میشود؟
- چه زمانی جستجوی درختی مونت کارلو بر مینیمکس با عمق محدود ترجیح داده میشود؟
Key concepts
- درخت بازی
- مقدار مینیمکس
- هرس آلفا-بتا
- تابع ارزیابی (اکتشافی)
- جستجوی با عمق محدود و اثر افق
- بازیهای با مجموع صفر و اطلاعات کامل
- جستجوی درختی مونت کارلو
- ترتیب حرکت
Key theories
- قاعده تصمیمگیری مینیمکس
- در یک بازی دو نفره با مجموع صفر، هر بازیکن حرکتی را انتخاب میکند که حداقل نتیجه تضمین شده خود را به حداکثر برساند؛ انتشار این مقادیر حداکثر/حداقل در درخت بازی، حرکت بهینه را در ریشه به دست میدهد.
- هرس آلفا-بتا
- با ردیابی بهترین مقادیر از قبل تضمین شده برای بازیکنان حداکثرکننده و حداقلکننده، جستجوی آلفا-بتا ثابت میکند که زیردرختهای خاصی نمیتوانند بر تصمیم نهایی تأثیر بگذارند و آنها را نادیده میگیرد، و مقدار دقیق مینیمکس را بازمیگرداند در حالی که در بهترین حالت عمق قابل دستیابی را در یک زمان معین تقریباً دو برابر میکند.
- جستجوی درختی مونت کارلو
- هنگامی که فاکتورهای انشعاب برای نگاه به جلو جامع بسیار بزرگ هستند، جستجوی درختی مونت کارلو یک درخت نامتقارن را با هدایت رولاوتهای تصادفی و یک قاعده انتخاب که تعادل بین اکتشاف و بهرهبرداری را برقرار میکند، میسازد، روشی که بازی کامپیوتری را در بازیهایی مانند Go متحول کرد.
Clinical relevance
جستجوی خصمانه سیستمهای هوش مصنوعی برجستهای را تولید کرده است، از موتورهای شطرنج با استفاده از جستجوی آلفا-بتا تا برنامههای Go بر اساس جستجوی درختی مونت کارلو، و همین تکنیکها مذاکرات خودکار، بازیهای امنیتی و هر محیطی را که به عنوان رقابتی بین طرفهای بهینهساز مدلسازی میشود، شکل میدهند.
History
مقاله شانون در سال ۱۹۵۰ شطرنج کامپیوتری را به عنوان جستجوی مینیمکس با یک تابع ارزیابی تعریف کرد و قضیه مینیمکس فون نویمان مبنای نظریه بازیها را فراهم آورد. هرس آلفا-بتا در طول دهههای ۱۹۵۰-۱۹۶۰ توسعه یافت و توسط نات و مور (۱۹۷۵) به طور دقیق تحلیل شد. جستجوی درختی مونت کارلو، که در دهه ۲۰۰۰ رسمی شد، جهش بعدی را در قدرت بازیهای رایانهای، به ویژه در Go، به ارمغان آورد.
Key figures
- Claude E. Shannon
- John von Neumann
- Arthur Samuel
- Donald E. Knuth
- Ronald W. Moore
Related topics
Seminal works
- shannon1950
- knuth1975
- browne2012
Frequently asked questions
- آیا هرس آلفا-بتا حرکتی را که مینیمکس انتخاب میکند تغییر میدهد؟
- خیر. هرس آلفا-بتا دقیقاً همان مقدار و حرکت را مانند مینیمکس کامل بازمیگرداند؛ فقط از کاوش شاخههایی که به طور اثباتشده نمیتوانند بر نتیجه تأثیر بگذارند، جلوگیری میکند. مزیت آن سرعت است و با ترتیب حرکت خوب میتواند تقریباً دو برابر عمیقتر را در همان زمان جستجو کند.
- چرا در بازیهایی مانند Go از جستجوی درختی مونت کارلو به جای مینیمکس استفاده میشود؟
- Go دارای فاکتور انشعاب بسیار زیادی است و فاقد یک تابع ارزیابی ساده و دقیق است، بنابراین مینیمکس با عمق ثابت بیاثر است. جستجوی درختی مونت کارلو به جای آن کیفیت حرکت را از طریق بسیاری از بازیهای تصادفی تخمین میزند و درخت را به طور انتخابی به سمت خطوط امیدوارکننده رشد میدهد، که در چنین بازیهایی بسیار بهتر مقیاسپذیر است.