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