الگوریتم هرس آلفا بتا ( Alpha-beta pruning ) الگوریتمی است که جهت بهبود کارایی الگوریتم درخت Minimax (درخت کمینه بیشینه یا درخت بازی) مورد استفاده قرار می گیرد. با استفاده از الگوریتم ( Alpha-beta pruning ) هرس آلفا بتا، قسمت های از درخت کمینه بیشینه پیمایش نمی شوند و به این ترتیب پیمایش درخت کمینه بیشینه تا یک عمق مشخص در زمانی کم تر صورت می گیرد. یکی از راههای پیاده سازی درخت کمینه بیشینه برای یک بازی دو نفره این است که راسهای درخت به گونه ای ارزش (امتیاز) گذاری شوند که ارزش هر راس بیان گر میزان برتری بازیکن نخست باشد. در این صورت:
توضیحات :
الگوریتم هرس آلفا بتا ( Alpha-beta pruning )
الگوریتمی است که جهت بهبود کارایی الگوریتم درخت Minimax (درخت کمینه
بیشینه یا درخت بازی) مورد استفاده قرار می گیرد. با استفاده از الگوریتم ( Alpha-beta pruning )
هرس آلفا بتا، قسمت های از درخت کمینه بیشینه پیمایش نمی شوند و به این
ترتیب پیمایش درخت کمینه بیشینه تا یک عمق مشخص در زمانی کم تر صورت می
گیرد.
یکی از راههای پیاده سازی درخت
کمینه بیشینه برای یک بازی دو نفره این است که راسهای درخت به گونه ای
ارزش (امتیاز) گذاری شوند که ارزش هر راس بیان گر میزان برتری بازیکن نخست
باشد. در این صورت:
– اگر در یک راس
نوبت با بازیکن نخست باشد ارزش آن راس برابر است با بیشترین ارزش نسبت
داده شده به فرزندان آن (به چنین راسی Max node یا راس بیشینه گفته می
شود.)
– اگر در یک راس نوبت با بازیکن
دوم باشد ارزش آن راس برابر است با کمترین ارزش نسبت داده شده به فرزندان
آن (به چنین راسی Min node یا راس کمینه گفته می شود.)