بازی ها: حالتی از محیطهای چند عاملی را نشان می دهند که:
þ هر عامل نیاز به در نظر گرفتن سایر عاملها و چگونگی تأثیر آنها دارد
þ تمایز بین محیطهای چند عامل رقابتی و همکار
þ محیطهای رقابتی، که در آنها اهداف عاملها با یکدیگر برخورد دارند، منجر به مسئله های رقابتی میشود که به عنوان بازی شناخته میشوند
تصمیمات کامل در بازیهای دونفره(ترسیم درخت بطور کامل):
اگر به آن به عنوان یک مسئله جستجو نگاه شود، جستجو برای دنبالهای از حرکات که منتهی به حالت پایانی میشد (مطابق با تابع سودمندی)، و سپس پیشروی و ساخت اولین حرکت در دنباله بود.
با توجه به اینکه حرکت MIN غیرقابل پیش بینی است
بنابراین MAX باید استراتژیای را بیابد که به یک حالت پایانی برنده بدون توجه به عملکرد MIN منجر شود، که این استراتژی شامل حرکات درست برای MAX برای هر حرکت ممکن از MIN میباشد.
مزایای هرس آلفا-بتا
مزایای آلفا-بتا به مرتبهای که در آن گرههای فرزندی آزمایش شدهاند، برمیگردد.
1) اگر انتخاب فرزند بصورت تصادفی انتخاب شود تعداد کل گره ها برابر O(b 3d/4) است و در بازی شطرنج ، یک تابع مرتبسازی خوب نتیجه را به حالت بهتر O(b d/2) سوق میدهد.
2) یعنی پیچیدگی O(b/log b) d یعنی O(b)d/2 میباشد.
3) رهیافت مشهور دیگر انجام جستجوی عمیقکننده تکراری است.
4) فاکتور انشعاب مؤثر به جای b برابر با جذرb خواهد بود
5) پیش بینی آن نسبت به minimax دو برابر است
دانلود پاورپوینت تئوری بازیها- 46 اسلاید