جستجوی حریصانه آلفا-بتا

[آبجی]

جستجوی حریصانه آلفا-بتا،الگوریتم جستجویی است که بدنبال کاهش تعداد محاسبات گره ها یا نود ها(node) در جستجوی درختی الگوریتم min-max می گردد.
http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Minimax.svg/300px-Minimax.svg.png

[الگوریتم minmax or min-max]
جستجوی حریصانه آلفا-بتا الگوریتمی برپایه روش مخالف است، که اغلب در بازی های دو نفره ای همچون شطرنج(chess), تیک-تاک-تو(Tic-tac-toa) و GO و تخته نرد(backgammon) بکار می رود.
در این الگوریتم اگر محاسبه حرکت فعلی بهتر از حرکت قبلی باشد،الگوریتم از ادامه دادن محاسبه بعدی صرف نظر می کند(پ.ن:اگر نتیجه محاسبات alpha و beta ها از alpha و beta های بعدی بهتر باشد،روند محاسباتی alpha و beta های جدید را متوقف می سازد).
الگوریتم آلفا و بتا در نتیجه نهایی الگوریتم min-max تاثیری نمی گزارد، و فقط باعث بهبود سرعت جستجوی الگوریتم min-max می شود.
[مشاهده روند جستجوی الگوریتم آلفا و بتا درعمل، به صورت انیمیشن (http://www.ndsu.nodak.edu/instruct/juell/vp/cs724s01/alpha/alpha.html)]
نقل قول:
Alpha-beta pruning is a search algorithm which seeks to reduce the number of nodes that are evaluated in the search tree by the minimax algorithm. It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. Alpha-beta pruning is a sound optimization in that it does not change the result of the algorithm it optimizes.
از ویکی پدیای انگلیسی


و در آخر چند PDF فارسی درباره هوش مصنوعی[Artificial Intelligence] و الگوریتم های alpha-beta و min-max،امیدوارم برای دوستان مفید واقع بشود:

كد:
کد:
http://www.sharemation.com/85b/term2/AI/hosh%20masnooee%20%28asgarzadeh%29.ppt (http://njavan.com/forum/redirector.php?url=http%3A%2F%2Fwww.sharemation.co m%2F85b%2Fterm2%2FAI%2Fhosh%2520masnooee%2520%2528 asgarzadeh%2529.ppt)
http://www.sharemation.com/85b/term2/AI/AI.pdf (http://njavan.com/forum/redirector.php?url=http%3A%2F%2Fwww.sharemation.co m%2F85b%2Fterm2%2FAI%2FAI.pdf)
http://www.sharemation.com/85b/term2/AI/AI-CH-4.pdf (http://njavan.com/forum/redirector.php?url=http%3A%2F%2Fwww.sharemation.co m%2F85b%2Fterm2%2FAI%2FAI-CH-4.pdf)
http://www.sharemation.com/85b/term2/AI/AI-CH-5.pdf (http://njavan.com/forum/redirector.php?url=http%3A%2F%2Fwww.sharemation.co m%2F85b%2Fterm2%2FAI%2FAI-CH-5.pdf)
http://www.sharemation.com/85b/term2/AI/AI-CH-6.pdf (http://njavan.com/forum/redirector.php?url=http%3A%2F%2Fwww.sharemation.co m%2F85b%2Fterm2%2FAI%2FAI-CH-6.pdf)
http://www.sharemation.com/85b/term2/AI/AI-CH-7.pdf (http://njavan.com/forum/redirector.php?url=http%3A%2F%2Fwww.sharemation.co m%2F85b%2Fterm2%2FAI%2FAI-CH-7.pdf)