advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

23000 تومان
دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

دانلود پروژه مدیریت کتابخانه با سی شارپ و SQL سرور

3000 تومان
دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

3000 تومان
سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

3000 تومان
دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

3000 تومان

الگوریتم هرس کردن آلفا - بتا

هرس کردن آلفا – بتا که یکی از استراتژی های جستوجوی خصمانه است، میتواند به هر درختی با هر عمق اعمال شود و مقادیر α و β را با هرس کردن انشعاب های باقیمانده در یک گره، به هنگام سازی میکند
الگوریتم هرس کردن آلفا - بتا

الگوریتم هرس کردن آلفا - بتا

مشکل جست وجوی minimax این است که تعداد حالتهای بازی که باید بررسی شوند، برحسب تعداد حرکتها، یک رابطه ی نمایی است. متاسفانه این رابطه نمایی را نمیتوان حذف کرد ولی میتوان آنرا به نصف تقلیل داد. علتش این است که محاسبه تصمیم minimax صحیح بدون دیدن همه گره های درخت بازی امکانپذیر است. یعنی با استفاده از مفهوم هرس کردن میتوان بخش های بزرگی از درخت را از بین برد. با استفاده از تکنیکی به نام هرس کردن آلفا – بتا میتوان این کار را انجام داد. وقتی این تکنیک به درخت minimax اعمال میشود، همان حرکتی را برمیگرداند که minimax برخواهد گرداند، اما انشعاب هایی که در تصمیم نهایی تاثیر ندارند، حذف خواهند شد.

هرس کردن آلفا – بتا که یکی از استراتژی های جستوجوی خصمانه است، میتواند به هر درختی با هر عمق اعمال شود. بطور کلی میتوان کل زیردرخت را به جای برگ ها هرس کرد. اصل کلی این است : گره n را در جایی از درخت در نظر بگیرید بطوریکه بازیکن بتواند به آن گره برود. اگر بازیکن، در گره والد n یا هر نقطه ای در سطح بالاتر، انتخاب بهتری مثل m  دارد، آنگاه در بازی واقعی هرگز به n نخواهد رسید. لذا وقتی اطلاعات کافی در مورد n کسب کردیم (با بررسی بعضی از فرزندان آن) تا به این نتیجه برسیم، میتوانیم آنرا هرس کنیم.

به یاد داشته باشید که جست وجوی minimax عمقی است، لذا در هر زمان فقط باید گره های موجود در یک مسیر درخت را در نظر بگیریم. نام هرس کردن آلفا – بتا از دو پارامتر  زیر به دست آمده که کران مقادیر ذخیره شده در  تمام طول مسیر هستند:

α = مقدار بهترین (یعنی بالاترین) انتخابی است که تاکنون در هر نقطه انتخاب در مسیر مربوط به MAX پیدا شده است.

β = مقدار بهترین (یعنی پایین ترین) انتخابی است که تاکنون در هر نقطه انتخاب در مسیر مربوط به MIN پیدا شده است.

جست وجوی آلفا – بتا ، مقادیر α و β را با هرس کردن انشعاب های باقیمانده در یک گره، به هنگام سازی میکند. این کار به محض اینکه مشخص شد مقدار گره فعلی بدتر از مقدار α یا β مربوط به MAX یا MIN است، انجام میگیرد.

اثر بخشی هرس کردن آلفا – بتا به ترتیب بررسی حالت ها بستگی دارد پس بهتر است ابتدا پسین هایی بررسی شوند که ممکن است بهترین باشند. اگر فرض کنیم این کار امکانپذیر باشد، نتیجه میگیریم  که در آلفا – بتا فقط O(bm/2) گره باید بررسی شوند تا بهترین انتخاب صورت گیرد در حالیکه در minimax، این تعداد O(bm) بوده است.

با اضافه کردن طرح های تعیین حرکتها بصورت پویا، مثل طرح هایی که سعی میکنند اول حرکتهایی را انجام دهند که در گذشته بهترین بودند، ضریب انشعاب به مقداری که در محاسبات نظری به دست می آید، نزدیک میشود. حرکت گذشته، میتوانست حرکت قبلی باشد یا میتوانست از اکتشاف قبلی مربوط به حرکت فعلی تعیین شود.

 

الگوریتم جست وجوی آلفا – بتا 

 

function  ALPHA – BETA - SEARCH (state)  returns  an  action

        v <-- MAX –VALUE (state , -∞ , +∞)

        return  the  action  in ACTION(state)  with  value  v

function   MAX – VALUE (state, α, β)  returns  a  utility  value

        if  THERMINAL – TEST (state)  then  return  UTILITY (state)

        v <--  - ∞

        for each  a  in  ACTIONS (state)  do

              v <--  MAX (v , MIN- VALUE (RESULT (s , a) , α, β ) )

              if  v >= β  then  return  v

              α <-- MAX (α , v)

        return  v

function   MIN – VALUE (state, α, β)  returns  a utility  value

        if  THERMINAL – TEST (state)  then  return  UTILITY (state)

        v <--  + ∞

        for each  a  in  ACTIONS (state)  do

              v <--  MIN (v , MAX- VALUE (RESULT (s , a) , α, β ) )

              if  v <=  α  then  return  v

              β <-- MAX (β , v)

        return  v

 

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
الگوریتم جست وجوی α βآموزش پیاده سازی الگوریتم آلفا بتاشبه کد الگوریتم آلفا بتادانلود سورس کد الگوریتم جست وجوی آلفا بتاالگوریتم جست وجوی آلفا بتااستراتژی های جستوجوی خصمانه هرس کردن آلفا بتاهرس کردن آلفا - بتاالگوریتم هرس کردن آلفا بتا چیست؟هرس کردن α βتبلیغات ارزان سایت آموزش برنامه نویسیتبلیغات مخصوص طراحان وب سایتتبلیغات در سایت برنامه نویسیتبلیغات اینترنتی برای برنامه نویساندر آغوش مینیمالیسممنوی همبرگر با سه خط افقی که روی یکدیگر قرار گرفته اند نشانه چیست؟ سوئیچ به یک ستون واحدتبدیل متن ساده به وبلاگ و سایت های پویا با React.jsکتابخانه sass برای استفاده آسان تر از آنکتابخانه سطح بالا برای اتوماتیک سازی اعمال مرورگر لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

سفارش پروژه در سورس کد

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php