(۱۴ اردیبهشت ۱۳۹۵ ۱۰:۱۱ ب.ظ)alirezaei نوشته شده توسط:  سلام، اینا چیز هایی هست که در مورد هرس آلفا-بتا میدونستم ، امیدوارم بدردت بخوره
یکم مقدمه:
یه سری روش های جستجو هست که شما هم با اون آشنایی مثل bfs, dfs, (* a و ... این روشا اصولا برای این استفاده میشن که از یک نقطه شروع ما رو به اهدافی برسونن یعنی فقط ما هستیم و اهدف، ولی یک نوع مسائل هستند که در اونها بحث رقابت وجود داره یعنی به طور همزمان فرد یا افرادی که رقیب هستند میخواهند به هدف برسند و اینجا چیزی که مهمه این هست که ما زودتر از رقیب به هدف برسیم، و مسیر رسیدن به هدف مهم نیست. پس روش های جستجوی قبلی که کارشون پیدا کردن کوتاه ترین مسیر در درخت جستجو بود کارساز نیستن ، و اصولا فضای حالت ما یه درخت هست بنام درخت بازی چون دو سطح داریم یکی برای رقیب و یکی برای خودمون که سطح ما بنام max خواهد بود و سطح رقیب بنام min یعنی داریم نوبتی بازی میکنیم .

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

خب اون پایین برگ ها هستند که هر کدوم عددی دارن، که اگه مسئله ما اونقدری بزرگ نباشه توانایی این رو داریم که درخت بازی رو تا سطح آخر رسم کنیم و این اعداد برگ ها برد و باخت و تساوی رو داره مشخص میکنه مثلا با سه عدد مشخص(۰و۱-و۱) ولی اگه مسئله پیچیده باشه ما درخت بازی رو نخواهیم توانست تا سطح آخر رسم کنیم و از یه جایی به بعد دیگه رسم درخت رو ادامه نمیدیم و گره های اون سطح رو به عنوان برگ تصور میکنیم و برای هر کدوم یه عدد در نظر میگیریم که نشون میده به طور تخمینی هر برگ چقدر تا هدف فاصله داره.مثل شکل زیر قاعده کلی الگوریتم min-max :اگر فرض کنیم ما گره max هستم همیشه عدد بزرگتر به نفع ماست و نشون میده با انتخاب گره ای که عدد بزرگتری داره به هدف نزدیک تر خواهیم شد و گره های min که علیه ما بازی میکنند همیشه سعی دارند تا کوچکترین عدد ها رو در نوبت خودشان انتخاب کنند تا ما دیرتر به هدف برسیم و خودشان زودتر.

برای حل ما از برگ ها شروع میکنیم و به سمت بالا(ریشه) میریم، یعنی با استفاده از عددی که برگ ها دارن برای پدرانشون مقداری رو تعیین میکنیم الان گره B که یک گره min هست(مثلث رو به پایین) از بین ۳ فرزندش مقداری رو انتخاب میکنه که از همه کمتره چون اینجوری خودش رو به هدف نزدیک تر میکنه و همزمان ما رو در نوبت بعدی از هدف تا جای ممکن دور میکنه. پس انتخاب B حتما ۳ هست. Cبه همین ترتیب از بین ۲و۴و۶ مقدار ۲ رو انتخاب میکنه و D نیز از بین ۲و۵و۱۴ مقدار ۲ رو انتخاب میکنه. B , C, D همه گره های min هستند که در سطح min قرار دارند . حالا نوبت سطح بالاتر یعنی سطح max است که در اینجا آخرین سطح است و ریشه در آن قرار دارد A باید در نوبت خودش بیشترین مقداری که ممکن است از فرزندانش انتخاب کند تا زودتر به هدف برسد پس از بین مقدارهای ۳و۲و۲ مقدار ۳ را انتخاب میکند . که نشون میده اگه ما کهmax هستیم بخوایم زودتر به هدف برسیم باید حرکت بعدیمون به سمت B باشه.


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

خب در شروع مثل قبل تنها گره هایی که مقدار دارن همون برگ ها هستند و باقی گره ها هنوز براشون عددی مشخص نشده و این مشخص نبودن یعنی از [tex]-\infty[/tex]تا [tex] \infty[/tex] میتونن مقداری داشته باشن.
[tex]\alpha[/tex] و [tex]\beta[/tex]هم مقادیری هستند که موقتا از فرزندان به پدران نسبت میدیم و از ۲ قاعده زیر برای هرس آلفا -بتا استفاده میکنیم:
۱-مقادیر آلفای گره های max هیچ وقت کاهش نمی یابند.
۲- مقادیر بتای گره های min هیچ وقت افزایش نمی یابند.

در شکل زیر گره A میدونه که صاحب عددی خواهد شد ولی چون فعلا مقدار دقیق اون مشخص نیست به اون [tex]\[-\infty, \infty\][/tex]رو نسبت میدیم همینطور به گره B .
میریم سراغ B اولین فرزندش مقدار ۳ رو داره پس مقدار B میتونه بین [tex]\[-\infty,3\][/tex] باشه، حالا B به امید دیدن عددی کوچکتراز ۳ به فرزند بعدی خود نگاه میکنه(چون B گره MIN هست و دنبال کوچکترین عدد از بین فرزندانش میگردد) اما نا امید میشه چون ۱۲ بزرگتر از ۳ هست وبرای B مناسب نیست و با همین امید به فرزند آخرش نگاه میکنه که باز هم نا امید میشه و درنهایت مقدار دقیق گره B عدد ۳خواهد بود. حالا یکی از ۳ فرزند A دارای مقدار مشخص شده و چون A گره MAX هست برای اون بازه [tex]\[3, \infty\][/tex]را در نظر میگیریم یعنی برای A فرزندانی مهم هستند که مقدارشون بتونه از ۳ بیشتر باشه. در ادامه میریم سراغ گره C ، اولین فرزند این گره مقدار ۲ را دارد پس C میتواند بین [tex]\[-\infty,2\][/tex]باشد. و حالا در ادامه C در بین فرزندانش میگردد تا اگر باشد مقداری کمتر از ۲ رو انتخاب کند ولی خود C فرزند گره A هست و گره A قرار است در ادامه از بین فرزندانش (B,C,D)اگر بشود مقداری بزرگتر از ۳ انتخاب کند و فعلا به ۳ رضایت داده پس با همین مقدار موقت که برای C مشخص شده (مقدار ۲)و شاید مقدار اصلی آن از همین مقدار هم کمتر باشد معلوم است که در آینده A اصلا به سمت C نخواهد آمد پس بررسی بقیه فرزندان C برای بدست آوردن مقدار دقیق برای C مهم نخواهند بود و هرس میشوند. حالا نوبت گره D هست اولین فرزند D مقدار ۱۴ رو داره که نشون میده مقدار D میتونه بین [tex]\[-\infty,14\][/tex] باشه در اینجا گره A به عنوان پدر D امیدوار میشه که مقدار D همین ۱۴ بمونه چون ۱۴ از ۳ که مقدار موقت A هست بزرگتره پس به D اجازه میدیم تا فرزند بعدی خودش رو هم نگاه کنه فرزند بعدی D مقدار ۵ رو به D میده یعنی الان D میتونه بین [tex]\[-\infty,5\][/tex]باشه خب در این صورت هم باز برای A جای امیدواری هست که بتونه از طریق D مقدار ۵ رو کسب کنه پس کار رو متوقف نمیکنیم و به D باز هم اجازه میدیم که فرزند بعدی خود را نگاه کند که در اینجا D مقدار ۲ را میبیند و چون از ۵ کمتر است آنرا انتخاب میکند و چون همه فرزندان D مشاهده شده مقدار دقیق ۲ به D داده میشود. و حالا نوبت A هست که از بین فرزندانش بزرگترین مقدار را انتخاب کند که برابر ۳ است.
توجه کن که اگر فرزند آخر D مثلا به جای ۲ مقدار ۱۰ رو داشت مقدار D همون ۵ میموند که چون از ۳ بزرگتر بود برای A مقدار ۵ رو در نظر میگرفتیم.

تا جایی که امید هست مقداری بیشتر از مقدار فعلی برای گره پدر که MAX هست بدست بیاد به فرزند اجازه میدیم که فرزندانش رو نگاه کنه و هر جا دیدیم که مقداری که الان پدر ( که MAX هست )داره از مقدار فرزندش بیشتر است دیگه به فرزندش اجازه نمیدیم به مشاهده فرزندانش ادامه دهد و از همون جا هرس میکنیم چون این پدر که MAX هست در ادامه هیچ وقت به سمت این فرزندش نخواهد آمد. در بالا A هیچ وقت به سمت C نمی آید .

برای گره پدر که MIN هست تا جایی که امید هست مقداری کمتر از مقدار فعلی برایش بدست آید به فرزند اجازه میدیم که فرزندانش رو نگاه کنه و هر جا دیدیم که مقداری که الان پدر( که MIN هست) داره از مقدار فرزندش کمتر است دیگه به فرزندش اجازه نمیدیم به مشاهده فرزندانش ادامه دهد و از همون جا هرس میکنیم چون این پدر که MIN هست در ادامه هیچ وقت به سمت این فرزندش نخواهد آمد.

دو فرزند c هرس شدند.
+مراحل جستجو: آبی پررنگ
موفق باشی

(۱۴ اردیبهشت ۱۳۹۵ ۱۰:۱۱ ب.ظ)alirezaei نوشته شده توسط:  سلام، اینا چیز هایی هست که در مورد هرس آلفا-بتا میدونستم ، امیدوارم بدردت بخوره
یکم مقدمه:
یه سری روش های جستجو هست که شما هم با اون آشنایی مثل bfs, dfs, (* a و ... این روشا اصولا برای این استفاده میشن که از یک نقطه شروع ما رو به اهدافی برسونن یعنی فقط ما هستیم و اهدف، ولی یک نوع مسائل هستند که در اونها بحث رقابت وجود داره یعنی به طور همزمان فرد یا افرادی که رقیب هستند میخواهند به هدف برسند و اینجا چیزی که مهمه این هست که ما زودتر از رقیب به هدف برسیم، و مسیر رسیدن به هدف مهم نیست. پس روش های جستجوی قبلی که کارشون پیدا کردن کوتاه ترین مسیر در درخت جستجو بود کارساز نیستن ، و اصولا فضای حالت ما یه درخت هست بنام درخت بازی چون دو سطح داریم یکی برای رقیب و یکی برای خودمون که سطح ما بنام max خواهد بود و سطح رقیب بنام min یعنی داریم نوبتی بازی میکنیم .

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

خب اون پایین برگ ها هستند که هر کدوم عددی دارن، که اگه مسئله ما اونقدری بزرگ نباشه توانایی این رو داریم که درخت بازی رو تا سطح آخر رسم کنیم و این اعداد برگ ها برد و باخت و تساوی رو داره مشخص میکنه مثلا با سه عدد مشخص(۰و۱-و۱) ولی اگه مسئله پیچیده باشه ما درخت بازی رو نخواهیم توانست تا سطح آخر رسم کنیم و از یه جایی به بعد دیگه رسم درخت رو ادامه نمیدیم و گره های اون سطح رو به عنوان برگ تصور میکنیم و برای هر کدوم یه عدد در نظر میگیریم که نشون میده به طور تخمینی هر برگ چقدر تا هدف فاصله داره.مثل شکل زیر قاعده کلی الگوریتم min-max :اگر فرض کنیم ما گره max هستم همیشه عدد بزرگتر به نفع ماست و نشون میده با انتخاب گره ای که عدد بزرگتری داره به هدف نزدیک تر خواهیم شد و گره های min که علیه ما بازی میکنند همیشه سعی دارند تا کوچکترین عدد ها رو در نوبت خودشان انتخاب کنند تا ما دیرتر به هدف برسیم و خودشان زودتر.

برای حل ما از برگ ها شروع میکنیم و به سمت بالا(ریشه) میریم، یعنی با استفاده از عددی که برگ ها دارن برای پدرانشون مقداری رو تعیین میکنیم الان گره B که یک گره min هست(مثلث رو به پایین) از بین ۳ فرزندش مقداری رو انتخاب میکنه که از همه کمتره چون اینجوری خودش رو به هدف نزدیک تر میکنه و همزمان ما رو در نوبت بعدی از هدف تا جای ممکن دور میکنه. پس انتخاب B حتما ۳ هست. Cبه همین ترتیب از بین ۲و۴و۶ مقدار ۲ رو انتخاب میکنه و D نیز از بین ۲و۵و۱۴ مقدار ۲ رو انتخاب میکنه. B , C, D همه گره های min هستند که در سطح min قرار دارند . حالا نوبت سطح بالاتر یعنی سطح max است که در اینجا آخرین سطح است و ریشه در آن قرار دارد A باید در نوبت خودش بیشترین مقداری که ممکن است از فرزندانش انتخاب کند تا زودتر به هدف برسد پس از بین مقدارهای ۳و۲و۲ مقدار ۳ را انتخاب میکند . که نشون میده اگه ما کهmax هستیم بخوایم زودتر به هدف برسیم باید حرکت بعدیمون به سمت B باشه.


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

خب در شروع مثل قبل تنها گره هایی که مقدار دارن همون برگ ها هستند و باقی گره ها هنوز براشون عددی مشخص نشده و این مشخص نبودن یعنی از [tex]-\infty[/tex]تا [tex] \infty[/tex] میتونن مقداری داشته باشن.
[tex]\alpha[/tex] و [tex]\beta[/tex]هم مقادیری هستند که موقتا از فرزندان به پدران نسبت میدیم و از ۲ قاعده زیر برای هرس آلفا -بتا استفاده میکنیم:
۱-مقادیر آلفای گره های max هیچ وقت کاهش نمی یابند.
۲- مقادیر بتای گره های min هیچ وقت افزایش نمی یابند.

در شکل زیر گره A میدونه که صاحب عددی خواهد شد ولی چون فعلا مقدار دقیق اون مشخص نیست به اون [tex]\[-\infty, \infty\][/tex]رو نسبت میدیم همینطور به گره B .
میریم سراغ B اولین فرزندش مقدار ۳ رو داره پس مقدار B میتونه بین [tex]\[-\infty,3\][/tex] باشه، حالا B به امید دیدن عددی کوچکتراز ۳ به فرزند بعدی خود نگاه میکنه(چون B گره MIN هست و دنبال کوچکترین عدد از بین فرزندانش میگردد) اما نا امید میشه چون ۱۲ بزرگتر از ۳ هست وبرای B مناسب نیست و با همین امید به فرزند آخرش نگاه میکنه که باز هم نا امید میشه و درنهایت مقدار دقیق گره B عدد ۳خواهد بود. حالا یکی از ۳ فرزند A دارای مقدار مشخص شده و چون A گره MAX هست برای اون بازه [tex]\[3, \infty\][/tex]را در نظر میگیریم یعنی برای A فرزندانی مهم هستند که مقدارشون بتونه از ۳ بیشتر باشه. در ادامه میریم سراغ گره C ، اولین فرزند این گره مقدار ۲ را دارد پس C میتواند بین [tex]\[-\infty,2\][/tex]باشد. و حالا در ادامه C در بین فرزندانش میگردد تا اگر باشد مقداری کمتر از ۲ رو انتخاب کند ولی خود C فرزند گره A هست و گره A قرار است در ادامه از بین فرزندانش (B,C,D)اگر بشود مقداری بزرگتر از ۳ انتخاب کند و فعلا به ۳ رضایت داده پس با همین مقدار موقت که برای C مشخص شده (مقدار ۲)و شاید مقدار اصلی آن از همین مقدار هم کمتر باشد معلوم است که در آینده A اصلا به سمت C نخواهد آمد پس بررسی بقیه فرزندان C برای بدست آوردن مقدار دقیق برای C مهم نخواهند بود و هرس میشوند. حالا نوبت گره D هست اولین فرزند D مقدار ۱۴ رو داره که نشون میده مقدار D میتونه بین [tex]\[-\infty,14\][/tex] باشه در اینجا گره A به عنوان پدر D امیدوار میشه که مقدار D همین ۱۴ بمونه چون ۱۴ از ۳ که مقدار موقت A هست بزرگتره پس به D اجازه میدیم تا فرزند بعدی خودش رو هم نگاه کنه فرزند بعدی D مقدار ۵ رو به D میده یعنی الان D میتونه بین [tex]\[-\infty,5\][/tex]باشه خب در این صورت هم باز برای A جای امیدواری هست که بتونه از طریق D مقدار ۵ رو کسب کنه پس کار رو متوقف نمیکنیم و به D باز هم اجازه میدیم که فرزند بعدی خود را نگاه کند که در اینجا D مقدار ۲ را میبیند و چون از ۵ کمتر است آنرا انتخاب میکند و چون همه فرزندان D مشاهده شده مقدار دقیق ۲ به D داده میشود. و حالا نوبت A هست که از بین فرزندانش بزرگترین مقدار را انتخاب کند که برابر ۳ است.
توجه کن که اگر فرزند آخر D مثلا به جای ۲ مقدار ۱۰ رو داشت مقدار D همون ۵ میموند که چون از ۳ بزرگتر بود برای A مقدار ۵ رو در نظر میگرفتیم.

تا جایی که امید هست مقداری بیشتر از مقدار فعلی برای گره پدر که MAX هست بدست بیاد به فرزند اجازه میدیم که فرزندانش رو نگاه کنه و هر جا دیدیم که مقداری که الان پدر ( که MAX هست )داره از مقدار فرزندش بیشتر است دیگه به فرزندش اجازه نمیدیم به مشاهده فرزندانش ادامه دهد و از همون جا هرس میکنیم چون این پدر که MAX هست در ادامه هیچ وقت به سمت این فرزندش نخواهد آمد. در بالا A هیچ وقت به سمت C نمی آید .

برای گره پدر که MIN هست تا جایی که امید هست مقداری کمتر از مقدار فعلی برایش بدست آید به فرزند اجازه میدیم که فرزندانش رو نگاه کنه و هر جا دیدیم که مقداری که الان پدر( که MIN هست) داره از مقدار فرزندش کمتر است دیگه به فرزندش اجازه نمیدیم به مشاهده فرزندانش ادامه دهد و از همون جا هرس میکنیم چون این پدر که MIN هست در ادامه هیچ وقت به سمت این فرزندش نخواهد آمد.

دو فرزند c هرس شدند.
+مراحل جستجو: آبی پررنگ
موفق باشی