جستجوی خصمانه در هوش مصنوعی

جستجوی خصمانه در هوش مصنوعی

اسلاید 1: 1هوش مصنوعيفصل ششمجستجوی خصمانه

اسلاید 2: 2هوش مصنوعي Artificial Intelligenceفهرستبازيها چيستند و چرا مطالعه ميشوند؟انواع بازيهاالگوريتم minimaxبازيهای چند نفرههرس آلفا-بتابازيهای قطعی با اطلاعات ناقصبازيهايي که حاوی عنصر شانس هستند

اسلاید 3: 3جستجوی خصمانهبازی ها چيستند و چرا مطالعه ميشوند؟بازيها حالتی از محيطهای چند عاملي هستندهر عامل نياز به در نظر گرفتن ساير عاملها و چگونگی تأثير آنها داردتمايز بين محيطهای چند عامل رقابتي و همکارمحيطهای رقابتی، که در آنها اهداف عاملها با يکديگر برخورد دارند، منجر به مسئله های خصمانه ميشود که به عنوان بازی شناخته ميشوندچرا مطالعه ميشوند؟قابليتهای هوشمندی انسانها را به کار ميگيرندماهيت انتزاعی بازی هاحالت بازی را به راحتی ميتوان نمايش داد و عاملها معمولا به مجموعه کوچکی از فعاليتها محدود هستند که نتايج آنها با قوانين دقيقي تعريف شده اند

اسلاید 4: 4جستجوی خصمانهانواع بازی هااطلاعات کاملاطلاعات ناقصقطعیتصادفیشطرنجريورسیتخته نردپوکر

اسلاید 5: 5جستجوی خصمانهيک نمونه بازی بازی دو نفره: Min و Maxاول Max حرکت ميکند و سپس به نوبت بازی ميکنند تا بازی تمام شوددر پايان بازی، برنده جايزه و بازنده جريمه ميشودبازی به عنوان يک جستجو:حالت اوليه: موقعيت صفحه و شناسه های قابل حرکتتابع جانشين:ليستی از (حالت,حرکت) که معرف يک حرکت معتبر استآزمون هدف:پايان بازی چه موقع است؟(حالتهای پايانه)تابع سودمندی: برای هر حالت پايانه يک مقدار عددی را ارائه ميکند. مثلا برنده(1+) و بازنده(1-)حالت اوليه و حرکات معتبر برای هر بازيکن، درخت بازی را برای آن بازی ايجاد ميکند

اسلاید 6: 6جستجوی خصمانهيک نمونه بازی الگوريتم؛بازيکن: انتخاب بهترين حالتحريف: انتخاب بهترين موقعيت برای خودش يا بدترين وضعيت برای بازيکنبازيکن: ماکزيمم حالتحريف: مينيمم حالت

اسلاید 7: 7جستجوی خصمانهالگوريتم minimax

اسلاید 8: 8جستجوی خصمانهيک نمونه بازی

اسلاید 9: 9جستجوی خصمانهيک نمونه بازی

اسلاید 10: 10جستجوی خصمانهيک نمونه بازی

اسلاید 11: 11جستجوی خصمانهيک نمونه بازی

اسلاید 12: 12جستجوی خصمانهيک نمونه بازی

اسلاید 13: 13جستجوی خصمانهالگوريتم minimaxکامل بودن: بله (اگر درخت محدود باشد)بهينگي: بلهپيچيدگي زمانی:پيچيدگی فضا:

اسلاید 14: 14جستجوی خصمانهبازيهای چند نفرهتخصيص يک بردار به هر گره، به جای يک مقداربازيهای چند نفره معولاً شامل اتحاد رسمی يا غير رسمي بين بازيکنان استاتحاد با پيشروی بازی ايجاد و از بين ميرودبازيکنان بطور خودکار همکاری ميکنند، تا به هدف مطلوب انحصاری برسند

اسلاید 15: 15جستجوی خصمانههرس آلفا-بتادر الگوريتم MaxMin:تعداد حالتهای بازی که بايد بررسی شوند، بر حسب تعداد حرکتها، توانی استراه حل: محاسبه تصميم الگوريتم، بدون ديدن همه گره ها امکانپذير استهرس آلفا-بتا:انشعابهايي که در تصميم نهايي تأثير ندارند را حذف ميکندآلفا: مقدار بهترين انتخاب در هر نقطه انتخاب در مسير Max تاکنونبتا: مقدار بهترين انتخاب در هر نقطه انتخاب در مسير Min تاکنونتعداد گره هايي که بايد بررسی شوند به تقليل ميابدفاکتور انشعاب مؤثر به جای b برابر با جذرb خواهد بودپيش بيني آن نسبت به minimax دو برابر است

اسلاید 16: 16جستجوی خصمانههرس آلفا-بتاگره n که هر جای درخت ميتواند باشد، بررسي ميشوداگر بازيکن انتخاب بهتری داشته باشددر گره والد nيا هر انتخاب بهتری تا کنونn هيچوقت در بازی واقعی قابل دسترس نخواهد بوددر نتيجه n هرس ميشود

اسلاید 17: 17جستجوی خصمانهمثال: هرس آلفا-بتا[-∞, +∞][-∞,+∞]محدوده مقادير ممکن

اسلاید 18: 18جستجوی خصمانهمثال: هرس آلفا-بتا[-∞,3][-∞,+∞]

اسلاید 19: 19جستجوی خصمانهمثال: هرس آلفا-بتا[-∞,3][-∞,+∞]

اسلاید 20: 20جستجوی خصمانه[3,+∞][3,3]

اسلاید 21: 21جستجوی خصمانهمثال: هرس آلفا-بتا[-∞,2][3,+∞][3,3]این گره برایMax مناسب نيست

اسلاید 22: 22جستجوی خصمانهمثال: هرس آلفا-بتا[-∞,2][3,14][3,3][-∞,14],

اسلاید 23: 23جستجوی خصمانهمثال: هرس آلفا-بتا[−∞,2][3,5][3,3][-∞,5],

اسلاید 24: 24جستجوی خصمانهمثال: هرس آلفا-بتا[2,2][−∞,2][3,3][3,3]

اسلاید 25: 25جستجوی خصمانهمثال: هرس آلفا-بتا[2,2][-∞,2][3,3][3,3]

اسلاید 26: 26جستجوی خصمانهبازيهای قطعي با اطلاعات ناقصمعايب الگوريتم های پيشينالگوريتم minimax کل فضای جست و جوی بازی را توليد ميکندالگوريتم آلفا-بتا با وجود هرس درخت، اما کل مسير حالتهای پايانه، حداقل برای بخشي از فضای حالت، بايد جست و جو شوداين عمق عملي نيست، زيرا حرکات بايد در زمانی معقول انجام شودشانون(1950)برای کمتر شدن زمان جست و جو و اعمال تابع ارزيابي اکتشافی به حالتهای جستجو، بهتر است از گره های غير پايانه به گره های پايانه پرداخته شود

اسلاید 27: 27جستجوی خصمانهبازيهای قطعي با اطلاعات ناقصدر شانون, minimax و آلفا-بتا به دو روش بطور متناوب عمل ميکنندجايگزيني تابع سودمندی با تابع ارزيابی اکتشافی بنام EVALتخمينی از سودمندی موقعيت ارائه ميکندجايگزين تست پايانه با تست توقفتصميم ميگيرد EVAL چه موقع اعمال شود

اسلاید 28: 28جستجوی خصمانهتابع ارزيابي اکتشافی EVALتابع ارزيابی، ارائه تخمينی از سودمندی مورد انتظار بازی از يک موقعيت خاصتوابع اکتشافی، تخمينی از فاصله تا هدف را بر ميگرداندنداغلب توابع ارزيابي، خواص گوناگونی از حالتها را محاسبه ميکنندخواص روی هم رفته، کلاسهای هم ارزی يا دسته های مختلفی از حالتها را تعريف ميکنندحالتهای هر دسته، برای تمام خواص مقدار يکسانی دارندهر دسته حاوی چند حالت است کهموجب برنده شدنموجب رسم شدنمنجر به باختنتابع ارزيابی نميداند کدام حالت منجر به چه چيزی ميشود، اما ميتواند مقداری برگرداند که تناسب حالتها را با هر نتيجه نشان دهد

اسلاید 29: 29جستجوی خصمانهEval(s) = w1 f1(s) + w2 f2(s) + … + wnfn(s)مثال: تابع EVALاغلب توابع ارزيابی, مقدار عددی جداگانه ای برای هر خاصيت محاسبه، سپس آنها را ترکيب ميکنند تا مقدار کل بدست آيدمثال در تابع بازی شطرنج: تعداد هر نوع قطعه در صفحه مقادير آن قطعات(1 برای پياده، 3 برای اسب يا فيل،5 برای رخ و ...)

اسلاید 30: 30جستجوی خصمانهمثال: تابع EVALب) سفيد حرکت ميکندالف) سفيد حرکت ميکندالف) سياه، مزيت اسب و دو پياده دارد و بازي را ميبردب) پس از اينکه سفيد، وزير را در اختيار ميگيرد، سياه ميبازدارزيابی تابع EVAL از مقدار پيروزی در دو موقعيت کاملا متفاوت

اسلاید 31: 31جستجوی خصمانهاثر افقوقتی بوجود مي آيد که برنامه با اثری از رقيب مواجه شود که منجر به خرابی جدی گشته و اجتناب پذير استمثال: شکل مقابل؛سياه در اصل جلوست، اما اگر سفيد پياده اش را از سطر هفتم به هشتم ببرد، پياده به وزير تبديل ميشود و موقعيت برد برای سفيد بوجود مي آيد

اسلاید 32: 32جستجوی خصمانهبازيهايي که حاوی عنصر شانس هستندشانسشانسپايانه