هرس آلفا بتا

برای بررسی ایدهٔ کلی هرس آلفا بتا این دو مسئلهٔ مشابه را در نظر بگیرید:

- تعدادی زیر مجموعهٔ ناتهی و متناهی از مجموعهٔ اعداد حقیقی در اختیار داریم. ارزش (یا امتیاز) هر یک از این مجموعه‌ها را برابر با کوچک‌ترین عضو آن تعریف می‌کنیم. هدفمان یافتن مجموعه‌ای با بیش‌ترین ارزش است.

فرض کنید که ارزش یکی از مجموعه‌ها برابر با m است. در این صورت مجموعه‌ای که دست کم یک عضو کوچک‌تر از m داشته باشد، پاسخ مسئله نخواهد بود. پس نیازی به بررسی اعضای این مجموعه (و یافتن ارزش آن) نیست. (چرا که ارزش آن کوچک‌تر از m است)

- همان پرسش بالا را این گونه تغییر می‌دهیم: ارزش هر مجموعه برابر با بزرگ‌ترین عضو آن تعریف می‌شود و هدف یافتن کم ارزش‌ترین مجموعه است.

در این حالت نیز اگر مجموعه‌ای با ارزش m وجود داشته باشد مجموعه‌هایی که حداقل یک عضو بزرگ‌تر از m دارند، نمی‌توانند پاسخ مسئله باشند.

از همین ایده می‌توان برای بهینه کردن پیمایش روی درخت کمینه بیشینه بهره جست. شکل زیر را به عنوان بخشی از یک درخت کمینه بیشینه در نظر بگیرید:

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

یکی از راه‌های پیاده‌سازی درخت کمینه بیشینه برای یک بازی دو نفره این است که راس‌های درخت به گونه‌ای ارزش (امتیاز) گذاری شوند که ارزش هر راس بیان گر میزان برتری بازکن نخست باشد. در این صورت:

- اگر در یک راس نوبت با بازیکن نخست باشد ارزش آن راس برابر است با بیش‌ترین ارزش نسبت داده شده به فرزندان آن (به چنین راسی Max node یا راس بیشینه گفته می‌شود)

- اگر در یک راس نوبت با بازیکن دوم باشد ارزش آن راس برابر است با کم‌ترین ارزش نسبت داده شده به فرزندان آن (به چنین راسی Min node یا راس کمینه گفته می‌شود)

تابع بازگشتی زیر برای یافتن ارزش هر راس در درخت کمینه بیشینه استفاده می‌شود. در این تابع دو ورودی alpha و beta نشان دهندهٔ آن هستند که اگر ارزش راس مورد بررسی در بازهٔ [ alpha , beta ] قرار نداشت نیازی به یافتن ارزش دقیق آن نیست.

function AlphaBeta (node, depth, IsMaxNode, alpha, beta)

/* IsMaxNode shows that it is the first player's turn to choose a move or not. */

if depth = 0 or node is a terminal node

return the heuristic value of node

for each child of node

if IsMaxNode

alpha = max (alpha, AlphaBeta (child, depth - 1, not IsMaxNode, alpah, beta))

else

beta  = min (beta,  AlphaBeta (child, depth - 1, not IsMaxNode, alpha, beta))

if beta <= alpha

break

if IsMaxNode

return alpha

else

return beta

end of function

فراخوانی اولیه این تابع برای یک Max node

AlphaBeta (FirstNode, MaxDepth, true, -Inf, +Inf)

فراخوانی اولیه این تابع برای یک Min node

AlphaBeta (FirstNode, MaxDepth, false, -Inf, +Inf)

برخی دیگر از الگوریتم‌هایی که برای بهینه‌سازی پیمایش روی درخت کمینه بیشینه استفاده می‌شوند عبارتند از: نگااسکات و الگوریتم MTD-F و الگوریتم sss* (این الگوریتم‌ها معمولاً کارایی بیش تری نسبت به هرس آلفا بتا دارند)