هرس آلفا بتا
هرس آلفا بتا الگوریتمی است که کارایی الگوریتم درخت Minimax (درخت کمینه بیشینه یا درخت بازی) را بهبود می‌بخشد. با استفاده از هرس آلفا بتا، بخش‌هایی از درخت کمینه بیشینه که پیمایششان بی تأثیر است پیمایش نمی‌شوند و به این ترتیب پیمایش درخت کمینه بیشینه تا یک عمق مشخص در زمانی کم‌تر صورت می‌گیرد.
ایدهٔ هرس آلفا بتا[ویرایش]
برای بررسی ایدهٔ کلی هرس آلفا بتا این دو مسئلهٔ مشابه را در نظر بگیرید:
- تعدادی زیر مجموعهٔ ناتهی و متناهی از مجموعهٔ اعداد حقیقی در اختیار داریم. ارزش (یا امتیاز) هر یک از این مجموعه‌ها را برابر با کوچک‌ترین عضو آن تعریف می‌کنیم. هدفمان یافتن مجموعه‌ای با بیش‌ترین ارزش است.
فرض کنید که ارزش یکی از مجموعه‌ها برابر با 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* (این الگوریتم‌ها معمولاً کارایی بیش تری نسبت به هرس آلفا بتا دارند)