نگامکس

جستجوی Negamax حالتی از جستجوی مینیمکس است که بر ویژگی مجموع صفر یک بازی دو نفره متکی است.

این الگوریتم بر این واقعیت تکیه دارد که $\max(a,b)=-\min(-a,-b)$ باشد، که بتوان الگوریتم مینیمکس را به راحتی پیاده‌سازی کرد. به‌طور دقیق تر، ارزش موقعیت برای بازیکن A در یک بازی، برابر با منفی آن مقدار برای بازیکن B است؛ بنابراین، بازیکن در حال حرکت به دنبال حرکتی است که نفی ارزش حاصل از حرکت را به حداکثر برساند: این موقعیت جانشین بنا به تعریف باید توسط حریف ارزش گذاری شده باشد. استدلال جمله قبلی صرف نظر از اینکه A یا B در حال حرکت باشد قابل قبول است. این بدان معنی است که می‌توان از یک رویه واحد برای ارزش گذاری هر دو موقعیت استفاده کرد. این یک ساده‌سازی کدشده نسبت به minimax است، که مستلزم آن است که A حرکت را با حداکثر ارزش انتخاب کند در حالی که B حرکت با کم‌ترین مقدار را انتخاب کند.

نباید آن را با negascout اشتباه گرفت. negascout الگوریتمی برای محاسبه سریع مقدار minimax یا negamax می‌باشد که استفاده هوشمندانه ای از هرس آلفا-بتا می‌کند و در دهه ۱۹۸۰ کشف شد. توجه داشته باشید که هرس آلفا-بتا خود راهی برای محاسبه سریع مقدار یک موقعیت مینیمکس یا نگامکس با اجتناب از جستجوی موقعیت‌های خاص غیر جالب است.

اکثر موتورهای جستجوی متخاصم با استفاده از نوعی جستجوی negamax کدگذاری می‌شوند.

الگوریتم پایه نگامکس

NegaMax روی همان درخت‌های بازی که با الگوریتم جستجوی minimax استفاده می‌شوند، عمل می‌کند. هر گره و گره ریشه در درخت حالت‌های بازی (مانند پیکربندی صفحه بازی) یک بازی دو نفره هستند. انتقال به گره‌های فرزند نشان دهنده حرکت‌های موجود برای بازیکنی است که می‌خواهد از یک گره معین بازی کند.

هدف جستجوی negamax یافتن مقدار امتیاز گره برای بازیکنی است که در گره اصلی بازی می‌کند. شبه کد زیر الگوریتم پایه negamax را نشان می‌دهد،^[۱] با یک محدودیت قابل تنظیم برای حداکثر عمق جستجو:

function negamax(node, depth, color) is
 if depth = 0 or node is a terminal node then
 return color × the heuristic value of node
 value := −∞
 for each child of node do
 value := max(value, −negamax(child, depth − 1, −color))
 return value

(* Initial call for Player A's root node *)
negamax(rootNode, depth, 1)

(* Initial call for Player B's root node *)
negamax(rootNode, depth, −1)

گره ریشه امتیاز خود را از یکی از گره‌های فرزند اولیه خود به ارث می‌برد. گره فرزند که در نهایت بهترین امتیاز گره ریشه را تعیین می‌کند نیز بهترین حرکت را برای بازی نشان می‌دهد. اگرچه تابع negamax نشان داده شده تنها بهترین امتیاز گره را برمی‌گرداند، پیاده‌سازی‌های عملی negamax هم بهترین حرکت و هم بهترین امتیاز را برای گره ریشه حفظ کرده و برمی‌گرداند. فقط بهترین امتیاز گره در گره‌های غیر ریشه ضروری است. و بهترین حرکت یک گره برای گره‌های غیر ریشه‌ای برای حفظ یا بازگشت ضروری نیست.

چیزی که می‌تواند گیج کننده باشد این است که چگونه مقدار heuristic گره فعلی محاسبه می‌شود. در این پیاده‌سازی همیشه این مقدار از دید بازیکن A که مقدار رنگ آن یک است محاسبه می‌شود. به عبارت دیگر، مقادیر اکتشافی بالاتر همیشه موقعیت‌های مطلوب‌تری را برای بازیکن A نشان می‌دهد. ارزش heuristic لزوماً با مقدار بازگشتی یک گره به دلیل نفی مقدار توسط negamax و پارامتر رنگ یکسان نیست. مقدار بازگشتی گره negamax یک امتیاز heuristic از دیدگاه بازیکن فعلی گره است.

نگامکس امتیازات را برای گره‌هایی که بازیکن A در شرف بازی است و جایی که بازیکن A بازیکن حداکثر کننده در معادل مینیمکس است، مطابقت می‌دهد. Negamax همیشه حداکثر مقدار را برای تمام گره‌های خود جستجو می‌کند؛ بنابراین برای گره‌های بازیکن B، امتیاز مینیمکس منفی امتیاز نگامکس آن است. بازیکن B بازیکن مینیمم کردن در معادل مینیمکس است.

تغییرات در اجرای negamax ممکن است پارامتر رنگ را حذف کند. در این حالت، تابع ارزیابی heuristic باید مقادیر را از نقطه نظر بازیکن فعلی گره برگرداند.

نگامکس با هرس آلفا بتا

بهینه‌سازی الگوریتم برای مینیمکس نیز به همان اندازه برای Negamax قابل استفاده است. هرس آلفا-بتا می‌تواند تعداد گره‌هایی را که الگوریتم نگامکس در درخت جستجو ارزیابی می‌کند به روشی مشابه با استفاده از الگوریتم مینیمکس کاهش دهد.

شبه کد جستجوی نگامکس با عمق محدود با هرس آلفا بتا به شرح زیر است:^[۱]

function negamax(node, depth, α, β, color) is
 if depth = 0 or node is a terminal node then
 return color × the heuristic value of node

 childNodes := generateMoves(node)
 childNodes := orderMoves(childNodes)
 value := −∞
 foreach child in childNodes do
 value := max(value, −negamax(child, depth − 1, −β, −α, −color))
 α := max(α, value)
 if α ≥ β then
 break (* cut-off *)
 return value

(* Initial call for Player A's root node *)
negamax(rootNode, depth, −∞, +∞, 1)

آلفا (α) و بتا (β) نشان دهنده مرزهای پایین و بالایی برای مقادیر گره فرزند در یک عمق معین درخت است. Negamax آرگومان‌های α و β را برای گره ریشه روی کمترین و بالاترین مقدار ممکن قرار می‌دهد. سایر الگوریتم‌های جستجو، مانند negascout و MTD(f)، ممکن است α و β را با مقادیر متناوب مقداردهی اولیه کنند تا عملکرد جستجوی درخت را بهبود بیشتری بخشند.

هنگامی که negamax با مقدار گره فرزند خارج از محدوده آلفا/بتا مواجه می‌شود، جستجوی negamax به این ترتیب بخش‌هایی از درخت بازی را از کاوش قطع می‌کند. برش‌ها بر اساس مقدار بازگشتی گره ضمنی هستند. یک مقدار گره که در محدوده α و β اولیه آن یافت می‌شود، مقدار دقیق (یا واقعی) گره است. این مقدار با نتیجه ای که الگوریتم پایه negamax برمی‌گرداند یکسان است، بدون برش و بدون هیچ کران α و β. اگر مقدار بازگشتی یک گره خارج از محدوده باشد، آن‌گاه مقدار نشان‌دهنده یک کران بالاتر (اگر مقدار ≤ α) یا پایین‌تر (اگر مقدار ≥ β) برای مقدار دقیق گره است. هرس آلفا-بتا در نهایت هر گونه نتایج محدود به ارزش را کنار می‌گذارد. چنین مقادیری بر مقدار negamax در گره ریشه آن کمک نمی‌کند و تأثیری نمی‌گذارد.

این کد نوعی fail-soft از هرس آلفا-بتا را نشان می‌دهد. Fail-soft هرگز α یا β را مستقیماً به عنوان مقدار گره برنمی‌گرداند؛ بنابراین، یک مقدار گره ممکن است خارج از محدوده اولیه α و β باشد که با فراخوانی تابع negamax تنظیم شده‌است. در مقابل، نوع fail-hard هرس آلفا-بتا همیشه مقدار گره را در محدوده α و β محدود می‌کند.

این پیاده‌سازی همچنین ترتیب حرکت اختیاری را قبل از حلقه foreach نشان می‌دهد که گره‌های فرزند را ارزیابی می‌کند. ترتیب حرکت^[۲] یک بهینه‌سازی برای هرس آلفا بتا است که سعی می‌کند محتمل‌ترین گره‌های فرزند را که امتیاز گره را به دست می‌آورند حدس بزند. الگوریتم ابتدا آن گره‌های فرزند را جستجو می‌کند. نتیجه حدس‌های خوب زودتر است و قطع‌های آلفا/بتا بیشتر اتفاق می‌افتد، در نتیجه شاخه‌های درخت بازی اضافی و گره‌های فرزند باقی‌مانده از درخت جستجو هرس می‌شوند.

Negamax با جداول هرس و جابجایی آلفا بتا

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

هنگامی که negamax درخت بازی را جستجو می‌کند و چندین بار با همان گره مواجه می‌شود، یک جدول جابجایی می‌تواند مقدار محاسبه‌شده قبلی گره را برگرداند، و از محاسبه مجدد بالقوه طولانی و تکراری مقدار گره صرفنظر کند. عملکرد Negamax به ویژه برای درخت‌های بازی با مسیرهای زیادی که به یک گره مشترک منتهی می‌شوند، بهبود می‌یابد.

شبه کد که توابع جدول جابجایی را با هرس آلفا/بتا به negamax اضافه می‌کند به شرح زیر است:^[۱]

function negamax(node, depth, α, β, color) is
 alphaOrig := α

 (* Transposition Table Lookup; node is the lookup key for ttEntry *)
 ttEntry := transpositionTableLookup(node)
 if ttEntry is valid and ttEntry.depth ≥ depth then
 if ttEntry.flag = EXACT then
 return ttEntry.value
 else if ttEntry.flag = LOWERBOUND then
 α := max(α, ttEntry.value)
 else if ttEntry.flag = UPPERBOUND then
 β := min(β, ttEntry.value)

 if α ≥ β then
 return ttEntry.value

 if depth = 0 or node is a terminal node then
 return color × the heuristic value of node

 childNodes := generateMoves(node)
 childNodes := orderMoves(childNodes)
 value := −∞
 for each child in childNodes do
 value := max(value, −negamax(child, depth − 1, −β, −α, −color))
 α := max(α, value)
 if α ≥ β then
 break

 (* Transposition Table Store; node is the lookup key for ttEntry *)
 ttEntry.value := value
 if value ≤ alphaOrig then
 ttEntry.flag := UPPERBOUND
 else if value ≥ β then
 ttEntry.flag := LOWERBOUND
 else
 ttEntry.flag := EXACT
 ttEntry.depth := depth
 transpositionTableStore(node, ttEntry)

 return value

(* Initial call for Player A's root node *)
negamax(rootNode, depth, −∞, +∞, 1)

هرس آلفا/بتا و محدودیت‌های حداکثر عمق جستجو در negamax می‌تواند منجر به ارزیابی جزئی، نادقیق و کاملاً نادیده گرفته شده گره‌ها در درخت بازی شود. این اضافه کردن بهینه‌سازی‌های جدول انتقال negamax را پیچیده می‌کند. ردیابی فقط مقدار گره در جدول کافی نیست، زیرا مقدار ممکن است مقدار واقعی گره نباشد؛ بنابراین کد باید رابطه مقدار با پارامترهای آلفا/بتا و عمق جستجو را برای هر ورودی جدول انتقال حفظ و بازیابی کند.

جداول جابجایی معمولاً دارای تلفات هستند و مقادیر قبلی گره‌های درخت بازی خاص را در جداول خود حذف یا بازنویسی می‌کنند. این امر ضروری است زیرا تعداد بازدیدهای گره‌های negamax اغلب بسیار بیشتر از اندازه جدول انتقال است. ورودی‌های جدول گم شده یا حذف شده غیر مهم هستند و بر نتیجه negamax تأثیر نمی‌گذارند. با این حال، ورودی‌های از دست رفته ممکن است نیاز به negamax داشته باشند تا مقادیر گره درخت بازی خاص را بیشتر محاسبه کند، بنابراین بر عملکرد تأثیر می‌گذارد.

منابع

George T. Heineman; Gary Pollice & Stanley Selkow (2008). "Chapter 7:Path Finding in AI". Algorithms in a Nutshell. Oreilly Media. pp. 213–217. ISBN 978-0-596-51624-6.
John P. Fishburn (1984). "Appendix A: Some Optimizations of α-β Search". Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis). UMI Research Press. pp. 107–111. ISBN 0-8357-1527-2.

↑ ^۱٫۰ ^۱٫۱ ^۱٫۲ Breuker, Dennis M. Memory versus Search in Games, Maastricht University, October 16, 1998
↑ Schaeffer, Jonathan The History Heuristic and Alpha-Beta Search Enhancements in Practice, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989

پیوند به بیرون

[Breuker-1] ۱٫۰ ^۱٫۱ ^۱٫۲ Breuker, Dennis M. Memory versus Search in Games, Maastricht University, October 16, 1998

[Schaeffer-2] Schaeffer, Jonathan The History Heuristic and Alpha-Beta Search Enhancements in Practice, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989

[۱]

[۲]