advertise laitec sharif univercity
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

148000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم ازدحام ذرات PSO در #C

10000 تومان
دانلود مقاله ای در مورد الگوریتم  کرم شب تاب FireFly در هوش مصنوعی

دانلود مقاله ای در مورد الگوریتم کرم شب تاب FireFly در هوش مصنوعی

10000 تومان
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

10000 تومان
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

48000 تومان

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

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

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

مشکل جست وجوی 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