PDA

View Full Version : مقاله: جستجوی حریصانه آلفا- بتا



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

http://upload.wikimedia.org/wikipedia/commons/thumb/6/6f/Minimax.svg/300px-Minimax.svg.png (http://en.wikipedia.org/wiki/File:Minimax.svg)
[الگوریتم 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 (http://en.wikipedia.org/wiki/Search_algorithm) which seeks to reduce the number of nodes that are evaluated in the search tree (http://en.wikipedia.org/wiki/Game_tree) by the minimax algorithm (http://en.wikipedia.org/wiki/Minimax#Minimax_algorithm_with_alternate_moves). It is a search with adversary algorithm used commonly for machine playing of two-player games (Tic-tac-toe (http://en.wikipedia.org/wiki/Tic-tac-toe), Chess (http://en.wikipedia.org/wiki/Chess), Go (http://en.wikipedia.org/wiki/Go_(board_game)), 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 (http://www.staroceans.com/alpha-beta-prune.htm)


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

http://www.sharemation.com/85b/term2/AI/hosh%20masnooee%20%28asgarzadeh%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
پیروز باشید.

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

mortezamsp
دوشنبه 09 آذر 1388, 10:11 صبح
سلام.خسته نباشي حاجي.ميشه اينه pdf ها رو آپلود كني رو سايت،آخه لينكشون ديگه باز نميشه!

lordarma
جمعه 07 اسفند 1388, 14:08 عصر
سلام.خسته نباشي حاجي.ميشه اينه pdf ها رو آپلود كني رو سايت،آخه لينكشون ديگه باز نميشه!

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

hosssein_azar
جمعه 07 اسفند 1388, 23:48 عصر
منظوراز نودهای بعدی ،گره های بعدی تو همون شاخه است.نه تمام گره های درخت.
و باید یادمون باشه که الفا بتا بر اساس جستجوی عمقی کار می کنه

mohandes ehsan
چهارشنبه 21 دی 1390, 12:51 عصر
pdfa دانلود نميشه