نگااسکات

از ویکی‌پدیا، دانشنامهٔ آزاد.

نگا اسکات یا جستجوی شاخه اصلی یک الگوریتم کمینه بیشینه سریعتر از هرس آلفابتا می باشد. همانند هرس آلفابتا ، نگااسکات یک الگوریتم جستجوی هدایت شده برای محاسبه مقدار کمینه بیشینه برای یک گره از درخت می باشد.این الگوریتم با پی بردن به اینکه هیچگاه یک گره را که بوسیله آلفابتا هرس میشود را بررسی نکند ، میتواند بر آلفابتا چیره میشود. یک الگوریتم جستجو دیگر که MTD-f به طور تئوری منتج به جستجوی کمتر گرههای همسطح شود. به هرحال این یک مقوله کاربردی می باشد که امروزه هنوز در بیشتر موتورهای شطرنج ازیک فرم نگااسکات در جستجوهای آنها استفاده میشود .تاکنون الگوریتم دیگری که در عمل بهتر از نگااسکات عمل کرده است نخستین-بهترین الگوریتم که SSS-star نامیده میشود بوده است، هرچند به طور دقیق نمی توان گفت که کدام از دیگری بهتر است. در عین حال درختهایی وجود دارند که نگااسکات گرههای کمتری از SSS-star و برعکس مورد جستجو قرار می دهد .

[ویرایش] پیاده سازی

در ادامه شبه کدی از نگااسکات آورده شده است


  /* Compute minimax value of position p */ 
  NegaScout (node, depth, alpha, beta)   
     if node is a leaf OR depth equals 0
        return the heuristic value of node
     b = beta
     for each child of node
        temp = -NegaScout ( child, depth -1, -b, -alpha )
        if ( alpha > temp > beta) && AND not the first child
           alpha = -NegaScout ( child, depth -1, -beta, -temp )   
 /* re-search */
        alpha = max(alpha, temp )
        if alpha >= beta  
            return (alpha)                            /* cut-off */
        b = alpha + 1                       /* set new null window */
     return ( alpha )

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