جستجوی 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 هم بهترین حرکت و هم بهترین امتیاز را برای گره ریشه حفظ کرده و برمی گرداند. فقط بهترین امتیاز گره در گره های غیر ریشه ضروری است. و بهترین حرکت یک گره برای گره های غیر ریشه ای برای حفظ یا بازگشت ضروری نیست.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین الگوریتم بر این واقعیت تکیه دارد که 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 هم بهترین حرکت و هم بهترین امتیاز را برای گره ریشه حفظ کرده و برمی گرداند. فقط بهترین امتیاز گره در گره های غیر ریشه ضروری است. و بهترین حرکت یک گره برای گره های غیر ریشه ای برای حفظ یا بازگشت ضروری نیست.
wiki: نگامکس