موضوع مقاله: نگامکس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نگامکس | مقدمه: جستجوی Negamax حالتی از جستجوی مینیمکس است که بر ویژگی مجموع صفر یک بازی دو نفره متکی است. | ## بخش 1: نگامکس | این الگوریتم بر این واقعیت تکیه دارد که باشد، که بتوان الگوریتم مینیمکس را به راحتی پیاده‌سازی کرد. به‌طور دقیق تر، ارزش موقعیت برای بازیکن A در یک بازی، برابر با منفی آن مقدار برای بازیکن B است؛ بنابراین، بازیکن در حال حرکت به دنبال حرکتی است که نفی ارزش حاصل از حرکت را به حداکثر برساند: این موقعیت جانشین بنا به تعریف باید توسط حریف ارزش گذاری شده باشد. این بدان معنی است که می‌توان از یک رویه واحد برای ارزش گذاری هر دو موقعیت استفاده کرد. این یک ساده‌سازی کدشده نسبت به minimax است، که مستلزم آن است که A حرکت را با حداکثر ارزش انتخاب کند در حالی که B حرکت با کم‌ترین مقدار را انتخاب کند. توجه داشته باشید که هرس آلفا-بتا خود راهی برای محاسبه سریع مقدار یک موقعیت مینیمکس یا نگامکس با اجتناب از جستجوی موقعیت‌های خاص غیر جالب است. شخصی که جستجوی درخت بازی را انجام می‌دهد، کسی است که باید در وضعیت فعلی بازی اول حرکت کند (بازیکن در این مورد) NegaMax روی همان درخت‌های بازی که با الگوریتم جستجوی minimax استفاده می‌شوند، عمل می‌کند. هر گره و گره ریشه در درخت حالت‌های بازی (مانند پیکربندی صفحه بازی) یک بازی دو نفره هستند. انتقال به گره‌های فرزند نشان دهنده حرکت‌های موجود برای بازیکنی است که می‌خواهد از یک گره معین بازی کند. گره فرزند که در نهایت بهترین امتیاز گره ریشه را تعیین می‌کند نیز بهترین حرکت را برای بازی نشان می‌دهد. در این پیاده‌سازی همیشه این مقدار از دید بازیکن A که مقدار رنگ آن یک است محاسبه می‌شود. | ## بخش 2: نگامکس | به عبارت دیگر، مقادیر اکتشافی بالاتر همیشه موقعیت‌های مطلوب‌تری را برای بازیکن A نشان می‌دهد. نگامکس امتیازات را برای گره‌هایی که بازیکن A در شرف بازی است و جایی که بازیکن A بازیکن حداکثر کننده در معادل مینیمکس است، مطابقت می‌دهد. Negamax همیشه حداکثر مقدار را برای تمام گره‌های خود جستجو می‌کند؛ بنابراین برای گره‌های بازیکن B، امتیاز مینیمکس منفی امتیاز نگامکس آن است. شخصی که جستجوی درخت بازی را انجام می‌دهد، کسی است که باید از وضعیت فعلی بازی اول حرکت کند (بازیکن در این مورد) بهینه‌سازی الگوریتم برای مینیمکس نیز به همان اندازه برای Negamax قابل استفاده است. هرس آلفا-بتا می‌تواند تعداد گره‌هایی را که الگوریتم نگامکس در درخت جستجو ارزیابی می‌کند به روشی مشابه با استفاده از الگوریتم مینیمکس کاهش دهد. Negamax آرگومان‌های α و β را برای گره ریشه روی کمترین و بالاترین مقدار ممکن قرار می‌دهد. یک مقدار گره که در محدوده α و β اولیه آن یافت می‌شود، مقدار دقیق (یا واقعی) گره است. این مقدار با نتیجه ای که الگوریتم پایه negamax برمی‌گرداند یکسان است، بدون برش و بدون هیچ کران α و β. اگر مقدار بازگشتی یک گره خارج از محدوده باشد، آن‌گاه مقدار نشان‌دهنده یک کران بالاتر (اگر مقدار ≤ α) یا پایین‌تر (اگر مقدار ≥ β) برای مقدار دقیق گره است. این پیاده‌سازی همچنین ترتیب حرکت اختیاری را قبل از حلقه foreach نشان می‌دهد که گره‌های فرزند را ارزیابی می‌کند. | ## بخش 3: نگامکس | نتیجه حدس‌های خوب زودتر است و قطع‌های آلفا/بتا بیشتر اتفاق می‌افتد، در نتیجه شاخه‌های درخت بازی اضافی و گره‌های فرزند باقی‌مانده از درخت جستجو هرس می‌شوند. Negamax با جداول هرس و جابجایی آلفا بتا جداول جابجایی به‌طور انتخابی مقادیر گره‌ها را در درخت بازی حفظ می‌کنند. جابجایی یک مرجع اصطلاحی است که به یک موقعیت معین تخته بازی می‌توان به بیش از یک روش با توالی حرکت بازی‌های مختلف رسید. هنگامی که negamax درخت بازی را جستجو می‌کند و چندین بار با همان گره مواجه می‌شود، یک جدول جابجایی می‌تواند مقدار محاسبه‌شده قبلی گره را برگرداند، و از محاسبه مجدد بالقوه طولانی و تکراری مقدار گره صرفنظر کند. عملکرد Negamax به ویژه برای درخت‌های بازی با مسیرهای زیادی که به یک گره مشترک منتهی می‌شوند، بهبود می‌یابد. ردیابی فقط مقدار گره در جدول کافی نیست، زیرا مقدار ممکن است مقدار واقعی گره نباشد؛ بنابراین کد باید رابطه مقدار با پارامترهای آلفا/بتا و عمق جستجو را برای هر ورودی جدول انتقال حفظ و بازیابی کند. جداول جابجایی معمولاً دارای تلفات هستند و مقادیر قبلی گره‌های درخت بازی خاص را در جداول خود حذف یا بازنویسی می‌کنند. این امر ضروری است زیرا تعداد بازدیدهای گره‌های negamax اغلب بسیار بیشتر از اندازه جدول انتقال است. | ## جمع‌بندی | با این حال، ورودی‌های از دست رفته ممکن است نیاز به negamax داشته باشند تا مقادیر گره درخت بازی خاص را بیشتر محاسبه کند، بنابراین بر عملکرد تأثیر می‌گذارد.