1
هوش مصنوعی
جستجوی خصمانه
2
هوش مصنوعی Artificial Intelligence
فهرست
بازیها چیستند و چرا مطالعه میشوند؟
انواع بازیها
الگوریتم minimax
بازیهای چند نفره
هرس آلفا-بتا
بازیهای قطعی با اطلاعات ناقص
بازیهایی که حاوی عنصر شانس هستند
3
جستجوی خصمانه
بازی ها چیستند و چرا مطالعه میشوند؟
بازیها حالتی از محیطهای چند عاملی هستند
هر عامل نیاز به در نظر گرفتن سایر عاملها و چگونگی تاثیر آنها دارد
تمایز بین محیطهای چند عامل رقابتی و همکار
محیطهای رقابتی، که در آنها اهداف عاملها با یکدیگر برخورد دارند، منجر به مسئله های خصمانه میشود که به عنوان بازی شناخته میشوند
چرا مطالعه میشوند؟
قابلیتهای هوشمندی انسانها را به کار میگیرند
ماهیت انتزاعی بازی ها
حالت بازی را به راحتی میتوان نمایش داد و عاملها معمولا به مجموعه کوچکی از فعالیتها محدود هستند که نتایج آنها با قوانین دقیقی تعریف شده اند
4
جستجوی خصمانه
انواع بازی ها
اطلاعات کامل
اطلاعات ناقص
قطعی
تصادفی
شطرنج
ریورسی
تخته نرد
پوکر
5
جستجوی خصمانه
یک نمونه بازی
بازی دو نفره: Min و Max
اول Max حرکت میکند و سپس به نوبت بازی میکنند تا بازی تمام شود
در پایان بازی، برنده جایزه و بازنده جریمه میشود
بازی به عنوان یک جستجو:
حالت اولیه: موقعیت صفحه و شناسه های قابل حرکت
تابع جانشین:لیستی از (حالت,حرکت) که معرف یک حرکت معتبر است
آزمون هدف:پایان بازی چه موقع است؟(حالتهای پایانه)
تابع سودمندی: برای هر حالت پایانه یک مقدار عددی را ارائه میکند. مثلا برنده(1+) و بازنده(1-)
حالت اولیه و حرکات معتبر برای هر بازیکن، درخت بازی را برای آن بازی ایجاد میکند
6
جستجوی خصمانه
یک نمونه بازی
الگوریتم؛
بازیکن: انتخاب بهترین حالت
حریف: انتخاب بهترین موقعیت برای خودش یا بدترین وضعیت برای بازیکن
بازیکن: ماکزیمم حالت
حریف: مینیمم حالت
7
جستجوی خصمانه
الگوریتم minimax
8
جستجوی خصمانه
یک نمونه بازی
9
جستجوی خصمانه
یک نمونه بازی
10
جستجوی خصمانه
یک نمونه بازی
11
جستجوی خصمانه
یک نمونه بازی
12
جستجوی خصمانه
یک نمونه بازی
13
جستجوی خصمانه
الگوریتم minimax
کامل بودن: بله (اگر درخت محدود باشد)
بهینگی: بله
پیچیدگی زمانی:
پیچیدگی فضا:
14
جستجوی خصمانه
بازیهای چند نفره
تخصیص یک بردار به هر گره، به جای یک مقدار
بازیهای چند نفره معولاً شامل اتحاد رسمی یا غیر رسمی بین بازیکنان است
اتحاد با پیشروی بازی ایجاد و از بین میرود
بازیکنان بطور خودکار همکاری میکنند، تا به هدف مطلوب انحصاری برسند
15
جستجوی خصمانه
هرس آلفا-بتا
در الگوریتم MaxMin:
تعداد حالتهای بازی که باید بررسی شوند، بر حسب تعداد حرکتها، توانی است
راه حل: محاسبه تصمیم الگوریتم، بدون دیدن همه گره ها امکانپذیر است
هرس آلفا-بتا:
انشعابهایی که در تصمیم نهایی تاثیر ندارند را حذف میکند
آلفا: مقدار بهترین انتخاب در هر نقطه انتخاب در مسیر Max تاکنون
بتا: مقدار بهترین انتخاب در هر نقطه انتخاب در مسیر Min تاکنون
تعداد گره هایی که باید بررسی شوند به تقلیل میابد
فاکتور انشعاب موثر به جای b برابر با جذرb خواهد بود
پیش بینی آن نسبت به minimax دو برابر است
16
جستجوی خصمانه
هرس آلفا-بتا
گره n که هر جای درخت میتواند باشد، بررسی میشود
اگر بازیکن انتخاب بهتری داشته باشد
در گره والد n
یا هر انتخاب بهتری تا کنون
n هیچوقت در بازی واقعی قابل دسترس نخواهد بود
در نتیجه n هرس میشود
17
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞, +∞]
[-∞,+∞]
محدوده مقادیر ممکن
18
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,3]
[-∞,+∞]
19
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,3]
[-∞,+∞]
20
جستجوی خصمانه
[3,+∞]
[3,3]
21
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,2]
[3,+∞]
[3,3]
این گره برایMax مناسب نیست
22
جستجوی خصمانه
مثال: هرس آلفا-بتا
[-∞,2]
[3,14]
[3,3]
[-∞,14]
,
23
جستجوی خصمانه
مثال: هرس آلفا-بتا
[−∞,2]
[3,5]
[3,3]
[-∞,5]
,
24
جستجوی خصمانه
مثال: هرس آلفا-بتا
[2,2]
[−∞,2]
[3,3]
[3,3]
25
جستجوی خصمانه
مثال: هرس آلفا-بتا
[2,2]
[-∞,2]
[3,3]
[3,3]
26
جستجوی خصمانه
بازیهای قطعی با اطلاعات ناقص
معایب الگوریتم های پیشین
الگوریتم minimax کل فضای جست و جوی بازی را تولید میکند
الگوریتم آلفا-بتا با وجود هرس درخت، اما کل مسیر حالتهای پایانه، حداقل برای بخشی از فضای حالت، باید جست و جو شود
این عمق عملی نیست، زیرا حرکات باید در زمانی معقول انجام شود
شانون(1950)
برای کمتر شدن زمان جست و جو و اعمال تابع ارزیابی اکتشافی به حالتهای جستجو، بهتر است از گره های غیر پایانه به گره های پایانه پرداخته شود
27
جستجوی خصمانه
بازیهای قطعی با اطلاعات ناقص
در شانون, minimax و آلفا-بتا به دو روش بطور متناوب عمل میکنند
جایگزینی تابع سودمندی با تابع ارزیابی اکتشافی بنام EVAL
تخمینی از سودمندی موقعیت ارائه میکند
جایگزین تست پایانه با تست توقف
تصمیم میگیرد EVAL چه موقع اعمال شود
28
جستجوی خصمانه
تابع ارزیابی اکتشافی EVAL
تابع ارزیابی، ارائه تخمینی از سودمندی مورد انتظار بازی از یک موقعیت خاص
توابع اکتشافی، تخمینی از فاصله تا هدف را بر میگرداندند
اغلب توابع ارزیابی، خواص گوناگونی از حالتها را محاسبه میکنند
خواص روی هم رفته، کلاسهای هم ارزی یا دسته های مختلفی از حالتها را تعریف میکنند
حالتهای هر دسته، برای تمام خواص مقدار یکسانی دارند
هر دسته حاوی چند حالت است که
موجب برنده شدن
موجب رسم شدن
منجر به باختن
تابع ارزیابی نمیداند کدام حالت منجر به چه چیزی میشود، اما میتواند مقداری برگرداند که تناسب حالتها را با هر نتیجه نشان دهد
29
جستجوی خصمانه
Eval(s) = w1 f1(s) + w2 f2(s) + … + wnfn(s)
مثال: تابع EVAL
اغلب توابع ارزیابی, مقدار عددی جداگانه ای برای هر خاصیت محاسبه، سپس آنها را ترکیب میکنند تا مقدار کل بدست آید
مثال در تابع بازی شطرنج:
تعداد هر نوع قطعه در صفحه
مقادیر آن قطعات(1 برای پیاده، 3 برای اسب یا فیل،5 برای رخ و …)
30
جستجوی خصمانه
مثال: تابع EVAL
الف) سیاه، مزیت اسب و دو پیاده دارد و بازی را میبرد
ب) پس از اینکه سفید، وزیر را در اختیار میگیرد، سیاه میبازد
ارزیابی تابع EVAL از مقدار پیروزی در دو موقعیت کاملا متفاوت
31
جستجوی خصمانه
اثر افق
وقتی بوجود می آید که برنامه با اثری از رقیب مواجه شود که منجر به خرابی جدی گشته و اجتناب پذیر است
مثال: شکل مقابل؛
سیاه در اصل جلوست، اما اگر سفید پیاده اش را از سطر هفتم به هشتم ببرد، پیاده به وزیر تبدیل میشود و موقعیت برد برای سفید بوجود می آید
32
جستجوی خصمانه
بازیهایی که حاوی عنصر شانس هستند
شانس
شانس
پایانه
پایان