نگااسکات

نگا اسکات (به انگلیسی: Negascout) یا جستجوی شاخه اصلی یک الگوریتم کمینه بیشینه سریعتر از هرس آلفابتا می‌باشد. همانند هرس آلفابتا، نگااسکات یک الگوریتم جستجوی هدایت شده برای محاسبه مقدار کمینه بیشینه برای یک گره از درخت می‌باشد. این الگوریتم با پی بردن به اینکه هیچگاه یک گره را که به‌وسیله آلفابتا هرس می‌شود را بررسی نکند، می‌تواند بر آلفابتا چیره می‌شود. یک الگوریتم جستجو دیگر که الگوریتم 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)

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