فصل 5

تئوری بازی

1. فصل اول هوش مصنوعی Artificial Intelligence
2. فصل دوم عامل های هوشمند
3. فصل سوم حل مسائل توسط جستجو
4. فصل چهارم روش‌های جستجو آگاهانه
5. فصل 5 تئوری بازی
6. فصل ششم عامل‌هاییکه به طور منطقی استدلال می‌‌کنند
7. فصل هفتم منطق مرتبه اول
8. فصل هشتم استنتاج در منطق مرتبه اول
9. فصل نهم برنامه‌ریزی
10. فصل دهم عدم قطعیت

 

 

 

بازی‌ها در نقش مسائل جستجو

رقابت انتزاعی، که در بازی‌های صفحه‌ای دیده می‌شود، موجب شده تا تئوری بازی جزء تحقیقات AI قرار بگیرد.

وضعیت بازی برای بازنمایی آسان است و عامل‌ها معمولاً به تعداد کمی از عملیات محدود می‌شوند.

دلایلی که محققین قدیم، شطرنج را به‌عنوان موضوعی در AI برگزیدند:

• بازی شطرنج کامپیوتری اثباتی بر وجود ماشینی است که اعمال هوشمندانه‌ای را انجام می‌دهند.
• سادگی قوانین
• وضعیت دنیا کاملاً برای برنامه شناخته شده است. (بازنمایی بازی به عنوان یک جستجو از طریق فضای موقعیت‌های ممکن بازی، ساده است.)
• پیچیدگی بازی‌ها، به طور کامل نوعی از عدم قطعیت را معرفی می‌کنند.
• عدم قطعیت به علت وجود اطلاعات گم شده رخ نمی‌دهد، اما به علت اینکه فرد زمانی برای محاسبه دقیق نتایج حرکت ندارد عدم قطعیت بوجود می‌آید.
• در این مورد، فرد بر اساس تجربیات گذشته می‌تواند بهترین حدس را بزند.
• تصمیمات کامل در بازی‌های دونفره:
• مورد کلی از یک بازی با دو بازیکن را در نظر می‌گیریم که آن را MIN,MAX می‌نامیم.

یک بازی به طور رسمی می‌تواند به عنوان نوعی از مسئله جستجو به همراه قسمت‌های زیر تعریف شود:

• حالت اولیه شامل مکان صفحه وتعیین نوبت حرکت هر بازیکن است.
• مجموعه‌ای از عملگرها که حرکات صحیح را که بازیکن می‌تواند انجام دهد، تعیین می‌کند.
• آزمون پایانی زمان بازی را تعیین می‌کند. حالاتی را که بازی درآنها به پایان رسیده است حالات پایانی نامیده می‌شوند.
• تابع سودمندی (تابع امتیاز payoff) که مقدار عددی برای نتیجه بازی را تعیین می‌کند.

اگر به آن به عنوان یک مسئله جستجو نگاه شود، جستجو برای دنباله‌ای از حرکات که منتهی به حالت پایانی می‌شد (مطابق با تابع سودمندی)، و سپس پیشروی و ساخت اولین حرکت در دنباله بود.

اما حرکات MIN غیر قابل پیش‌بینی است؛

بنابراین:

MAX باید استراتژی‌ای را بیابد که به یک حالت پایانی برنده بدون توجه به عملکرد MIN منجر شود، که این استراتژی شامل حرکات درست برای MAX برای هر حرکت ممکن از MIN می‌باشد.

الگوریتم MINMAX به منظور تعیین استراتژی بهینه برای MAX طراحی شده است و از این رو می‌توان بهترین حرکت را تصمیم‌‌گیری کرد. الگوریتم شامل 5 مرحله است:

1. تولید درخت کامل بازی، تمام راه تا مراحل پایانی
2. درخواست تابع سودمندی برای هر حالت پایانی به منظور بدست آوردن مقدارش.
3. از سودمندی حالات پایانی به منظور تعیین سودمندی گره‌ها یک مرحله بالاتر دردرخت جستجو استفاده کنید.
4. بررسی مقادیر را از گره‌های برگی تا ریشه، یک لایه در هر لحظه، ادامه دهید.
5. احتمالاً مقادیر به بالای درخت می‌رسند، MAX حرکتی را انتخاب می‌کند که به بالاترین مقدار منتهی می‌شود.

اگر:

m: حداکثر عمق درخت،

b: تعداد حرکات قانونی در هر نقطه،

آنگاه:

زمان پیچیدگی الگوریتم minimax ، O(bm) است.

الگوریتم یک جستجو عمقی است.

تصمیمات ناقص:

الگوریتم  minimax  فرض می‌کند که برنامه زمان لازم برای جستجوی تمامی راه‌های ممکن وضعیت‌های پایانی را دارد که این فرض معمولاً عملی نیست.

الگوریتم مینی‌ماکس،  به دو راه تغییر یابد:

• تابع سودمندی با تابع ارزیابی EVAL جایگزین شود.
• آزمون پایانی با آزمون قطع CUTOFF-TEST جایگزین گردد.

تابع ارزیابی:

تابع ارزیابی تخمینی از سودمندی مورد انتظار بازی را ازموقعیت داده شده برمی‌گرداند.

واضح است که ارائه یک برنامه بازی بی نهایت به کیفیت تابع ارزیابی بستگی دارد.

چگونه به طور دقیق کیفیت را می‌توان اندازه گرفت؟

1. تابع ارزیابی با تابع سودمندی در مورد حالت پایانی باید به توافق برسند.
2. نباید زیاد طول بکشد! (اگر پیچیدگی را محدود نکنیم minimax به عنوان یک زیربرنامه فراخوانی می‌شود و مقدار دقیق وضعیت محاسبه می‌شود.) از این رو، معامله‌ای بین صحت تابع ارزیابی و هزینه زمان آن وجود دارد.
3. تابع ارزیابی باید به درستی شانس‌های واقعی برای برد را منعکس کند.

تابع ارزیابی فرض می‌گیرد که مقدار هر مهره می‌تواند به طور مستقل از دیگر مهره‌ها روی صفحه قضاوت شود. این نوع از تابع ارزیابی، تابع خطی وزن دار نامیده می‌شود.

این تابع می‌تواند به صورتی ذکر شود که Wها وزن ها هستند و fها اعداد هر نوع مهره روی صفحه خواهند بود.

قطع جستجو:

صریح‌ترین رهیافت برای کنترل میزان جستجو قراردادن محدودیتی برای داشتن یک عمق ثابت است، بنابراین تست قطع برای تمام گره‌ها در زیر عمق d موفق می‌شود. عمق طوری انتخاب می‌شود که میزان زمان استفاده شده از آنچه که قوانین بازی اجازه می‌دهد تجاوز نکند.

زمانی که، وقت تمام می‌شود، برنامه حرکت انتخابی توسط عمیق‌ترین جستجوی کامل شده را برمی‌گرداند.

به دلیل تخمینی بودن توابع ارزیابی این رهیافتها می‌توانند نتایج ناخوشایندی را به همراه داشته باشند.

تابع ارزیابی فقط باید برای مواقعی به کاربرده شود که خاموش هستند، یعنی اینکه تفاوتهای چشم‌گیر در مقدار، در آینده نزدیک بعید به نظر می‌رسد.

این جستجوی فوق العاده جستجوی خاموش نامیده می‌شود.

مسئله افقی (horizonproblem): رخ سیاه مانع از حرکت وزیر سفید به حالت افقی شده است و این موقعیت به نفع سیاه است. در حالی که برگ برنده در دست سفید است.

هرس آلفا-بتا:

هرس درخت جستجو:

پردازش حذف شاخه‌ای از درخت جستجو، با در نظر داشتن و بدون آزمایش، هرس درخت جستجو نامیده می‌شود.

زمانی که این تکنیک برای یک درخت minimax استاندارد، به کار برده می‌شود، حرکت مشابهی همانطور که minimax انجام می‌داد، برمی‌گرداند؛ اما شاخه‌هایی که در تصمیم‌ نهایی دخالتی ندارند را هرس می‌کند.

جستجوی minimax عمقی است، بنابراین، در هر لحظه، باید گره‌هایی در نظر گرفته شوند که در طول یک مسیر مجزا در درخت هستند.

α مقدار بهترین انتخابی باشد که تا کنون در طول مسیر برای MAX پیدا شده است. و β مقدار بهترین (به طور مثال، پایین‌ترین مقدار) انتخابی باشد که در طول مسیر تا این لحظه برای MIN پیدا شده است.

درخت جستجوی آلفا-بتا:

این درخت، مقدار α و β را همچنانکه جلو می‌رود، به روز درمی‌آورد، و زیر درخت را هرس می‌کند (فراخوانی بازگشتی را قطع می‌کند) به محض اینکه معلوم می‌شود که این زیر درخت بدتر از مقدار α یا β جاری است.

مزایای هرس آلفا-بتا

مزایای آلفا-بتا به مرتبه‌ای که در آن گره‌های فرزندی آزمایش شده‌اند، برمی‌گردد.

پیچیدگی O(b/log b)d می‌باشد.

• در عمل، یک تابع ساده مرتب‌کننده شما را به نتیجه بهترین حالت بر خلاف نتیجه تصادفی سوق می‌دهد.
• رهیافت مشهور دیگر انجام جستجوی عمیق‌کننده تکراری و استفاده از مقادیر backed-up از یک تکرار برای تعیین ترتیب جانشین‌ها در تکرار بعدی است.

نتایج بازی‌ها نیز قابل ملاحظه هستند (و در حقیقت، مسائل جستجو در حالت کلی) و باید به صورت یک مدل درخت مطلوب فرض شوند تا نتایجشان را به دست آورند.

بازی‌هایی که شامل عنصر شانس هستند:

تخته نرد یک بازی عمومی است که شانس و مهارت را با هم ترکیب می‌کند.

تاس‌های سفید 5-6، چهار حرکت زیر را می‌تواند انجام دهد:

(16-10 و 10-5) و (24-19 و 11-5) و (11-5 و 10-5) و (16-11 و 11-5)

درخت بازی در تخته نرد باید شامل گره‌های شانس برای گره‌های MIN و MAX‌ باشد.

مرحله بعدی فهم چگونگی ساخت تصمیمات صحیح است.

محاسبه مقادیر انتظاری گره‌ها، صریح است. برای گره‌های پایانی، از تابع سودمندی مانند بازیهای قطعی استفاده می‌کنیم.

با پیشروی در درخت جستجو به اندازه یک مرحله، به یک گره شانس برخورد می‌کنیم.

اگر ما فرض کنیم که S(C,d_i) مجموعه موقعیت‌های تولید شده توسط اعمال حرکات قانونی برای پرتاب P(d_i) در موقعیت C باشد، می‌تواند مقدار expectimax از ‍C را با استفاده از فرمول زیر محاسبه نمود:

Expectimax (c)=∑_I P(d_i) max_sε S(c,d_i) (utility(s))

این فرمول، سودمندی مورد انتظار در موقعیت c را با فرض بهترین بازی ارائه می‌دهد.

ارزیابی موقعیت در بازی‌ها با گره‌های شانس:

حضور گره‌های شانس بدین معناست که باید در مورد آنچه که به معنای مقادیر ارزیابی است، دقیق بود.

اگر ما تغییری را در مقیاس مقادیر ارزیابی ایجاد کنیم، برنامه در مجموع به طور متفاوت رفتار می‌کند.

پیچیدگی:

بدلیل اینکه expectiminimax تمام دنباله‌های پرتاب تاس را در نظر می‌گیرد، زمانی معادل O(bmnm) می‌برد، که n تعداد پرتابهای محدود است.

مزیت آلفا- بتا، با داشتن بهترین بازی نادیده گرفتن پیشرفت‌ها در آینده است که احتمال وقوعشان کم است.

در بازیهای به همراه تاس، دنباله‌های محتملی از حرکات وجود ندارد، چون برای آن حرکاتی که باید انجام بگیرند، ابتدا تاس باید به روش درستی پرتاب شود تا آن حرکات منطقی شوند.

اگر بگوئیم که تمام مقادیر سودمندی بین 1+ و 1-  هستند، سپس مقدار گره‌های برگی محدود می‌شوند و در عوض‌ ما می‌توانیم حد بالایی روی مقدار گره شانسی بدون توجه به فرزندانش قرار دهیم.