محیط
های چند عاملی هم میتوانند رقابتی باشند
و هم رفاقتی!
در
بازی با مجموع صفر دو نفره سودمندی Min
و
Max
برعکس
هم است.
ارزیابی
الگوریتم مین مکس:
عمقی
است پس پیچیدگی زمانی نمایی و پیچیدگی
فضایی خطی دارد.
الگوریتم
کامل است.
فرض
میشود min
بهینه
بازی میکند و اگر بهینه بازی نکند سود max
کمتر
نخواهد شد.
مین
مکس همه گره ها را بررسی میکند اما هرس
آلفا بتا سعی میکند بعضی از گره ها را هرس
کند.
حرکتی
که الگوریتمهای مین مکس و هرس آلفا بتا
میدهند عین هم است.
الگوریتم
هرس آلفا بتا مانند مین مکس عمقی است پس
پیچیدگی فضایی خطی دارد.
اگر
در بازی سودمندی گرهها محدود باشد(منفی
و مثبت بی نهایت نباشد)
هیچگاه
یکی از شاخه های عمیقترین زیردرخت سمت
چپترین شاخه از بازی هرس نمیشود ولی اگر
محدود باشد ممکن است بشود.
ترتیب
بررسی شاخه برروی الگوریتم هرس آلفا بتا
تاثیر میگذارد.
برای
بازی ای که سودمندی تا بینهایت باشد
بیشترین هرس زمانی اتفاق میافتد که :(این
ترتیب بندی برای گره های سطح بالاتر بسیار
سودمندتر است)
۱.
برای
هر گره مکس فرزند با بیشترین سودمندی آن
در سمت چپترین شاخه باشد.
۲.
برای
هر گره مین فرزند با کمترین سودمندی آن
در سمت چپترین شاخه باشد.
هرس
آلفا بتا در حالت بالا حداکثر نصف شاخه
ها را هرس خواهد کرد.
بنابراین
میشود فاکتور انشعاب را رادیکال b
در
نظر گرفت.
سرعت
الگوریتم هرس آلفا بتا دو برابر مین مکس
است.
اگر
ترتیب رندم انتخاب شود فاکتور انشعاب
آلفابتا b
به
توان سه رادیکال ۴ است.
چون
حالت تکراری در بازی زیاد است.
بهتر
است مقادیر حالاتی که تا الان حساب شده
اند به همراه حالت آنها در یک جدول درهم
سازی نگهداری شوند.
در
بازی های دارای شانس باید ارزش گره را به
اندازه ارزش واقعی تخمین زد ولی در بازی
هایی که عنصر شانس ندارند نیازی نیست بلکه
تنها کافی است گره ها را همانند تابع
سودمندی مرتب کند.
مشکلهای
پایان دادن به جستجو:
وضعیت
غیرساکن و اثر افق که هر دو بعلت دقیق
نبودن تابع ارزیابی رخ میدهند.
برای
رفع مشکل وضعیت غیر ساکن باید تابع ارزیابی
را فقط به وضعیتهایی که ساکن هستند اعمال
کرد و وضعیت های غیر ساکن را بسط داد تا
به وضعیت ساکن رسید.(جستجوی
سکون)
هرس
پیشرو ممکن است خطرناک باشد و بهترین حرکت
را هرس کند.
هرس
پیشرو بهتر است برای گرهها در عمق زیاد
بکار رود.
هرس
پیشرو میتواند در وضعیتی که دو حرکت متقارن
یا معادل باشند یکی را در نظر بگیرد.
در
بازی های حاوی عنصر شانس برای minmax
باید
بجای مقدار مورد انتظار استفاده کنیم.
پیچیدگی
minmax
در
حالت شانسی که نمیدانیم عنصر شانس به چه
ترتیبی ظاهر میشود O(b^m
n^m) است
که n
تعداد
حالات شانس است بنابراین عمق کمتری را
میتوانیم بگردیم.
اگر
برنامه از قبل بداند مقادیر عنصر شانس به
چه ترتیبی ظاهر میشوند مساله مشابه مین
مکس عادیست.
مقدار
تابع Eval
تخمینی
از موفق بودن مورد انظار گرههای یک پیکربندی
خاص است.
اگر
در هرس آلفا بتا بجای جستجوی اول عمق از
جستجوی اول سطح استفاده کنیم کارایی آن
در حد مین مکس پایین میآید.
چیزهایی
که باید از کتاب خوانده شود:بازی
با مجموع صفر.
تعریف
های بازی ها.
تعریفهای
Min
Max. پیاده
سازی Minmax.
الگوریتم
هرس آلفا بتا.
تعریف
تابع EVAL.
روشهای
پایان دادن به جستجو(cutting
of search). وضعیت
غیرساکن و اثر افق.
بسط
یکتا.
هرس
پیشرو.
بازی
های شامل عنصر شانس.
هیچ نظری موجود نیست:
ارسال یک نظر