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

جستجوی حریصانه آلفا-بتا،الگوریتم جستجویی است که بدنبال کاهش تعداد محاسبات گره ها یا نود ها(node) در جستجوی درختی الگوریتم min-max می گردد.

http://upload.wikimedia.org/wikipedi...inimax.svg.png
[الگوریتم minmax or min-max]

جستجوی حریصانه آلفا-بتا الگوریتمی برپایه روش مخالف است، که اغلب در بازی های دو نفره ای همچون شطرنج(chess), تیک-تاک-تو(Tic-tac-toa) و GO و تخته نرد(backgammon) بکار می رود.
در این الگوریتم اگر محاسبه حرکت فعلی بهتر از حرکت قبلی باشد،الگوریتم از ادامه دادن محاسبه بعدی صرف نظر می کند(پ.ن:اگر نتیجه محاسبات alpha و beta ها از alpha و beta های بعدی بهتر باشد،روند محاسباتی alpha و beta های جدید را متوقف می سازد).
الگوریتم آلفا و بتا در نتیجه نهایی الگوریتم min-max تاثیری نمی گزارد، و فقط باعث بهبود سرعت جستجوی الگوریتم min-max می شود.
[مشاهده روند جستجوی الگوریتم آلفا و بتا درعمل، به صورت انیمیشن]

نقل قول:

---

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.

---

از ویکی پدیای انگلیسی
و نمونه کد آن در ++C


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

• http://www.sharemation.com/85b/term2...arzadeh%29.ppt
• http://www.sharemation.com/85b/term2/AI/AI.pdf
• http://www.sharemation.com/85b/term2/AI/AI-CH-4.pdf
• http://www.sharemation.com/85b/term2/AI/AI-CH-5.pdf
• http://www.sharemation.com/85b/term2/AI/AI-CH-6.pdf
• http://www.sharemation.com/85b/term2/AI/AI-CH-7.pdf

پیروز باشید.

[quote=aminsharifi67;728503]
در این الگوریتم اگر محاسبه حرکت فعلی بهتر از حرکت قبلی باشد،الگوریتم از ادامه دادن محاسبه بعدی صرف نظر می کند(پ.ن:اگر نتیجه محاسبات alpha و beta ها از alpha و beta های بعدی بهتر باشد،روند محاسباتی alpha و beta های جدید را متوقف می سازد).
الگوریتم آلفا و بتا در نتیجه نهایی الگوریتم min-max تاثیری نمی گزارد، و فقط باعث بهبود سرعت جستجوی الگوریتم min-max می شود.
quote]
دوستان پرسشی برای من پیش آمده است.اگر الگوریتم به محض رسیدن به جواب بهتر از محاسبه نود های بعدی ممانعت ورزد.به نظر می رسد در نتیجه الگوریتم min-max اثر میگذارد.آیا این چنین است؟

سلام.خسته نباشي حاجي.ميشه اينه pdf ها رو آپلود كني رو سايت،آخه لينكشون ديگه باز نميشه!

نقل قول:

---

نوشته شده توسط mortezamsp

سلام.خسته نباشي حاجي.ميشه اينه pdf ها رو آپلود كني رو سايت،آخه لينكشون ديگه باز نميشه!

---

من همین الان همه رو دانلود کردم،
مشکلی نداشت :چشمک::لبخندساده:

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

pdfa دانلود نميشه