تالار گفتمان مانشت

کدام عبارت در مورد جستجوی mini-max و هرس آلفا بتا غلط است؟ (فناوری اطلاعات 89)

پوران گفته هرس آلفا بتا باعث افزایش سرعت جستجو نمیشه

و راهیان گفته باعث افزایش سرعت میشه و گزینه دیگه ای رو جواب گرفته...حالا کدومش درسته؟دوستانی که کتاب راهیانو دارن لطفا کمک

(02 آبان 1392 07:37 ب.ظ)sahar_rostami2 نوشته شده توسط: [ -> ]کدام عبارت در مورد جستجوی mini-max و هرس آلفا بتا غلط است؟ (فناوری اطلاعات ۸۹)

پوران گفته هرس آلفا بتا باعث افزایش سرعت جستجو نمیشه

و راهیان گفته باعث افزایش سرعت میشه و گزینه دیگه ای رو جواب گرفته...حالا کدومش درسته؟دوستانی که کتاب راهیانو دارن لطفا کمک

من مرجع نخوندم ولی تو تعریف هرس آلفا-بتا گفته نشده که سرعت رو زیاد میکنه ...
بعد راهیان کدوم گزینه رو گفته جواب ؟!‌بقیشون که درستن...

این تعریف راسل :

نقل قول: Alpha–beta pruning is a search algorithm that seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search 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. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.[1]

هرس الفا بتا به طور متوسط پیچیده گی رو کاهش می ده ولی در بدترین حالت نه
درمجموع میشه گفت کاهش میده و پیچیدگی رو تبدیل به b**n/2 می رسونه(تو یه سری اسلاید این رو دیدم)

(07 آبان 1392 05:19 ب.ظ)afshin18 نوشته شده توسط: [ -> ]هرس الفا بتا به طور متوسط پیچیده گی رو کاهش می ده ولی در بدترین حالت نه
درمجموع میشه گفت کاهش میده و پیچیدگی رو تبدیل به b**n/2 می رسونه(تو یه سری اسلاید این رو دیدم)

خب بالاخره جواب درست کدومه؟

(10 آبان 1392 05:42 ب.ظ)sahar_rostami2 نوشته شده توسط: [ -> ]

(07 آبان 1392 05:19 ب.ظ)afshin18 نوشته شده توسط: [ -> ]هرس الفا بتا به طور متوسط پیچیده گی رو کاهش می ده ولی در بدترین حالت نه
درمجموع میشه گفت کاهش میده و پیچیدگی رو تبدیل به b**n/2 می رسونه(تو یه سری اسلاید این رو دیدم)

خب بالاخره جواب درست کدومه؟

وقتی پیچیدگی کم میشه سرعت بالا میره دیگه

اینو ببین. توضیح کاملی داده.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


من با استدلال زیر موافقم:
"فرض کنین درخت شما مثلا دارای ۱۰۰۰ سطح باشه. و اگر بخواین با روش minimax جواب را پیدا کنین الگوریتم تا ۱۰ سطح را براتون پیمایشمی کنه و جواب مورد نظرش را بر میگردانه. حالا اگر با هرس آلفابتا بخواین اینکار را بکنین در بهترین حالت اگر الگوریتم از نصف گره‌ها هم که صرفنظر کنه باز زمان شما کم نمیشه. چون فضای خالی که براش باقی مانده را برای افزایش عمق استفاده میکنه. مثلا اینبار جای ۱۰ سطح، ۲۰ سطح را بررسی می کنه. نتیجه اینکه هرس باعث افزایش عمق جستجو میشه نه کاهش زمان جستجو."

(16 آبان 1392 03:06 ب.ظ)g_monireh نوشته شده توسط: [ -> ]اینو ببین. توضیح کاملی داده.


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


من با استدلال زیر موافقم:
"فرض کنین درخت شما مثلا دارای ۱۰۰۰ سطح باشه. و اگر بخواین با روش minimax جواب را پیدا کنین الگوریتم تا ۱۰ سطح را براتون پیمایشمی کنه و جواب مورد نظرش را بر میگردانه. حالا اگر با هرس آلفابتا بخواین اینکار را بکنین در بهترین حالت اگر الگوریتم از نصف گره‌ها هم که صرفنظر کنه باز زمان شما کم نمیشه. چون فضای خالی که براش باقی مانده را برای افزایش عمق استفاده میکنه. مثلا اینبار جای ۱۰ سطح، ۲۰ سطح را بررسی می کنه. نتیجه اینکه هرس باعث افزایش عمق جستجو میشه نه کاهش زمان جستجو."

پس با این حساب پوران درست گفته که این گزینه غلطه

(02 آبان 1392 07:37 ب.ظ)sahar_rostami2 نوشته شده توسط: [ -> ]کدام عبارت در مورد جستجوی mini-max و هرس آلفا بتا غلط است؟ (فناوری اطلاعات ۸۹)

پوران گفته هرس آلفا بتا باعث افزایش سرعت جستجو نمیشه

و راهیان گفته باعث افزایش سرعت میشه و گزینه دیگه ای رو جواب گرفته...حالا کدومش درسته؟دوستانی که کتاب راهیانو دارن لطفا کمک

ممکنه همه دوستان کتاب شما رو نداشته باشن؛ بهتر بود صورت سوال رو هم قرار میدادید؛
بنظرم هدف طراح تو این سوال گزینه 1 بوده؛
"در جستجوی مینی-مکس فقط بهترین راه حل یا بیشترین امتیاز برای بازیکن مکس تولید میشه"
ولی در پایان مینی-مکس بازیکن مین هم به بهترین وضعیت خودش میرسه؛
گزینه 2 و 3 هم درسته (3 با اغماض)؛
چند خط در کتاب راهیان درباره رابطه سرعت آلفا-بتا و مینی-مکس آورده که بنظرم درسته؛ اگه در یک زمان معین، مینی-مکس تا عمق d رو بررسی کنه، توی همون زمان آلفا-بتا میتونه تا عمق 2d رو بررسی کنه (یعنی تقریبا دوبرابر کار انجام بده)، و این یعنی سرعت آلف-بتا در پیمایش فضای حالت بیشتر از مینی-مکسه؛

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