پاورپوینت جستجوی خصمانه

بخشی از پاورپوینت

اسلاید 1 :

فصل ششم

جستجوی خصمانه

اسلاید 2 :

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

اسلاید 3 :

بازیها
تعریف مساله یک بازی دونفره (MIN-MAX):
S0: حالت شروع
Player(s): در حالت s نوبت کدام بازیکن است؟
Actions(s): مجموعه حرکتهای معتبر در یک حالت
Result(s,a): مدل گذر؛ از یک حالت با یک حرکت به چه حالتی میرویم؟
Terminal-Test(s): تست پایانی؛ وقتی بازی تمام میشود true برمیگرداند.
Utility(s,p): تابع سودمندی (هدف یا پاداش)؛ مقدار سودبردن بازیکن p در حالت پایانی s
بازیها محیطهای چندعاملی و رقابتی هستند.
بازیهای با مجموع امتیاز صفر
بازیهای با اطلاعات دقیق (قطعی، رعایت کننده نوبت و دونفره)
بازیهای احتمالی
بازیهای با اطلاعات ناقص

اسلاید 4 :

درخت MIN-MAX
بازيکن (MAX) به دنبال انتخاب بهترين حالت یعنی بیشینه کردن تابع سودمندی است.
حريف (MIN) به دنبال انتخاب بهترين موقعيت برای خودش يا بدترين وضعيت برای بازيکن یعنی کمینه کردن تابع سودمندی است.

اسلاید 5 :

تصمیمهای بهینه در بازیها
بازیکن باید با فرض اینکه حریف بدون اشتباه تصمیم میگیرد، بازی کند.
MAX و MIN گره ای را انتخاب میکنند که به ترتیب بیشترین و کمترین مقدار MINIMAX را دارد؛ میتوان گفت MINIMAX تابع سود بازیکن MAX یا تابع هزینه بازیکن MIN است.

اسلاید 6 :

الگوریتم تصمیم گیری MINIMAX
کامل، بهینه، پیچیدگی زمانی O(bm) و پیچیدگی فضایی O(bm)

اسلاید 7 :

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

اسلاید 8 :

هرس آلفا بتا
انشعابهايي که در تصميم نهايي تأثير ندارند را جستجو نمیکنیم.
در هنگام بررسی گره n اگر بازیکن قبلاً در مسیر جستجو انتخابهای بهتری نسبت به n داشته باشد لزومی به بررسی و پیمایش زیردرخت با ریشه n نیست
آلفا: مقدار بهترين انتخاب در هر نقطه انتخاب در مسير Max تاکنون (حد پایین تضمین شده تابع سودمندی تا به اینجای جستجو)
بتا: مقدار بهترين انتخاب در هر نقطه انتخاب در مسير Min تاکنون (حد بالای تضمین شده تابع سودمندی تا به اینجای جستجو)

اسلاید 9 :

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

اسلاید 10 :

مثال: هرس آلفا-بتا
[-∞,3]
[-∞,+∞]

اسلاید 11 :

مثال: هرس آلفا-بتا
[-∞,3]
[-∞,+∞]

اسلاید 12 :

مثال: هرس آلفا-بتا
[3,+∞]
[3,3]

اسلاید 13 :

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

اسلاید 14 :

مثال: هرس آلفا-بتا
[-∞,2]
[3,14]
[3,3]
[-∞,14]

اسلاید 15 :

مثال: هرس آلفا-بتا
[−∞,2]
[3,5]
[3,3]
[-∞,5]

اسلاید 16 :

مثال: هرس آلفا-بتا
[2,2]
[−∞,2]
[3,3]
[3,3]

اسلاید 17 :

مثال: هرس آلفا-بتا
[2,2]
[-∞,2]
[3,3]
[3,3]

اسلاید 18 :

هرس آلفا-بتا

اسلاید 19 :

تصمیمهای بیدرنگ ناقص

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

اسلاید 20 :

توابع ارزیابی

تابع ارزيابی، تخمينی از سودمندی مورد انتظار بازی از يک موقعيت خاص میدهند.

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