تئوری های سازمانی پیشرفته (محیط خارجی)

صفحه 1:


صفحه 2:
فصل ‎ae‏ با[یها - مستموهاي رقابتي ۳ تلوري بازي ها ۱۳۲۲ ۲ 5< بلزي ها چه هستند و چبا مطلاعه میشجند؟ بازي ها: حللتي از محيطياي چند عاملي را نشان مي دهند که: 7 هر عامل نیاز به در نظر گرفتن سابر عاملها و چکونگی تأثیر آنها دارد تمایز بین محيطهاي چند عامل رقابتي و همکار محیطهای رقابتی. که در آنها اهداف عاملها با بکدیگر برخورد دارند. منجر به مسئله هاي رقابتی میشود که به عنوان بازي شناخته میشوند 

صفحه 3:
و چرا بازي ها مطالعه مي شوند : گ قابليتهاي هوشمندي انسانها را به کار میگیرند گماهیت انتزاعی بازی ها حالت بازي را به راحتي میتوان نمایش داد و عاملها معمولا به مجموعه كوجكي از فعالیتها محدود هستند که نتایج آنها با قوانین دقیقی تعریف شده اند به عنوان مثال: دلايلي که محققین قدیم. شطرنج را به‌عنوان موضوعي در 90) بر گزیدند: ؟ بازي شطرنج کامپيوتري اثباتي بر وجود ماشيني است که اعمال هوشمندانه‌اي را انجام می‌دهند. ا © سادكي قوانين > وضعيت دنيا كاملاً براي برنامه شناخته شده است. (بازنمايي بازي به عنوان يك جستجو از طریق فضاي موقعيت‌هاي ممکن بازي» ساده است.) 

صفحه 4:
فصل 596 با[یها - ادامه بيجيدكي بازيهاء به طورکامل نوعي از عدم قطعیت را معرفي مي‌کنند. عدم تعاس به علت وجود اطلاعات گم شده رخ نمي‌دهد. بلکه‌به علت اینکه فرد زماني براي محاسبه دقیق نتایج حرکت ندارد عدم قطعیت بوجود مي‌آید. در اين مورد. فرد بر اساس. مي تواند بهترين حدس را بزند. 

صفحه 5:
ee at ae eet 5 Minimax gj - ‏بازيها‎ -5 ea ‏فصل‎ يك نمونه بازي - يك بازي با دو بازيكن را در نظر ميكيريم كه آن ,1 ‎DID-DOX‏ ‏می‌فاههم‌سناست که هر یک از بازیکن ها . حرکت خود را در جهت افزایش برد خود ۳0 و نیز در جهت کاهش برد حریف (0) انجام مي دهد. - يس هميشه حركت با »© است. قبل از حركت گرافي از دید بازیکن رسم مي شود که بتواند بهترين حركت را انتخاب كند. بازي به عنوان یک جستجو: >مالت اوليه: موقعيت صفمه و شناسايي مركت مجاز > عملكرها؛ ليستي ‎(١‏ (مالت,حركت) كه معرف يك مركت معتبدٍ است > آزمون هدف: بايان بازي جه موقع است؟ (مالتهاي بايانه) > تابع سودمندي: براي هر هالت يايائه يك مقدار عددي زا ازائه ميكند. مثلاً: برنده(1+) و بازنده(1-) و مساوي(0) 

صفحه 6:
بهترین موقعیت براي ‎Pea Mg ae‏ وضعیت براي بازیکن 2۳2 belo] :واه Soe 5 9 x] 0 alata! MAX 29) man (0} Max) دنسي TERMINAL, vty حالت اولیه و حر کات معتبر براي هر بازیکن. درخت بازي را براي آن بازي ایجاد میکند 

صفحه 7:
فصل تند : تلوري بایها - تممیمات کامل تصمیمات کامل در بازي‌هاي دونفره(ترسیم درخت بطور کامل): اگر به آن به عنوان یک مسئله جستجو نگاه شود. جستجو براي دنباله‌اي از حرکات که منتهي به حالت پاياني مي‌شد (مطابق با تابع سودمندي)؛ و سپس پيشروي و ساخت اولین حرکت ذر دنباله بود. با توجه به اینکه حرکت 20160 غیرقابل پیش بيني است بنابرایین 600026 باید استراتژي‌اي را پیلبد که به یک حللت پايلني برنده بدون توجه به عملکرد 6210 منجر شود. که این استراتژي شامل حرکات درست براي 000916 براي هر حركت ممكن از 00100 مي باشد. 

صفحه 8:
Minimax att! ‏با[یها‎ 9 الكوريتم ‎O1D-DOX:‏ ‏به منظور تعیین استراتژي ‎dine‏ براي ‎DOX‏ طراحي شده است و از اینرو مي‌توان بیترین حرکت را تصمیم‌گيري کرد. الگوریتم شامل 5 مرحله است: 1. توليد درخت کامل بازي, تمام راه تا مراحل پاياني 2 درخواست تابع سودمندي براي هر حالت پاياني به منظور بدست آوردن مقدارش. 3. از سودمندي حالات پابلني‌به منظور تعیین سودمندي گره‌هایک مرحله بالاتر در درخت جستجو استفاده کنید. 4 بررسی مقادیر را از گره‌هاي برگی تا ربشه. یک لابه در هر لحظه. ادامه دهید. 5 احتمالاً مقادیربه بالاي درخت می‌رسند. (60() حرکتی را انتخاب مي‌کند که به بالاترین مقدار منتهي مي‌شود. 

صفحه 9:
فصل ‎ant‏ سم بآزيها - الكوريتم ‎‘Mintmax‏ ۷ LEN 1 © 5 0 ide J. This is the move a8 ‏ی‎ selected by ae value 

صفحه 10:
فصل ‎ant‏ سم با[یها - الکوریتم 11:12 ۷ تعناد حركات قانونودر هرنقطة. كا كامل بودن: بله (اكر درخت محدود باشد) كا بيينتي: بله لكا بيجيدكي زماني: الكوريتم (69) 0 . 00000000007 است. الگوريتم یک جستجو عمقي است. ‎Olbw) i Sn. 4‏ 

صفحه 11:
فصل مسج باژیها - اطلاعات تاقصل" 9 بازيهاي قطعي با اطلاعات ناقص (ترسیم درخت بطور ناقص): بهترین نتیجه ممکنه براي بازيكني است که گراف را کامل کرده است . استراتژي بازي براساس مسيرهايي از گراف که بهترین نتیجه را مي دهد. تعریف مي شوند لین تثوري در عمل براي بازيهليي که گراف آنها بسیار پرهزینه است استفاده نمي شود. براي مثال در بازي شطرنج: میانگین فاکتور انشعاب در حدود 35 بنابراین درخت جستجو در در اغلب بازیبا هر بازیکن تا 50 حرکتیا حدود 35 گره خواهد داشت پس اگر بخواهیم به این تئوري جنبه عمل دهیم باید سعي کنيم براساس گراف کوچک که بفشي از گراف اصلي محسوب مي شود استراتژي را تعیین کرد 

صفحه 12:
رد بازیها - اطلاعات تاقص 0" الگوریتم ۲ به دو راه تغییر یابد: لس تابع سودمندي با تابع ارزيابي اكتشافي 60069 جایگزین شود - تفميني از سودمندي موقعیت ارائه میکند لس آزمون پاباني با آزمون قطع بسح *ص) جایگزین گردد - تصمیم میگیرد ,006 چه موقع اعمال شود 

صفحه 13:
فصل سح با[یها - تابع ارزیاب = تابع ارزيابي اكتشافي: ‎Cudkatics @urcction‏ تابع ارزیلبی تخمینی از سودمندی مورد انتظار بازی را از یک موقعیت خاص برمی‌گرداند > توابع اکتشافي. تفميني از فاصله تا هدف را بر میکرداند ‎WOO 20‏ > (مامظ ‎ ‏واضح است که ارائه یک برنامه بازی بی نهایت به کیفیت تابع ارزیابی بستگی دارد ‏أ تابع ارزيابي نمیداند کدام مالت منم به چه چيزي ميشود. اما میتواند مقدازي بركرداند كه تناسب هالتها را با هر نتيجه را نشان دهد 

صفحه 14:
فصل ‎ail gi sell‏ تابع ارزيب جكونه به دقیق کیفیت تابع ارزباب را ان اندازه گر فت؟ 4 بع ارزیاب را مي‌نوان اندازه گر دز 3 . تابع ارزيابي با تابع سودمندي در مورد حالت پاباني باید به توافق برسند. . نبايد زياد طول بكشد! (اگر پيچيدگي را محدود نکنیم 6 به عنوان یک زبربرنامه فراخولني مي‌شود و مقدار دقیق وضعیت محاسبه مي‌شود.) از لین رو. معامله‌اي بین صحت تلبع ارزيلبي و هزینه زمان ‎co‏ ‏وجود دارد. تابع ارزيابي باید به درستي شانس‌هاي واقعي براي برد را منعکس کند. 

صفحه 15:
فصل ‎am‏ = بأزيها - تابع ارزياب فطي = تابع ارزیاب خطي (وزن دار) : تابع ارزياببي فرض مي‌گیرد که مقدار هر مهره مي‌تواند به طور مستقل از دیگر مهره‌ها روي صفحه قضاوت شود. این نوع از تابع ارزيابي, تابع خطي وزن دا نامیده می‌شود. ‎Eval(s) = w, f,(s) + w, f(s) + ...‏ + w,f,(s) ‏ها پارلمترهای‌سهم تلثیر گنار در ارزبلبي ین کحلات‎ ۶ singe yl ‏مد ها میزلیاهمینهر پارلمتر لوزر) در لیوا یابیرا‎ 

صفحه 16:
زى بازیها - قطع ‎gai‏ قطع جستجو: صریح ترین رهیافت براي کنترل میزان جستجو قراردادن محدوديتضي براي داشتن یک عمق ثابت است. بنابرلین تست قطع براي تمام گره‌ها در زیر عمق | ‎Gago‏ مي‌شود. عمق طوري انتخاب می‌شود که میزان زمان استفاده شده از آنچه که قوانین بازی اجازه می‌دهد تجاوز نکند. یک رهیافت قوی برای تعیین عمق 4: استفاده از جستجوي عمقي تکرار 3 ۳ شونده است زملني كه. مقت تمام مي شود. برنلمه حركت انتخلبي توسط عميق ترين جستجوي کامل شده را برمی گرداند. 

صفحه 17:
زک بازیها - بازيهاي هند نفره تخصیصر ی یک بزدابه هر گره .به جای یک مقدار ‎sla! Sole Yash lh‏ رسعى يا غير رسمى بين بازيكتنان است 0 اتجاه با پيشروي 0 بازیکتان بطور خودکار هتنکاری نیکنند. تا به هد ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‏)5.4.5( 0 کی الک اف )6.1.2( )4.2.3( )1.2.6( ‎ ‎ ‎ ‎ 

صفحه 18:
9 ‏ا‎ mies هرس ‎Alpha - Beta 263 —WT‏ فرض: یک برنامه خوب وجود دارد که مي تواند 1000 ‎Pruning,‏ ‏ثانیه انجام دهد در شطرن: خاکتور انشعاب - 35 مرکت پس مي توانیم 150000 براي هر حركت 150 ثانيه زمان مي برد موقعيت يوجود بباوريم با فاکتور انشعاب 35 يعني 3 تا جهار حر كت بازي را بيش بيني مي كند [] يك بازي مبتدي بازيكنان انساني متوسط 6 تا 8 حركت را پیش بيني مي کنند 

صفحه 19:
فصل شنلع: = با[یها - هرس الفا بت ‎a‏ هرس ‎Alpha - Beta 263 —WT‏ فرض: یک برنامه خوب وجود دارد که مي تواند 1000 ‎Pruning,‏ ‏ثانیه انجام دهد در شطرن: خاکتور انشعاب - 35 مرکت پس مي توانیم 150000 براي هر حركت 150 ثانيه زمان مي برد موقعيت يوجود بباوريم با فاكتور انشعاب 35 يعني 3 تا جهار حركت بازي را بيش بيني بازیکنان انساني متوسط 6 تا 8 حرکت را پیش بيني مي کنند 

صفحه 20:
زک بازیها - هرس الفا بتا هرس درخت جستجو: پردازش حذف شاخه‌ای از درخضت جستجو, با در نظر داشتسن و بدون آزمایش. هرس درخت جستجو نامیده مي‌شود. ( بصورت قطعي ) زملنی که لین تکنیک براي یک درخت ۳۳۲ استانداردسبه کار برده می‌شود. حرکت مشابهى همانطور كه 456 انجام مىداد. برمىكرداند؛ « شاخه‌هایی که در تصمیم نهایی دخالتي ندارند را هرس مي‌کند. 

صفحه 21:
- ‏تلو و مسال به‎ en as جستجوي ۷۵ عمقي است. بنابرلین. در هر لحظه. بلید گره‌هليي در نظر گرفته شوند که در طول یک مسیر مجزا در درخت هستند. 0 0 وس 

صفحه 22:
= a atts a-pruning افثآ ‏هرس‎ تا موقعي پ«فرزند « محسوب مي شود که ارزيابي آن بزرگتر (>..م) از باشد وموقعي که ‎max (F(X X-1))‏ > (رت) > )1 در این حالت دیگر نيازي به بررسي گره هاي مبررلابه بعد نمي باشد 

صفحه 23:
فصل ‎am‏ - با[یها - هرس الفا بت ۳ هرس تا 6-0۳111116 تا موقعي ,لافرزند ,لا محسوب مي شود که ارزيابي آن کوچکتراز ‎DID. Mag)‏ باشد و موقعي كه : ‎Fp)‏ $ (رن)] > ((1-رند ‎min (f (x4 ٠‏ دراين حالت ديكر نيازي به بررسي كره هاي رب,لابه بعد نمي باشد 

صفحه 24:


صفحه 25:
rs ۸۸۸ vith p= 6» 

صفحه 26:
۳ :_تنوزي بازيها - هرس الفا ۳ بو © عام : ‎eg x :‏ A هما << ‎oO‏ ‎a,‏ ‏30 ‎a‏ © 8 

صفحه 27:
cs eee 0 

صفحه 28:
:تلور بازیها 

صفحه 29:
5 = بازیها - مرس الق بتا 59 مثالي ديكر : MAX MIN 

صفحه 30:
5 = بازیها - مرس الق بتا 59 مثالي ديكر : MAX [~+,0-] /\ 23 

صفحه 31:
5 = بازیها - مرس الق بتا 59 مثالي ديكر : MAX foro] 3 

صفحه 32:
5 = بازیها - مرس الق بتا 59 مثالي ديكر : MAX ‏(ه+-]‎ 3 

صفحه 33:
سح باژیها - هرس الفا بتا = 

صفحه 34:
= a atts مثالي دیگر : MAX fe,aey/\ 23, < 14 MIN 

صفحه 35:
سح باژیها - هرس الفا بتا = مثالي دیگر : MAX 9/۱25 MIN 

صفحه 36:
سح باژیها - هرس الفا بتا = مثالي دیگر : MAX ech SS SE 2 

صفحه 37:
سح باژیها - هرس الفا بتا = مثالي دیگر : 

صفحه 38:
زک بازیها - هرس الفا بتا مزاياي هرس آلفا-بتا مزاياي آلفاجتا به مرتبه‌اي که در آن گره‌هاي فرزندي آزمایش شده‌اند. برمي‌گردد. 1) اگر انتخاب فرزند بصورت تصادفي انتخاب شود تعداد کل گره ها برابر ( ۹۷۹ 0() است و در بازي شطرنج . یک تلبع مرتب‌سازي خوب نتیجه را به حللت بهتر (۷ ۳)() سوق می‌دهد. 2 يعني پيچيدگي "۲ (۳/۳۷۳)) يعني ؟*(۳)() مي‌باشد. 3 رهیافت مشهور دیگر انجام جستجوي عمیق کننده تكراري است. 4 فاکتور انشعاب موّثر به جاي ۲ برابر با جذرط خواهد بود 5 پیش بینی آن نسبت به 56 دو برابر است 

صفحه 39:
فصل :لو با[یها -عامل شانس بازي‌هايي که عامل شانس دارند: در زندگي واقعي حوادث غیر قابل پیش بيني زيادي وجود دارند که ما را در شرایط غافلكيرانه اي قرار مي دهند 1 در بازيها اين حوادث غيرقابل ييش بيني را توسط عنصر تصادفي مانند تاس نشان مي دهند تخته نرد یک بازي عمومي است كه شانس و ميبارت را با هم تركيب مي كند. در اینجا تاسي توسط بازیکن () ريخته مي شود تا مجموعه اي از حرکتها که قابل انجام هستند ات گردد يعني نمي توان درخت کامل بازي را ترسیم کرد 

صفحه 40:
TERMINAL ff a4 ‏تاس‌هاي سفید 6-5 چپار حر کت زیر را مي‌تواند انجام دهد:‎ )5-11 ‏و 5-10) و (19-24 و 5-11) و (5-11 و 5-10) و (11-16 و‎ 16-10( 

صفحه 41:
فصل زک بازیها -عامل شانس * درخت بازي در تخته نرد باید شامل گره‌هاي شانس براي گره‌هاي 210 و 6 باشد. * مرحله بعدي فهم چگونگي ساخت تصمیمات صحیح است. * محاسبه مقادیر انتظاري گره‌ها. صریح است. براي گره‌هاي پاياني. از تابع سودمندي مانند بازيهاي قطعي استفاده مي‌کنيم. ۵ با پيشروي در درخت جستجو ‎ay‏ اندازه یک مرحله. به یک گره شانس برخوره مي كنيم 

صفحه 42:
زک بازیها -عامل شانس مثال : مي خواهيم حركتي از 62 ۰.. ,9) را انتخاب کنیم که به بهترین موقعیت منجر شود. نکته: در اینجا مقدار عس» قطعی وجود ندارد در عوض فقط مي توانیم میانگین با مقدار مورد انتظار را محاسبه کنیم Dux Ove 0, ® 

صفحه 43:
فصل ‎am‏ = با[یها - عامل شانس ۳ اگر ما فرض کنیم که (!9)60,۷) مجموعه موقعيت‌هاي تولید شده توسط اعمال حرکات قانوني براي پرتاب ((ع)۳) در موقعیت () باشد مي‌تواند مقدار ۳۳ از () را با استفاده از فرمول زیر محاسبه نمود: Expectimax (c) =¥, P(d,) .max,, Expectimines {EQ} .min,, S(c,d) (utility(s)) لین فرمول. سودمندي مورد انتظار در موقعیت ۵ رابا فرض بهترین بازي ارائه مي‌دهد. 

صفحه 44:
فصل ‎am‏ = با[یها - عامل شانس در منال قبلي: ‎Cxpoctri(®,) = 0.0" wif} + 0.4" wef} = ©.6*)0( + 0.0") = -0.0‏ ‎O.O*(O) + ©.0*0( - 0‏ = (ه, لد *0.ه + (0 ,لمم *0.6 د (و6)م مسوم 

صفحه 45:
فصل بيجيدكي: ۴ بدلیل اینکه نوج تمام دنبالهدهاى يرتاب تاس را در نظر می‌گیرد. زملنی معادل (0)*97 مى برد. كه - تعداد يرتابهاي محدود است. )65 يازيها - عامل شانس * مزیت آلفا- بتا.با داشتن بهترین بازی نادیده گرفتن پیشرفت‌ها در آینده است که احتمال وقوعشان کم است * در بازبهای به همراه تاس. دنباله‌هاي محتملی از حرکات وجود ندارد. چون براي تن حرکاتی که بیید انجام بگیرند. ابتدا تاس باید به روش درستی پرتاب شود تا آنن حرکات منطقی شوند. " اكر بكوئيم كه تمام مقادیر سودمندي بین 1+ و 1- هستند. سپس مقدار گره‌هاي بر کي محدود مي‌شوند و در عوض سا مي نوانیم حد بالايي روي مقدار گره شانسي بدون توجه به فرزندانش ثرار دهیم 

Alireza yousefpour yousefpour@shomal.ac.ir فصل ششم: تئوري بازيها – تئوري بازي ها جستجوهاي رقابتي ‏Game Theory بازي ها چه هستند و چرا مطالعه ميشوند؟ بازي ها :حالتي از محيطهاي چند عاملي را نشان مي دهند که: هر عامل نياز به در نظر گرفتن ساير عاملها و چگونگي تأثير آنها دارد تمايز بين محيطهاي چند عامل رقابتي و همکار محيطهاي رقابتي ،که در آنها اهداف عاملها با يکديگر برخورد دارند، منجر به مسئله هاي رقابتي ميشود که به عنوان بازي شناخته ميشوند فصل ششم: تئوري بازيها – ادامه و چرا بازي ها مطالعه مي شوند : قابليتهاي هوشمندي انسانها را به کار ميگيرند ‏ماهيت انتزاعي بازي ها ‏حالت بازي را به راحتي ميتوان نمايش داد و عاملها معموال به مجموعه کوچکي از فعاليتها محدود هستند که نتايج آنها با قوانين دقيقي تعريف شده اند به عنوان مثال :داليلي که محققين قديم ،شطرنج را به‌عنوان موضوعي در AIبرگزيدند: بازي شطرن ج کامپيوتري اثبات ي بر وجود ماشين ي اس ت ک ه اعمال هوشمندانه‌اي را انجام مي‌دهند. سادگي قوانين وضعي ت دني ا کام ً ال براي برنام ه شناخت ه شده اس ت( .بازنماي ي بازي ب ه عنوان ي ک جستجو از طريق فضاي موقعيت‌هاي ممکن بازي ،ساده است). فصل ششم: تئوري بازيها – ادامه پيچيدگي بازي‌ها ،به طور کامل نوعي از عدم قطعيت را معرفي مي‌کنند. عدم قطعي?تب?ه عل?ت وجود اطالعات گ?م شده رخ نمي‌ده?د ،بلک?هب?ه عل?ت اينک?ه فرد زماني براي محاسبه دقيق نتايج حرکت ندارد عدم قطعيت بوجود مي‌آيد. در اين مورد ،فرد بر اساس? تجربيات گذشته مي‌تواند بهترين حدس? را بزند. فصل ششم: يک نمونه بازي تئوري بازيها – بازي Minimax ي ک بازي ب ا دو بازيک ن را در نظ ر مي‌گيري م ک ه آن را MIN-MAX‌ناميم.معناست که هر يک از بازيکن ها ،حرکت خود را در جهت افزايش برد ميبدينخود ( )maxو نيز در جهت کاهش برد حريف ( )minانجام مي دهد. پس هميشه حرکت با maxاست .قبل از حرکت گرافي از ديد بازيکن maxرسم مي شود که بتواند بهترين حرکت را انتخاب کند: بازي به عنوان يک جستجو: ‏حالت اوليه :موقعيت صفحه و شناسايي حرکت مجاز ‏عملگرها :ليستي از (حالت,حرکت) که معرف يک حرکت معتبر است ‏آزمون هدف :پايان بازي چه موقع است؟ (حالتهاي پايانه) ‏تابع سودمندي :براي هر حالت پايانه يک مقدار عددي را ارائه ميکند. مث ًال :برنده( )+1و بازنده( )-1و مساوي()0 فصل ششم: مثال : oبازيکن: تئوري بازيها – بازي Minimax انتخاب بهترين حالت oحريف: انتخاب بهترين موقعيت براي خودش ي ا بدترين وضعيت براي بازيکن حالت اوليه و حرکات معتبر براي هر بازيکن ،درخت بازي را براي آن بازي ايجاد ميکند فصل ششم: تئوري بازيها – تصميمات کامل تصميمات کامل در بازي‌هاي دونفره(ترسيم درخت بطور کامل): اگر به آن به عنوان يک مسئله جستجو نگاه شود ،جستجو براي دنباله‌اي از حرکات ک ه منته ي ب ه حال ت پايان ي مي‌ش د (مطاب ق ب ا تاب ع س ودمندي) ،و س پس پيشروي و ساخت اولين حرکت در دنباله بود. با توجه به اينکه حرکت MINغيرقابل پيش بيني است بنابراي?ن MAXباي?د اس?تراتژي‌اي را بياب?د ک?ه ب?ه ي?ک حال?ت پايان?ي برنده بدون توج?ه ب?ه عملکرد MINمنج?ر شود ،ک?ه اي?ن اس?تراتژي شام?ل حرکات درس?ت براي MAXبراي هر حرکت ممکن از MINمي‌باشد. فصل ششم: تئوري بازيها – الگوريتم Minimax الگوريتم MIN-MAX: به منظور تعيين استراتژي بهينه براي MAXطراحي شده است و از م‌گيري کرد .الگوريتم شامل 5 اينرو مي‌توان بهترين حرکت را تصمي ‌ مرحله است: .1 .2 .3 .4 توليد درخت کامل بازي ،تمام راه تا مراحل پاياني درخواس?ت تاب?ع س?ودمندي براي ه?ر حال?ت پايان?ي ب?ه منظور بدس?ت آوردن مقدارش. از س?ودمندي حاالت پايان?يب?ه منظور تعيي?ن س?ودمندي گره‌ه?ا ي?ک مرحل?ه باالت?ر در درخت جستجو استفاده کنيد. بررسي مقادير را از گره‌هاي برگي تا ريشه ،يک اليه در هر لحظه ،ادامه دهيد. .5احتما ً ال مقادي?رب?ه باالي درخ?ت مي‌رس?ند MAX ،حرکت?ي را انتخاب مي‌کن?د ک?ه به باالترين مقدار منتهي مي‌شود. Minimax – الگوريتم تئوري بازيها :فصل ششم :مثال 2 Max Min 1 2 2 1 Max 2 7 1 Static evaluator value 2 7 8 1 8 2 7 8 2 This is the move selected by min-max Max 1 2 1 Min 2 7 1 8 فصل ششم: اگر: تئوري بازيها – الگوريتم Minimax ‏Eت :mحEداEکثر عEمقدرEخ ، :bتEعEداد حرکات قEانونEيدر هر نEEقطه، کامل بودن :بله (اگر درخت محدود باشد) بهينگي :بله پيچيدگي زماني :الگوريتم) MINIMAX ، O(bmاست. الگوريتم يک جستجو عمقي است. پيچيدگي فضاO(bm) : فصل ششم: تئوري بازيها – اطالعات ناقص بازيهاي قطعي با اطالعات ناقص (ترسيم درخت بطور ناقص): بهتري?ن نتيج?ه ممکن?ه براي بازيکن?ي اس?ت ک?ه گراف را کام?ل کرده است . اس?تراتژي بازي براس?اس مس?يرهايي از گراف ک?ه بهتري?ن نتيج?ه را م?ي دهد، تعريف مي شوند اي?ن تئوري در عم?ل براي بازيهاي?ي ک?ه گراف آنه?ا بس?يار پرهزين?ه اس?ت استفاده نمي شود .براي مثال در بازي شطرنج: ميانگين فاکتور انشعاب در حدود 35 بنابراين درخت جستجو در در اغلب بازيها هر بازيکن تا 50حرکت حدود 35100گره خواهد داشت پس اگر بخواهيم به اين تئوري جنبه عمل دهيم بايد سعي کنيم براساس گراف کوچک که بخشي از گراف اصلي محسوب مي شود استراتژي را تعيين کرد. فصل ششم: تئوري بازيها – اطالعات ناقص الگوريتم MINIMAXبه دو راه تغيير يابد: تابع سودمندي با تابع ارزيابي اکتشافي EVALجايگزين شود. -تخميني از سودمندي موقعيت ارائه ميکند آزمون پاياني با آزمون قطع Coutoff testجايگزين گردد. -تصميم ميگيرد EVALچه موقع اعمال شود فصل ششم: تئوري تابع ارزيابي اکتشافي: بازيها – تابع ارزياب ‏Evaluation Function تابع ارزياب?ي تخميني از س?ودمندي مورد انتظار بازي را از يک موقعيت خاص برمي‌گرداند. ‏توابع اکتشافي ،تخميني از فاصله تا هدف را بر ميگرداند ‏Eval(n) ≤ 100 ≤ 0 برد مطلق باخت مطلق واضح است که ارائه يک برنامه بازي بي نهايت به کيفيت تابع ارزيابي بستگي دارد.تابع ارزيابي نميداند کدام حالت منجر به چه چيزي ميشود ،اما ميتواند مقداري برگرداند که تناسب حالتها را با هر نتيجه را نشان دهد فصل ششم: تئوري بازيها – تابع ارزياب چگونه به طور دقيق کيفيت تابع ارزياب را مي‌توان اندازه گرفت؟ .1تابع ارزيابي با تابع سودمندي در مورد حالت پاياني بايد به توافق برس?ند. .2نباي?د زياد طول بکش?د! (اگ?ر پيچيدگ?ي را محدود نکني?م minimaxب?ه عنوان ي?ک زيربرنام?ه فراخوان?ي مي‌شود و مقدار دقي?ق وضعي?ت محاس?به مي‌شود ).از اي?ن رو ،معامله‌اي بي?ن ص?حت تاب?ع ارزياب?ي و هزين?ه زمان آ?ن وجود دارد. .3تابع ارزيابي بايد به درستي شانس?‌هاي واقعي براي برد را منعکس کند. فصل ششم: تئوري بازيها – تابع ارزياب خطي تابع ارزياب خطي (وزن دار) : تاب?ع ارزياب?ي فرض مي‌گيرد ک?ه مقدار ه?ر مهره مي‌توان?د ب?ه طور مس?تقل از ديگ?ر مهره‌ه?ا روي ص?فحه قضاوت شود .اي?ن نوع از تاب?ع ارزياب?ي ،تاب?ع خط?ي وزن دار ناميده مي‌شود. … Eval(s) = w1 f1(s) + w2 f2(s) + )+ wnfn(s fها پ??ارا?م?ترهايم?همت??اث?ير گ?ذار در ارز?ياب?يي?کح?ا?لت ?ن در ا?ي?نارز?ياب?يرا ن??شانم?يد?ه?ند. ?ن?ه?ميتهر پ??ارا?م?تر(?وز ) wها م?يزا ا فصل ششم: تئوري بازيها – قطع جستجو قطع جستجو: ص??ريح‌ترين رهياف??ت براي کنترل ميزان جس??تجو قراردادن محدوديت??ي براي داشتن يک عمق ثابت است، بنابراي?ن تس?ت قط?ع براي تمام گره‌ه?ا در زي?ر عم?ق dموف?ق مي‌شود .عم?ق طوري انتخاب مي‌شود ک?ه ميزان زمان اس?تفاده شده از آنچ?ه ک?ه قواني?ن بازي اجازه مي‌دهد تجاوز نکند. يک رهيافت قوي براي تعيين عمق : d استفاده از جستجوي عمقي تکرار شونده است زمان?ي ک?ه ،وق?ت تمام مي‌شود ،برنام?ه حرک?ت انتخاب?ي توس?ط عميق‌تري?ن جس?تجوي کامل شده را برمي‌گرداند. فصل ششم :تئوري بازيهاي چند نفره بازيها – بازيهاي چند نفره ‏تخصيص يک بردار به هر گره ،به جاي يک مقدار ‏بازيهاي چند نفره معو ً ال شامل اتحاد رسمي يا غير رسمي بين بازيکنان است oاتحاد با پيشروي بازي ايجاد و از بين ميرود oبازيکنان بطور خودکار همکاري ميکنند ،تا به هدف مطلوب انحصاري برسند فصل ششم: تئوري بازيها – هرس الفا بتا ‏Alpha – Beta هرس آلفا -بتا: ‏Pruning فرض :يک برنامه خوب وجود دارد که مي تواند 1000جستجو را در يک ثانيه انجام دهد در شطرنج :فاکتور انشعاب = 35حرکت براي هر حرکت 150ثانيه زمان مي برد پس مي توانيم 150000 موقعيت بوجود بياوريم با فاکتور انشعاب 35يعني 3تا چهار حرکت بازي را پيش بيني مي کند يک بازي مبتدي بازيکنان انساني متوسط 6تا 8حرکت را پيش بيني مي کنند فصل ششم: تئوري بازيها – هرس الفا بتا ‏Alpha – Beta هرس آلفا -بتا: ‏Pruning فرض :يک برنامه خوب وجود دارد که مي تواند 1000جستجو را در يک ثانيه انجام دهد در شطرنج :فاکتور انشعاب = 35حرکت براي هر حرکت 150ثانيه زمان مي برد پس مي توانيم 150000 موقعيت بوجود بياوريم با فاکتور انشعاب 35يعني 3تا چهار حرکت بازي را پيش بيني مي کند يک بازي مبتدي بازيکنان انساني متوسط 6تا 8حرکت را پيش بيني مي کنند ش ک س ت ب ر ن ا مه فصل ششم: تئوري بازيها – هرس الفا بتا هرس درخت جستجو: پردازش? حذف شاخه‌اي از درخ??ت جس??تجو ،ب??ا در نظ??ر داشت??ن و بدون آزمايش ،هرس? درخت جستجو ناميده مي‌شود ( .بصورت قطعي ) زمان?ي ک?ه اي?ن تکني?ک براي ي?ک درخ?ت minimaxاس?تاندارد،ب?ه کار برده مي‌شود، حرکت مشابهي همانطور که minimaxانجام مي‌داد ،برمي‌گرداند؛ و شاخه‌هايي که در تصميم‌ نهايي دخالتي ندارند را هرس مي‌کند. فصل ششم: تئوري بازيها – هرس الفا بتا جس?تجوي minimaxعمق?ي اس?ت ،بنابراي?ن ،در ه?ر لحظ?ه ،باي?د گره‌هاي?ي در نظر گرفته شوند که در طول يک مسير مجزا در درخت هستند. مقدار بهترين انتخابي باشد که تا کنون در طول مسير براي MAXپيدا شده است. مقدار بهتري$ن (ب$ه طور مثال ،پايين‌تري$ن مقدار) انتخاب$ي باش$د ک$ه در طول مس$ير ت$ا اي$ن لحظ$ه براي MINپيدا شده است. با استفاده از تکنيک هايي بدون از دست دادن دقت فضاي جستجو را کوچک کرد. يعني هرس هاي و نوعي hقطعي هستند که در آنها خطا پيش نمي آيد فصل ششم: هرس آلفا بازيها – هرس الفا بتا تئوري ‏-pruning تا موقعي xijفرزند xiمحسوب مي شود که ارزيابي آن بزرگتر ) max(x1...xi-1از باشد و موقعي که : در اين حالت ديگر نيازي به بررسي گره هاي XIJ+1به بعد نمي باشد فصل ششم :تئوري ‏-pruning هرس بتا بازيها – هرس الفا بتا تا موقعي XIJفرزند XIمحسوب مي شود که ارزيابي آن کوچکتراز ) MIN(X1...XI-1از باشد و موقعي که : در اين حالت ديگر نيازي به بررسي گره هاي XIJ+1به بعد نمي باشد فصل ششم: ‏max تئوري بازيها – هرس الفا بتا :Example ‏min ‏max ‏min ‏=4 45 3 فصل ششم: ‏max تئوري بازيها – هرس الفا بتا :Example ‏min ‏max ‏min ‏=3 ‏=1 ‏=3 45 3 1 7 0 بازيها – هرس الفا بتا :Example =3 =3 =3 =1 تئوري :فصل ششم max min max =8 -pruning  45 3 1 7 0 8 6 min بازيها – هرس الفا بتا = 3 :Example تئوري :فصل ششم max =3 =2 min  =3 =6 =2 max  =3 =1 =6 =2 =1  45 3 1 min  86 7 264 1 =3 :Example تئوري بازيها :فصل ششم max =3 =2 min  =3 =6 =2 max  =3 =1 =6 =2 =1  45 3 1 min  86 7 264 1 فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : محدوده مقادير ممکن []∞+,∞- []∞+ ,∞- فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : []∞+,∞- []3,∞- فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : []∞+,∞- []3,∞- فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : []∞+,3 []3,3 فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : []∞+,3 اين گره براي Maxمناسب نيست []2,∞- []3,3 فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : , []14,∞- []3,14 []2,∞- []3,3 فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : , []5,∞- 35 []3,5 []2,∞− []3,3 فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : []3,3 []2,2 36 []2,∞− []3,3 فصل ششم: تئوري بازيها – هرس الفا بتا مثالي ديگر : []3,3 []2,2 37 []2,∞- []3,3 فصل ششم: تئوري بازيها – هرس الفا بتا مزاياي هرس آلفا-بتا مزاياي آلفا-بتا به مرتبه‌اي که در آن گره‌هاي فرزندي آزمايش شده‌اند ،برمي‌گردد. ) 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دو برابر است فصل ششم: تئوري بازيها – عامل شانس بازي‌هايي که عامل شانس دارند: در زندگي واقعي حوادث غير قابل پيش بيني زيادي وجود دارند که ما را در شرايط غافلگيرانه اي قرار مي دهند در بازيها اين حوادث غيرقابل پيش بيني را توسط عنصر تصادفي مانند تاس نشان مي دهند تخته نرد يک بازي عمومي است که شانس و مهارت را با هم ترکيب مي‌کند. در اينجا تاسي توسط بازيکن Aريخته مي شود تا مجموعه اي از حرکتها که قابل انجام هستند تعيين گردد يعني نمي توان درخت کامل بازي را ترسيم کرد فصل ششم: درخت جستجو : تئوري بازيها – عامل شانس تاس‌هاي سفيد ،6-5چهار حرکت زير را مي‌تواند انجام دهد: ( 16-10و )5-10و ( 19-24و )5-11و ( 5-11و )5-10و ( 11-16و )5-11 فصل ششم: تئوري بازيها – عامل شانس درخت بازي در تخته نرد بايد شامل گره‌هاي شانس براي گره‌هاي MINو ‌MAXباشد. مرحله بعدي فهم چگونگي ساخت تصميمات صحيح است. محاسبه مقادير انتظاري گره‌ها ،صريح است .براي گره‌هاي پاياني ،از تابع سودمندي مانند بازيهاي قطعي استفاده مي‌کنيم. oبا پيشروي در درخت جستجو به اندازه يک مرحله ،به يک گره شانس برخورد مي‌کنيم. فصل ششم: مثال : تئوري بازيها – عامل شانس مي خواهيم حرکتي از A1 … A2را انتخاب کنيم که به بهترين موقعيت منجر شود. نکته :در اينجا مقدار min-maxقطعي وجود ندارد در عوض فقط مي توانيم ميانگين يا مقدار مورد انتظار را محاسبه کنيم ‏Max ‏A ‏A ‏Dice ‏A1 2 ‏Min 3 1 0 1 2 1 2 1- فصل ششم: تئوري بازيها – عامل شانس اگ ر م ا فرض کني م ک ه ) S(C,diمجموع ه موقعيت‌هاي تولي د شده توس ط اعمال حرکات قانون ي براي پرتاب ) P(diدر موقعي ت Cباش د ،مي‌توان د مقدار expectimaxاز ‍Cرا ب ا استفاده از فرمول زير محاسبه نمود: ‏Expectimax (c) =∑i P(di) .maxsε ‏S(c,d ) ))(utility(s ‏i ‏Expectimin (c) =∑ P(d ) .min ‏sε ‏i ‏i ))S(c,di) (utility(s ايEن فرمول ،سEودمندي مورد انتظار در موقعيEت Cرا بEا فرض بهتريEن بازي ارائه مي‌دهد. بازيها – عامل شانس Max تئوري A Dice 0. 9 Min 1- 2 A1 A 0.1 0. 2 9 1 2 1 :فصل ششم :در مثال قبلي 0.1 0 1 3 Expectimin(A1) = 0.9* min{-1,2} + 0.1* min{1,2} = 0.9*(-1) + 0.1*(1) = -0.8 Expectimin(A2) = 0.9* min{1,0} + 0.1* min{1,3} = 0.9*(0) + 0.1*(1) = 0.1 ا نتخابم يش ودA2 فصل ششم: پيچيدگي: تئوري بازيها – عامل شانس بدلي?ل اينک?ه expectiminimaxتمام دنباله‌هاي پرتاب تاس را در نظ?ر مي‌گيرد ،زمان?ي معادل ) O(bmnmمي‌برد ،که nتعداد پرتابهاي محدود است. مزي?ت آلف?ا -بت?ا،ب?ا داشت?ن بهتري?ن بازي ناديده گرفت?ن پيشرفت‌ه?ا در آينده اس?ت ک?ه احتمال وقوعشان کم است. در بازيهاي ب?ه همراه تاس ،دنباله‌هاي محتمل?ي از حرکات وجود ندارد ،چون براي آ?ن حرکات?ي ک?ه باي?د انجام بگيرن?د ،ابتدا تاس باي?د ب?ه روش درس?تي پرتاب شود ت?ا آ?ن حرکات منطقي شوند. اگ?ر بگوئي?م ک?ه تمام مقادي?ر س?ودمندي بي?ن +1و -1هس?تند ،س?پس مقدار گره‌هاي برگ?ي محدود مي‌شون?د و در عوض‌ م?ا مي‌تواني?م ح?د باالي?ي روي مقدار گره شانس?ي بدون توجه به فرزندانش قرار دهيم.