بخشی از پاورپوینت
اسلاید 1 :
هوش مصنوعی Artificial Intelligence
اسلاید 2 :
فصل ششم: جست و جوی خصمانه
تئوری بازی
بازیهای دو نفره
الگوریتم جستجوی minimax
هرس کردن آلفا-بتا
بازی های حاوی عنصر شانس
اسلاید 3 :
رقابت انتزاعي، که در بازيهاي صفحهاي ديده ميشود، موجب شده تا تئوري بازي جزء تحقيقات AI قرار بگيرد.
وضعيت بازي براي بازنمايي آسان است و عاملها معمولاً به تعداد کمي از عمليات محدود ميشوند.
بازيها در نقش مسائل جستجو
اسلاید 4 :
دلايلي که محققين قديم، شطرنج را بهعنوان موضوعي در AI برگزيدند:
بازي شطرنج کامپيوتري اثباتي بر وجود ماشيني است که اعمال هوشمندانهاي را انجام ميدهند.
سادگي قوانين
وضعيت دنيا کاملاً براي برنامه شناخته شده است. (بازنمايي بازي به عنوان يک جستجو از طريق فضاي موقعيتهاي ممکن بازي، ساده است.)
تئوری بازی در AI
اسلاید 5 :
پيچيدگي بازيها، به طور کامل نوعي از عدم قطعيت را معرفي ميکنند.
عدم قطعيت به علت وجود اطلاعات گم شده رخ نميدهد، اما به علت اينکه فرد زمان لازم را براي محاسبه دقيق نتايج حرکت، در اختیار ندارد عدم قطعيت بوجود ميآيد.
در اين مورد، فرد بر اساس تجربيات گذشته ميتواند بهترين حدس را بزند.
اسلاید 6 :
تصميمات کامل در بازيهاي دونفره:
يک بازي با دو بازيکن را در نظر ميگيريم که آن را MIN,MAX ميناميم.
اول MAX حرکت می کند.
بازی های تصمیم گیری بهینه
اسلاید 7 :
يک بازي به طور رسمي ميتواند به عنوان نوعي از مسئله جستجو به همراه قسمتهاي زير تعريف شود:
حالت اوليه شامل مکان صفحه و شناسه هایی است که بازيکنان باید حرکت دهند.
تابع جانشین: لیستی از جفتهای حرکت صحيح که بازيکن ميتواند انجام دهد، و حالت حاصل را تعيين ميکند.
آزمون پايانه زمان پایان بازي را تعيين ميکند. حالاتي را که بازي درآنها به پايان رسيده است حالات پايانه ناميده ميشوند.
تابع سودمندي (تابع پاداش یا هدف) که مقدار عددي براي نتيجه بازي را تعيين ميکند.
اسلاید 8 :
اگر به آن به عنوان يک مسئله جستجو نگاه شود، جستجو براي دنبالهاي از حرکات که منتهي به حالت پاياني ميشد (مطابق با تابع سودمندي)، و سپس پيشروي و ساخت اولين حرکت در دنباله بود.
اما حرکات MIN غير قابل پيشبيني است؛
بنابراين:
MAX بايد استراتژياي را بيابد که به يک حالت پاياني برنده بدون توجه به عملکرد MIN منجر شود، که اين استراتژي شامل حرکات درست براي MAX براي هر حرکت ممکن از MIN ميباشد.
اسلاید 9 :
درخت بازی
اسلاید 11 :
الگوريتم minimax
اسلاید 12 :
اگر:
m: حداکثر عمق درخت،
b: تعداد حرکات قانوني در هر نقطه،
آنگاه:
پيچيدگي زمانی الگوريتم minimax ، O(bm) است.
الگوريتم يک جستجو عمقي است.
پیچیدگی الگوريتم minimax
اسلاید 13 :
الگوريتم minimax به منظور تعيين استراتژي بهينه براي MAX طراحي شده است و از اين رو ميتوان بهترين حرکت را تصميمگيري کرد. الگوريتم شامل 5 مرحله است:
1. توليد درخت کامل بازي، تمام راه تا مراحل پاياني
2. درخواست تابع سودمندي براي هر حالت پاياني به منظور بدست آوردن مقدارش.
3. از سودمندي حالات پاياني به منظور تعيين سودمندي گرهها يک مرحله بالاتر دردرخت جستجو استفاده کنيد.
4. بررسي مقادير را از گرههاي برگ تا ريشه، يک لايه در هر لحظه، ادامه دهيد.
5. احتمالاً مقادير به بالاي درخت ميرسند، MAX حرکتي را انتخاب ميکند که به بالاترين مقدار منتهي ميشود.
مراحل الگوريتم minimax
اسلاید 14 :
جست و جوی minimax
اسلاید 15 :
هرس درخت جستجو:
پردازش حذف شاخهاي از درخت جستجو، با در نظر داشتن و بدون آزمايش، هرس درخت جستجو ناميده ميشود.
زماني که اين تکنيک براي يک درخت minimax استاندارد، به کار برده ميشود، حرکت مشابهي همانطور که minimax انجام ميداد، برميگرداند؛ اما شاخههايي که در تصميم نهايي دخالتي ندارند را هرس ميکند.
هرس کردن آلفا-بتا:
اسلاید 16 :
جستجوي minimax عمقي است، بنابراين، در هر لحظه، بايد گرههايي در نظر گرفته شوند که در طول يک مسير مجزا در درخت هستند.
α مقدار بهترين انتخابي باشد که تا کنون در طول مسير براي MAX پيدا شده است. و β مقدار بهترين (به طور مثال، پايينترين مقدار) انتخابي باشد که در طول مسير تا اين لحظه براي MIN پيدا شده است.
هرس کردن آلفا-بتا:
اسلاید 17 :
درخت جستجوي آلفا-بتا:
اين درخت، مقدار α و β را همچنانکه جلو ميرود، به روز درميآورد، و زير درخت را هرس ميکند (فراخواني بازگشتي را قطع ميکند) به محض اينکه معلوم ميشود که اين زير درخت بدتر از مقدار α يا β جاري است.
هرس کردن آلفا-بتا:
اسلاید 18 :
هرس کردن آلفا-بتا:
اسلاید 19 :
الگوريتم minimax فرض ميکند که برنامه زمان لازم براي جستجوي تمامي راههاي ممکن وضعيتهاي پاياني را دارد که اين فرض معمولاً عملي نيست.
الگوريتم مينيماکس، به دو راه تغيير يابد:
تابع سودمندي با تابع ارزيابي EVAL جايگزين شود.
آزمون پاياني با آزمون قطع CUTOFF-TEST جايگزين گردد.
تصميمات ناقص:
اسلاید 20 :
تابع ارزيابي:
تابع ارزيابي تخميني از سودمندي مورد انتظار بازي را ازموقعيت داده شده برميگرداند.
واضح است که ارائه يک برنامه بازي بي نهايت به کيفيت تابع ارزيابي بستگي دارد.
تصميمات ناقص:
