هرس آلفا بتا

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
AB pruning.png

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

ایدهٔ هرس آلفا بتا[ویرایش]

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

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

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

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

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

مثال[ویرایش]

Alpha beta.png

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

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


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

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

- اگر در یک راس نوبت با بازیکن نخست باشد ارزش آن راس برابر است با بیش‌ترین ارزش نسبت داده شده به فرزندان آن (به چنین راسی 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* (این الگوریتم‌ها معمولاْ کارایی بیش تری نسبت به هرس آلفا بتا دارند.)

منابع[ویرایش]